Lambda the Ultimate

by Jérôme Vouillon

We propose a type system based on regular tree grammars, where algebraic datatypes are interpreted in a structural way. Thus, the same constructors can be reused for different types and a flexible subtyping relation can be defined between types, corresponding to the inclusion of their semantics. For instance, one can define a type for lists and a subtype of this type corresponding to lists of even length. Patterns are simply types annotated with binders. This provides a generalization of algebraic patterns with the ability of matching arbitrarily deep in a value. Our main contribution, compared to languages such as XDuce and CDuce, is that we are able to deal with both polymorphism and function types.

It will appear in POPL '06.

Hello everyone,

I am currently trying to understand what the trade-offs are between uniqueness typing and monads. On the surface uniqueness typing seems a little easier to grasp and read (code wise), but it seems there is a lot of fascination with Monads.

I was curious how one would judge whether to use one or the other in order to model side-effects in a pure functional language. Which strategy gives the most 'bang-for-the-buck' in regards to language semantics but also in regards to learning curve?

Thank you everyone in advance for being so helpful. =)

Regards,

-M.