I’ve talked a lot about the “m” combinator (”dup apply”) which is a critical component of nameless recursion algorithms. The most recent Cat interpreter in the subversion repository is able to infer the type correctly of the “m” combinator as “(’A self -> ‘B)”. This type is the same as: “(’A (’A self -> ‘B) -> ‘B)”. You can see the type itself is recursive. What is also interesting is that the “omega” combinator, defined in combinatory logic as “m(m)” or in Cat: “[m] m”, is rejected by the type system. The inferred type is “(’A -> ‘B)”. This is ill-typed because ‘B can not be deduced from the stack. In simple terms, ‘B does not appear in the consumption, so it can never be assigned a concrete type.
I still have more testing to do, but I should have a new version of Cat posted in a few days.
A new version of the Cat to C++ translator has been released. Details on the release are available at: the Cat language discussion group.
My paper about the Cat type system was rejected from ICFP. The reviewers were encouraging however. Overall consensus seems to be that I am going in an interesting direction but I need more rigour. Going back to school to pursue a Master’s degree in Computer Science in September should be a good step in this direction.
There is still work progressing on the Cat implementation in Omega by Gabor Greif.
I’m trying to fix some bugs in the interpreter’s Cat type inference algorithm.
Colin Hirsch is developing a typed extension to Cat called Mog. This is being discussed at length on the Cat language discussion group.
Doug Coleman has expressed interest in developing a Cat to Factor translator.
I am now trying out “#concatenative” on IRC for discussing Cat. Look for “cdiggins”. I’m using the following client: http://irc.netsplit.de/webchat/?net=freenode&room=%23concatenative
I had blogged previously about the type of the M combinator. This is “dup apply” in Cat or “dup i” in Joy. The issue is that the type is self-referential: it only accepts functions which accept themselves as input. I had previously planned on using labeled types (i.e. type variables with implicit constraints) to deal with such scenarios, however I am now considering just using “self” types. A “self” type is a reference to an enclosing function type. This will allow me to define the type of “M” as (’A (’A self -> ‘B) -> ‘B). In other words “M” accepts only functions that accept themselves as a parameter on the top of the stack. This is significantly less expressive than type labels, but should be sufficient to cover all Cat programs that are likely to occur in practice. I’d appreciate it if anyone can think of a Cat (or Joy) program which is useful but can’t be typed using this scheme.
A call-with-current continuation primitive looks like it will be added soon to Cat. The callcc primitive would probably have the following type:
callcc : (’A (’A (’A -> ‘B) -> ‘B) -> ‘B)
The implementation would call a function after first pushing a pointer to the next instruction on the stack (looks just like a function).
define do_twice { dup [apply] dip apply }
define test { 1 [do_twice] callcc inc }
test == 3
What do you think? Is there any interest in this feature? It would make translating from a large range of languages such as Scheme or C into Cat much easier. The reason it is needed for C is to make a “return” keyword easier to implement. The translation process wouldn’t have to jump through hoops trying to rewrite the code to make it Cat friendly.
Edit: By the way here are the proposed semantics:
[$A [$B] callcc $C] == [$A [$C] $B]
I have also posted about the idea at http://lambda-the-ultimate.org/node/2281.
I’ve just released a beta version of a public domain Level-1 Cat to C++ compiler at http://code.google.com/p/cat-language/downloads/list. This implementation bootstraps a Level-1 implementation of Cat from a Level-0 implementation. There are a hundred unit tests and only a handful of predefined functions so this is a very stable release.
The translation is done without any type-checking. The resulting code is implemented using optimized polymorphic variant types (see http://www.ddj.com/dept/cpp/184402027 and http://www.codeproject.com/cpp/dynamic_typing.asp ) and stable fast-growing stacks (see http://www.codeproject.com/cpp/fast-stack.asp ).
For an updated list of primitives that now contains unit tests for all of the level-0 and level-1 primitives and better definitions see http://www.cat-language.com/primitives.html.
This release is intended to help people who are interested in possibly using Cat as a back-end for other programming languages. By using Cat as a back-end you get the following for free:
- an interactive interpreter
- a Cat to MSIL compiler (this is built in to the interpreter)
- a Cat to C++ translator
These are all projects which I have been developing single-handedly. As more people get involved, you can expect to see the number of compilers and translators to and from Cat increase quickly.
Other Cat projects by other people that I am aware of are:
- a statically typed Cat to C++ translator
- a Cat to assembly translator
- a Cat to Omega (a dialect of Haskell) translator
I’d love to hear what project you are thinking of using Cat for. I just might be able to help out.
I found a step-by-step description of how to write a compiler from Scheme to C using the continuation passing style (CPS) compiler technique at http://chicken.wiki.br/chicken-compilation-process. This would be an excellent starting point for someone learning how to write compilers.