Lambda the Ultimate

Ran across a short weblog entry on Leonhard Euler, the father of functions and initiator of much in the way of number theory. The mention of Project Euler caught my eye, as I rather like projects that involve multiple PLs attacking the same sets of problems.

Project Euler is a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems. The motivation for starting Project Euler, and its continuation, is to provide a platform for the inquiring mind to delve into unfamiliar areas and learn new concepts in a fun and recreational context.

Project Euler has been around for almost as long as LtU but this is the first I'd heard of it. I find the questions and the competitive gaming aspect to be interesting, though I have a long way to go (level 2 out 5). Not sure there is a direct tie into PLs, but since I'm using it to learn more math and investigate the breaking points and elegance of PLs... and anything involving multiple PLs in competition and mathematics can't be too far removed... and since I haven't posted a story to LtU in a while and this happens to be my current interest... well, that will have to suffice. I'll have to admit though that many of the solutions I looked at are either too rushed (brute force), too cumbersome (indexes flying everywhere) or too terse. But that's true of most code that I run across (including my own). Still hoping for a PL that has that just right aspect - though I'm leaning to Oz these days.

_{(For those of us that are looking for walk-through/cheat guides, the Haskell wiki has the code to the first 200 problems, and I've put my Oz code for the first 50 up on the CTM wiki).}

I'm working on a compiler for a Scheme-like language, 'Irken'. The purpose of Irken is to generate a VM for a (yet to be designed) python-like language. I intend for Irken to be the implementation language for the VM, and also to be the language by which the language is extended - similar to the role of pre-scheme in scheme48.

http://www.nightmare.com/rushing/irken/

One goal here is to eliminate the need for end users to program in C.

Another reason for the roundabout approach: I want massively scalable cooperative threads (think 100,000+ threads, think Erlang)... so using the C stack is out (as is BitC, which I've recently learned about here).

Irken is a whole-program compiler that generates one large C function - 'vm()'. Irken uses the gcc address-of-label extension and 'goto' to implement closures. The current continuation (i.e., 'stack') is heap-allocated.

A couple of months ago my desire for a speedy VM got the best of me and I decided to dabble with type inference - mostly so I could get rid of runtime type checks. It's also nice to get the type safety. 8^)

I now have ML-style let-polymorphism - the algebraic data types. I can implement nice polymorphic data structures like red-black trees, parsers, etc. I've been pleasantly surprised at how little trouble the type inference has been. I've been able to write well-typed generators using call/cc, for example.

I put off thinking about records for a while, assuming that it would be a sugary detail. Now I'm seeing that it's more of a tar pit.

So I'm asking for advice - given the purpose of Irken, what approach should I take in adding a record type? Depending on the amount of work and complexity involved, I could accept anything in the range of 'all records require type annotation' to 'everything is figured out magically by the compiler and has no run-time cost'. Leaning toward the latter direction, though. Also, it'd be nice if I could sugar it up to support some simple OO features.

I've read Wand's "Type Inference for Record Concatenation..." and a bunch of stuff by Remy related to OCaml's row polymorphism. I've also been reading Ohori's "A Polymorphic Record Calculus...".

The impression I have right now is:

Wand: simple monomorphic records + recursive types.
Remy: less simple polymorphic records + recursive types.
Ohori: really cool polymorphic records but no recursive types?

The Ohori approach also looks like I'd have to throw my existing code away - it seems to replace products and sums with labeled records?

Thanks for any and all advice!