6 ms·

3-Lisp: an infinite tower of meta-circular interpreters

84 points by nikita_d 4y ago

nikita_d 4y ago
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.
- 082349872349872 4y ago
  two implementation hints: https://en.wikipedia.org/wiki/Drawing_Hands#/media/File:DrawingHands.jpg https://en.wikipedia.org/wiki/Drawing_Hands#/media/File:Draw... https://www.youtube.com/watch?v=DgIDStgaybc&t=74s https://www.youtube.com/watch?v=DgIDStgaybc&t=74s
lisper 4y ago
I honestly can't tell if this is intended to be a joke or not.
- gumby 4y ago
  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.
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 ago
  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.
  - gumby 4y ago
    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.
    - agumonkey 4y ago
      Do you know any articles about the history of AoMOP or other influences ?
      - gumby 4y ago
        No, but you could look in the proceedings of contemporary POPLs and ACM Lisp and Functional Programming conferences.
  - doug-moen 4y ago
    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.
- 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
asplake 4y ago
Does this point to improvements that could/should be made to other Lisps?
- gumby 4y ago
  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.

84 points by nikita_d 4y ago

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.

082349872349872 4y ago
two implementation hints: https://en.wikipedia.org/wiki/Drawing_Hands#/media/File:DrawingHands.jpg https://en.wikipedia.org/wiki/Drawing_Hands#/media/File:Draw... https://www.youtube.com/watch?v=DgIDStgaybc&t=74s https://www.youtube.com/watch?v=DgIDStgaybc&t=74s

lisper 4y ago

I honestly can't tell if this is intended to be a joke or not.

gumby 4y ago
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.

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 ago
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.
- gumby 4y ago
  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.
  - agumonkey 4y ago
    Do you know any articles about the history of AoMOP or other influences ?
    - gumby 4y ago
      No, but you could look in the proceedings of contemporary POPLs and ACM Lisp and Functional Programming conferences.
- doug-moen 4y ago
  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.
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

asplake 4y ago

Does this point to improvements that could/should be made to other Lisps?

gumby 4y ago
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.