• easily optimized
• easily translated

• a variable/argument stack
• an evaluation 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)()

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 

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) = ()

  [
    1 2 3 
    cat.standard.integer.add 
    cat.standard.integer.add 
  ]

  [
    1 2 3 
    loadint loadint addint storeint
    loadint loadint addint storeint
  ]

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