1 # The Make-A-Lisp Process
3 So you want to write a Lisp interpreter? Welcome!
5 The goal of the Make-A-Lisp project is to make it easy to write your
6 own Lisp interpreter without sacrificing those many "Aha!" moments
7 that come from ascending the McCarthy mountain. When you reach the peak
8 of this particular mountain, you will have an interpreter for the mal
9 Lisp language that is powerful enough to be self-hosting, meaning it
10 will be able to run a mal interpreter written in mal itself.
12 So jump right in (er ... start the climb)!
16 You might already have a language in mind that you want to use.
17 Technically speaking, mal can be implemented in any sufficiently
18 complete programming language (i.e. Turing complete), however, there are a few
19 language features that can make the task MUCH easier. Here are some of
20 them in rough order of importance:
22 * A sequential compound data structure (e.g. arrays, lists,
24 * An associative compound data structure (e.g. a dictionary,
25 hash-map, associative array, etc)
26 * Function references (first class functions, function pointers,
28 * Real exception handling (try/catch, raise, throw, etc)
29 * Variable argument functions (variadic, var args, splats, apply, etc)
31 * PCRE regular expressions
33 In addition, the following will make your task especially easy:
35 * Dynamic typing / boxed types (specifically, the ability to store
36 different data types in the sequential and associative structures
37 and the language keeps track of the type for you)
38 * Compound data types support arbitrary runtime "hidden" data
39 (metadata, metatables, dynamic fields attributes)
41 Here are some examples of languages that have all of the above
42 features: JavaScript, Ruby, Python, Lua, R, Clojure.
44 Many of the most popular languages already have Mal implementations.
45 However, this should not discourage you from creating your own
46 implementation in a language that already has one. However, if you go
47 this route, I suggest you avoid referring to the existing
48 implementations (i.e. "cheating") to maximize your learning experience
49 instead of just borrowing mine. On the other hand, if your goal is to
50 add new implementations to mal as efficiently as possible, then you
51 SHOULD find the most similar target language implementation and refer
54 If you want a fairly long list of programming languages with an
55 approximate measure of popularity, try the [Programming Language
56 Popularity Chart](http://langpop.corger.nl/)
61 * Install your chosen language interpreter/compiler, language package
62 manager and build tools (if applicable)
64 * Fork the mal repository on github and then clone your forked
67 git clone git@github.com:YOUR_NAME/mal.git
71 * Make a new directory for your implementation. For example, if your
72 language is called "quux":
77 * Modify the top level Makefile to allow the tests to be run against
78 your implementation. For example, if your language is named "quux"
79 and uses "qx" as the file extension, then make the following
80 3 modifications to Makefile:
84 quux_STEP_TO_PROG = mylang/$($(1)).qx
86 quux_RUNSTEP = ../$(2) $(3)
89 This allows you to run tests against your implementation like this:
97 Stackoverflow and Google are your best friends. Modern polyglot
98 developers do not memorize dozens of programming languages. Instead,
99 they learn the peculiar terminology used with each language and then
100 use this to search for their answers.
102 Here are some other resources where multiple languages are
104 * http://learnxinyminutes.com/
105 * http://hyperpolyglot.org/
106 * http://rosettacode.org/
107 * http://rigaux.org/language-study/syntax-across-languages/
109 Do not let yourself be bogged down by specific problems. While the
110 make-a-lisp process is structured as a series of steps, the reality is
111 that building a lisp interpreter is more like a branching tree. If you
112 get stuck on tail call optimization, or hash-maps, move on to other
113 things. You will often have a stroke of inspiration for a problem as
114 you work through other functionality. I have tried to structure this
115 guide and the tests to make clear which things can be deferred until
118 An aside on deferrable/optional bits: when you run the tests for
119 a given step, the last tests are often marked with an "optional"
120 header. This indicates that these are tests for functionality that is
121 not critical to finish a basic mal implementation. Many of the steps
122 in this process guide have a "Deferrable" section, however, it is not
123 quite the same meaning. Those sections include the functionality that
124 is marked as optional in the tests, but they also include
125 functionality that becomes mandatory at a later step. In other words,
126 this is a "make your own Lisp adventure".
128 Use test driven development. Each step of the make-a-lisp process has
129 a bunch of tests associated with it and there is an easy script to run
130 all the tests for a specific step in the process. Pick a failing test,
131 fix it, repeat until all the tests for that step pass.
133 The `process` directory contains abbreviated pseudocode and
134 architecture images for each step of the make-a-lisp process. Use
135 a textual diff/comparison tool to compare the previous pseudocode step
136 with the one you are working on. The architecture images have changes
137 from the previous step highlighted in red.
139 If you get completely stuck and are feeling like giving up, then you
140 should "cheat" by referring to the same step or functionality in
141 a existing implementation language. You are here to learn, not to take
142 a test, so do not feel bad about it. Okay, you should feel a little
146 ## The Make-A-Lisp Process
148 In the steps that follow the name of the target language is "quux" and
149 the file extension for that language is "qx".
156 ![step0_repl architecture](step0_repl.png)
158 This step is basically just creating a skeleton of your interpreter.
160 * Create a `step0_repl.qx` file in `quux/`.
162 * Add the 4 trivial functions `READ`, `EVAL`, `PRINT`, and `rep`
163 (read-eval-print). `READ`, `EVAL`, and `PRINT` are basically just
164 stubs that return their first parameter (a string if your target
165 language is a statically typed) and `rep` calls them in order
166 passing the return to the input of the next.
168 * Add a main loop that repeatedly prints a prompt (needs to be
169 "user> " for later tests to pass), gets a line of input from the
170 user, calls `rep` with that line of input, and then prints out the
171 result from `rep`. It should also exit when you send it an EOF
174 * If you are using a compiled (ahead-of-time rather than just-in-time)
175 language, then create a Makefile (or appropriate project definition
176 file) in your directory.
178 It is time to run your first tests. This will check that your program
179 does input and output in a way that can be captured by the test
180 harness. Go to the top level and run the following:
185 Add and then commit your new `step0_repl.qx` and `Makefile` to git.
187 Congratulations! You have just completed the first step of the
193 * Add full line editing and command history support to your
194 interpreter REPL. Many languages have a library/module that provide
195 line editing support. Another option if your language supports it is
196 to use an FFI (foreign function interface) to load and call directly
197 into GNU readline, editline, or libnoise library. Add line
198 editing interface code to `readline.qx`
203 ### Step 1: Read and Print
205 ![step1_read_print architecture](step1_read_print.png)
207 In this step, your interpreter will "read" the string from the user
208 and parse it into an internal tree data structure (an abstract syntax
209 tree) and then take that data structure and "print" it back to
212 In non-lisp languages, this step (called "lexing and parsing") can be
213 one of the most complicated parts of the compiler/interpreter. In
214 Lisp, the data structure that you want in memory is basically
215 represented directly in the code that the programmer writes
218 For example, if the string is "(+ 2 (* 3 4))" then the read function
219 will process this into a tree structure that looks like this:
232 Each left paren and its matching right paren (lisp "sexpr") becomes
233 a node in the tree and everything else becomes a leaf in the tree.
235 If you can find code for an implementation of a JSON encoder/decoder
236 in your target language then you can probably just borrow and modify
237 that and be 75% of the way done with this step.
239 The rest of this section is going to assume that you are not starting
240 from an existing JSON encoder/decoder, but that you do have access to
241 a Perl compatible regular expressions (PCRE) module/library. You can
242 certainly implement the reader using simple string operations, but it
243 is more involved. The `make`, `ps` (postscript) and Haskell
244 implementations have examples of a reader/parser without using regular
247 * Copy `step0_repl.qx` to `step1_read_print.qx`.
249 * Add a `reader.qx` file to hold functions related to the reader.
251 * If the target language has objects types (OOP), then the next step
252 is to create a simple stateful Reader object in `reader.qx`. This
253 object will store the tokens and a position. The Reader object will
254 have two methods: `next` and `peek`. `next` returns the tokens at
255 the current position and increments the position. `peek` just
256 returns the token at the current position.
258 * Add a function `read_str` in `reader.qx`. This function
259 will call `tokenizer` and then create a new Reader object instance
260 with the tokens. Then it will call `read_form` with the Reader
263 * Add a function `tokenizer` in `reader.qx`. This function will take
264 a single string and return an array/list
265 of all the tokens (strings) in it. The following regular expression
266 (PCRE) will match all mal tokens.
268 [\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"|;.*|[^\s\[\]{}('"`,;)]*)
271 * Add the function `read_form` to `reader.qx`. This function
272 will peek at the first token in the Reader object and switch on the
273 first character of that token. If the character is a left paren then
274 `read_list` is called with the Reader object. Otherwise, `read_atom`
275 is called with the Reader Object. The return value from `read_form`
276 is a mal data type. If your target language is statically typed then
277 you will need some way for `read_form` to return a variant or
278 subclass type. For example, if your language is object oriented,
279 then you can define a top level MalType (in `types.qx`) that all
280 your mal data types inherit from. The MalList type (which also
281 inherits from MalType) will contains a list/array of other MalTypes.
282 If your language is dynamically typed then you can likely just
283 return a plain list/array of other mal types.
285 * Add the function `read_list` to `reader.qx`. This function will
286 repeatedly call `read_form` with the Reader object until it
287 encounters a ')' token (if it reach EOF before reading a ')' then
288 that is an error). It accumulates the results into a List type. If
289 your language does not have a sequential data type that can hold mal
290 type values you may need to implement one (in `types.qx`). Note
291 that `read_list` repeatedly calls `read_form` rather than
292 `read_atom`. This mutually recursive defintion between `read_list`
293 and `read_form` is what allows lists to contain lists.
295 * Add the function `read_atom` to `reader.qx`. This function will
296 look at the contents of the token and return the appropriate scalar
297 (simple/single) data type value. Initially, you can just implement
298 numbers (integers) and symbols . This will allow you to proceed
299 through the next couple of steps before you will need to implement
300 the other fundamental mal types: nil, true, false, and string. The
301 remaining mal types: keyword, vector, hash-map, and atom do not
302 need to be implemented until step 9 (but can be implemented at any
303 point between this step and that). BTW, symbols types are just an
304 object that contains a single string name value (some languages have
305 symbol types already).
307 * Add a file `printer.qx`. This file will contain a single function
308 `pr_str` which does the opposite of `read_str`: take a mal data
309 structure and return a string representation of it. But `pr_str` is
310 much simpler and is basically just a switch statement on the type of
313 * symbol: return the string name of the symbol
314 * number: return the number as a string
315 * list: iterate through each element of the list calling `pr_str` on
316 it, then join the results with a space separator, and surround the
317 final result with parens
319 * Change the `READ` function in `step1_read_print.qx` to call
320 `reader.read_str` and the `PRINT` function to call `printer.pr_str`.
321 `EVAL` continues to simply return its input but the type is now
324 You now have enough hooked up to begin testing your code. You can
325 manually try some simple inputs:
330 * `(123 456)` -> `(123 456)`
331 * `( 123 456 789 ) ` -> `(123 456 789)`
332 * `( + 2 (* 3 4) ) ` -> `(+ 2 (* 3 4))`
334 To verify that your code is doing more than just eliminating extra
335 spaces (and not failing), you can instrument your `reader.qx` functions.
337 Once you have gotten past those simple manual tests, it is time to run
338 the full suite of step 1 tests. Go to the top level and run the
344 Fix any test failures related to symbols, numbers and lists.
346 Depending on the functionality of your target language, it is likely
347 that you have now just completed one of the most difficult steps. It
348 is down hill from here. The remaining steps will probably be easier
349 and each step will give progressively more bang for the buck.
354 * Add error checking to your reader functions to make sure parens
355 are properly matched. Catch and print these errors in your main
356 loop. If your language does not have try/catch style bubble up
357 exception handling, then you will need to add explicit error
358 handling to your code to catch and pass on errors without crashing.
360 * Add support for the other basic data type to your reader and printer
361 functions: string, nil, true, and false. These become mandatory at
362 step 4. When a string is read, a slash followed by a doublequote is
363 translated into a plain doublequote character and a slash followed by
364 "n" is translated into a newline. To properly print a string (for
365 step 4 string functions), the `pr_str` function needs another
366 parameter called `print_readably`. When `print_readably` is true,
367 doublequotes and newlines are translated into their printed
368 representations (the reverse of the reader). The `PRINT` function in
369 the main program should call `pr_str` with print_readably set to
372 * Add support for the other mal types: keyword, vector, hash-map, and
374 * keyword: just a string stored with unicode prefix (or char 127 if
376 * vector: can be implemented with same underlying type as list if
377 there is some mechanism for marking/distinguishing from a list.
378 * hash-map: only need to implement string keys (which enables
379 keyword keys since they are just special strings).
381 * Add support for reader macros which are special forms that are
382 transformed into other forms during the read phase.
384 * Add comment support to your reader. The tokenizer should ignore
385 tokens that start with ";". Your `read_str` function will need to
386 properly handle when the tokenizer returns no values. The simplest
387 way to do this is to return `nil` mal value. A cleaner option (that
388 does not print `nil` at the prompt is to throw a special exception
389 that causes the main loop to simply continue at the beginning of the
390 loop without calling `rep`.
397 ![step2_eval architecture](step2_eval.png)
399 In step 1 your mal interpreter was basically just a way to validate
400 input and eliminate extraneous white space. In this step you will turn
401 your interpreter into a simple number calculator by adding
402 functionality to the evaluator (`EVAL`).
404 Compare the pseudocode for step 1 and step 2 to get a basic idea of
405 the changes that will be made during this step:
407 diff -urp ../process/step1_read_print.txt ../process/step2_eval.txt
410 * Copy `step1_read_print.qx` to `step2_eval.qx`.
412 * Define a simple initial REPL environment. This environment is an
413 associative structure that maps symbols (or symbol names) to
414 numeric functions. For example, in python this would look something
417 repl_env = {'+': lambda a,b: a+b,
418 '-': lambda a,b: a-b,
419 '*': lambda a,b: a*b,
420 '/': lambda a,b: int(a/b)}
423 * Modify the `rep` function to pass the REPL environment as the second
424 parameter for the `EVAL` call.
426 * Create a new function `eval_ast` which takes `ast` (mal data type)
427 and an associative structure (the environment from above).
428 `eval_ast` switches on the type of `ast` as follows:
430 * symbol: lookup the symbol in the environment structure and return
431 the value or raise an error no value is found
432 * list: return a new list that is the result of calling `EVAL` on
433 each of the members of the list
434 * otherwise just return the original `ast` value
436 * Modify `EVAL` to check if the first parameter `ast` is a list.
437 * `ast` is not a list: then return the result of calling `eval_ast`
439 * `ast` is a list: call `eval_ast` to get a new evaluated list. Take
440 the first item of the evaluated list and call it as function using
441 the rest of the evaluated list as its arguments.
443 If your target language does not have full variable length argument
444 support (e.g. variadic, vararg, splats, apply) then you will need to
445 pass the full list of arguments as a single parameter and split apart
446 the individual values inside of every mal function. This is annoying,
449 The process of taking a list and invoking or executing it to return
450 something new is known in Lisp as the "apply" phase.
452 Try some simple expressions:
455 * `(+ 2 (* 3 4))` -> `14`
457 The most likely challenge you will encounter is how to properly call
458 a function references using an arguments list.
460 Now go to the top level, run the step 2 tests and fix the errors.
465 You now have a simple prefix notation calculator!
470 ### Step 3: Environments
472 ![step3_env architecture](step3_env.png)
474 In step 2 you were already introduced to REPL environment (`repl_env`)
475 where the basic numeric functions were stored and looked up. In this
476 step you will add the ability to create new environments (`let*`) and
477 modify existing environments (`def!`).
479 A Lisp environment is an associative data structure that maps symbols (the
480 keys) to values. But Lisp environments have an additional important
481 function: they can refer to another environment (the outer
482 environment). During environment lookups, if the current environment
483 does not have the symbol, the lookup continues in the outer
484 environment, and continues this way until the symbol is either found,
485 or the outer environment is `nil` (the outermost environment in the
488 Compare the pseudocode for step 2 and step 3 to get a basic idea of
489 the changes that will be made during this step:
491 diff -urp ../process/step2_eval.txt ../process/step3_env.txt
494 * Copy `step2_eval.qx` to `step3_env.qx`.
496 * Create `env.qx` to hold the environment definition.
498 * Define an `Env` object that is instantiated with a single `outer`
499 parameter and starts with an empty associative data structure
502 * Define three methods for the Env object:
503 * set: takes a symbol key and a mal value and adds to the `data`
505 * find: takes a symbol key and if the current environment contains
506 that key then return the environment. If no key is found and outer
507 is not `nil` then call find (recurse) on the outer environment.
508 * get: takes a symbol key and uses the `find` method to locate the
509 environment with the key, then returns the matching value. If no
510 key is found up the outer chain, then throws/raises a "not found"
513 * Update `step3_env.qx` to use the new `Env` type to create the
514 repl_env (with a `nil` outer value) and use the `set` method to add
515 the numeric functions.
517 * Modify `eval_ast` to call the `get` method on the `env` parameter.
519 * Modify the apply section of `EVAL` to switch on the first element of
521 * symbol "def!": call the set method of the current environment
522 (second parameter of `EVAL` called `env`) using the unevaluated
523 first parameter (second list element) as the symbol key and the
524 evaluated second parameter as the value.
525 * symbol "let*": create a new environment using the current
526 environment as the outer value and then use the first parameter as
527 a list of new bindings in the "let*" environment. Take the second
528 element of the binding list, call `EVAL` using the new "let*"
529 environment as the evaluation environment, then call `set` on the
530 "let*" environment using the first binding list element as the key
531 and the evaluated second element as the value. This is repeated
532 for each odd/even pair in the binding list. Note in particular,
533 the bindings earlier in the list can be referred to by later
534 bindings. Finally, the second parameter (third element) of the
535 original `let*` form is evaluated using the new "let*" environment
536 and the result is returned as the result of the `let*` (the new
537 let environment is discarded upon completion).
538 * otherwise: call `eval_ast` on the list and apply the first element
539 to the rest as before.
541 `def!` and `let*` are Lisp "specials" (or "special atoms") which means
542 that they are language level features and more specifically that the
543 rest of the list elements (arguments) may be evaluated differently (or
544 not at all) unlike the default apply case where all elements of the
545 list are evaluated before the first element is invoked. Lists which
546 contain a "special" as the first element are known as "special forms".
547 The are special because the follow special evaluation rules.
549 Try some simple environment tests:
551 * `(def! a 6)` -> `6`
553 * `(def! b (+ a 2))` -> `8`
555 * `(let* (c 2) c)` -> `2`
557 Now go to the top level, run the step 3 tests and fix the errors.
562 You mal implementation is still basically just a numeric calculator
563 with save/restore capability. But you have set the foundation for step
564 4 where it will begin to feel like a real programming language.
567 An aside on mutation and typing:
569 The "!" suffix on symbols is used to indicate that this symbol refers
570 to a function that mutates something else. In this case, the `def!`
571 symbol indicates a special form that will mutate the current
572 environment. Many (maybe even most) of runtime problems that are
573 encountered in software engineering are a result of mutation. By
574 clearly marking code where mutation may occur, you can more easily
575 track down the likely cause of runtime problems when they do occur.
577 Another cause of runtime errors is type errors, where a value of one
578 type is unexpectedly treated by the program as a different and
579 incompatible type. Statically typed languages try to make the
580 programmer solve all type problems before the program is allowed to
581 run. Most Lisp variants tend to be dynamically typed (types of values
582 are checked when they are actually used at runtime).
584 As an aside-aside: The great debate between static and dynamic typing
585 debate can be understood by following the money. Advocates of strict
586 static typing use words like "correctness" and "safety" and thus get
587 government and academic funding. Advocates of dynamic typing use words
588 like "agile" and "time-to-market" and thus get venture capital and
596 ![step4_if_fn_do architecture](step4_if_fn_do.png)
598 In step 3 you added environments and the special forms for
599 manipulating environments. In this step you will add 3 new special
600 forms (`if`, `fn*` and `do`) and add several more core functions to
601 the default REPL environment. Our new architecture will look like
604 The `fn*` special form is how new user-defined functions are created.
605 In some Lisps, this special form is named "lambda".
607 Compare the pseudocode for step 3 and step 4 to get a basic idea of
608 the changes that will be made during this step:
610 diff -urp ../process/step3_env.txt ../process/step4_if_fn_do.txt
613 * Copy `step3_env.qx` to `step4_if_fn_do.qx`.
615 * If you have not implemented reader and printer support (and data
616 types) for `nil`, `true` and `false`, you will need to do so for
619 * Update the constructor/initializer for environments to take two new
620 arguments: `binds` and `exprs`. Bind (`set`) each element (symbol)
621 of the binds list to the respective element of the `exprs` list.
623 * Add support to `printer.qx` to print functions values. A string
624 literal like "#<function>" is sufficient.
626 * Add the following special forms to `EVAL`.
628 * `do`: Evaluate the all the elements of the list and return the
629 final element (evaluated).
630 * `if`: Evaluate the first parameter (second element). If the result
631 (condition) is anything other than `nil` or `false`, then evaluate
632 the second parammeter (third element of the list) and return the
633 result. Otherwise, evaluate the third parameter (fourth element)
634 and return the result. If condition is false and there is no third
635 parameter, then just return `nil`.
636 * `fn*`: Return a new function closure. The body of that closure
638 * Create a new environment using `env` (closed over from outer
639 scope) as the `outer` parameter, the first parameter (second
640 list element of `ast` from the outer scope) as the `binds`
641 parameter, and the parameters to the closure as the `exprs`
643 * Call `EVAL` on the second parameter (third list element of `ast`
644 from outer scope), using the new environment. Use the result as
645 the return value of the closure.
647 If your target language does not support closures, then you will need
648 to implement `fn*` using some sort of structure or object that stores
649 the values being closed over: the first and second elements of the
650 `ast` list (function parameter list and function body) and the current
651 environment `env`. In this case, your native functions will need to be
652 wrapped in the same way. You will probably also need a method/function
653 that invokes your function object/structure for the default case of
654 the apply section of `EVAL`.
656 Try out the basic functionality you have implemented:
658 * `(fn* [a] a)` -> `#<function>`
659 * `( (fn* [a] a) 7)` -> `7`
660 * `( (fn* [a] (+ a 1)) 10)` -> `11`
661 * `( (fn* [a b] (+ a b)) 2 3)` -> `5`
663 * Add a new file `core.qx` and define an associative data structure
664 `ns` (namespace) that maps symbols to functions. Move the numeric
665 function definitions into this structure.
667 * Modify `step4_if_fn_do.qx` to iterate through the `core.ns`
668 structure and add (`set`) each symbol/function mapping to the
669 REPL environment (`repl_env`).
671 * Add the following functions to `core.ns`:
672 * `list`: take the parameters and return them as a list.
673 * `list?`: return true if the first parameter is a list, false
675 * `empty?`: treat the first parameter as a list and return true if
676 the list is empty and false if it contains any elements.
677 * `count`: treat the first parameter as a list and return the number
678 of elements that it contains.
679 * `=`: compare the first two parameters and return true if they are
680 the same type and contain the same value. In the case of equal
681 length lists, each element of the list should be compared for
682 equality and if they are the same return true, otherwise false.
683 * `<`, `<=`, `>`, and `>=`: treat the first two parameters as
684 numbers and do the corresponding numeric comparison, returning
685 either true or false.
687 Now go to the top level, run the step 4 tests. There are a lot of
688 tests in step 4 but all of the non-optional tests that do not involve
689 strings should be able to pass now.
695 Your mal implementation is already beginning to look like a real
696 language. You have flow control, conditionals, user-defined functions
697 with lexical scope, side-effects (if you implement the string
698 functions), etc. However, our little interpreter has not quite reach
699 Lisp-ness yet. The next several steps will take
703 * Implement Clojure-style variadic function parameters. Modify the
704 constructor/initializer for environments, so that if a "&" symbol is
705 encountered in the `binds` list, the next symbol in the `binds` list
706 after the "&" is bound to the rest of the `exprs` list that has not
709 * Defines a `not` function using mal itself. In `step4_if_fn_do.qx`
710 call the `rep` function with this string:
711 "(def! not (fn* (a) (if a false true)))".
713 * Implement the strings functions in `core.qx`. To implement these
714 functions, you will need to implement the string support in the
715 reader and printer (deferrable section of step 1). Each of the string
716 functions takes multiple mal values, prints them (`pr_str`) and
717 joins them together into a new string.
718 * `pr-str`: calls `pr_str` on each argument with `print_readably`
719 set to true, joins the results with " " and returns the new
721 * `str`: calls `pr_str` on each argument with `print_readably` set
722 to false, concatenates the results together ("" separator), and
723 returns the new string.
724 * `prn`: calls `pr_str` on each argument with `print_readably` set
725 to true, joins the results with " ", prints the string to the
726 screen and then returns `nil`.
727 * `println`: calls `pr_str` on each argument with `print_readably` set
728 to false, joins the results with " ", prints the string to the
729 screen and then returns `nil`.
734 ### Step 5: Tail call optimization
736 ![step5_tco architecture](step5_tco.png)
738 In step 4 you added special forms `do`, `if` and `fn*` and you defined
739 some core functions. In this step you will add a Lisp feature called
740 tail call optimization (TCO). Also called "tail recursion" or
741 sometimes just "tail calls".
743 Several of the special forms that you have defined in `EVAL` end up
744 calling back into `EVAL`. For those forms that call `EVAL` as the last
745 thing that they do before returning (tail call) you will just loop back
746 to the beginning of eval rather than calling it again. The advantage
747 of this approach is that it avoids adding more frames to the call
748 stack. This is especially important in Lisp languages because they do
749 not tend to have iteration control structures preferring recursion
750 instead. However, with tail call optimization, recursion can be made
751 as stack efficient as iteration.
753 Compare the pseudocode for step 4 and step 5 to get a basic idea of
754 the changes that will be made during this step:
756 diff -urp ../process/step4_if_fn_do.txt ../process/step5_tco.txt
759 * Copy `step4_env.qx` to `step5_tco.qx`.
761 * Add a loop (e.g. while true) around all code in `EVAL`.
763 * Modify each of the following form cases to add tail call recursion
765 * `let*`: remove the final `EVAL` call on the second `ast` argument
766 (third list element). Set `env` (i.e. the local variable passed in
767 as second parameter of `EVAL`) to the new let environment. Set
768 `ast` (i.e. the local variable passed in as first parameter of
769 `EVAL`) to be the second `ast` argument. Continue at the beginning
770 of the loop (no return).
771 * `do`: change the `eval_ast` call to evaluate all the parameters
772 the except for the last (2nd list element up to but not
773 including last). Set `ast` to the last element of `ast`. Continue
774 at the beginning of the loop (`env` stays unchanged).
775 * `if`: the condition continues to be evaluated, however, rather
776 than evaluating the true or false branch, `ast` is set to the
777 unevaluated value of the chosen branch. Continue at the beginning
778 of the loop (`env` is unchanged).
780 * The return value from the `fn*` special form will now become an
781 object/structure with attributes that allow the default invoke case
782 of `EVAL` to do TCO on mal functions. Those attributes are:
783 * `fn`: the original function value return in step 4 (this is
784 actually deferrable until step 9 when it is needed for the `map`
785 and `apply` core functions).
786 * `ast`: the second `ast` argument (third list element) representing
787 the body of the function.
788 * `params`: the first `ast` argument (second list element)
789 representing the parameter names of the function.
790 * `env`: the current value of the `env` parameter of `EVAL`.
792 * The default "apply"/invoke case of `EVAL` must now be changed to
793 account for the new object/structure returned by the `fn*` form.
794 Continue to call `eval_ast` on `ast`. The first element is `f`.
795 Switch on the type of `f`:
796 * regular function (not one defined by `fn*`): apply/invoke it as
797 * before (in step 4).
798 * a `fn*` value: set `ast` to the `ast` attribute of `f`. Generate
799 a new environment using the `env` and `params` attributes of `f`
800 as the `outer` and `binds` arguments and rest `ast` arguments
801 (list elements 2 through the end) as the `exprs` argument. Set
802 `env` to the new environment. Continue at the beginning of the loop.
804 Run some manual tests from previous steps to make sure you have not
805 broken anything by adding TCO.
807 Now go to the top level, run the step 5 tests.
813 Look at the step 5 test file `tests/step5_tco.mal`. The `sum-to`
814 function cannot be tail call optimized because it does something after
815 the recursive call (`sum-to` calls itself and then does the addition).
816 Lispers say that the `sum-to` is not in tail position. The `sum2`
817 function however, calls itself from tail position. In other words, the
818 recursive call to `sum2` is the last action that `sum2` does. Calling
819 `sum-to` with a large value will cause a stack overflow exception in
820 most target languages (some have super-special tricks they use to
821 avoid stack overflows).
823 Congratulations, your mal implementation already has a feature (TCO)
824 that most mainstream languages lack.
829 ### Step 6: Files and Evil
831 ![step6_file architecture](step6_file.png)
833 In step 5 you added tail call optimization. In this step you will add
834 some string and file operations and give your implementation a touch
835 of evil ... er, eval. And as long as your language supports function
836 closures, this step will be quite simple. However, to complete this
837 step, you must implement string type support, so if you have been
838 holding off on that you will need to go back and do so.
840 Compare the pseudocode for step 5 and step 6 to get a basic idea of
841 the changes that will be made during this step:
843 diff -urp ../process/step5_tco.txt ../process/step6_file.txt
846 * Copy `step5_tco.qx` to `step6_file.qx`.
848 * Add two new string functions to the core namespaces:
849 * `read-string`: this function just exposes the `read_str` function
850 from the reader. If your mal string type is not the same as your
851 target language (e.g. statically typed language) then your
852 `read-string` function will need to unbox (extract) the raw string
853 from the mal string type in order to call `read_str`.
854 * `slurp`: this function takes a file name (string) and returns the
855 contents of the file as a string. Once again, if your mal string
856 type wraps a raw target language string, then you will need to
857 unmarshall (extract) the string parameter to get the raw file name
858 string and marshall (wrap) the result back to a mal string type.
860 * In your main program, add a new `eval` (symbol) entry to your REPL
861 environment. The value of the new entry is a regular function
862 closure with a single argument `ast`. The closure calls the real
863 `EVAL` function using the `ast` as the first argument and the REPL
864 environment (closed over from outside) as the second argument. The
865 result of the `EVAL` call is returned.
867 * Define a `load-file` function using mal itself. In your main
868 program call the `rep` function with this string:
869 "(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \")\")))))".
872 * `(load-file "../tests/incA.mal")` -> `9`
875 The `load-file` function does the following:
876 * Call `slurp` to read in a file by name. Surround the contents with
877 "(do ...)" so that the whole file will be treated as a single
878 program AST (abstract syntax tree).
879 * Call `read-string` on the string returned from `slurp`. This uses
880 the reader to read/convert the file contents into mal data/AST.
881 * Call `eval` (the one in the REPL environment) on the AST returned
882 from `read-string` to "run" it.
884 Now go to the top level, run the step 6 tests. The optional tests will
885 need support from the reader for comments, vectors and hash-maps:
890 Congratulations, you now have a full-fledged scripting language that
891 can run other mal programs. However, the set of functions that are
892 available (from `core.qx`) is fairly limited. The bulk of the
893 functions you will add are described in step 9, but you will begin to
894 flesh them out over the next few steps to support quoting (step 7) and
900 * Add the ability to run another mal program from the command line.
901 Prior to the REPL loop, check if your mal implementation is called
902 with command line arguments. If so, treat the first argument as
903 a filename and use `rep` to call `load-file` on that filename, and
904 finally exit/terminate execution.
906 * Add the rest of the command line arguments to your REPL environment
907 so that programs that are run with `load-file` have access to their
908 calling environmnet. Add a new "*ARGV*" (symbol) entry to your REPL
909 environment. The value of this entry should be the rest of the
910 command line arguments as a mal list value.
917 ![step7_quote architecture](step7_quote.png)
919 In step 7 you will add the special forms `quote` and `quasiquote` and
920 add supporting core functions `cons` and `concat`. The two quote forms
921 add a powerful abstraction for manipulating mal code itself
924 The `quote` special form indicates to the evaluator (`EVAL`) that the
925 parameter should not be evaluated (yet). At first glance, this might
926 not seem particular useful but an example of what this enables is the
927 ability for a mal program to refer to a symbol itself rather than the
928 value that it evaluates to. Likewise with lists. For example, consider
931 * `(prn abc)`: this will lookup the symbol `abc` in the current
932 evaluation environment and print it. This will result in error if
933 `abc` is not defined.
934 * `(prn (quote abc))`: this will print "abc" (prints the symbol
935 itself). This will work regardless of whether `abc` is defined in
936 the current environment.
937 * `(prn (1 2 3))`: this will result in an error because `1` is not
938 a function and cannot be applied to the arguments `(2 3)`.
939 * `(prn (quote (1 2 3)))`: this will print "(1 2 3)".
940 * `(def! l (quote (1 2 3)))`: list quoting allows us to define lists
941 directly in the code (list literal). Another way of doing this is
942 with the list function: `(def! l (list 1 2 3))`.
944 The second special quoting form is `quasiquote`. This allows a quoted
945 list to have internal elements of the list that are temporarily
946 unquoted (normal evaluation). There are two special forms that only
947 mean something within a quasiquoted list: `unquote` and
948 `splice-unquote`. These are perhaps best explained with some examples:
950 * `(def! lst (quote (2 3)))` -> `(2 3)`
951 * `(quasiquote (1 (unquote lst)))` -> `(1 (2 3))`
952 * `(quasiquote (1 (splice-unquote lst)))` -> `(1 2 3)`
954 The `unquote` form turns evaluation back on for its argument and the
955 result of evaluation is put in place into the quasiquoted list. The
956 `splice-unquote` also turns evaluation back on for its argument, but
957 the evaluated value must be a list which is then "spliced" into the
958 quasiquoted list. The true power of the quasiquote form will be
959 manifest when it used together with macros (in the next step).
961 Compare the pseudocode for step 6 and step 7 to get a basic idea of
962 the changes that will be made during this step:
964 diff -urp ../process/step6_file.txt ../process/step7_quote.txt
967 * Copy `step6_file.qx` to `step7_quote.qx`.
969 * Before implementing the quoting forms, you will need to implement
970 * some supporting functions in the core namespace:
971 * `cons`: this function takes a list as its second
972 parameter and returns a new list that has the first argument
974 * `concat`: this functions takes 0 or more lists as
975 parameters and returns a new list that is a concatenation of all
978 An aside on immutability: note that neither cons or concat mutate
979 their original list arguments. Any references to them (i.e. other
980 lists that they may be "contained" in) will still refer to the
981 original unchanged value. Mal, like Clojure, is a language which uses
982 immutable data structures. I encourage you to read about the power and
983 importance of immutability as implemented in Clojure (from which
984 Mal borrows most of its syntax and feature-set).
986 * Add the `quote` special form. This form just returns its argument
987 (the second list element of `ast`).
989 * Add the `quasiquote` special form. First implement a helper function
990 `is_pair` that returns true if the parameter is a non-empty list.
991 Then define a `quasiquote` function. This is called from `EVAL` with
992 the first `ast` argument (second list element) and then `ast` is set
993 to the result and execution continues at the top of the loop (TCO).
994 The `quasiquote` function takes a parameter `ast` and has the
995 following conditional:
996 1. if `is_pair` of `ast` is false: return a new list containing:
997 a symbol named "quote" and `ast`.
998 2. else if the first element of `ast` is a symbol named "unquote":
999 return the second element of `ast`.
1000 3. if `is_pair` of first element of `ast` is true and the first
1001 element of first element of `ast` (`ast[0][0]`) is a symbol named
1002 "splice-unquote": return a new list containing: a symbol named
1003 "concat", the second element of first element of `ast`
1004 (`ast[0][1]`), and the result of calling `quasiquote` with the
1005 second through last element of `ast`.
1006 4. otherwise: return a new list containing: a symbol named "cons", the
1007 result of calling `quasiquote` on first element of `ast`
1008 (`ast[0]`), and result of calling `quasiquote` with the second
1009 through last element of `ast`.
1012 Now go to the top level, run the step 7 tests:
1014 make test^quux^step7
1017 Quoting is one of the more mundane functions available in mal, but do
1018 not let that discourage you. Your mal implementation is almost
1019 complete, and quoting sets the stage for the next very exiting step:
1025 * The full names for the quoting forms are fairly verbose. Most Lisp
1026 languages have a short-hand syntax and Mal is no exception. These
1027 short-hand syntaxes are known as reader macros because they allow us
1028 to manipulate mal code during the reader phase. Macros that run
1029 during the eval phase are just called "macros" and are described in
1030 the next section. Expand the conditional with reader `read_form`
1031 function to add the following four cases:
1032 * token is "'" (single quote): return a new list that contains the
1033 symbol "quote" and the result of reading the next form
1035 * token is "`" (back-tick): return a new list that contains the
1036 symbol "quasiquote" and the result of reading the next form
1038 * token is "~" (tilde): return a new list that contains the
1039 symbol "unquote" and the result of reading the next form
1041 * token is "~@" (tilde + at sign): return a new list that contains
1042 the symbol "splice-unquote" and the result of reading the next
1045 * Add support for quoting of vectors. The `is_pair` function should
1046 return true if the argument is a non-empty list or vector. `cons`
1047 should also accept a vector as the second argument. The return value
1048 is a list regardless. `concat` should support concatenation of
1049 lists, vectors, or a mix or both. The result is always a list.
1052 <a name="step8"></a>
1056 ![step8_macros architecture](step8_macros.png)
1058 Your mal implementation is now ready for one of the most Lispy and
1059 exciting of all programming concepts: macros. In the previous step,
1060 quoting enabled some simple manipulation data structures and therefore
1061 manipulation of mal code (because the `eval` function from step
1062 6 turns mal data into code). In this step you will be able to mark mal
1063 functions as macros which can manipulate mal code before it is
1064 evaluated. In other words, macros are user-defined special forms. Or
1065 to look at it another way, macros allow mal programs to redefine
1066 the mal language itself.
1068 Compare the pseudocode for step 7 and step 8 to get a basic idea of
1069 the changes that will be made during this step:
1071 diff -urp ../process/step7_quote.txt ../process/step8_macros.txt
1074 * Copy `step7_quote.qx` to `step8_macros.qx`.
1077 You might think that the infinite power of macros would require some
1078 sort of complex mechanism, but the implementation is actually fairly
1081 * Add a new attribute `is_macro` to mal function types. This should
1084 * Add a new special form `defmacro!`. This is very similar to the
1085 `def!` form, but before the evaluated value (mal function) is set in
1086 the environment, the `is_macro` attribute should be set to true.
1088 * Add a `is_macro_call` function: This function takes arguments `ast`
1089 and `env`. It returns true if `ast` is a list that contains a symbol
1090 as the first element and that symbol refers to a function in the
1091 `env` environment and that function has the `is_macro` attribute set
1092 to true. Otherwise, it returns false.
1094 * Add a `macroexpand` function: This function takes arguments `ast`
1095 and `env`. It calls `is_macro_call` with `ast` and `env` and loops
1096 while that condition is true. Inside the loop, the first element of
1097 the `ast` list (a symbol), is looked up in the environment to get
1098 the macro function. This macro function is then called/applied with
1099 the rest of the `ast` elements (2nd through the last) as arguments.
1100 The return value of the macro call becomes the new value of `ast`.
1101 When the loop completes because `ast` no longer represents a macro
1102 call, the current value of `ast` is returned.
1104 * In the evaluator (`EVAL`) before the special forms switch (apply
1105 section), perform macro expansion by calling the `macroexpand`
1106 function with the current value of `ast` and `env`. Set `ast` to the
1107 result of that call. If the new value of `ast` is no longer a list
1108 after macro expansion, then return `ast`, otherwise continue with
1109 the rest of the apply section (special forms switch).
1111 * Add a new special form condition for `macroexpand`. Call the
1112 `macroexpand` function using the first `ast` argument (second list
1113 element) and `env`. Return the result. This special form allows
1114 a mal program to do explicit macro expansion without applying the
1115 result (which can be useful for debugging macro expansion).
1117 Now go to the top level, run the step 8 tests:
1119 make test^quux^step8
1122 There is a reasonably good chance that the macro tests will not pass
1123 the first time. Although the implementation of macros is fairly
1124 simple, debugging runtime bugs with macros can be fairly tricky. If
1125 you do run into subtle problems that are difficult to solve, let me
1126 recommend a couple of approaches:
1128 * Use the macroexpand special form to eliminate one of the layers of
1129 indirection (to expand but skip evaluate). This will often reveal
1130 the source of the issue.
1131 * Add a debug print statement to the top of your main `eval` function
1132 (inside the TCO loop) to print the current value of `ast` (hint use
1133 `pr_str` to get easier to debug output). Pull up the step8
1134 implementation from another language and uncomment its `eval`
1135 function (yes, I give you permission to violate the rule this once).
1136 Run the two side-by-side. The first difference is likely to point to
1139 Congratulations! You now have a Lisp interpreter with a super power
1140 that most non-Lisp languages can only dream of (I have it on good
1141 authority that languages dream when you are not using them). If you
1142 are not already familiar with Lisp macros, I suggest the following
1143 excercise: write a recursive macro that handles postfixed mal code
1144 (with the function as the last parameter instead of the first). Or
1145 not. I have not actually done so myself, but I have heard it is an
1146 interesting excercise.
1148 In the next step you will add try/catch style exception handling to
1149 your implementation in addition to some new core functions. After
1150 step9 you will be very close to having a fully self-hosting mal
1151 implementation. Let us continue!
1156 * Add the following new core functions which are frequently used in
1158 * `nth`: this function takes a list (or vector) and a number (index)
1159 as arguments, returns the element of the list at the given index.
1160 If the index is out of range, this function raises an exception.
1161 * `first`: this function takes a list (or vector) as its argument
1162 and return the first element. If the list (or vector) is empty or
1163 is `nil` then `nil` is returned.
1164 * `rest`: this function takes a list (or vector) as its argument and
1165 returns a new list containing all the elements except the first.
1167 * In the main program, use the `rep` function to define two new
1168 control structures macros. Here are the string arguments for `rep`
1169 to define these macros:
1170 * `cond`: "(defmacro! cond (fn* (& xs) (if (> (count xs) 0) (list 'if (first xs) (if (> (count xs) 1) (nth xs 1) (throw \"odd number of forms to cond\")) (cons 'cond (rest (rest xs)))))))"
1171 * `or`: "(defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) `(let* (or_FIXME ~(first xs)) (if or_FIXME or_FIXME (or ~@(rest xs))))))))"
1174 <a name="step9"></a>
1178 ![step9_try architecture](step9_try.png)
1180 Compare the pseudocode for step 8 and step 9 to get a basic idea of
1181 the changes that will be made during this step:
1183 diff -urp ../process/step8_macros.txt ../process/step9_try.txt
1186 * Copy `step8_macros.qx` to `step9_try.qx`.
1189 * In step 5, if you did not add original function (`fn`) to the
1190 returned structure returned from `fn*`, the you will need to do so
1194 <a name="step9"></a>
1196 ### Step A: Interop and Self-hosting
1198 ![stepA_mal architecture](stepA_mal.png)
1200 Compare the pseudocode for step 9 and step A to get a basic idea of
1201 the changes that will be made during this step:
1203 diff -urp ../process/step9_try.txt ../process/stepA_mal.txt
1206 * Copy `step9_try.qx` to `stepA_mal.qx`.
1213 * simplify: "X argument (list element Y)" -> ast[Y]
1214 * step 8 summary (power of macros, warning about macros, almost to
1218 * more info on hash-map and keyword implementation. Hash-maps just
1219 need to support string keys.
1220 * list of types with metadata: list, vector, hash-map, mal functions
1221 * more clarity about when to peek and poke in read_list and read_form
1222 * tokenizer: use first group rather than whole match (to eliminate