Lambda the Ultimate

A programming language needs to be mapped to model of computation. Otherwise, it is syntax without semantics.

Some models of computation, (e.g., functions that can be implemented in the lambda calculus) limit the abstractions that can be implemented.

I still don't get the ideas here. I haven't ever worked through the details of Felleisen's result, but the idea of comparing expressiveness of two languages by whether or not it's possible to macro express one in the other is pretty simple. I have been unable to attain a comparable understanding of your abstractiveness from the blog and technical report.

For example, you say that abstractiveness is like a second derivative of semantics, but I have trouble even identifying Felleisen's expressiveness as a first derivative of semantics. A high first derivative of semantics would seem to me to mean that you change the program a little and the meaning changes a lot. That doesn't sound like a very useful property. Expressiveness is rather an ordering of languages, rather than a rate of anything. By the time we go to take a second derivative I'm completely lost.

And I don't like the example you've chosen as a test case, because it feels like something that fits perfectly well into Felleisen's expressiveness, save for a technicality that reporting error messages in certain cases isn't one of his observables. Can you give a test case that better conveys what abstractiveness is about?

In general, my intuition is that there are certain classes of languages that are maximally extensible, in a sense that can probably be made precise, but that involves only a reachability test and not a metric/distance. And that this will be a useful property for a language to have, but that there will be a large variance in language quality among languages with this extensibility property.

It turns out we've been tackling something similar. I work on an extensible languages tool called Silver. Our goal has been to develop a practical notion of language extension where extensions will reliably compose together, guaranteed no problems. That, of course, requires restricting the range of extensions that are possible. We've only relatively recently figured out the analyses and properties that extensions must satisfy to permit this composition property, and we've recently turned to looking at just how restrictive it is.

These properties essentially provide a dividing line between "this new language feature is a potential extension" vs "this feature constitutes a change to the host language itself." We've discovered the range of possible extensions varies considerably with the host language. Indeed there seems to be a few small tweaks that host languages require to allow useful extensions at all, and other changes that have really massive effects on what's possible. (We have a draft paper currently under review with some of these sorts of experiences in building an extensible C compiler. Hopefully I'll have some links mid-January, if anyone's interested.)

At any rate, it seems like John Shutt is trying to put restrictions on, for example, what macros are capable of, and thus expose a richer underlying structure of relationships between languages. Perhaps we have an alternative set of restrictions that get to a similar idea.

I wonder if your framework can apply to the extension of C to C++. I have quite a few examples! Here's one.

A language C contains base types I, and a postfix type constructor i*, so that if t in I, t in C, and if t in C then t* in C also. Let us now add the usual struct aggregate to get a new language C.

Now some wag comes along and adds template<T> to structs. C has the usual expressions but now we add terms like X<int> where X is a template struct, and int in I.

So far so good, this works. But now someone else comes along and tries to add a new type i&. The rule for the original template free C is simple enough: R is C extended by the set of types c& where c in C, i.e. references are only allowed at the top level. Now we add templates to that an all hell breaks loose because we can derive int&& which is nonsense.

This is actual C++. You cannot write this term but you can template expand to get it and it's defined as meaning int&.

So it's clear to me *intuitively* that the introduction of reference types limits the extensibility of the language by excluding coherent templates or vice versa.

Now please construct an argument that this is so in terms of your paper. I'm not looking for mathematics, just the way of *explaining* the problem. If we make references only part of function argument passing mechanics instead, what happens?

I have a list of faults in C++ a mile long of the kind "fails to be orthogonal", from unions of constructible types to the failure of templates to properly generalise C struct by disallowing incomplete types as arguments, thereby making combinatorial type recursion possible.

In some cases the extensions were bad but in most it is C that is so badly designed it already at a fixpoint: radius-of-abstraction (C) == C. In fact it's worse, K&R was almost there but introduction of typedefs in ISO C actually pushes it *outside* its radius of abstraction (you can't parse anything but whole programs so the notion of transforming a prefix is nonsense).