Lambda the Ultimate

How I got here was, two recent pieces of writing that made me think heavily were Ruby-centric: Mikael Brockman’s Continuations on the Web and Sam Ruby’s Rails Confidence Builder... So I went and bought Programming Ruby ('Pickaxe' in the same sense that Programming Perl is the 'Camel book')

The conclusion of this piece is that Ruby looks like more than a fad, so LtU readers who still haven't checked it out might want to do so...

Where are the other editors, I wonder?

This paper presents a typed intermediate language EMI that supports multiple and virtual inheritance of classes in C++-like languages. EMI faithfully represents standard implementation strategies of object layout, "this" pointer adjustment, and dynamic dispatch. The type system is sound. Type checking is decidable. The translation from a source language to EMI preserves types. We believe that EMI is the first typed intermediate language that is expressive enough for describing implementation details of multiple and virtual inheritance of classes.

If you really must have mutiple inheritance...

Distributed and communicating objects are becoming ubiquitous. In Grid and Peer-to-Peer environments, extensive use is made of objects. This book provides a general theory for distributed objects interacting asynchronously, for the sake of efficiency and scalability. Further, it copes with advanced issues such as mobility, groups, and components.

Pi-Calculus, Join-Calculus and more...

Check out the sample chapter to get a feeling of the writing style.

it has been awhile since we mentioned Squeak, but there were days when it was mentioned quite regularly...

Generics Considered Harmful

Ken Arnold, "programmer and author who helped create Jini, JavaSpaces, Curses, and Rogue", writes that the usefulness of generics is outweighed by their complexity. Ken is talking about Java 5, but such critiques are well-known for C++, and C# is not immune either. Ken describes the Java case as follows:

So, I don't know how to ease into this gently. So I'll just spit it out.

Generics are a mistake.

This is not a problem based on technical disagreements. It's a fundamental language design problem.

Any feature added to any system has to pass a basic test: If it adds complexity, is the benefit worth the cost? The more obscure or minor the benefit, the less complexity its worth. Sometimes this is referred to with the name "complexity budget". A design should have a complexity budget to keep its overall complexity under control.

[...]

Which brings up the problem that I always cite for C++: I call it the "Nth order exception to the exception rule." It sounds like this: "You can do x, except in case y, unless y does z, in which case you can if ..."

Humans can't track this stuff. They are always losing which exception to what other exception applies (or doesn't) in any given case.

[...]

Without [an explicit complexity] budget, it feels like the JSR process ran far ahead, without a step back to ask “Is this feature really necessary”. It seemed to just be understood that it was necessary.

It was understood wrong.

The article contains a few simple supporting examples, including the interesting definition of Java 5's Enum type as:

Enum<T extends Enum<T>>

...which "we're assured by the type theorists ... we should simply not think about too much, for which we are grateful."

If we accept the article's premise, here's a question with an LtU spin: do the more elegant, tractable polymorphic inferencing type systems, as found in functional languages, improve on this situation enough to be a viable alternative that could address these complexity problems? In other words, are these problems a selling point for better type systems, or another barrier to adoption?

[Thanks to Perry Metzger for the pointer.]

Method mixins - written by Erik Ernst

It is quite common to describe languages with mutable state as machine-oriented, and to describe functional, logical, and other kinds of `declarative' languages as more abstract, liberated from the old-fashioned attachment to bits and memory cells. This opinion was brought to prominence with the 1977 Turing Award
speech by John Backus [...] We must recognize that the functional and other paradigms have have produced deep and useful results. However, it is our opinion that imperative languages, especially object-oriented ones, are being widely used because of their
inherent power and not because programmers are nostalgic about
writing programs in assembly language. It is not a question of abstraction or hardware concreteness, it is about safety and freedom. Restrictive communication topologies bring safety, and flexible topologies bring freedom. To substantiate this, we need to consider variables and similar concepts as communication channels, thereby making them comparable.

This paper provides an interesting perspective on the role of variables in programming. It is about a construct called method mixins, but the discussion about the role of variables in Sec. 2 is relatively independent of the specific construct proposed in the paper:

A Core Calculus of Metaclasses - written by Sam Tobin-Hochstadt and Eric Allen for Fool 12

Metaclasses provide a useful method of abstraction for programmers working with object-oriented languages, but they have not seen the formal exploration applied to more conventional object-oriented programming features. In order to elucidate the structure of metaclasses and their relationship with static typing, we present a core calculus for a nominally-typed object-oriented language with metaclasses and prove type soundness over this core.

Metaclasses are a nifty (albeit somewhat arcane) OOP feature. I found the article interesting, but I had a lot of trouble with the elaborate type soundness proofs. Those who are unfamiliar with metaclass programming might want to read some introductory material before tackling this article. Metaclass Programming in Python by Mertz and Simionato is a particularly good overview.

Parameterized unit tests extend the current industry practice of using closed unit tests defined as parameterless methods. Parameterized unit tests separate two concerns: 1) They specify the external behavior of the involved methods for all possible test arguments. 2) Test cases can be re-obtained as traditional closed unit tests by instantiating the parameterized unit tests. Symbolic execution and constraint solving can be used to automatically choose a minimal set of inputs that exercise a parameterized unit test with respect to possible code paths of the implementation. In addition, parameterized unit tests can be used as symbolic summaries which allows symbolic execution to scale for arbitrary abstraction levels. We have developed a prototype tool which computes test cases from parameterized unit tests; it is integrated into the forthcoming Visual Studio Team System product. We report on its first use to test parts of the .NET base class library.

By adding parameters the authors turn a closed unit test into a universally quantified conditional axiom that must hold for all inputs under specified assumptions. Adding parameters improves the expressiveness of unit cases, at the expense of not providing concrete test cases. Symbolic execution is used to automatically find the set of parameters that have to be tested.

This seems like an interesting approach to unifying unit testing and algebraic specifications.

Metaphor is a strongly-typed, multi-stage, object-oriented programming language. Metaphor is based on a subset of C# and is extended with multi-stage programming constructs in the style of MetaML or MetaOCaml. Metaphor is implemented as a compiler on the .NET CLR.

Metaphor features a static type system for object-oriented reflection operations (i.e. run-time type analysis). This allows the reflection system to be safely incorporated into the language’s staging constructs and thus allows the generation of code based on the structure of types.

A lot of language theory goes past here on Lambda the Ultimate, but we rarely see that theory directly impacting commercial programmers.

I'm a great fan of theoretical concepts like arrows, but at the same time I'm a self-employed programmer interested in solving my clients' problems.

Pugs is notable in that it profitably uses recent developments such as GADTs and Template Haskell for an implementation of Perl6.

I recently became a regular on the #perl6 irc channel and soon after joined the list of committers.

In just a few days I've seen a lot. I've seen enthusiastic members of the Perl community learning Haskell. I've seen myself learning Perl. I've also seen how daily Perl programmers work with abstractions like monad transformers. I've seen how some structures are easy to extend for programmers new to both the Pugs codebase and Haskell.

The Pugs project was started 64 days ago by Autrijus Tang, as an exercise while reading TaPL. Pugs already includes network and threading primitives. New tests and code are add at an amazing rate, as evidenced by the smoke tests.

I don't know if I'll end up using Perl after Pugs is written, but I am learning how to practice the theory of programming language design and implementation.