Tony Finch – blog

I came up with a new word in the pub this evening. I was trying to remember Peter Van Roy’s term “definitive language”, which he uses to describe a language which is the ultimate refinement of a popular, well-understood programming paradigm. He argues that Erlang, E, and Oz are working towards the definitive concurrent functional language, and I suppose that C++/Modula-3/Java/C# are working towards a definitive object-oriented language.

But the word I came out with was “eigenlanguage” not “definitive language”, and I was told that this has entirely the wrong implication: an eigenlanguage must be a language that is pared down to its essentials. Scheme (not Common Lisp), Forth (not Postscript), BCPL (not C++), etc. The fun thing about eigenlanguages happens when you push them as far as you can. Write code in the lambda calculus, or if that isn’t hard-core enough, SK combinators! Single-instruction machine codes! Turing machines! Cellular automata!

I have an interesting eigenlanguage in my head. The “eigen” in this one is related to the data structure (singular) that programs manipulate.

One of the ugly things about Forth is that it has two stacks, one for expression evaluation and one for control flow. It’s well-known that you can get significant fun out of making function return addresses explicit (continuation-passing style, and for the serious lunatics, call-with-current-continuation), which in Forth terms means using one stack for both purposes. For more interesting data, Forth descends to low-level array-of-words machine memory.

Lisp, however has nice lists/trees/pairs/do-what-you-like s-expressions. It’s well-known that you can use a singly-linked list as a stack. But this stack doesn’t have to be just a linear data structure like in Forth: it can be tree-like, or loopy, or whatever you like!

So why not try defining a language with only one data structure? A Lispish directed graph, which you can only manipulate via your single stack pointer, and which you have to code in continuation-passing Forth. If done properly, it can lead to some really elegant pessimizations such as multi-instruction sequences that implement the Forth primitives dup and exch.

However it is too late for me to go into the details now…