# HG changeset patch # User Steve Losh # Date 1466902904 0 # Node ID cc9b027d5b2a93b720310c4f857d43e729a83f95 # Parent 2d9281a1f7e7fc3d9e53f25e8d23be149fa62673 Initial draft of symbol post diff -r 2d9281a1f7e7 -r cc9b027d5b2a content/blog/2016/06/symbolic-computation.html --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/content/blog/2016/06/symbolic-computation.html Sun Jun 26 01:01:44 2016 +0000 @@ -0,0 +1,852 @@ + {% extends "_post.html" %} + + {% hyde + title: "What the Hell is Symbolic Computation?" + snip: "Symbols, REPLs, and Quoting -- Oh My!" + created: 2016-06-29 13:45:00 + %} + + {% block article %} + +I've been reading a lot of Lisp books lately, some more advanced than others. +All of the introductory books I've seen cover the idea of "Symbolic Computation" +to some extent, but most of them breeze past it pretty quickly with just a few +pages about "symbols" and "quote". + +For most programmers coming from non-Lisp languages, these are new, foreign +concepts that don't really map back to anything in their previous experience. +But the books seem to expect you to understand this things after just a couple +of paragraphs. + +One book that *does* spend more time on this is the appropriately-named [Common +Lisp: A Gentle Introduction to Symbolic Computation][gentle]. If you're looking +for a good introductory Lisp book, that's the one I'd recommend. However, it's +quite a long book and starts at the *very* basics. If you already know the some +Lisp then you might find yourself bored if you go through the entire thing just +for the symbolic computation bits. + +So this post will be an attempt to explain what symbols are, what quoting does, +and why it's all interesting and useful. If you already know what something +like this would print, you'll be bored by this post: + + :::text + (let ((foo ''a)) + (print foo) + (print 'foo) + (print (car foo)) + (print (cdr foo))) + +[gentle]: + +[TOC] + +## Disclaimer + +Before we start, I'll get this warning out of the way: this post is going to +gloss over a lot of gory details to get at the important core ideas. + +When I say "this thing is implemented like so" it's safe to assume that in +reality things are messier and more complicated and will vary between dialects +like Common Lisp, Scheme, and Clojure. My goal is to give you some intuition +for the basic ideas, not to exhaustively cover how a particular implementation +works. + +With that out of the way, let's dive in! + +## The REPL + +The Read-Eval-Print-Loop that so many languages these days have built-in is +a good place to start in our exploration. You're probably familiar with the +idea of a REPL from languages like Python, Ruby, Javascript, etc. In Python it +looks like this: + + :::text + $ python + >>> if True: + ... print "Yes" + ... else: + ... print "No" + ... + Yes + +A handwavey definition of a REPL could be something like this: + +> A REPL is a program that lets you type in code. It runs that code, prints out +> the result, and loops back to the beginning to let you type in more. + +This is a good first start, but to understand symbols we're going to need to get +a much clearer, more precise handle on what exactly each letter in "REPL" means. +We'll start backwards and outside-in with the simplest component. + +## Loop + +The "L" in "REPL" stands for "Loop", and it's the easiest part to understand. +A REPL doesn't just process one bit of code and then exit, it loops forever (or +until you tell it to quit). + +There's not a lot to say here, except that we'll go ahead and lump together the +extra busywork that a REPL needs to do into this step so we can ignore it for +the rest of the post. Things like: + +* Printing the nice prompt at the beginning (`>>>` or `...` in Python). +* Checking for `Ctrl-D` to quit. +* Handling exceptions (so they don't kill the process). + +## Print + +The next letter is "P" for "print". Like loop, this should be familiar +territory, but let's nail down *exactly* what it does. The job of the `print` +function is to: + +* Take as input some kind of object/data structure in memory. +* Produce some series of characters (a string) that represent this object. +* Write those characters somewhere (standard output, a text panel in a GUI, etc). + +For example: if we give the integer `1` to Python's `print`, it produces +a string of two characters (the digit `1` and a newline) and writes it to the +terminal. There are a lot of little details that aren't important here (line +endings, string encoding, where the output actually goes, etc). The important +part that you should fix in your mind is this: + +**`print` takes an object, converts it into a string, and outputs it.** + +Note: I've called `print` a function here, and I'll do the same for `read` and +`eval` later on. This is correct for Common Lisp, but not necessarily for +languages like Python or Javascript. For the purposes of this post you can just +imagine them as functions and realize that in the real world they're more like +"phases" that have a lot more complex machinery under them. + +## Read + +We'll jump over to the other side of the acronym now. "R" is for "read", and +this is where things start to get tricky. + +In most non-Lisp languages the "read" and "eval" phases of the REPL tend to get +blurred together, but if you want to understand symbolic computation in Lisp you +absolutely *must* keep these two parts cleanly separated in your mind. + +We can define `read` as almost the polar opposite of `print`. `read` is +a function whose job is to: + +* Take as input a string of characters from some source. +* "Decode" that string and produce some kind of object in memory. +* Return that object. + +Notice how this mirrors `print`: + +* `print`: Object → Characters +* `read`: Characters → Object + +If we `read` in the string `1.0` (that's three ASCII characters), we'll get some +kind of floating point number object back. + +Sometimes there are many ways to represent the same object in memory. For +example: `read`ing the strings `1.0`, and `1.0000` will (in just about any sane +language) both produce equivalent floating point objects representing the number +"one". + +Side note (if you're not feeling pedantic feel free to skip this): the word +"equivalent" here is a bit tricky. When you `read` two strings like `1.0` and +`1.000` you might get back two pointers to the same hunk of memory, or you might +get back two pointers to two separate hunks of memory, or even just a machine +word representing the floating point number directly. It depends on the +language (or even the implementation). What I mean by "equivalent" is that +there's no way to tell which value came from which input. You can't say "this +hunk of memory must have come from the string `1.000`" because `read` has +"sanitized" the input by that point. + +## The RPL + +So now we've got `read`, `print`, and `loop`. `read` takes characters from +a stream and produces objects, and `print` takes objects and produces characters +and writes them to a stream. What would happen if we just hook them up together +right now? + + :::text + CL-USER> (loop (print (read))) + > 1 + 1 + > 1.0 + 1.0 + > 1.00000 + 1.0 + +I've added a little `>` prompt to the output here to make it clear where I'm +typing. + +Essentially what we've got here is a little pretty-printer! Notice how things +like extra whitespace and useless zeroes got stripped out. This isn't terribly +useful, but at least it's doing something. + +However, it's important to realize where the "prettifying" actually happened. +`read` actually did the hard work! By the time `print` got its grubby little +paws on those floating point one-point-zeroes the extra whitespace and digits +were long gone. Maybe it would be more accurate to give credit where it's due +and call this a "pretty-reader". + +## Reading Other Data + +Up to this point I've been using numbers as examples because they're simple, but +of course we can read and print lots of other kinds of things. Lists and +strings (and lists *of* strings!) are some common examples: + + :::text + CL-USER> (print (read)) + > ("hello" "world") + ("hello" "world") + + $ python + >>> ["hello", "world"] + ['hello', 'world'] + +There are lots of other kinds of data you can read and print, which of course is +highly dependent on the particular language. What's important is the strict +separation of `read` and `print`. + +## Readable Printing + +Before we move on, one thing we should talk about is the idea of "readable +printing". This idea becomes clear almost immediately when you work at the +Python REPL: + + :::text + $ python + >>> "foo\nbar" + 'foo\nbar' + >>> print "foo\nbar" + foo + bar + +Why was the first string printed with quotes and an escaped newline, and the +second without quotes and an actual newline? + +When we defined `print` earlier, one of the steps was: + +* Produce some series of characters (a string) that represent this object. + +But there are often many ways we can represent a particular object as a series +of characters. For example: we can represent the number two as `2`, or `10` in +binary. We can represent a string as the actual characters in it, or we could +represent it "escaped" like Python does in the first line. + +The core idea here is that of "readable printing", or *printing the characters +you would need to give to `read` to produce this object*. + +This is different from what I'll call "aesthetic printing", which is *printing +characters for this object that look nice to a human*. + +In Python these two kinds of printing are seen in the separate [`__str__` and +`__repr__` methods][str_repr]. In Common Lisp it's controlled by the +[`*print-readably*` variable][print-readably]. Other language have different +mechanisms. + +[str_repr]: +[print-readably]: + +## Reading Non-Lisp + +So we know how reading and printing data works, but you can do more than that at +a typical REPL. Let's revisit the first Python example: + + :::text + $ python + >>> if True: + ... print "Yes" + ... else: + ... print "No" + ... + Yes + +We know that `read` takes a series of characters and turns them into an object. +When we `read` this series of characters, what comes out the other end? For +most languages (Python, Ruby, Javascript, Scala, etc) the answer is some kind of +[abstract syntax tree][] represented as a data structure. You might imagine +something like this buried deep within the guts of the Python interpreter: + + :::python + class IfStatement(ASTNode): + def __init__(self, test_node, then_node, else_node): + self.test_node = test_node + self.then_node = then_node + self.else_node = else_node + +The details would surely be a lot hairier in the real world, but the general +idea is that the stream of characters representing your code gets read in and +parsed into some kind of data structure in memory. + +This is all well and good, but our example printed "Yes", which certainly isn't +a representation of an AST node. Where did that come from? To answer that +we'll need the final letter in the acronym. + +[abstract syntax tree]: + +## Evaluating Non-Lisp + +The "E" in REPL stands for "eval". + +This is the last time we'll consider Python in this post, because we're about to +move past it to more powerful ideas. In Python, the purpose of the `eval` phase +of the REPL is to: + +* Take an AST node (or simple data) as input. +* Run the code (also known as *evaluating* it). +* Return the result (if any). + +This is fairly straightforward, at least for our simple `if` statement. Python +will evaluate the `test_node` part of the `if`, and then evaluate one of the +other parts depending on whether the test was truthy or falsey. + +Of course the actual process of evaluating real-life Python code is much more +complicated than I've glossed over here, but this is good enough for us to use +as a springboard to dive into the beautiful world of Lisp. + +## Reading Lisp + +When we talked about reading in the Python `if` statement I said that Python +would read/parse it into some kind of data structure representing an AST node. +I didn't point you at the *actual* data structure in the Python source code +because I have no idea where it actually *is*, and it's probably not nearly as +simple as the one I sketched out. + +Now that we're talking about Lisp, however, I really *can* show you exactly what +an `if` statement in Lisp reads as! I'll use `read-from-string` to make it +a bit easier to see what's input and what's output, but it would work the same +way with just plain old `read` and input from standard in. Here we go: + + :::text + CL-USER> (print (read-from-string "(if t (print 1) (print 2))")) + + (IF T (PRINT 1) (PRINT 2)) + + CL-USER> (type-of (read-from-string "(if t (print 1) (print 2))")) + + CONS + +Instead of some kind of AST node data structure buried deep within the heart of +our implementation we get... a list! An ordinary, garden-variety, vanilla list +made of good old trusty cons cells! + +The list we get contains four elements, two of which are themselves lists. But +what do these lists actually *contain*? + +The numbers are simple enough -- we saw them earlier. `read` turns a series of +digits into a number somewhere in memory, and `print` spits out a series of +characters that represent the number: + + :::text + CL-USER> (type-of (read-from-string "100")) + + (INTEGER 0 4611686018427387903) + +The string `100` does indeed represent an integer between zero and four +squillion-something. + +But what are the other things in our `if` statement's list? The `if` and `t` +and `print`? Are they some magic keywords internal to the guts of our Lisp that +`print` is just outputting nicely for our benefit? + + :::text + CL-USER> (type-of (read-from-string "if")) + + SYMBOL + +Buckle up -- it's time to learn about symbols. + +## Symbols + +A symbol in Lisp is [a pretty basic data structure][clhs-symbol] that turns out +to be *extremely* useful. You can imagine it to be defined something like this: + + :::text + (defstruct symbol + name + function + value + property-list + package) + +The `name` of a symbol is a string of characters representing the symbol's name: + + :::text + CL-USER> (type-of (read-from-string "if")) + + SYMBOL + + CL-USER> (symbol-name (read-from-string "if")) + + "IF" + +Symbols get created (usually) when they are `read` for the first time. If you +`read` a sequence of characters that matches the name of an existing symbol +(let's ignore the lowercase/uppercase thing for now), `read` just returns that +existing symbol: + + :::text + CL-USER> (eq (read-from-string "cats") (read-from-string "cats")) + + T + +Here `read` saw the string `cats` and created a new symbol somewhere in memory +with `CATS` as its `name`. The second call to `read-from-string` read in the +string `cats`, saw an existing symbol with the matching name, and just returned +it straight away. That's why `eq` returned true -- the two `read` calls +returned pointers to the exact same hunk of memory. + +(`read` also "interned" the symbol into the current package. We're going to +ignore the package system for this post -- it's not important to the core +topic. We'll also ignore the property list.) + +So to recap: + +* `read` is a function that takes characters and turns them into objects. +* When you feed `read` certain strings of characters (i.e. without special + characters), it returns a symbol object whose name matches those characters + (creating it if necessary). +* Symbols are just normal Lisp data structures with a few specific fields. + +So what does `print` do with a symbol? It just prints the `name`! + + :::text + CL-USER> (print (read-from-string "cats")) + + CATS + +Simple enough. Note that this is *readably printed* -- if we feed it back to +`read` we'll get an equivalent symbol back (the *exact same* symbol, in fact). + +But wait! If we `read` symbols in and they're just normal vanilla structures, +then how do we actually *do* anything in Lisp? How does anything actually +*run*? + +[clhs-symbol]: + +## Evaluating Lisp + +Now we need to go back to `eval`. In the Python example I handwaved a bit and +said that `eval` "ran the code" but didn't really explain how that happened. +Now that we're in the warm embrace of Lisp we can nail things down a lot more +cleanly. + +`eval` (in Lisp) is a function whose job is to: + +* Take an object. +* Do something useful with it to get another object. +* Return the resulting object. + +I know, I know, that seems as clear as a brick. But if we can actually define +what "something useful" means, it will be a lot more helpful. Lisp's `eval` +follows a few simple rules to produce its output. + +### Strings and Numbers + +First of all, `eval` will just pass numbers and strings straight through without +touching them at all: + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ; ... + (t (error "What the hell is this?")))) + +This makes sense because there's not a lot more useful stuff you can do with +a number or a string on its own. I suppose you could write a language where the +evaluation phase ran all numbers through the absolute value function because you +wanted to remove all negativity from programming or something, but that seems +a bit esoteric. + +### Basic Lists + +What about lists, like our friend the `if` statement (a list of four things)? +Well the first thing anyone learns about Lisp is the funny syntax. In most +cases, when passed a list `eval` treats the first element as the name of +a function, and the rest as the arguments. It will evaluate the arguments and +call the function with them: + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ((typep thing 'list) + (destructuring-bind (head . arguments) + (apply (symbol-function head) + (mapcar #'eval arguments)))) + ; ... + (t (error "What the hell is this?")))) + +At this point we know enough to understand exactly what happens when we say +something like `(+ 1 2)` at a Lisp REPL! + +* Lisp `read`s the seven characters we gave it, which becomes a list of three + objects: the symbol `+`, the integer `1`, and the integer `2`. +* Lisp passes that three-object list to `eval`. +* `eval` looks up what is in the `function` slot of the symbol at the front of + the list (that symbol is `+`). +* The symbol `+` was helpfully given a function by the Lisp implementation (run + `(symbol-function (read-from-string "+"))` to confirm that I'm not lying to + you). +* Lisp evaluates each item in the rest of the list. In this case they're each + a number, so each one evaluates to itself. +* Lisp calls the function with the evaluated arguments to get a result (in this + case: the integer `3`). +* Lisp passes the result to `print`, which turns it into a string of characters + (one character, in this case) and prints it to standard out. + +Whew! That seems like a lot, but each piece is pretty small. Go slowly through +it and make sure you *really* understand each step in the preceding list before +you move on. + +If you don't believe me that this is really how it works, try this: + + :::text + CL-USER> (setf (symbol-function (read-from-string "square")) + (lambda (x) (* x x))) + + # + + CL-USER> (square 4) + + 16 + +We just set the `function` slot of the symbol `square` to be a function that +squares its argument. We can then run it just like any other function. + +### Variables + +What about symbols that *aren't* at the front of a list? For example: + + :::text + CL-USER> (defvar ten 10) + + 10 + + CL-USER> (square ten) + + 100 + +In this case, everything proceeds as it did before until the recursive call to +`eval` the argument to `square`. The argument is just a bare symbol (not +a number or a list or a string), so we need another rule in our `eval` function: + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ((symbolp thing) (symbol-value thing)) + ((listp thing) + (destructuring-bind (head . arguments) + (apply (symbol-function head) + (mapcar #'eval arguments)))) + ; ... + (t (error "What the hell is this?")))) + +If `eval` sees a symbol on its own, it will just return whatever is in the +`value` slot of the symbol data structure. Simple enough! + +### Special Forms +If course there are a few things we haven't talked about yet. First of all, +there are some "magic" symbols that aren't functions, but are hardcoded into the +evaluation function to do certain things. In Common Lisp they're called +["special operators"][special-operators] and there are twenty-five of them. + +Let's add a special rule to our `eval` function to handle one of them (our old +friend `if`): + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ((symbolp thing) (symbol-value thing)) + ((listp thing) + (destructuring-bind (head . arguments) thing + (cond + ((eq head (read-from-string "if")) ; NEW + (destructuring-bind (test then else) arguments + (if (eval test) + (eval then) + (eval else)))) + (t + (apply (symbol-function head) + (mapcar #'eval arguments)))))) + ; ... + (t (error "What the hell is this?")))) + +At this point your head might be starting to hurt. How have we just used `if` +to define itself? Is anything here actually *real*, or is Lisp just a serpent +eating its own tail forever? + +### An Ouroborromean Paradox + +If the "metacircularity" (god, I hate that word) of what we've just done bothers +you, remember that this `eval` function here is just a sample of how you *can* +write it in Lisp. You could also write it in some other language, like C or +Java (see: [ABCL][]) or really anything. That would let you "bottom out" to +something that's not Lisp. + +But really, is that any *less* circular? You still need *some* language to run +the thing! Why does an `eval` written in C seem less "cheaty" than one written +in Lisp? Because it compiles to machine code? Try +`(disassemble #'sb-impl::simple-eval-in-lexenv)` in SBCL and you'll get a few +thousand bytes of x86 assembly that was [originally some Lisp code much like +ours][sbcl-eval]. + +My advice is to just let it flow over you, even if you feel a bit uneasy at the +sight of something like this. Eventually as you become more at home in your +chosen Lisp, writing high-level code one moment and `disassemble`ing a function +the next, you'll make peace with the serpent. + +### Exercises + +There are quite a few things in `eval` that we haven't covered here, like the +other twenty-four special operators, lexical variables, lambda forms, and more. +But this should be enough for you to wrap your head around symbols and how +they're used in Lisp. + +Before we move on to the final part of this story, make sure you can figure out +the answers to these questions: + +1. What does the single character `1` read as? What does it evaluate to? +2. What do the characters `"hello\"world"` read as? What do they evaluate to? + How would the result be printed readably? How would the result be printed + aesthetically? +3. What do the characters `(list (+ 1 2) ten)` read as? What does it evaluate + to? How does each step of the evaluation work? Trace out each of the calls + to `eval` on paper, with their arguments and their results. What does the + final result print as? +4. Use `symbol-function` to see what's in the function slot of the symbol `car`. + How does your Lisp print that thing? +5. Try to look up the function slot of a symbol without a function. What + happens? +4. Use `symbol-function` to see what's in the function slot of the symbol `if`. + What happens? Does that seem right? If so, why? +5. Go to the [HyperSpec page for `symbol`][clhs-symbol] and search for + "the consequences are undefined if". Try all of those things and find out + what interesting things break. + +If you're not using Common Lisp, port these exercises to your language. + +[special-operators]: +[ABCL]: +[sbcl-eval]: +[clhs-symbol]: + +## Quote + +Up to now we've been using the clumsy `(read-from-string "foo")` form to get +ahold of symbols, but there's an easier way called "quoting". + +Quoting often confuses new Lisp programmers, and they'll end up randomly +adding/removing quotes to something until it appears to do what they want. Now +that you've got `read`, `eval`, and `print` firmly separated in your mind, +`quote` will be much easier to understand. + +### The Special Operator + +Quoting actually has two distinct components: one that affects `read` and one +that affects `eval`. In most books the distinction between these two only gets +barely a sentence or two, which is probably why beginners are so confused. +Let's look at the `eval` side of things first. + +`quote` is one of the twenty-five special operators. All it does it pass its +(single) argument back from `eval` *untouched*. Normally the argument itself +would have been evaluated, but `quote` prevents that: + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ((symbolp thing) (symbol-value thing)) + ((listp thing) + (destructuring-bind (head . arguments) thing + (cond + ((eq head (read-from-string "if")) + (destructuring-bind (test then else) arguments + (if (eval test) + (eval then) + (eval else)))) + ((eq head (read-from-string "quote")) ; NEW + (first arguments)) + (t + (apply (symbol-function head) + (mapcar #'eval arguments)))))) + ; ... + (t (error "What the hell is this?")))) + +I know that seems strange, but let's look at it in action: + + :::text + CL-USER> (+ 1 2) + + 3 + + CL-USER> (quote (+ 1 2)) + + (+ 1 2) + +Our first example is the same one we used in the previous section: + +* `read` takes in seven characters and returns a list of three items: the symbol + `+` and two numbers. +* `eval` gets the three-element list, looks up the function for the symbol `+`, + recursively evaluates the arguments (which evaluate to themselves), and + applies the function. +* `print` gets the integer `3`, turns it into ASCII, and writes it to the + terminal. + +The second example uses `quote`: + +* `read` takes in fifteen characters and returns a list of two items: the symbol + `quote` and a list of three items (the symbol `+` and two numbers). +* `eval` gets the three element list and notices that the first element is the + special operator `quote`. It simply returns the second element in the list + untouched, which in this case is a list of three items. +* `print` gets that three element list, turns it into seven characters, and + writes it to the terminal. + +Just for fun, let's ride the serpent and use `quote` in the definition of +itself inside `eval` to clean things up a bit: + + :::lisp + (defun eval (thing) + (cond + ((numberp thing) thing) + ((stringp thing) thing) + ((symbolp thing) (symbol-value thing)) + ((listp thing) + (destructuring-bind (head . arguments) thing + (cond + ((eq head (quote if)) + (destructuring-bind (test then else) arguments + (if (eval test) + (eval then) + (eval else)))) + ((eq head (quote quote)) ; WHAT IN THE + (first arguments)) + (t + (apply (symbol-function head) + (mapcar #'eval arguments)))))) + ; ... + (t (error "What the hell is this?")))) + +That `(quote quote)` looks just completely bonkers, right? Step through it +piece by piece to figure it out: + +* What do the five characters `quote` read as? What do they evaluate to? +* What do the thirteen (spooky!) characters `(quote quote)` read as? When + `eval` gets its hands on that, what clause in the `cond` does it hit? What + does that return? + +Try these in a Lisp REPL if you're not 100% sure of the answers. The functions +`read-from-string`, `eval`, and `type-of` will come in handy. + +### The Read Macro + +Now let's look at the final piece of the puzzle. `'` (that's a single ASCII +quote character) is a [read macro][]. Don't worry if you don't know exactly +what that means right now. The important part is that when `read` sees a quote +character, it returns a two-element list containing the symbol `quote` and the +next form, which is read normally. + +The four characters `'foo` go into `read` and come out as a two-element list +containing: the symbol `quote` and the symbol `foo`. Again, because it's +important, this happens *at read time*. By the time `eval` sees anything, it's +already been turned into that two-element list. + +It can be a bit slippery to get a grip on this, because `print` will "helpfully" +print a list of `(quote whatever)` as `'whatever`! But we can use trusty old +`car` and `cdr` to see what's really going on: + + :::lisp + CL-USER> (read-from-string "'foo") + + 'FOO + + CL-USER> (type-of (read-from-string "'foo")) + + CONS + + CL-USER> (car (read-from-string "'foo")) + + QUOTE + + CL-USER> (cdr (read-from-string "'foo")) + + (FOO) + +That's really all there is to it: `'form` is returned by `read` as `(quote +form)`. Note that `form` doesn't have to be a symbol: + +* `'(1 2 (4 5))` reads as `(quote (1 2 (4 5)))` +* `'150` reads as `(quote 150)` +* `'"hello"` reads as `(quote "hello")` +* `'(if if if if)` reads as `(quote (if if if if))` + +[read macro]: + +### Exercises + +That's just about all there is to `quote`. Once you've cleanly separate `read`, +`eval`, and `print` in your mind it becomes a lot less mystical (or perhaps +*more*, depending on your point of view). + +If you want to twist your brain just a bit more, try these exercises: + +1. What do the characters `foo` read in as? What do they evaluate to? How does it print? +2. What do the characters `'foo` read in as? What do they evaluate to? How does it print? +3. What do the characters `''foo` read in as? What do they evaluate to? How does it print? +4. What do the characters `'1.0` read in as? What do they evaluate to? How does it print? +5. What do the characters `'(1 2 3)` read in as? How many elements are in the list? What does it evaluate to? How many elements are in *that* list? +6. Update the `eval` function to use the `'` read macro instead of `quote`. +7. Certain symbols like `t` and `nil` are special -- they evaluate to themselves much like numbers or strings. Add this to `eval`. +8. What do the characters `nil` read in as? What is the type of that object? What do they evaluate to? What type is that result? +9. What do the characters `'nil` read in as? What is the type of that object? What do they evaluate to? What type is that result? +10. What do the characters `''nil` read in as? What is the type of that object? What do they evaluate to? What type is that result? + +## A Quick Recap + +This post has gotten quite a bit longer than I intended. Here are the main +things I hope you've gotten from it: + +* `read`, `eval`, and `print` are three separate, distinct functions/phases in + the interpretation of Lisp (and really *all* (okay, *most*)) code. +* Keeping these three phases clearly separated in your mind will make it easier + to understand symbols and quoting in Lisp. +* Symbols are nothing magic, they're just a particular data structure with + a couple of fields. +* The important thing is how `read` and `eval` *treat* symbols. That's where + the magic happens. +* `quote` is just a "short-circuit" in `eval` that turns out to be really + useful. +* `'` is just a lazier way of writing `(quote ...)`. + +## Where to Go From Here + +Now that you've got a firmer grasp on what the hell symbols actually *are*, +there are a lot of cool things you might want to check out. + +* Reread some of your introductory Lisp books again, seeing if things seem to + make a bit more sense now. +* Read about backquote/quasiquote. How does it compare to the `quote` we + explored here? +* Read [Paradigms of Artificial Intelligence Programming][PAIP] and pay + attention to how Norvig uses symbols for various tasks. Pay attention to what + he says about property lists, because we skipped them here. +* Read the [guide to the Common Lisp package system][packaging] to learn all the + stuff I left out about the Common Lisp package system. +* Gaze upon [this macro][symbolicate] in wonder (or horror). +* Read the HyperSpec pages for things like `symbol` and `quote`. +* Find and read your Lisp implementation's `eval` function. +* Find and read *another* Lisp implementation's `eval` function. +* Watch the [SICP Lectures][SICP] on YouTube. + +[PAIP]: +[symbolicate]: +[packaging]: +[SICP]: + + {% endblock article %}