Lambda the Ultimate

Acute: high-level programming language design for distributed computation

This work is exploring the design space of high-level languages for distributed computation, focussing on typing, naming, and version change. We have designed, formally specified and implemented an experimental language, Acute. This extends an OCaml core to support distributed development, deployment, and execution, allowing type-safe interaction between separately-built programs. It is expressive enough to enable a wide variety of distributed infrastructure layers to be written as simple library code above the byte-string network and persistent store primitives, disentangling the language runtime from communication.

This requires a synthesis of novel and existing features:

• type-safe interaction between programs, with marshal and unmarshal primitives;
• dynamic loading and controlled rebinding to local resources;
• modules and abstract types with abstraction boundaries that are respected by interaction;
• global names, generated either freshly or based on module hashes: at the type level, as runtime names for abstract types; and at the term level, as channel names and other interaction handles;
• versions and version constraints, integrated with type identity;
• local concurrency and thread thunkification; and
• second-order polymorphism with a namecase construct.

The language design deals with the interplay among these features and the core. The semantic definition tracks abstraction boundaries, global names, and hashes throughout compilation and execution, but still admits an efficient implementation strategy.

Unfolds generate data structures, and folds consume them. A hylomorphism is a fold after an unfold, generating then consuming a virtual data structure. A metamorphism is the opposite composition, an unfold after a fold; typically, it will convert from one data representation to another. In general, metamorphisms are less interesting than hylomorphisms: there is no automatic fusion to deforest the intermediate virtual data structure. However, under certain conditions fusion is possible: some of the work of the unfold can be done before all of the work of the fold is complete. This permits streaming metamorphisms, and among other things allows conversion of infinite data representations. We present the theory of metamorphisms and outline some examples.

More origami work from Gibbons.

This paper is related to several previous papers by Gibbons that were mentioned here (e.g., spigot pi, arithmetic coding), and it could be said that it summarizes the main results. I don't think this paper was linked to directly, so here goes.

Simon Peyton Jones, Geoffrey Washburn, and Stephanie Weirich.
July 2004
Postscript

Generalised algebraic data types (GADTs), sometimes known as "guarded recursive data types" or "first-class phantom types", are a simple but powerful generalisation of the data types of Haskell and ML. Recent works have given compelling examples of the utility of GADTs, although type inference is known to be difficult.

It is time to pluck the fruit. Can GADTs be added to Haskell, without losing type inference, or requiring unacceptably heavy type annotations? Can this be done without completely rewriting the already-complex Haskell type-inference engine, and without complex interactions with (say) type classes? We answer these questions in the affirmative, giving a type system that explains just what type annotations are required, and a prototype implementation that implements it. Our main technical innovation is wobbly types, which express in a declarative way the uncertainty caused by the incremental nature of typical type-inference algorithms.

Edit: Made the title into a hyperlink, as the "Postscript" link could easily get lost in a sea of blue text...

Edit 2:Quoted the article with a plain-ol' <blockquote> instead. Better?

(Link)

Vadim Nasardinov pointed out this article, which although pitched at an introductory level, provides a reasonably thorough overview of functional programming possibilities in Java. It focuses on the use of closures and higher-order functions, via Java's anonymous inner classes, and works its way up to "using closures to implement business rules" as one of its concrete examples.

Perhaps a little too introductory for LtU, but articles like this can be a useful starting point when talking to Java programmers who've had little or no previous exposure to FP, or who need some hints about useful ways to apply FP concepts in Java. Using anonymous inner classes to implement e.g. GUI event listeners in Java is common practice, but often, more advanced and useful possibilities are overlooked.

Objective Caml release 3.08.0 is official and incorporates many improvements. A big thank-you to the OCaml team for this stable release. Those on the bleeding edge of post-3.08 CVS work can follow Xavier's advice.

One of the gems squirreled away on Oleg's site is "Makefile as a functional language program":

"The language of GNU make is indeed functional, complete with combinators (map and filter), applications and anonymous abstractions. That is correct, GNU make supports lambda-abstractions."

Although I've classified this under Fun, Oleg exploits
the functional nature of Make for a real, practical application:

"...avoiding the explosion of makefile rules in a project that executes many test cases on many platforms. [...] Because GNU make turns out to be a functional programming system, we can reduce the number of rules from <number-of-targets> * <number-of-platforms> to just <number-of-targets> + <number-of-platforms>."

See the article for a code comparison
between make and Scheme, and check out the Makefile in question.

In this paper,we explain an elegant technique for enumerating the positive rationals without duplicates. Moreover, we show how to do so as a simple iteration, generating each element of the enumeration from the previous one alone,with constant cost per element (assuming unit cost for simple operations on arbitrary-precision rationals). Best of all, the resulting program is extremely simple...

Cute. Nothing earth shattering, but fun none the less.

I am not sure whether the most reasonable conclusion from this thread isn't to not choose lazy languages. I don't think it's simply a problem of lack of tools. Debugging lazy code is iherently problematic.