Lambda the Ultimate

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...

Safe Garbage Collection = Regions + Intensional Type Analysis, by Daniel C. Wang and Andrew W. Appel:

We present a technique to implement type-safe garbage collectors by combining existing type systems used for compiling type-safe languages. We adapt the type systems used in region inference [16] and intensional type analysis [8] to construct a safe stop-and-copy garbage collector for higher-order polymorphic languages. Rather than using region inference as the primary method of storage management, we show how it can be used to implement a garbage collector which is provably safe. We also introduce a new region calculus with non-nested object lifetimes which is significantly simpler than previous calculi. Our approach also formalizes more of the interface between garbage collectors and code generators. The efficiency of our safe collectors are algorithmically competitive with unsafe collectors.

I'm surprised this region calculus hasn't received more attention or follow-up discussion in subsequent papers. It seems eminently practical, as it replaces the more complicated alias analyses required in other region calculi, with garbage collection of region handles; seems like a huge improvement over general GC, assuming region inference is sufficiently precise.

I recently came across the language SequenceL, which it seems NASA is using in some of its human spaceflight programs. SequenceL is described as a high-level language for declarative computation on nonscalars. One of the key features of the language appears to be the avoidance of the need to explicitly specify recursive or iterative operations. For example, given the function definition

Search(scalar Target, tuple [Subscript, Word]) = 
    Subscript when Word = Target 

which applies to tuples, the programmer can apply the function directly to lists of tuples without any need to specify how that application will be performed, e.g.

search(fox,[[1,dog],[2,cat],[3,fox],[4,parrot]]) → 3 
search(rabbit,[[1,dog],[2,cat],[3,fox],[4,parrot]]) → [] 

The language designers (Daniel Cooke and J. Nelson Rushton) claim that this kind of thing leads to more concise and readable code, and a more direct representation of a specification.

Unfortunately, the SequenceL website appears to be inaccessible at the moment. However, Daniel Cooke's site includes links to a number of papers and talks that describe SequenceL. In particular, the paper Normalize, Transpose, and Distribute: An Automatic Approach for Handling Nonscalars provides a detailed description of the "Consume-Simplify-Produce/Normalize-Transpose" approach that is embodied by SequenceL. There's also an overview of SequenceL available through CiteSeer.