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 MSILAbstract
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.
Sounds incredibly exciting, but I can't for the life of me follow what you are doing. Perhaps it is due to my lack of experience with stack based languages? It would be nice if you had a Cat tutorial that went over the most basic of functionalities that Cat makes available, but at a slower and more detailed pace.
> Sounds incredibly exciting, but I can't for the life of me > follow what you are doing. Perhaps it is due to my lack of > experience with stack based languages? It would be nice if > you had a Cat tutorial that went over the most basic of > functionalities that Cat makes available, but at a slower > and more detailed pace.
I too thought you'd retired from language design, hence my rather cheeky comment about "replacing Christopher Diggins" in my blog bio. Dunno if Bill allows us to rewrite those :-)
Anyway, this sounds interesting - I came to your blog initially because I too had been studying/snake-victim-like-fascinated-by Forth and Lisp and some of the ideas in concatenative languages as part of the CEDSimply research.
Did you know there's already a dotNet Forth? Maybe you can collaborate.
> I too thought you'd retired from language design, hence my > rather cheeky comment about "replacing Christopher > Diggins" in my blog bio. Dunno if Bill allows us to > rewrite those :-)
That is too flattering :-)
For the record you can rewrite bios. I got grief because my old bio was percieved by some as too self-promotional. Mine should also be changed again, now that I work for the dark side.
> Anyway, this sounds interesting - I came to your blog > initially because I too had been > studying/snake-victim-like-fascinated-by Forth and Lisp > and some of the ideas in concatenative languages as part > of the CEDSimply research. > > Did you know there's already a dotNet Forth? Maybe you can > collaborate. > > http://www.codeproject.com/dotnet/dforthnet.asp
I've looked at it, albeit rather briefly. Forth in of itself is of less interest to me. I wanted a language where all of the constructs were functions, no variables or argument declarations were allowed, and side-effects were clearly delineated.
I doubt a language like Cat would be popular to write in directly (unless I come up with a really nice macro system)but it is intended as a backend implementation for other languages.
The big idea is that an arbitrary language can compile to Cat, which can then be retargetted to other formats (like MSIL, C, C--, LLVM, Java byte code, Parrot, NASM, C, etc.).
Hmmm... maybe you could find Cat useful as a backend for CEDSimply?