Cat: A Functional Stack-Based Little Language

Cat is an intermediate language for program verification, optimization, and more!


April 15, 2008
URL:http://drdobbs.com/architecture-and-design/cat-a-functional-stack-based-little-lang/207200779

Christopher is a freelance programmer and consultant, with a particular interest in the design and implementation of programming languages. He can be contacted at [email protected].


I've always been fascinated by stack-oriented languages because of their simplicity and elegance. Instructions take input off of the stack, do something with it, and push the output back onto the stack. Thus, there are no named variables or arguments, and the order of execution is left-to-right without any need for parentheses to denote precedence. As a result, it doesn't take long for people to learn the basics of programming in a stack language.

Another appeal of stack languages is that it is relatively easy to create reasonably efficient implementations for them, especially where memory considerations are at a premium. Because of this, we find stack languages in multicore processors (SeaForth, www.dspdesignline.com/188701424), virtual machines (Java Virtual Machine language), and embedded devices.

In general, when we think of stack languages, we often think of imperative languages: Each instruction does something to a shared stack. An alternative and equally accurate view of stack languages is that each instruction is a function that takes a stack as input and returns a stack as output. This is the principle upon which Manfred von Thun based the Joy language (www.latrobe.edu.au/philosophy/phimvt/joy.html).

The language that Joy most closely resembles is PostScript in that explicit control structures (branches, gotos, jumps) are replaced with higher order instructions (instructions that execute other instructions). Joy, however, introduced explicit function literals (PostScript uses a delayed execution operator) and eliminated the concept of the definition dictionary; in other words, you can't dynamically define or redefine new operations. This yielded a new breed of stack language that shares the advantages of pure functional languages (for example, it is expressive and easy to reason about and manipulate formally). It is interesting to note that despite its similarities to other stack-based languages, Joy evolved independently from Schoenfinkel and Curry's combinatory logic and the FP language by John Backus (www.vector.org.uk/archive/v203/vonthun203.htm).

My interest in Joy was primarily motivated by my search for an intermediate language that could be easily targeted by imperative and functional languages, could be easily optimized, and could be statically verified. Joy relies heavily on dynamic checking, so I created a more restricted, statically typed language based on Joy and called it "Cat."

Introducing Cat

In the Cat specification, instructions are referred to as "functions," regardless of whether they have side effects. New functions are defined using the define keyword, and have global scope. Functions cannot be redefined, and are only visible after they are defined. Example 1 presents some simple examples.


