Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.

Channels ▼


Cat: A Functional Stack-Based Little Language

Source Code Accompanies This Article. Download It Now.

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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.