So fun to see this — I worked on 3-Lisp for Brian at PARC back in the early 1980s.
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.
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).
It has a mathematical elegance and really makes you think about the semantics of programming language execution.
As an analogy, consider o/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)
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/cc) allows you to implement throw without leaving “user space).
So while I found this work intellectually stimulating, at the end it didn’t seem to add significant expressive power.
My understanding (it's been well over a decade since I read Brian's paper) was that 3-lisp was the direct inspiration for the CLOS Metaobject Protocol. The semantics of CLOS are given in terms of CLOS, and as a reflective object system, you can happily intercede and change those semantics.
With Danny and Jim as authors of the book (with Gregor), that’s likely, though perhaps “direct inspiration” is rather strong. “An inspiration” might be better.
The goals of CLOS were to support object-oriented programming, inspired by Smalltalk, which was the first reflective object system, and which has its own meta-objects and corresponding protocols. CLOS evolved out of earlier LISP object systems, LOOPS and Flavors, both of which predate Brian's thesis, and both of which have various kinds of meta-objects with protocols.
I don't know anything about how 3-Lisp might have influenced CLOS, but I'd like to hear more about that.
> 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.
I used to think that was true, but it turns out not to be. It's true if lambda is strict, but there is no reason lambda has to be strict. If you have a lazy lambda as your primitive you can write OR as a function. [EDIT: I see Tromp already pointed this out earlier.]
Even with a non-lazy lambda you can write OR as a function if you impose a programmer discipline that you have to pass it closures as arguments.
> there may really be a finite set of them (interesting philosophical question)
Not really. IF and WHILE are, together, Turing-complete. (So are any number of other small sets of primitives, including LAMBDA). But of course the sky is the limit in terms of complicated constructs you can invent to layer on top of these primitives.
There may be a finite number of these things that turn out to be useful, but that's not a philosophical question, it's an engineering question.
> 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.
Not in a strict language. But it's trivial to write in a lazy language like Haskell, or the plain lambda calculus.
For a language like binary lambda calculus [1], what would be the things that you cannot write in the language itself?
I’m not familiar with binary lambda calculus; it’s been over 35 years since I thought extensively about reflective languages. But note even in a language like Haskell the lazy semantics comes from the interpreter itself. The proposition that no language (mathematics) can represent all propositions goes back to Russel/Gödel.
Perhaps the better answer is at the end of my comment: for all intents and purposes you can get essentially all the value of a reflexive language through other means, even if those means are much less elegant.
I’m not sure those famous math papers apply here - while programs can be proofs, they in general occupy a much larger category, don’t they?
Calculable functions quickly “outgrow” mathematics.
I mean the Curry-Howard-Lambek correspondance is that lambda calculus, proofs/logic and category theory are all just different ways of talking about the same thing for the most part
> 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.
This isn't strictly correct. The problem is a function call that always evaluates its arguments on function entry.
However, this is NOT a fundamental axiom. Tcl doesn't do it. John Shutt created a Scheme-like language called Kernel that doesn't do it (see: https://web.wpi.edu/Pubs/ETD/Available/etd-090110-124904/unr...). The very early Lisps all had FEXPRs which didn't do it.
The issue is that you have to be able to also pass around the environment (lexical, dynamic, etc.) in which to evaluate those arguments if you don't evaluate them on entry. If you do that, you can have a consistent language that bootstraps itself with only basic support (see: Kernel). However, it doesn't necessarily optimize well--you're almost working as an interpreter continuously.
> there may really be a finite set of [control structures]
Kleene Algebras (which compose via sequencing, choice, and repetition) map so well to sequential programming that I currently believe, yeah, we have them[0]:
- cf ';', case, and while
- Hoare triples map nicely into a Kleene Algebra. I suspect the rise of structured programming tanked adoption of formal methods, because informal methods sufficed, where they may not have had we continued with spaghetti coding.
- matrices/graphs of Kleene Algebras also form a Kleene Algebra, so the state machine[2] a "structured program" compiles down to is still expressed in the same paradigm.
- Kleene himself was originally modelling neural networks, not sequential programs, and he still arrived at the same theory.
So if we're looking for new control structures, they're probably to be found in non-sequential programming.
- unix '|' is a nice example: 'f | g' is not strictly parallel, because f can only run a finite amount ahead of g, which I'm guessing was a deliberate design decision.
- and sometimes not even there? NESL had novel control, but it implicitly followed the data structure[1].
[0] modulo Duff's Device, but so far even that seems to be unique, and not a whole family of too-narrowly-useful control structures.
[1] the 1962 formulation of APL already has a number of primitives suitable for parallel jobs. I have wondered if people in the Unit Record Equipment days often sped up computations by breaking decks into pieces, running them through a gang of machines, and recombining the output decks. However, the oldest APL person I've had contact with was still too young to remember those times, so it remains a hypothesis.
Edit: [2] upon reflection, this would explain why we have these three classical control structures: anything that doesn't really fit into them gets coded as a state machine, which does. Eg. https://arxiv.org/pdf/1109.5416.pdf is a recent rediscovery of a program derivation technique I've seen used elsewhere by at least Hehner and (IIRC) Pratt.
One possibility for going beyond: if we think geometrically, sequencing corresponds to snapping two paths together at a common endpoint to form a new path, choice to splitting the path into multiple paths (leaving a hole instead of a face between them, where 'if' often explicitly marks the beginning of a split, but any join, unless one is using ϕ functions, remains implicit — cf "comefrom"), and repetition to joining into an ancestor, forming (per Euler) a new face. So 0-d points are sets of states (iow: predicates), 1-d paths are maps, and 2-d faces are loops.
What would a 3-d volume be, if anything?
You might like "System design from provably correct constructs", it's written by James Martin but it's presenting the work of Margaret Hamilton. She developed the ideas while working on Apollo 11
In modern terms it works by allowing the user to edit a kind of abstract syntax tree (without the syntax) using only operations that preserve correctness (essentially type checking) so you literally can't make a bug. (You can still make a program that does the wrong thing correctly.)
The four essential operators are (of course) sequence, branch, loop, and parallel (non-interference).
(As you note, state machines are useful for describing complicated systems, but they themselves are simple in terms of the four operations.)
I feel like we have all the tools on the theory side and we just have to put them to use in real systems. I'm trying to make a system for portable computation that can be used to bootstrap a bare machines and would also be useful to offline computations using pen and paper across multiple people.
> I feel like we have all the tools on the theory side and we just have to put them to use in real systems.
I'm glad that this process does happen (if slowly) in mainstream language design. IMH (and casual) opinion, up through the 80s mainstream programming languages were super ad hoc, but (again, IMHO) from the late 90s formalisms from computer science started to filter into the mainstream. I think this is in part because of the crisis of crappy code and a flood of new developers (before computers were so important, code quality was often not that important) so there was more impetus for "steering away from the bad path".
So for example CLU seemed like a purely academic (and restrictive) project to me back in the 80s, but ultimately spurred a lot of currently mainstream concepts like iterators and strong type systems. It just took 30 years (as did Liskov's well-deserved Turing). Lisp was scorned for its GC, anonymous lambda functions, dynamic type system, huge standard library and many other things, many of which are now table stakes today, 50 years later.
By the way, again IMHO, we lose something when language evolution increases guard rails. The Lisp environments of the 70s and 80s allowed lots of people to manufacture a rope and then hang themselves. But for others they were enormously powerful (e.g. I wrote the base of Cyc, a "blank sheet" reimplementation, in just a few weeks). The Smalltalk environment was like that too: infinitely malleable, designed for people who wanted to explore, and powerful enough to easily kill your machine. Nowadays languages with great expressiveness (e.g. C++, especially if you act as if its long ago "parent", C, doesn't exist) draw complaints that it's "too complicated" and "too hard".
I am guessing the guard rails are a symptom of Conway's Law.
In the 80s, we expected to actually code most of a system ourselves. (even in the mid-90s, I personally recall a startup where we had less than a handful of dependencies on the day we sold)
Nowadays, I gather[0] large numbers of people largely develop by plumbing together a bunch of dependencies.
When it's mostly your own code, guard rails may be redundant. When it's mostly Someone Else's Code, guard rails become effective, if not required.
When it's mostly your own code, there's a lot of crunch code[1] relative to parsley code and glue code, and well-meant guard rails may pose obstructions. When it's mostly Someone Else's Code, there's a lot of glue and parsley code relative to crunch, and guard rails provide a handy place to hang all the plumbing.
[0] if HN can be believed
[1] for definitions see https://news.ycombinator.com/item?id=32498382 . I am confident gumby (along with most —if not all— of this thread) will recognize the latinate names "glue code", "parsley code", and "crunch code" go by, when they're at home.
(Note also that 50 years later, we finally have the hardware to use languages like CPL or ALGOL 68 as they were originally envisioned. Thanks, EEs!)
One sees this with Dijkstra’s guarded commands (which are heavily influenced by Hoare) as well. The conditional and loop both pick some true guard nondeterministically. It’s nice on account of it keeps the theory cleaner and of course trying the cases deterministically in program order in the implementation is fully compatible with the formal nondeterministic semantics.
I used to feel it was tragic that even languages which start with unordered choice tend to migrate to ordered choice under practitioner pressure (and I'm unaware of any language which has gone in the opposite direction).
However, now I've made my peace with "working up to isomorphism", and regard ordered choice just as the popular way to specify a state space partition that may also be expressed with (more dignity[0] via) unordered choice.
"How I learned to stop worrying and love IF THEN"
[0] and perhaps even —if we take a moment to remember EWD— without prematurely making decisions that need not be taken...
State machines are tragically underused IMHO. They are powerful and easy to reason about. I often see a rat's nest of fragile code that could much more easily have been built as a state machine.
A 3-lisp program is conceptually executed by an interpreter written in 3-lisp that is itself executed by an interpreter written in 3-lisp and so on ad infinitum. This forms an infinite tower of meta-circular interpreters, which can be implemented efficiently.
See my top level comment on working on this. Also there was a good paper at the 84 POPL by Smith and Desrivieres, though it did feel at the time like few attendees understood it. Perhaps they were put off by the amount of predicate calculus.
This was an area of interesting and active research (at places like PARC and Indiana) for a decade or so but IMHO by now all the juice has long been sucked from this attractive fruit.
Such is the fate of some fundamental research, and not a bad one.
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.
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).
It has a mathematical elegance and really makes you think about the semantics of programming language execution.
As an analogy, consider o/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)
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/cc) allows you to implement throw without leaving “user space).
So while I found this work intellectually stimulating, at the end it didn’t seem to add significant expressive power.