define myFirstCatProgram
{ "what is your name?" writeln readln "Hello " swap strcat writeln }
define addone : (int -> int)
{ 1 + }
define swapd : ('a 'b 'c -> 'b 'a 'c)
{ [swap] dip }
define dupd : ('a 'b -> 'a 'a 'b)
{ [dup] dip }
define bury : ('a 'b 'c -> 'c 'a 'b)
{ swap swapd }
define fib // compute fibonnacci
{ dup 1 <= [dup dec fib swap fib +] [] if }
define fact // compute factorial
{ dup <= 1 [dup dec fact *] [pop 1] if }

Example 1: Sample Cat functions.

At the core of the Cat language are primitive instructions for:

In Cat, a literal (for example, 42, 'q', "Hello Christopher\n", 3.14) pushes a value onto the stack. Additionally, you can also write literal functions, by enclosing an expression in square braces ([1 +]). This has the effect of pushing a function onto the stack without executing it. In Joy parlance, this is called a "quotation," but I think of it as an anonymous function. Anonymous functions are first class values: They can be constructed dynamically and treated like any other primitive value (you can dup them, swap them, pop them, and so on). You can execute anonymous functions using higher order functions such as apply, if, and while.

Closures (functions bound to values in the local environment) can be constructed in Cat using the papply primitive instruction. This has the effect of binding the top value on the stack to the function, a process known as "partial application" (partial application is frequently mislabeled as "currying"). An example of partial application is that if you wrote 1 [<=] papply, it has the same effect as if you wrote [1 <=].

The quicksort algorithm in Example 2 is a more sophisticated example of Cat. The algorithm relies on a binary recursion instruction (bin_rec) that provides a general implementation of a binary recursive process (also called "tree recursion"). Example 3 is a possible definition of bin_rec.


define qsort : (list -> list)
{{
  desc:
    This is a simple implementation of 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
}

Example 2: A simple quick-sort algorithm.


define binrec(input, cond, term, unfold, fold) {
  input cond
    [term] // termination transformation
    [input unfold // split input
      [cond term unfold fold binrec] // self call with same arguments
      app2 // call function twice:
        // once with second value removed
        // once with top value removed
  ]
  if
}

Example 3: Example implementation of the bin_rec function.

The bin_rec function is an example of a hylomorphism (see citeseer.ist.psu.edu/meijer91functional.html)—the composition of an anamorphism (an unfolding function) and a catamorphism (a folding function). Hylomorphisms are interesting because they can be used to eliminate the construction of intermediate data structures (citeseer.ist.psu.edu/launchbury95warm.html).

The quicksort algorithm in Example 2 also demonstrates an extended feature of Cat called "metadata"—a form of structured comment that can associate additional data with a Cat function that can be used by tools. For example, metadata can be used to document functions and perform automatic unit tests. The format is based on YAML (Yet Another Markup Language) and uses significant whitespace to denote hierarchical structure.

To demonstrate how compact Cat can be, Example 4 includes an implementation of the Google MapReduce algorithm (labs.google.com/papers/mapreduce.html). The general idea of the Google MapReduce algorithm is to define a task in terms of subtasks that can be executed (in this example, counting instances of words), and a function to combine the results of the subtasks (called the "reduce function"). While my implementations of Cat do not execute MapReduce concurrently, you can easily develop an implementation of Cat that automatically executes map and self_join to take advantage of available parallelism in the executing environment. This leads to an important point about Cat: As an implementor, you decide how to implement the primitive instructions and whether to implement standard library functions as library functions or built-in functions. This opens lots of opportunities for high-performance implementations.


define map_reduce
{ [map flatten self_join] dip map }
define test_strings
{
  (
    (("The", "quick", "brown", "fox", "jumped", "over", "the", "lazy", "dog"), 1),
    (("I", "am", "very", "lazy"), 2),
    (("I", "hope", "this", "is", "over", "quick"), 3),
    (("I", "have", "high", "hopes", "for", "the", "lazy", "dog"), 4)
  )
}
define test_map_fxn
{ unpair pop [1 swap pair] map }
define test_reduce_fxn
{ unpair [vec_sum] dip pair }
define test_map_reduce
{ test_strings [test_map_fxn] [test_reduce_fxn] map_reduce print_list }

Example 4: An implementation of the Google MapReduce algorithm.

The Type System

Static type systems are useful for documentation, static verification of code, and optimization. It is common practice in stack languages to document the stack effects of each instruction—what type of values are removed from the stack (the consumption), and what type of values are placed on the stack (the production). The Cat type system allows type annotations (aka "type signatures" or "stack diagrams") that express the effect of an expression in terms of the consumption and production. If a type annotation is omitted, Cat is able to infer a type automatically using a variant of the Hindley-Milner algorithm (research.microsoft.com/Users/luca /Papers/BasicTypechecking.pdf). Example 5 shows some type signatures. From the Cat interpreter, the metacommand #t gives you the type of any function on the stack (metacommands are commands intended for the interpreter and are not part of the language; by convention, they are affixed with a "#" character).

Type variables are denoted with a leading apostrophe ('). Type variable names starting with lowercase letters represent individual types (scalar type variables). Type variable names starting with uppercase letters represent type vectors. A type vector is zero or more types on the stack. A type vector can be left unbound in the type signature of an expression, but ultimately has to be bound to a concrete sequence of types for an expression to be executable. ([apply] apply is not a valid program because we cannot resolve all the type variables.)

The arrow is used to differentiate function types with side effects ('A ~>'B) from those without ('A->'B). The rule for determining whether a function has a side effect is simply whether it uses a function with a side effect.


42 : ( -> int)
+ : (int int -> int)
dup : ('a -> 'a 'a)
pop : ('a -> )
apply : ('A ('A -> 'B) -> 'B)
if : ('A bool ('A -> 'B) ('A -> 'B) -> 'B)
[1 +] : ( -> (int -> int))
quote : ('a -> ( -> 'a))

Example 5: Sample type signatures.

In intermediate languages, it is useful to be able to verify certain properties of code statically. The most important properties are:

To guarantee proper verification of these properties, intermediate languages with stack-based semantics (such as the JVML) usually have a requirement that conditional execution cannot lead to different stack configurations (the types of values on the stack have to agree). The same principle applies to Cat, so the following is illegal:


is_monday ["I hate Mondays"] [42] if

In this case, depending on whether it is Monday, you would have either a string or integer on the top of the stack. This violates the type of the if function, which requires that both arguments ["I hate Mondays"] and [42] yield the same vector of types (denoted by 'B).

A novel feature of the Cat type system is that all functions are row polymorphic. Each function takes an implicit type-vector variable (called a "row variable") as an argument representing the rest of the stack. The row variable is returned implicitly along with the rest of the results. Another nice feature of the Cat type system is that you can perform partial type inference and compute the type of a polymorphic expression without context. This feature is not present in the Hindley-Milner type inference algorithms.

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 }

Example 6: MetaCat rewriting rule examples.

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.

Cat Implementation

I have released several Cat interpreters as public domain code, which you can use and modify as you wish. The primary implementation of Cat is an open-source C# interpreter (www.cat-language.com) that performs type checking, type inference, and some basic optimization (function inlining and partial evaluation). It also has several extensions such as named parameters and MetaCat rewriting rules. The Cat language website provides an embedding of Cat in Scheme and an online Cat interpreter written in JavaScript. The JavaScript and Scheme implementations are a bit out of sync with the language specification and are intended only as demonstrations, but feel free to redistribute and/or modify them. I have also written a basic Scheme-to-Cat translator, in Scheme.

Conclusion

Cat has potential applications in many domains. I can envision a place for it in embedded devices due to its compact and expressive nature. I also believe that Cat would be useful in a computer-science curriculum as a tool for explaining the rudiments of computer programs. The immediate feedback you get viewing the stack after each instruction can be useful for instruction. My intentions are to use Cat as an intermediate language for translation and optimization for my other computer language projects, and as a language for teaching programming.

If you are interested stack languages and aren't familiar with Forth, a fun primer is a fully documented bootstrapping compiler by Richard W.M. Jones (www.annexia.org/forth). I also recommend Manfred von Thun's writings on Joy, even if you never plan on using stack languages. Some up-and-coming stack languages are Factor (www.factorcode.org) by Slava Pestov and Ripple (ripple.fortytwo.net) by Joshua Shinavier, a stack language designed for the Semantic Web.

Acknowledgments

Thanks to the members of the concatenative mailing list (tech.groups.yahoo.com/group/concatenative), the Cat mailing list (groups.google.com/group/catlanguage), and the Lambda-the-Ultimate.org programming language blog. In particular, I want to thank William Tanksley, Joshua Shinavier, Frank Krueger, and John Nowak.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.