The Most Beautiful Program Ever Written

If you’re a lisper and enjoy Scheme, you may like William Byrd’s video on The Most Beautiful Program Ever Written. Unless you’ve been immersed in the Lisp culture, it’s probably not what you think. According to Byrd, the most beautiful program is just 5 lines of code implementing a metacircular interpreter for Scheme. He has, he says, spent the last 13 years or so trying to understand the implications of those 5 lines.

His presentation starts off with a short introduction to Scheme and then moves immediately to writing a function (in Scheme) that can interpret Scheme expressions. He builds on a simple implementation and eventually pares it down to 5 lines.

His real interest, though, is using the ideas in the metacircular interpreter to do logic programming. The second half of the video is about a program that does program synthesis. You can specify some or even none of a program and what output you want and the program will compute Scheme expressions to give you the results. It’s sort of like Wilfred Hughes’ suggest.el for Emacs but much more sophisticated.

The video is just over and hour and a half so you will definitely need to schedule time. If you have only a casual interest in Lisp the hour and a half may be more time then you want to spend but the talk is interesting and self contained. You needn’t worry about not having enough background.

This entry was posted in General and tagged , . Bookmark the permalink.
  • NoonianAtall

    Thanks for sharing, very interesting. Very cool that Emacs has its own little version of Barliman in suggest.el. The rabbit hole is deep!

  • What are the five lines?

    • NoonianAtall

      He talked a lot about putting 5 lines on a 3x5 card, but he didn't seem to actually focus on 5 lines by themselves. What he showed was a way to write a little lexically scoped, environment-passing interpreter in a few lines, which was more like 7-12 altogether. At least, that's as well as I can explain it. :)