Here is the proposal which accompanies the presentation:

Cat Programming Language: A Functional Optimization Framework for the MSIL

Abstract

Cat is a stack-based pure functional language, inspired by the Joy programming language, which targets the Microsoft Intermediate Language (MSIL). Cat, like Joy, differs from mainstream functional languages in that it is based on the composition of functions rather than the application of functions. This design makes algebraic manipulation of programs trivial, and thus facilitates optimization.

This goal of the presentation (http://www.cdiggins.com/cat.ppt ) is to introduce the semantics and syntax of Cat, demonstrate rewriting rules for high-level functional optimizations, and show preliminary performance results for a simple IL Code generator written in C#.

Summary of Language

The Cat language is a pure functional language, inspired by Joy, which in turn is inspired by Forth and FP. All constructs in Cat (atomic programs, user defined programs, operators, literals, lists) behave as functions which takes a single stack as input and returns a new stack. In Cat the concatenation of two functions (e.g. [f g]) has the effect of composition of both functions (e.g. g(f(x))). All new user defined functions are defined as lists of functions. Cat not only has no variable declaration, there are no argument declarations. Cat also lends itself to the higher order functional programming: the lambda operation in Cat is the list construction operator "[...]" and currying can be achieved used basic operations such as "cons".

Results of Research

The primary result of the work done with Cat is the observation that high-level functional optimizations can be very easily expressed and applied. Consider the examples:

f map g map => [f g] map
[f] map x [g] fold => x [[f' f] g] fold 
[f] filter x [g] fold => x [f [g] [pop] if] fold
[f] map [g] filter x [h] fold => x [f g [h] [pop] if] fold 

These optimizations are very important, but are extremely hard to apply once a langauge has been reduced to an assembly, or pseudo-assembly, form.

The thesis of this work is that by first compiling a language to a stack-based functional language such as Cat, before targeting a lower level target such as MSIL, better performance can be achieved.