I’m a new member of the Seattle Functional Users group (SeaFunc for short) which meets in Seattle roughly every three weeks (their next meeting is tonight, Tuesday February 27th, 8:00pm at Ralph’s Grocery downtown at 4th and Lenora.
Many SeaFunc members have expressed an interest in an East-side version of the user’s group, so a bunch of us have agreed to meet at the Overlake Red Robin at 8pm on Wednesday, March 6th (South East corner of 148th and 24th).
Everyone is invited! The setting is quite casual, and there could be impromptu presentations of functional technologies.
The Cat technical paper is based primarily on the theory of types and programming languages presented in the book Types and Programming Languages by Benjamin Pierce. The TAPL, as it is commonly referred to, is an excellent book for understanding some of the jargon and formulas used in the Cat paper.
I recommend this book to anyone who wants to learn the foundations of type theory, and programming language theory.
I’ve posted a revised version of the Cat programming language technical report at http://www.cat-language.com/paper.html.
The abstract follows:
Cat: A Typed Functional Stack-Based Language
Cat is a purely functional stack-based language with very simple semantics and a novel type system, which makes it appropriate for usage as an intermediate language. Cat differs from most other functional languages in that the concatenation of terms implies the operation of function composition instead of the more common operation of function application.
This paper presents the semantics and a type-system for Cat, and briefly discusses some of the interesting properties of the language.
My goal is to submit the article to the International Conference on Functional Programming (http://www.informatik.uni-bonn.de/~ralf/icfp07.html)
Any suggestions on how to improve the paper would be much appreciated.
I just ran my first faster-than-C# benchmark, on the Cat to MSIL compiler (sorry the compiler isn’t ready for prime-time yet, but you can play with the CatNip prototype). The Cat program, on my Dual-3.4 GHZ Xeon box, was 43% faster than the same program in C#.
The benchmark is a simple binary recursion algorithm. In C# the code is:
static int Test(int n) {
if (n > 27) {
return 1;
}
else {
return Test(n + 1) + Test(n + 1);
}
}
The same program written in Cat is:
[dup 27 >] [pop 1] [+] [1 + dup] bin_rec
What makes Cat much faster on my dual-Xeon computer is that certain primitives like bin_rec are run in parallel. C# just isn’t that great at parallelization.
So what are the implications of this? Well I think this indicates that the tides have turned for functional programming languages. As multi-core and multi-processors become ubiquitous (see, for example, the essay The Free Lunch is Over by Herb Sutter), functional languages can start flexing their muscles.
Perhaps this also means Cat has a fighting chance to actually become relevant in the near future?
I have just posted some C# source code for generating MSIL byte-code from strings. The code is public domain, and tested, but the project isn’t actively supported. CatNip is actually the prototype for the upcoming Cat to MSIL compiler.
Have Fun!
One thing I realize that really helped me grow immensely as a programmer, which was a hard thing to do at first, was to share my code publicly. I realize that very few programmers have had the experience of putting their code out on display in a very public forum for others to publicly disect and critique.
This can be a very frustrating and humbling experience. The initial reaction you may have upon hearing my suggestion is, well you are already very humble and modest about your code and you don’t need the harship. Despite that, the experience can still be very rewarding. Seeing your code through other people’s eyes can be a real wake-up call as well as a crash course in things you may never have realized you didn’t know!
I really only started to become adept at C++ when I first started sharing code with the Boost community, and had it torn to shreds by my peers. Other forums which were very helpfuyl were newsgroups, such as comp.lang.c++, where people are always happy to point out even the smallest non-standard conformance issues in your code.
I encourage all programmers to find some public code sharing forum, such as CodeProject.com, and take the plunge and share some code with the community. You may be surprised at how much more you have to learn than you have to teach. The people who learn something from your sharing experience will also be grateful, and will make the experience that much more gratifying.
[Postscript]
There has been some interesting feedback on this idea at Artima.com.
I spent the weekend with my sleeves rolled up, waist deep in MSIL byte-code. As I work with the MSIL, my code is starting to resemble an assembly compiler more and more. I found it easier to write wrapper functions which takes string arguments, and generate the neccessary OpCodes from that, rather than having to write the annoying API calls: myILGenerator.Emit(OpCodes.someopcode, somevariable). I’d rather write: Emit("1 2 + ret"). The library function I needed to write to do this wasn’t a whole lot work, and signficantly reduces the complexity of the rest of my code.
As a matter of practice if an API is sufficiently complex I will invariably write a wrapper library for my own purposes which does house-keeping or takes care of the boiler-plate. This requires a certain amount of extra effort up-front, and despite resembling a YAGNI almost always pays off when debugging and refactoring. This is related to the Agile/XP practice of anticipating and embracing change.
This brings me to an interesting point, I very often end-up refactoring my code, because better designs occur to me only while in the middle of development (or new features creep in which demand it). I try to do some upfront design, but often I need to work with a prototype, or stub implementation to uncover the bugbears that lurk in the design. Ok … the real reason is I’m lazy, and I find it quicker and easier to sketch the design in code (using modules, objects, structs, and interfaces), rather than writing a bunch of UML diagrams. I always code in a top-down manner sketching out the high-level components, and then breaking it down into smaller sub-problems. This way my code can substitute for the design document.
It seems as if being lazy and planning so that I can continue to be lazy in the future, is a path which leads naturally to agility in programming and software development.
Any thoughts about lazinesss and agility that you care to share?
My recent blog post at Artima, Stages of Software Development, caught the eye of a PM blogger named Raven who had very nice things to say.
Thanks for the encouragement Raven!
I am pretty sure Steve Yegge is refering to C# 3.0 in his recent post The Next Big Language.
What do you think?
[PS: I am now thinking it is JavaScript 2.0, this presentation provides some interesting insight.]
An important goal for programming languages moving towards a multi-code future are compilers which automatically parallelize computer programs. This is very hard to do in imperative programming languages like C++ which have lots of side-effects. Consider code such as:
int a[1000];
...
for (int i=0; i < sizeof(a) / sizeof(a[0]); ++i)
{
a[i] = f();
}
This kind of code is very hard (in fact often impossible) for a compiler to parallelize, because side-effects are so hard to detect. In fact it explicitly states that it should be run serially. In a language like Cat where side-effects are part of the type-system it becomes a lot easier to automate concurrency. The equivalent code in Cat is:
[pop 0] 1000 init ... [f] map
The key to parallelizing this code is the fact that map can run in parallel if the function f is known at compile-time to have no side-effects.
I have already implemetned an automatic parallel implementation of “bin_rec” which is the binary recursion primitive. So far I can get full utilization of both processors but the basic arithmetic primitives run far too slow when compared to C#.
The next step is get the core language (arithmetic, comparisons, bit twiddling, etc.) to run at least as fast as C# … if not faster :-)