Skip to content
Hallway
0:00 / 0:00

#metacircularinterpreter#lisp#scheme

William Byrd on "The Most Beautiful Program Ever Written" [PWL NYC]

PapersWeLove

23K subscribers • 33 videos on Hallway • Community channel

YouTube
  • Recommended by 14 people: 11 on Hacker News, 1 on Lobsters, 1 in engineering communities and 1 curated list.
  • A classic. People kept recommending it from 2017 to 2025.
  • Presented by William E. Byrd

Intermediate. Assumes working knowledge.

367K views9 years ago14 recommendations

Programming languagesComputer scienceLisp and ClojureFunctional programmingLanguage design and type systems

William Byrd explores the metacircular Lisp interpreter, relational programming, and demos the Barliman program synthesis tool.

Meetup: bit.ly/2okyAH3 Audio: bit.ly/2qkAczZ Sponsored and hosted by Two Sigma (@twosigma) and Chartbeat (@Chartbeat) Description ------------------ William E. Byrd "explores what he considers to be the most beautiful program ever written---a Lisp interpreter written in Lisp---and a few of the many amazing ideas related to this metacircular interpreter." References - The Little Schemer by Daniel P. Friedman and Matthias Felleisen - Essentials of Programming Languages by Daniel P. Friedman and Mitchell Wand - John McCarthy's Recursive functions of symbolic expressions and their computation by machine, Part I - LISP 1.5 Programmer's Manual by John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin (see especially page 13!) - John McCarthy's A micro-manual for LISP - not the whole truth - "Maxwell's equations of software" examined by Ken Shirriff - Lisp as the Maxwell’s equations of software by Michael Nielsen - miniKanren, live and untagged: quine generation via relational interpreters (programming pearl) by William E. Byrd, Eric Holk, and Daniel P. Friedman - The Reflective Language Black by Asai, Kenichi - Programming Should Eat Itself by Nada Amin, Strange Loop, 2014 Bio ----- William E. Byrd (@webyrd) is a Research Assistant Professor in the School of Computing at the University of Utah. He is co-author of 'The Reasoned Schemer', and is co-designer of the miniKanren relational programming language. He loves StarCraft (BW & SC2). Ask him about the scanning tunneling microscope (STM) he is building.

Why it's here

14 people recommend this, 1 disputes it

What people say. Highly recommended as a fascinating and mind-expanding lecture on Lisp, metacircular interpreters, and relational programming.

u/fminutesin r/ProgrammingLanguages • Recommends

Do you know any interesting talks about PL design/compilers/interpreters? Hi folks! Let’s share your favorite talks about whatever related to designing and creating programming languages! I’ll start first: William Byrd on “The most beautiful programm ever written” - link to this video EDIT: putted title to the talk
74View on Reddit

hashemion Lobsters • Recommends

William Byrd on "The Most Beautiful Program Ever Written"
12View on Lobsters

labriaon Hacker News • Recommends

On “Ask HN: What is the most beautiful piece of code you've ever read?”

(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: link to this video
View on Hacker News

BoiledCabbageon Hacker News • Recommends

On “A Conversation with Alan Kay (2004)”

If you haven't watched it - check out William Byrd on "The Most Beautiful Program Ever Written" link to 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.
View on Hacker News

uptherootson Hacker News • Recommends

On “William Byrd on logic and relational programming, miniKanren (2014)”

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. link to this video
View on Hacker News

hazboon Hacker News • Recommends

On “A Lisp interpreter written in Lisp (2017)”

I can't recommend the talk Dr Byrd did on this enough: link to 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
View on Hacker News

programming-talkscurated list on GitHubRecommends

Under “Lisp”

The Most Beautiful Program Ever Written 01:31:05 by **William Byrd** (2017)
View the list

geogriffinon Hacker News • Recommends

On “Near Future of Programming Languages [pdf]”

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: link to this video
View on Hacker News

carapaceon Hacker News • Recommends

On “Yes, code is data, but that's not what makes Lisp cool”

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) link to this video
View on Hacker News

eindiranon Hacker News • Recommends

On “Collapsing Towers of Interpreters (2018) [pdf]”

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 talk1 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 link to this video 2 link
View on Hacker News

m463on Hacker News • Recommends

On “The Evolution of Lisp (1993) [pdf]”

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" link to this video
View on Hacker News

kragenon Hacker News • Recommends

On “The Fifth Generation Computing Project”

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 link to 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.
View on Hacker News

hcarvalhoalveson Hacker News • Recommends

On “Ask HN: Production Prolog in 2020?”

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 link to this video (skip to 1h mark to see some examples)
View on Hacker News

hcarvalhoalveson Hacker News • Recommends

On “Programming breakthroughs we need”

Watch this (skip to 1:17:28 to see a quick demo, the rest of the video is the explanation): link to this video It’s exploiting logic programming to query for a program that satisfies some condition.
View on Hacker News

spartanatreyuon Hacker News • Recommends

On “Toying with the Lambda Calculus”

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: link to 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.
View on Hacker News

timonokoon Hacker News • Disputes

On “The Evolution of Lisp (1993) [pdf]”

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. link to this video
View on Hacker News