The Most Important Idea in Computer Science

Summary: Computer Science has ideas that are important to the broader world. The most important is the Universal Turing Machine. From one perspective, Lisp embodies the idea at its core. To really understand how, I ask you to implement your own Lisp interpreter.

The most important^1^ idea in Computer Science is the idea of the Universal Turing Machine. There are all these different types of computation, which can be ordered by their power. For instance, finite state machines can't count arbitrarily high, but stack machines can. And way at the top of the list, the most powerful, is the Turing Machine.

The Turing Machine is curious because, according to the Church-Turing Thesis, what it can compute is the definition of computability. Practically, this means that all languages are equivalently powerful in the computability sense. PHP, JavaScript, Java, C, machine code. They're all Turing-complete, meaning they're sitting on the same top rung of that hierarchy of computing power.

So not only is the Turing Machine up at the top (and we believe that nothing can be higher), the Turing Machine is also curious for another very important reason: it can compute itself. You can program a Turing Machine to act like a Turing Machine. Put another way, on Turing Machine hardware, you can write a Turing Machine in software. And, of course, that software Turing Machine can run another software Turing Machine, ad infinitum.

We take this property for granted every day. Our computers are Turing Machines. They leave the factory complete, never to be changed. And we buy them, completely confident that we can run Turing-complete software on them. We don't need specialized hardware for each problem we want to solve. We can solve it in software. And what about virtualization? We run a virtual machine (software) that emulates a machine (hardware) to run more software. That's all thanks to the idea of the Universal Turing Machine.

All general-purpose languages are Turing-complete. It doesn't take that much to be Turing-complete. But there's something that most languages don't address that Lisp does. You can break up Turing-completeness into two parts: one is that it can compute any computable function. All general-purpose languages do that. The second thing is that they can emulate themselves and all other languages. Most languages don't even try that part.

Just to be clear, not doing the second thing does not affect where it sits on the hierarchy. It's still at the top. Not doing the second one merely omits the meatiest idea in Computer Science.

Lisp was first defined in itself^2^. From day one, it could emulate itself. And it was also a demonstration of how you could emulate other semantics. Lisp embodies the coolest idea that Computer Science has brought to the world.

Yes, you can write a JavaScript interpreter in JavaScript. But it's not at the core. It's not part of the JavaScript ethos. It's right there at the center in Lisp. It's actually really easy. And there's a rite of passage that Lisp programmers go through: write your own Lisp.

So let's do that! Let's write a Lisp interpreter in Clojure. It's actually a small Lisp, because, well, Lisps are big and this is just an exercise. But you could continue past this small language if you like.

Specification

Write a function my-eval that takes an environment (all the variables defined) and an expression (some code). my-eval should evaluate the code.

my-eval (and js/window js/window.cljs js/window.cljs.user (js-delete js/window.cljs.user "my_eval"))

;; This is a live editor. Make changes to turn the tests above green.
(defn my-eval [env exp])

nil evals to nil

(my-eval nil) nil

numbers eval to themselves

(my-eval 1) 1

strings eval to themselves

(my-eval "hello") "hello"

symbols eval to their value in the environment

(my-eval 'x) 10

symbols eval to their value in the environment

(my-eval 'x) "yo!"

symbols eval to their value in nil

(my-eval 'x) nil

functions evaluate to themselves

(my-eval +) +

functions evaluate to themselves

(my-eval *) *

if statements with nil test eval else

(my-eval '(if nil 0 1)) 1

if statements with non-nil test eval then

(my-eval '(if test x y)) 0

empty do statement evals to nil

(my-eval '(do)) nil

one-expression do evals to expression

(my-eval '(do 1)) 1

multi-expression do evals to last expression

(my-eval '(do 1 2 3 4)) 4

let statements add to environment

(my-eval '(let [x 1] x)) 1

function application

evals the args, then applies function to evaled args (use map and apply)

(my-eval '(+ 1 1)) 2

function application

evals the args, then applies function to evaled args (use map and apply)

(my-eval '(/ 20 4)) 5

ensure we're calling my-eval recursively

(my-eval '(do (+ 1 2))) 3

ensure we're calling my-eval recursively

(my-eval '(+ (+ 1 10) 2)) 13

do expressions evaluate all forms

(my-eval '(do (reset! a 10) (+ (deref a) 75))) 85

Conclusions

I really like the idea of the Universal Turing Machine. It makes my mind spin with recursive infinities. And I see it in our everyday lives. And it's right there at the heart of Lisp. Lispers write interpreters all the time. It's just another layer of emulation.

If you'd like to experience this idea firsthand, you may want to learn Clojure with LispCast Introduction to Clojure. It starts at the very beginning and goes deep into this idea of interpretation that's at the heart of Lisp. It uses exercises, animations, screenscasts, and metaphor to guide you through everything you need to know to get to that deep experience.

1. [According to me.]
2. [Recursive Functions of Symbolic Expressions and Their Computation by Machine.]