Cat: A Functional Stack-Based Little Language

Cat for Application Development

I originally designed Cat as an intermediate language, but also wanted it to be directly usable by programmers who wanted to hand-write Cat libraries. I added a few extensions to Cat to make it more attractive for programmers. One thing I noticed was that it was hard to translate programs from other languages into Cat, especially when multiple arguments were concerned. A classic example is:

double quadratic(double x,    double a, double b, double c) {
     return a * x * x + b * x + c;
}

In Cat, this would be expressed as something like:

define quadratic {
[[[dup dup *] dip * swap]     dip * +] dip + }

Clearly, there are better techniques in this particular example (Slava Pestov shows two alternatives using Factor; see factor-language.blogspot.com/2007/03/evaluating-quadratic-polynomial.html) that leverage other properties of the quadratic equation; however, the core issue remains that converting formulas with multiple arguments can be hard in stack languages.

Using named parameters in Cat, you can write:

define quadratic(x a b c)     { x x * a * b x * + c + }

Functions with named parameters are converted in point-free Cat (that is, Cat without named parameters) by the compiler in a preprocessing phase. Cat also lets anonymous functions accept named parameters. For example, an anonymous function that swaps two values can be written as "\x.\y.[y x]".

Rewriting Rules and Partial Evaluation

As a compiler and tool developer, one of the most attractive aspects of Cat is that program transformation is simple and can be done using a system of rewriting rules. Manfred von Thun has described a rewriting system for Joy (www.latrobe.edu.au/philosophy/phimvt/joy/j07rrs.html). I've implemented a similar rewriting system called "MetaCat" as an extension to the Cat interpreter for expressing rewriting rules. Example 6 presents some MetaCat examples.

In these rules, you use lowercase letters preceded by a dollar sign ($a) to refer to any expression that generates a single value ("1 2 +"). Uppercase letters preceded by a dollar sign ($A) refer to arbitrary length expressions bounded by square brackets. By applying rewriting rules that guarantee convergence (repeated application of the rules is guaranteed to reach a point where further application causes no more changes), you are effectively constructing a partial evaluator for the language (citeseer.ist.psu.edu/610056.html). Partial evaluation is the compilation technique of evaluating portions of a program related to the statically available input. A common example of partial evaluation is constant folding (aka "constant propagation"). This means you can use rewriting rules to evaluate expressions ahead of time, making the code more efficient in terms of space and speed. Another interesting fact is that you can use the rewriting rules to express the semantics of instructions.

rule { swap swap } => { }
rule { dup swap } => { dup }
rule { $a pop } => { }
rule { dup eq } => { pop true }
rule { true $a $b if } => { $a apply }
rule { [$A] apply } => { $A }
rule { [$B] [$A] compose } => { [$B $A] }
rule { $a [$B] papply } => { [$a $B] }
rule { $a [$B] dip } => { $B $a }

The MetaCat rules can be used to express deforestation algorithms (http://citeseer.ist.psu.edu/593502.html), such as those used in the Glasgow Haskell Compiler (citeseer.ist.psu.edu/article/peytonjones01playing.html). A deforestation algorithm is an algorithm for eliminating the construction of intermediate data structures (trees or lists—hence, the name) during a computation. For example, two successive map functions can be fused into a single map function:

rule { $c $b map $a map } =>     { $c $b $a compose map }

Because there is only one call to map, you eliminate the construction of an intermediate list. You can see the example at work in this example:

define scale_vector    { [*] papply map }
define translate_vector   { [+] papply map }
define example   { 2 scale_vector 1 translate_vector }

After inline expansion, you get:

define example   { 2 [*] papply map 1 [+] papply map }

Now, you partially evaluate the papply functions:

define example { [2 *] map [1 +] map }

If evaluated directly, you would need to allocate an intermediate array before arriving at the final result. Applying the map fusion rewriting rule gives:

define example { [2 * 1 +] map }

This is more efficient because no intermediate array is generated. I have only scratched the surface of possible rewriting rules.