Lambda the Ultimate

From the post:

FeML
----

So I was thinking that an eager language with:

* polymorphic variants as its only data structure;
* pattern-matching as its only conditional;
* (higher-order) functions as its only means of abstraction;
* tail-calls as its only means of iteration;
* and complete run-time type erasure

Ought to be:

* feasible to implement;
* as safe as ML;
* as flexible as Smalltalk (or more so, since the “messages” can
contain other messages you pattern-match on);
* easy to optimize to the neighborhood of C performance;
* relatively terse;
* and a language in the simplicity neighborhood of C, Scheme, and Lua.

Let’s call it “FeML”, for “Femto-ML”.

What’s the equivalent of classes? You need *either* λ-calculus-style
automatic currying *or* closures, but you don’t need both. (That is,
you could make it work like C, without nested functions; you could
require people to write their code directly in supercombinators.)

Interestingly, you can take advantage of polymorphic-inline-cache
optimizations from Self for your pattern-matching; at call-sites to
functions that pattern-match their arguments, you can test the common
cases for that callsite and jump straight to the clause that is
usually used.

It would be pretty awesome to be able to write programs in
happy-go-lucky Python style, but with full pattern-matching and C-like
efficiency. *Predictable* C-like efficiency. And parametric
polymorphism (aka templates) without the hassle that accompanies it in
C++ or Java. And it seems like FeML might be able to deliver that.

The author seems to insist on not having to write down type definitions. I find that strange, because that's something I like to do and I think is important in both the design and maintenance process. He advocates OCaml polymorphic variants, which I precisely found to be most useful when combined with tight type declarations (of the set of allowed variants in some circumstances).

You have have arbitrarily fine-grained types if you allow them to basically reveal anything of a program's semantics; in the limit, the type can be the program code itself. In an open system (eg. developing a library for external use), you need to confront what has been inferred against what you *think* has been inferred about the open parts to be sure that you made no mistake. Type annotations (whether explicit, or through implicit limiting design choices like unique constructor names for algebraic datatypes) are a big part of helping with that; in a sense they (loosely) capture a wide range invariants about its reaction to opponents^Wusers.

That's the reason why, I think, it is generally admitted that module/component boundaries are a good place where to put type annotations.

.

On other aspects of the post: I'm a little dubious of the idea that one will achieve "bare to the metal" efficiency by having *less* than current functional programming languages. The incremental, step-after-step way to enable writing such efficient code is on the contrary to integrate *more* low-level concerns into the language: unboxed values, low-level control flow, stack-allocated locally-shared data... This tends to make bigger languages, rather than smaller ones. Of course you may hide the complexity in specific "expert supersets" (Haskell unboxing features) or be lucky and find an elegant break down of the "simple" techniques as a combination of the "low-level ones" (eg. current boxed product types are a composition of a boxing operation on top of an unboxed product, so you may not consider boxed products as a primitive of your language), but I suspect you will still have to support and explain the simple features in isolation to your users (making them de-facto primitives), and this is not the way the break-down is made in this particular proposal (implementing product types as functions over polymorphic variants does not particularly help efficiency).

Take for example the suggestion to do polymorphic inline caching of dispatch on polymorphic variant tags: this looks like a way to try to regain some of the efficiency that we currently have with the usual, closed algebraic sum types, which can be efficiently compiled (I don't see how caching would help there), but that was lost when moving to open, arbitrary, structural polymorphic variants, which are harder to dispatch on. You get a more complex (and probably slower) implementation with more implicit and harder to predict performance characteristics, just for the sake of unifying two language features.
I understand why one would make this design choice, but it's not the one I would personally make. I'm more interested in providing both; maybe the usual variants only for the advanced users that wants predictable performance, and for internal use by the compiler to express optimizations.

I like it. This is almost exactly what I've had in my mind's eye for several years now. I'm glad others are thinking along the same lines.

I wonder how difficult the problem he raises with typing "inheritance" might be to address? The other problem with typing the language is the open recursion.