3-Lisp: an infinite tower of meta-circular interpreters
So fun to see this — I worked on 3-Lisp for Brian at PARC back in the early 1980s.<p>A simple way to state the proposition is: in any language there are things you cannot write in the language itself: they have to be supplied by your interpreter (or the compiler generated code which is “interpreted” by the CPU).  For example you can’t write OR because if the first case is true the second case is not evaluated — you can’t write that as a function.<p>But you know: if you know what your interpreter is written in, what if you could pass some code to it to execute on your behalf?  You could write new kinds of control structures (beyond the standard IF, OR, etc).<p>It has a mathematical elegance and really makes you think about the semantics of programming language execution.<p>As an analogy, consider o&#x2F;s systems that let you dynamically load modules into kernel space to do things that aren’t possible in user space (analogy only; don’t try this at home)<p>That being said, languages pretty much have the same set of control structures: there may really be a finite set of them (interesting philosophical question).  Also metasyntactic macros (such as hygienic macros or even Common Lisp macros, C++’s incorrectly-named but powerful constexpr) let you get a lot of the way there.  Continuation-passing (call&#x2F;cc) allows you to implement throw without leaving “user space).<p>So while I found this work intellectually stimulating, at the end it didn’t seem to add significant expressive power.