368K views · May 24, 2017 · 1:31:06 · 11 HN recommenders · 17 mentions · discussed 2017–2026
William Byrd presents at Papers We Love NYC on what he calls the most beautiful program ever written, a Lisp interpreter written in Lisp. He walks through the metacircular interpreter and related ideas, and demos relational programming and program synthesis near the end.
Why Hacker News points people here: HN repeatedly recommends it as an amazing talk that derives the essence of Lisp and shows miniKanren-style program synthesis.
“I can't recommend the talk Dr Byrd did on this enough”HN comment, 2021
“There's an amazing talk about it”
Amazing talk deriving a Lisp interpreter.
(define eval-expr (lambda (expr env) (pmatch expr [`,x (guard (symbol? x)) (env x)] [`(lambda (,x) ,body) (lambda (arg) (eval-expr body (lambda (y) (if (eq? x y) arg (env y)))))] [`(,rator ,rand) ((eval-expr rator env) (eval-expr rand env))]))) There's an amazing talk about it: this video
“It is fascinating to think of it as the essence of a language in 13 lines.”
Derives Lisp's essence in 13 lines.
If you haven't watched it - check out William Byrd on "The Most Beautiful Program Ever Written" this video It's the above and deriving it. It is fascinating to think of it as the essence of a language in 13 lines.
“One of my all time favorite YouTube videos is a lecture by William Byrd.”
Fascinating lecture the commenter keeps returning to.
One of my all time favorite YouTube videos is a lecture by William Byrd. I find myself still coming back to this video, it was so fascinating to me as an undergrad. this video
“I can't recommend the talk Dr Byrd did on this enough”
Byrd talk on Lisp-in-Lisp program.
I can't recommend the talk Dr Byrd did on this enough: this video It's one of my favorite programs to play around with. I wrote about an Erlang implementation of this a short while back: link
“It (Barliman) is demoed near the end of this video”
Demo of Barliman program synthesis editor near the end.
William Byrd's work in program synthesis is an interesting take on this, where an IDE can, guided by test cases written for a function, actually auto-complete code itself whilst writing the function, or tell the programmer when they have something wrong by violating a test case. Of course it is impractical right now, but a good step nonetheless.. It (Barliman) is demoed near the end of this video: this video
Lisp interpreter built from linked-list structures.
Well, I think lisper nailed it in the article: It's not just that the code is represented as data structured in linked-lists, it's that that data exposes the semantic structure of the code in ways that are more pragmatically useful (among other nice properties) than char strings. When you get into the LISP interpreter itself, which is just a linked-list structure describing how to process linked-list structures (like itself) as code, well... Here's William Byrd on "The Most Beautiful Program Ever Written" (ye LISP interpreter) this video
“More tangential but also cool: this talk[1] by William Byrd”
Byrd talk on reflective towers and relational programming demo.
If you're interested in the work that led to this, definitely check out Kenichi Asai's reflective languages. The code for his Black language with reflective semantics is reproduced here: [0] More tangential but also cool: this talk[1] by William Byrd mentions reflective towers, but jumps into a discussion of what he terms "relational programming". It's a demo of his Barliman Smart editor system: [2] [0] link [1] this video [2] link
“I watched a fascinating presentation”
Fascinating presentation showing lambda becoming a lambda symbol while typing.
I watched a fascinating presentation and when I saw the speaker typing (lambda ...) and having it change to (λ ...) and not having to deal with parens.. I was jealous. Does emacs do this? EDIT: the presentation: William Byrd on "The Most Beautiful Program Ever Written" this video
“people tell me it's good”
Popular description of astonishing miniKanren results, though unwatched by commenter.
As for what miniKanren is, there are a couple of books (one being Byrd's dissertation) and a lot of papers. I think maybe the best summary I've read is actually the interview transcript at link . But also, there's a summary on link , with links to the papers and talks, and an older summary on link . Most of these are a bit hard to understand the significance of if you aren't already familiar with logic programming. The talk on this video is a popular description of one of the most astonishing results; I haven't watched it but people tell me it's good. As for understanding academia, yeah, I don't know.
“skip to 1h mark to see some examples”
Examples of rule-based programming and query languages.
Equational reasoning makes TDD and property based testing trivial (encode rules by examples, base cases and corner cases, which is the most natural way for humans to think); rule-based system are easier to extend and correct by design (bounded set of possible states); provides more powerful and elegant query languages (E.g. Datalog). See this video (skip to 1h mark to see some examples)
“It’s exploiting logic programming to query for a program that satisfies some condition.”
Demo of querying for programs satisfying a condition.
Watch this (skip to 1:17:28 to see a quick demo, the rest of the video is the explanation): this video It’s exploiting logic programming to query for a program that satisfies some condition.
“understanding lambda calculus is much easier for the uninitiated after watching that video.”
Quick overview of Lisp then implementing Lisp in Lisp.
It's easy to miss since it's a small link near the top of the post, but something that will help a lot in understanding this post is this video: The most beautiful program: this video It essentially gives you a quick 5-min overview of the lisp language, then shows you how to implement lisp in lisp with only a few lines of code. IMO, understanding lambda calculus is much easier for the uninitiated after watching that video.
That is "The Most Beautiful Program Ever Written" - issue. Because I am stupid, I have to think very hard. Are we defining a language using the language itself or what? this video
Source of commenter's first exposure to program synthesis demo.
First heard about program synthesis myself thanks to William Byrd's demo at the end of "The Most Beautiful Program[...]", this video @ 1:17:15
“I associate program synthesis pretty heavily with William Byrd following his demo in the second half of this talk”
Program synthesis demo in second half of talk.
I associate program synthesis pretty heavily with William Byrd following his demo in the second half of this talk: this video
Mentioned as example of studying evaluation strategies and continuations.
While I (think) understand the sentiment (ergonomics and practicality), it is still worth studying Lisp for a number of reasons. In particular, I would recommend to everyone to study Lisp 1.5 [1] to appreciate how an entire universe of programming languages can be bootstrapped with just a few primitives and equations. It is true that, today, we have a vast array of impressive tools at our disposal, from parser combinators and generators, code generators to entire language workbenches with projectional editing capabilities. However, if one were to design a language for any reason, having a deep understanding of the expressiveness of computational models such as the lambda calculus would certainly be an "advantage" (especially for those who end up having to use the language): A Lisp/Scheme is as close to interactive lambda calculus as it gets. From there on, one can learn about implementing different evaluation strategies, scoping rules and continuations (William Byrd's "The Most Beautiful Program Ever Written" [2] also to mind). Now, I am not sure whether homoiconicity tends to lead people astray. It is true that is it not strictly necessary to make a language extensible (e.g., Smalltalk has no macros and is very extensible due to its powerful meta-object protocol and an elegant syntax for closures), but it's still worth studying the concept. For example, writing a metaintpreter in Prolog [3] is surprisingly easy because of its homoiconicity. [1] link [2] this video [3] link
“Most beautiful program ever" is short but the associated yapping takes almost 2 hours.”
Never seen Lisp-in-Lisp without additional (and boring) yapping. Just CAR, CDR and CONS. And assign and type-test and COND. It would probably be about 300 lines. "Most beautiful program ever" is short but the associated yapping takes almost 2 hours. this video
