Lambda the Ultimate

Mark S. Miller's PhD thesis on Robust Composition: Towards a Unified Approach to Access Control and Concurrency Control is now online.

When separately written programs are composed so that they may cooperate, they may instead destructively interfere in unanticipated ways. These hazards limit the scale and functionality of the software systems we can successfully compose. This dissertation presents a framework for enabling those interactions between components needed for the cooperation we intend, while minimizing the hazards of destructive interference.

Great progress on the composition problem has been made within the object paradigm, chiefly in the context of sequential, single-machine programming among benign components. We show how to extend this success to support robust composition of concurrent and potentially malicious components distributed over potentially malicious machines. We present E, a distributed, persistent, secure programming language, and CapDesk, a virus-safe desktop built in E, as embodiments of the techniques we explain.

E rates as a (very) important language for anyone interested in ideas of messaging, distribution and security. The nice thing about a thesis (such as this one and Joe Armstrong's) is that it gives a nice historical account of the related work and influences.

Jeremy Gibbons and Bruno C. d. S. Oliveira (2006). The Essence of the Iterator Pattern. Submitted for publication.

The Iterator pattern gives a clean interface for element-by-element access to a collection. Imperative iterations using the pattern have two simultaneous aspects: mapping and accumulating. Various functional iterations model one or other of these, but not both simultaneously. We argue that McBride and Paterson's idioms, and in particular the corresponding traverse operator, do exactly this, and therefore capture the essence of the Iterator pattern. We present some axioms for traversal, and illustrate with a simple example, the repmin problem.

The core of the solution is from McBride and Paterson's paper Applicative programming with effects, which wasn't posted to the home page before, but which was mentioned a couple of times in the LtU forum.

The context of this reseach is previous attempts to capture functional analogues of OOP design patterns:

Recently we have argued that pure datatype-generic maps are the functional analogue of the Iterator design pattern. It was partly while reflecting on that argument that we came to the (contradictory) position presented here.

I just noticed this project and since we like discussing language-in-a-language projects, I thought I'd mention it.

It seems that they are almost ready to run Rails. Now that's going to be cool!

In May I will be speaking at Expo-C in the beautiful town of Karlskrona, an official UN World Heritage Site. It is great to see that all the buzz around LINQ is putting functional programming back in the picture and the organizers have asked me to combine a Haskell tutorial with an overview of LINQ, including C# 3.0 and Visual Basic 9.(*) in addition to my "coming out" talk VB IsNot C#.

This, and the ICFP deadline last Friday have prompted me to write a short memoir of my journey to democratize distributed data-intensive dynamic applications by leveraging the great ides from functional programming. Comments, supplementary information, missing related work, and flames are all most welcome. In particular I am interested to learn if anyone is using H/Direct to use Haskell for programming against XPCOM.

Hope to see you in Sweden, or at any of my other gigs.

(*) I will be using Graham Hutton's excellent slides.

It's way too quiet around here, so maybe you'd want to check this blog entry about ST exception handling. Here's the juicy bit:

In Smalltalk... the stack is an argument held in the exception.

A screencast about Microsoft's Atlas toolkit (Flash, Windows Media and QuickTime formats available).

Atlas it ASP.Net's AJAX solution, and it seems quite well thought out from what I can tell.

Both the ASP.Net Atlas code and the Atlas XML Script DSL provide a declarative programming model, which should help build AJAX applications which otherwise require a somewhat confusing programming model for beginners.

It sohuld be interesting to see how this approach compares with web frameworks such as Rails (whose DWIM approach makes it quite DSL-ish), and with the approach Wadler takes with Links.

Python 2.5 seems to be feature complete now and is released as a first alpha. See here for a complete list of new features.

From a language perspective enhanced generators and the new with-statement are probably the most interesting features. For many developers the incorporation of the small relational database sqlite, the new XML package elementree and the foreign function interface ctypes might be the highlights.

Gilad Bracha is about to set in motion a JSR that may -- in a glacially unstoppable JCP fashion -- eventually address one of my pet peeves with Java: lack of distinction between public and published interfaces. The latter terms are due to Martin Fowler [PDF, 68K]:

One of the growing trends in software design is separating interface from implementation. The principle is about separating modules into public and private parts so that you can change the private part without coordinating with other modules. However, there is a further distinction -- the one between public and published interfaces.

... The two cases are quite different, yet there's nothing in the Java language to tell the difference -- a gap that's also present in a few other languages. Yet there's something to be said for the public-published distinction being more important than the more common public-private distinction.

Or, in the words of Erich Gamma:

A key challenge in framework development is how to preserve stability over time. The more miles a framework gets the better you understand how you should have built it in the first place. Therefore you would like to tweak and improve it. However, since your framework is heavily used you are highly constrained in what you can change. At this point it is crucial to have well defined APIs and to make it clear to the clients what is published API and what internal code is. For published APIs you should commit to stability and for internal code you have the freedom to change it.

To fully appreciate the kind of pain that this JSR is intended to ease, consider how developers deal with this problem today:

• The Eclipse model, as described by Erich Gamma:

  A good example of how I like to see reuse at work is Eclipse. It's built of components we call plug-ins. A plug-in bundles your code and there is a separate manifest where you define which other plug-ins you extend and which points of extension your plug-in offers. Plug-ins provide reusable code following explicit conventions to separate API from internal code. The Eclipse component model is simple and consistent too. It has this kernel characteristic. Eclipse has a small kernel, and everything is done the same way via extension points.

  Some other projects have adopted similar conventions. For example, France Telecom is known to maintain the distinction between lib and api packages:

  • org.objectweb.jorm.comp.cmdline.api
  • org.objectweb.jorm.comp.cmdline.lib

• Unpublished javadoc.

  J2SE implementations consist of two parts:

  1. Classes and interfaces implementing the published J2SE APIs.
  2. Internal implementation artifacts that aren't meant to be exposed to users of the J2SE libary.

  Sun generates Javadoc only for the "official" classes. Implementation artifacts are undocumented are not supposed to be relied on.

Both of these approach amount to the same thing: convention. Nothing stops you from using the non-published public interfaces. It will be interesting to see what will come out of Bracha's JSR.

All you guys waiting to implement zippers etc. in Ocaml can go right ahead: There's now a library implementation of delimited continuations.

In fact, there are two implementations. A native implementation in C that copies the relevant part of the interpreter's stack, and a pure Ocaml version that requires monadic style of writing code.

foldl.com and foldr.com are two fun websites that may just help you wrap your head around left and right folds. They are the product of Oliver Steele, designer of (Open)Laszlo.