Home » forums » LtU Forum

The Cat Programming Language

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.

By cdiggins at 2006-05-13 22:48 | LtU Forum | previous forum topic | next forum topic | other blogs | 15275 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Arbitrary idea that just popped in my head

I'm not interested enough to check the literature, but upon reading:

All constructs [...] behave as functions which takes a single stack as input and returns a new stack.

(of which I'm well aware) I just considered what would happen if we extended this scheme to "returning" multiple stacks, in particular, continuing execution on each stack concurrently. I'm not sure if this could be made into a viable or interesting concurrency scheme and, if so, if it has been looked at before. I'm not particularly motivated in finding out myself.

By Derek Elkins at Sun, 2006-05-14 17:28 | login or register to post comments

It sounds verry much like a

It sounds verry much like a parrallell logik language to me.

By Felicia Li Svilling at Sun, 2006-05-14 18:14 | login or register to post comments

I am unfamiliar with

I am unfamiliar with parallel logic languages. What characteristics do they have?

By cdiggins at Mon, 2006-05-15 01:20 | login or register to post comments

They are logic languages

They are logic languages that tries to exploit parrallelism by doing breath-first-search in parallel, instead of the usual deapth-first backtracking scheme.

By Felicia Li Svilling at Mon, 2006-05-15 09:36 | login or register to post comments

Interesting Idea

I'm not sure it would be neccessary to change the semantics since a function in Cat can return multiple value. Concurrency should be easy to implement in any Cat compiler. Consider the atomic program:

split (T -> bool, list[T]) -> (list[T], list[T])

Where split places all values matching the predicate (the function T-> bool) in the first list, and all values not matching the predicate in the second list. Any compiler can easily implement the "split" atomic program concurrently.

By cdiggins at Sun, 2006-05-14 19:07 | login or register to post comments

Some questions.

1) to what extend are these optimizations useful? for example, if I wanted to apply an operator F onto a list of values, and then operator G on those values (that's what "f map g map" does, right?), I would apply F(G) over the list. Are these types of code sequences frequently met in applications?

2) regarding typechecking, how are you going to typecheck two consecutive operations A and B, when the type of data A produces is not decided before A is executed? For example, if you have the program:

A = [1 =] "abc" 0 if
B = inc
C = A B

The above program pushes "abc" on the stack if the top element equals 1, otherwise it pushes 0. The next instruction increases the top element, which might be a string, and therefore C may be a valid or an invalid operation, depending on the result of previous operations.

By Achilleas Margaritis at Mon, 2006-05-15 12:52 | login or register to post comments

Map map

The big optimization (I think) is that you don't have to store intermediate results, and also that you can compile [F G] into much tighter code than F or G alone.

By Steven Hugg at Mon, 2006-05-15 13:11 | login or register to post comments

Optimization Scenarios and Typechecking

1) Such scenarios do occur frequently in code. Consider the cases where: 

q = [f map]
w = [g map]
qw = [q w];

Expanding qw we get:

qw => [f map g map] => [[f g] map]

2) The typechecking question is a good one. Currently Cat is not statically type-checked. However if it was, I might solve the problem by saying: 

A typeof => string | integer;

By cdiggins at Mon, 2006-05-15 14:47 | login or register to post comments

Even more questions.

1) Such scenarios do occur frequently in code.

I have never programmed anything more than short exercises in stack based languages. Do you have an example of code that contains such scenarios 'frequently'?

2) The typechecking question is a good one. Currently Cat is not statically type-checked. However if it was, I might solve the problem by saying:

Are you going to reject code that does not honour union types? what if the computation is really long and complex (e.g. a recursive one)? how are you going to get the type of that? most propably you will have to 'execute' the code in order to see what its possible result is, but I do not know how feasible that is.

By Achilleas Margaritis at Tue, 2006-05-16 11:28 | login or register to post comments

Optimization opportunities and type systems

I have never programmed anything more than short exercises in stack based languages. Do you have an example of code that contains such scenarios 'frequently'?

The example I gave is not particular to stack-based languages. In code in any language, it is common to see optimization opportunities which reveal themselves only if subroutines are inlined.

Are you going to reject code that does not honour union types? what if the computation is really long and complex (e.g. a recursive one)? how are you going to get the type of that?

Concerning the union types I think I would reject code which requires a non-union but gets a union type. I haven't designed the type system yet, though so it really is premature to make statements about it. For interest's sake I have been considering a mixed dynamic and static system.

By cdiggins at Tue, 2006-05-16 14:11 | login or register to post comments

Actually...

...my first question was 'how frequent it is that such a sequence happens unintentionally' in order to have the compiler optimize it; I think that most users that want to do [f map g map] will do [f(g) map] anyway. In other words, is it an effort that justifies the cost?

My second question is how do you intend to compute types that are results of computations. My assumption is that you will have to use a system like C++ templates, i.e. a Turing-complete execution environment during compile.

By Achilleas Margaritis at Tue, 2006-05-16 15:57 | login or register to post comments

Other optimisations may well

Other optimisations may well yield [f map g map], being able to further optimise that is a good thing.

By Philippa Cowderoy at Tue, 2006-05-16 16:59 | login or register to post comments

Such as?

Such as? can we have some examples, please?

By Achilleas Margaritis at Wed, 2006-05-17 10:25 | login or register to post comments

I gave you one

The qw example.

By cdiggins at Wed, 2006-05-17 13:38 | login or register to post comments

No, I meant real-life examples.

real application code, perhaps? just to get an idea.

By Achilleas Margaritis at Thu, 2006-05-18 10:21 | login or register to post comments

Autogenerated code

is full of stuff like this. As a concrete example my OCaml packrat parser generator generates such optimizable code (ASTs) during preprocessing, and it would be great if I could rely on automatic higher-level optimizations to be carried out by the compiler instead of having to do special casing in the code generator to make sure it generates "optimized" ASTs. It's much easier to just have the compiler recognize such constructs and optimize them automatically.

By Bárður Árantsson at Thu, 2006-05-18 16:17 | login or register to post comments