Lambda the Ultimate

We design and implement a library for adding backtracking computations to any Haskell monad. Inspired by logic programming, our library provides, in addition to the operations required by the MonadPlus interface, constructs for fair disjunctions, fair conjunctions, conditionals, pruning, and an expressive top-level interface. Implementing these additional constructs is well-known in models of backtracking based on streams, but not known to be possible in continuation-based models. We show that all these additional constructs can be generically and monadically realized using a single primitive which we call msplit. We present two implementations of the library: one using success and failure continuations; and the other using control operators for manipulating delimited continuations.

As you can expect from the author list, this is cool stuff. Enjoy!

A type-indexed function is a function that is defined for each member of some family of types. Haskell's type class mechanism provides open type-indexed functions, in which the indexing family can be extended at any time by defining a new type class instance. The purpose of this paper is to present TypeCase: a design pattern that allows the definition of closed type-indexed functions. It is inspired by Cheney and Hinze's work on lightweight approaches to generic programming. We generalise their techniques as a design pattern. Furthermore, we show that type-indexed functions with type-indexed types, and consequently generic functions with generic types, can also be encoded in a lightweight manner, thereby overcoming one of the main limitations of the lightweight approaches.

A new paper in a field we follow quite closely (i.e., generic programming).

The paper starts with a useful summary of important previous results, which is worth reading even if you don't plan on studying the whole paper.

As LtU readers know, I don't really care about language popularity metrics. They don't tell you much that isn't obvious.

But at least this graph is supposed to reflect real data...

JavaScript 2.0: Evolving a Language for Evolving Systems (pdf) Waldemar Horwat

JavaScript 2.0 is the next major revision of the JavaScript language. Also known as ECMAScript Edition 4, it is being standardized by the ECMA organization.

Starting with an evaluator for a language, an abstract machine for the same language can be mechanically derived using successive program transformations. This has relevance to studying both the space and time properties of programs because these can be estimated by counting transitions of the abstract machine and measuring the size of the additional data structures needed, such as environments and stacks. In this article we use this process to derive a function that accurately counts the number of steps required to evaluate expressions in a simple language.

Somewhat related to a recent discussion (in which I mentioned EOPL1's scetion on deriving a compiler and machine from an interpreter).

The paper is, of course, worth checking out regardless.

Jacob Matthews, of PLT fame, is writing a blog currently covering PLDI. It's an interesting and amusing read; check it out!

Not much that is new here, but the trend towards concurrency is one we discussed a few times, and which seemed to attract interest.

Bray's comments regarding erlang and other languages are sure to annoy LtU readers. Let's not start a flamefest. Let me just remark that even if you want shared data structures, Java isn't your only option. You should at least check out Ada... (and you can compile Ada to the JVM, if that's what you want to do. let's not confuse language and implementation).

Libraries are central to all major scientific, engineering, and business areas, yet the design, implementation, and use of libraries are underdeveloped arts. This workshop is one of the first steps in the process of placing all aspects of libraries on a sound technical and scientific basis through research into fundamental issues and documentation of best practices.

A software library is an organized collection of code with associated tools supporting programming in general or in specific domains, usually united by a specified set of principles and conventions. Most libraries are aimed at the use by several people and in different environments...

This is an important topic, so I urge you to take a look at the CFP for the workshop, and see if you can help improve the state of the art by contributing.

Some day I must find out why generic declarations extend rather than implement interfaces. Grr.

Kinda makes me understand what my students go through when they first encounter Ada's generic model (which is much easier to understand, I hasten to add).

For those who want to know what's up in the world of VB, the VB8 Language Spec is available. Mostly, it looks like the language keeps creeping towards the C# language model, so much so that I always recommend that anyone using MS VS simply go the C# route, as it is more true to the .Net model. Not much to report from the Language Innovation department:

• Operator Overloading
• Generics
• IsNot Keyword
• Using Keyword
• Unsigned Integer Types
• Partial Classes
• Background Worker Object

(Note: In typical MS fashion, the VB Spec is an executable file, but the file is just a zip executable that contains a Word document.)