5 ms·
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 y
by gumby 4y ago
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.
- momentoftop 4y agoMy 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.
- gumby 4y agoWith 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.
- doug-moen 4y agoThe 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.
- tromp 4y ago> 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? [1] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html
- gumby 4y agoI’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.
- kaba0 4y agoI’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.
- dumpsterlid 4y agoI 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
- gumby 4y agoWe’re not talking about trying to prove correctness; this is about the representational semantics of the language (a symbol system) itself.
- 082349872349872 4y ago> 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 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?
- samatman 4y ago
- deleted 4y ago[deleted]
- lisper 4y ago> 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.
- bsder 4y ago> 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/unrestricted/jshutt.pdf 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.