About Cat

Cat is a functional stack-based programming language. This means that all instructions share data using a single shared data structure called the stack. The stack can contain numbers, string, functions, lists, or any other kind of data.

Cat can also be described as a compositional language. The sequence of two instruction (i.e. functions) denotes the composition of these functions. This is different from traditional functional languages where the sequence of functions denotes the application operation.

There are several advantages of stack-based language: one is that data-flow is implicit. This means that there is no need to provide names for parameters to functions. Another advantage is that functions can return multiple results and can be composed with functions which accept multiple arguments.

Cat is a high-level intermediate language that can also be used as a stand-alone language for simple application development. In this way it occupies a similar niche to PostScript. Cat is also an appropriate language for teaching of basic programming concepts.

Cat is designed and being developed by Christopher Diggins, who studies at the University of Montreal with Marc Feeley and Stefan Monnier.

Cat as a Teaching Language

The syntax of Cat is very minimal, which means that beginners can focus immediately on how programs and computers work, without worrying about whether they are using correct syntax, or their parantheses are in the right place.

Despite the syntactic simplicity, Cat is a full-featured language with support for functional programming techniques, and has a strong static type-system with type-inference. This is very useful for beginners to understand precisely what the effects of their programs are going to be without resorting to guess-work. Type inference is a very useful tools, because it provides feedback, without introducing syntactic overhead. As programmers learn and evolve, they will quickly learn that using type-signatures in their definitions can speed up their development time, by making explicit their expectations, and forcing them to think in terms of the semantics of their programs.

Functional programming is a very powerful technique that is avoided in several introductory texts for no reason other than the fact that the language used has poor support for functional programming. Cat relies on functional programming to control the flow of programs. Instead of requiring the student to learn special syntax for conditional and looping constructs, Cat does this using higher-order functions. For example:

    1 1 +
    2 eq
    ["One plus one equals two, just as I expected"]
    ["you need to bring me in for an overhaul"]
    if

In fact new programmers expect rules to be consistent, and not for certain words to have arbitrary limitations (e.g. can't be treated like data). Using Cat fewer exceptions have to be explained and remembered, allowing students to focus on core concepts.

Stack-based languages like Cat are attractive for teaching because they have such a simple programming model. A new programmer can see each step of a computation explicitly, by simply viewing the stack. To demonstrate how powerful this can be we have provided a public-domain online interpreter for Cat written in JavaScript.

Another attractive feature of Cat for new programmers is the fact that it comes with a graphics library. New programmers are often encouraged when they are able to make visibly pleasing images using computer programs, and can help them have visual feedback as to what is happening, and why their programs might be going wrong.

Because Cat is relatively simple to implement it can also be useful for teaching or for self-directed study of programming language implementation. It can be used as a stepping stone to implementing more syntactically complex languages.

Cat as an Intermediate Language

As an intermediate language Cat is still quite experimental and more work is needed to be done to develop tools that target Cat. However, it has already been shown that Cat is very effective for performing optimizations using a simple syntactic rewriting system called MetaCat.

Manual translations of JVML and MSIL byte-code to Cat also show huge saving of code size, due to the more expressive nature of functional code. We hope to provide more concrete examples of this soon.

MetaCat and Rewriting Rules

Cat has no lexical environment and only a single stack. This makes it very easy to rewrite Cat code. The Cat interpreter comes with a built-in term rewriting system called MetaCat that is activated using the "#metacat" or "#m" command.

A MetaCat rule has the form:

  rule{ source_pattern } => { target_pattern }

  rule { swap swap } => { }
  rule { dup pop } => { }
  rule { quote eval } => { }
  rule { [$B] curry } => { quote [$B] compose }
  rule { map $a map } => { $a compose map }
  rule { and } => { quote [false] if }
  rule { or } => { quote [true] swap if }
  rule { unit rev } => { unit }
  rule { unit $a filter } => { $a apply [unit] [pop nil] if }

MetaCat patterns may contain literal names, value variables which start with a lower-case letter (e.g $a or $bob), and expression variables which start with an upper-case letter (e.g. $A or $Bob).

Unit Testing in Cat

Cat provides support for a meta-information documentation format for documenting and testing functions. These are called meta-comments and can be used by tools to provide support for automated testing and documentation generation.

Type Safety in Cat

A type-soundness proof is currently under development for Cat. So far the implementation is able to statically verify that all programs tested do not under-flow the stack. Type signatures in Cat are completely optional, and are used to verify that Cat programs do what are intended.

Example Cat Programs

The following are some example Cat programs.

  define times_two { 2 * }
  define square { dup * }
  define above_and_below { dec dup 2 + }
  define sum { 0 [+] fold }
  define square_list { [square] map }
  define first_hundred_naturals { 100 n }
  define apply_twice { dup [apply] dip apply }
  define iftrue { [] if }

The following are some more sophisticated Cat programs that demonstrate meta-comments and type-signatures.

  define fact : (int -> int)
  {{
    desc:
      A factorial function
    tests:
      in: 5 fact
      out: 120
  }}
  {
    eqz
    [pop 1]
    [dup dec fact mul_int]
    if
  }

  define fib : (int -> int)
  {{
    desc:
      A fibonacci function
    test:
      in: 5 fib
      out: 8
  }}
  {
    [dup 2 lt_int] // termination condition
    [pop 1]        // termination action
    [dec dup dec]  // argument relation
    [add_int]      // result relation
    bin_rec        // binary recursion operation
  }

  define qsort : (list -> list)
  {{
    desc:
      A quick sort algorithm.
    test:
      in: [5 4 2 1 3 2 4] list qsort
      out: [5 4 4 3 2 2 1] list
  }}
  {
    // Does list have 0 or 1 elements?
    [small]
    // Base case do nothing
    []
    // Argument-relation
    //  Split the list using the head as a pivot
    //  storing the pivot under for later use
    [uncons under [lt] papply split]
    // Append the pivot to the first list
    // then concatenate the two lists.
    [[swap cons] dip cat]
    bin_rec
  }

For more Cat programs browse see the definitions of the standard library or read the tutorial.