Summary
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.

---

Advertisement

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

• easily optimized
• easily translated

Mapping Cat to a lower level language like the MSIL poses some particular challenges since the MSIL is based on two stacks:

• a variable/argument stack
• an evaluation stack

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:

  $cat.standard.integer.add 
  [
    loadint   // (a:int)() => ()(a)
    loadint   // (a:int)() => ()(a)
    addint    // ()(a:int b:int) => ()(c:int)
    storeint  // ()(a:int) => (a)()
  ] // (a:int b:int)() => (c)()
  def 

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 
    cat.standard.integer.add 
    cat.standard.integer.add 
  ]

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.

Digg | del.icio.us | Reddit

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 ( www.heron-language.com ). Christopher is the co-author of the C++ Cookbook from O'Reilly. Christopher can be reached through his home page at www.cdiggins.com.