The Artima Developer Community
Sponsored Link

Heron-Centric: Ruminations of a Language Designer
Adding another Stack to Cat
by Christopher Diggins
July 4, 2006
When two stacks are better than one. Also an introduction to the type annotation syntax which will be introduced in an upcoming version of Cat.


The main role of Cat is to provide an intermediate representation of an arbitrary functional or imperative high-level language which can be:

Mapping Cat to a lower level language like the MSIL poses some particular challenges since the MSIL is based on two stacks: Any straightforward mapping from Cat to MSIL slow and cumbersome because I have to emulate an open-ended stack. Whenever I want to add or subtract two numbers the compiler has to move the values from the Cat stack to the evaulation stack, execute the MSIL opcode, and then move the result back to the Cat stack.

A nice solution to this problem, is to extend Cat with a second stack.

Internally Cat uses a type notation for the purposes of optimization, and to prepare for the fact that upcoming versions will support static typing. The challenge I faced was to express the type of a Cat program in a multi-stack language.

The best way to explain my proposed notation is throught the example of an integer addition function:

  add : (a:int, b:int)() => (c:int)()
I would read this as follows: the function add consumes two integer values from the main stack, and no values on the second stack. When add terminates it produces a single integer value on the main stack.

Now since I want to map my dialect of Cat to various byte-codes such as MSIL, there will be no primitive which actually adds values from the top of the main stack. All primitive arithmetic operations occur on the secondary stack. This means that the integer add function will need to be defined as a standard library function in terms of the following primitives:

    loadint   // (a:int)() => ()(a)
    loadint   // (a:int)() => ()(a)
    addint    // ()(a:int b:int) => ()(c:int)
    storeint  // ()(a:int) => (a)()
  ] // (a:int b:int)() => (c)()
The type notation for def in future versions will be optional. I want to support dynamic type checking, static type checking, and static type inference (ambitious I know).

So this in of itself hasn't yet solved the problem of frequent moving back and forth of values between stacks, however, there is now potential for the Cat optimization algorithms to be applied intelligently. For example I can write the following optimization rule:

  (storeint loadint) = ()
This optimization rule states simply that any-time you have a consecutive storeint and loadint operation you can simply eliminate them both. This becomes useful when you see something like:
    1 2 3 
When the compiler inlines these functions it reads:
    1 2 3 
    loadint loadint addint storeint
    loadint loadint addint storeint
Notice that the optimizer can now find the storeint/loadint pattern and eliminate it.
    1 2 3 
    loadint loadint addint 
    loadint addint storeint

This is only the tip of the iceberg of the optimization engine which I have planned for Cat. The ultimate goal is to develop a pattern-matching and rewriting macro language for Cat which is type-aware. What I find amusing is that the type annotations are more complicated than the actual code.

That's it for now, my brain hurts.

Talk Back!

Have an opinion? Readers have already posted 12 comments about this weblog entry. Why not add yours?

RSS Feed

If you'd like to be notified whenever Christopher Diggins adds a new entry to his weblog, subscribe to his RSS feed.

About the Blogger

Christopher Diggins is a software developer and freelance writer. Christopher loves programming, but is eternally frustrated by the shortcomings of modern programming languages. As would any reasonable person in his shoes, he decided to quit his day job to write his own ( ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at

This weblog entry is Copyright © 2006 Christopher Diggins. All rights reserved.

Sponsored Links


Copyright © 1996-2019 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use