Lambda the Ultimate

Hi,

For my master thesis I'm designing a new programming language for a specific domain related to data processing.

One of the neat features I'd like to include in the language would be the concept of memory, in that each variable would remember its past values and the interval it held them. This can simplify lot's of queries as time itself is central in this domain.

Anyway, being just a graduate student, I know this idea must not be new. However, the most similar topic I was able to dig were temporal databases and temporal query languages. I wonder if there is anything else. Also, I wonder if it is possible for the compiler to analyze the program and find out how much memory it really needs to keep. Comments?

Thanks,

Luís Pureza

It is often hard to write programs that are ef?cient yet reusable. For example, an efficient implementation of Gaussian elimination should be specialized to the structure and known static properties of the input matrix. The most profitable optimizations, such as choosing the best pivoting or memoization, cannot be expected of even an advanced compiler because they are specific to the domain, but expressing these optimizations directly makes for ungainly source code. Instead, a promising and popular way to reconcile efficiency with reusability is for a domain expert to write code generators. Two pillars of this approach are types and effects. Typed multilevel languages such as MetaOCaml ensure safety: a well-typed code generator neither goes wrong nor generates code that goes wrong. Side effects such as state and control ease correctness: an effectful generator can resemble the textbook presentation of an algorithm, as is familiar to domain experts, yet insert let for memoization and if for bounds-checking, as is necessary for efficiency. However, adding effects blindly renders multilevel types unsound...

Code generators have to be written in CPS or monadic style due to the need for let-insertion and if-insertion. This makes writing code generators unattractive to many programmers. The paper provides an alternative based on delimited continuations, and paper proposes a sound combination of staging and delimited continuations. The combination has been implemented. The authors show how pleasant it becomes to write interesting code generators (specializing dynamic programming and Gaussian elimination codes). The paper and the code for many generators is available online. I suggest reading the explanation of the problem, and then looking at the actual code generators.