Lambda the Ultimate

In my reading so far on ML type inference algorithms, the object seems to be to infer the most general type of expressions. If I have the terminology correct this is the "principal type".

Can someone point me at algorithms for inferring the most-specific or least-general types in ML programs? I'm interested in analysis methods, type inference being one of them, for find information about a program. So rather than most general types to encourage reuse of code, I'd like to find the most-specific types to see exactly and only the way the functions are being used in a program.

thanks in advance!
bill

This is the problem:

I have a function that yields a number N times. The caller invokes the function, and gets the number and a continuation. It does some work then invokes the continuation, getting another number and continuation. That repeats until N continuations are invoked.

Things become interesting when I try to type the continuation returned by the yielding function. It seems that it has a recursive type. Is that a known result? How do type systems deal with recursive types?

def numbers = fun(... -> return(Yield_int, int), throw(Exception) {...})
type Yield_int = fun(-> (Yield_int, int), (Exception))

I use continuation-passing style notation. Whatever comes after "->" is a continuation passed as argument to the function. By default a function takes two continuations, one for normal return and one for exceptions. So the notation above means the return value of Yield_int is the pair (Yield_int, int).

I am not sure how to manage the stack with a yielding function too. The Yield_int continuation looks like a capturing lambda, so I could allocate memory to hold captured variables. But I may need to allocate more memory for each Yield_int continuation, which does not look optimal.

My ideas range from a fragmented stack frame to read-only memory pages for the Yield_int continuation when it is not activated. That may not be a discussion for ltu...

I thought this paper may be of some interest to LtU readers. By Curt J. Sampson, Starling Software:

I describe the initial attempt of experienced business software developers with minimal functional programming background to write a non-trivial, business-critical application entirely in Haskell. Some parts of the application domain are well suited to a mathematically-oriented language; others are more typically done in languages such as C++.

I discuss the advantages and difficulties of Haskell in these circumstances, with a particular focus on issues that commercial developers find important but that may receive less attention from the academic community.

I conclude that, while academic implementations of "advanced" programming languages arguably may lag somewhat behind implementations of commercial languages in certain ways important to businesses, this appears relatively easy to fix, and that the other advantages that they offer make them a good, albeit long-term, investment for companies where effective IT implementation can offer a crucial advantage to success.

Paper available here, slides from ICFP talk available here.

The "disadvantages" section seems interesting, as many of the disadvantages of Haskell as a commercially viable language (in Sampson's opinion) seem to stem from lack of decent tool support. However, a quick browse seems to confirm that many efforts are being made to address this (e.g. Hare, a Haskell refactorer, HLint, a lint equivalent, etc. etc.)

Are there any more examples of papers, discussing the pros and cons of functional languages in a commercial setting, like this one?

EDIT: fixed broken link to paper.

Does anyone know of a "definitive guide" to using C as a compilation target? I have some of the dated references, like Appel's A Runtime System, and obviously "Cheney on the MTA" which forms the basis for Chicken Scheme, but there have been more recent developments, like Henderson's shadow stack and lazy pointer stacks.

I haven't found much recent work on supporting tail calls in C either, other than trampolines and Cheney on the MTA. Scheme has some papers on compiling to C, as does Bigloo, and Mercury. This Scheme paper seems like the best reference.

So does anyone know of a guide that discusses the various techniques and tradeoffs of compiling to C? Or any papers that you might consider relevant? I started writing my own guide, since I haven't found anything comprehensive yet, but figured someone here would know if something like it already exists.

Brian Beckman interviews Rich Hickey to understand the philosophy, history and general reasoning behind Clojure (why did Rich create Clojure? How is the language designed? How will it evolve? etc...) This conversation provides an excellent introduction to Clojure and it goes deep enough to be useful for professional language designers and academics. Enjoy! Many thanks to Rich and Brian.

I've posted a few times on encoding tagless interpreters in C#. Unfortunately, C# and the CLR don't support type constructor polymorphism, so after much sweat and tears I had developed a mostly type safe encoding using downcasts. I've never fully described this translation from ML modules and signatures to C# classes and interfaces in plain English, but a recent Stack Overflow question on that exact subject spurred me to describe it fully. Perhaps people here forced to work in Java and/or C# will find it useful:

Abstracting over Type Constructors using Dynamics in C#

I'm not sure whether this has already been posted (a quick search says "no"), but videos from 40 presentations at ICFP 2009 (in Edinburgh), are available through this Vimeo account. I'm sure this will be of some interest to LtU readers.

A year ago there was a forum topic about Swarm, a "distributed stack based programming language".

The basic idea is that data can be distributed across multiple computers, and when a thread needs to access some data on a remote computer, it is captured as a continuation, and migrated to that computer, where it is resumed. It is the ultimate expression of the maxim "its cheaper to move the computation, than to move the data".

Then, the idea is to use a "supervisor" process to monitor when the computation must jump between computers, and adaptively rearrange the data to minimize the frequency with which this must occur using some kind of clustering algorithm.

A year ago Swarm was a custom stack-based programming language, implemented in Scala. Of course, the fact that we had to design a completely new programming language was a serious problem, but at the time it was the only way we could get portable continuations.

Swarm has come a long way since then, and after a complete redesign you can now write Swarm code in (more or less) plain Scala. This is possible due to the delimited continuations Scala compiler plugin that will be bundled with Scala 2.8.

Swarm's source code is available under the LGPL, and we are actively looking for people to help us solve the many remaining problems with it.

You can find the source code, and a video explaining the project, at our Google Code page (sorry, no paper yet - the video is the best explanation).

There's a fair number of projects that take one highish-level language in and spit out another (often it seems to be JavaScript is the target, gosh i wonder why). But these translations often result in pretty non-human-readable output that doesn't respect the destination language's culture and commonly used style. That makes debugging harder, I think. So I wonder if there are any good approaches to bridging this gap? Ways of taking in e.g. Scheme and spitting out e.g. JavaScript that doesn't look horrible or confusing. (Presumably it depends on how far apart the two languages are in the first place.) Thanks for any thoughts.

Old news, but didn't see it mentioned on LtU yet. There have been a few revisions released already:

2009 May 19: The Timber compiler 1.0.3 released.

The overall purpose of a Timber program is to react to events sent to it from its execution environment. This process is potentially infinite, and the order of external events is also not generally known in advance.

To capture this intuition, Timber defines its primary run-time structure to be a set of interconnected reactive objects, that each encapsulate a piece of the global program state.