Summary
I'm developing a stack based functional language, inspired by the Joy programming language called Cat. What is particularly interesting about Cat is that it is particularly well-suited to optimization.

Those following my posts, may know that I am recently enamored with stack-based functional languages (like Joy). I have posted the powerpoint slides from a proposed talk about the Cat Programming Language at http://www.cdiggins.com/cat.ppt.

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.

Talk Back!

Have an opinion? Readers have already posted 7 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.