So jump right in (er ... start the climb)!
+- [Pick a language](#pick-a-language)
+- [Getting started](#getting-started)
+- [General hints](#general-hints)
+- [The Make-A-Lisp Process](#the-make-a-lisp-process-1)
+ - [Step 0: The REPL](#step-0-the-repl)
+ - [Step 1: Read and Print](#step-1-read-and-print)
+ - [Step 2: Eval](#step-2-eval)
+ - [Step 3: Environments](#step-3-environments)
+ - [Step 4: If Fn Do](#step-4-if-fn-do)
+ - [Step 5: Tail call optimization](#step-5-tail-call-optimization)
+ - [Step 6: Files, Mutation, and Evil](#step-6-files-mutation-and-evil)
+ - [Step 7: Quoting](#step-7-quoting)
+ - [Step 8: Macros](#step-8-macros)
+ - [Step 9: Try](#step-9-try)
+ - [Step A: Metadata, Self-hosting and Interop](#step-a-metadata-self-hosting-and-interop)
+
+
## Pick a language
You might already have a language in mind that you want to use.
Technically speaking, mal can be implemented in any sufficiently
-complete programming language (i.e. Turing complete), however, there are a few
-language features that can make the task MUCH easier. Here are some of
-them in rough order of importance:
+complete programming language (i.e. Turing complete), however, there
+are a few language features that can make the task MUCH easier. Here
+are some of them in rough order of importance:
* A sequential compound data structure (e.g. arrays, lists,
vectors, etc)
Here are some examples of languages that have all of the above
features: JavaScript, Ruby, Python, Lua, R, Clojure.
+Michael Fogus has some great blog posts on interesting but less well
+known languages and many of the languages on his lists do not yet have
+any mal implementations:
+* http://blog.fogus.me/2011/08/14/perlis-languages/
+* http://blog.fogus.me/2011/10/18/programming-language-development-the-past-5-years/
+
Many of the most popular languages already have Mal implementations.
However, this should not discourage you from creating your own
implementation in a language that already has one. However, if you go
IMPLS = ... quux ...
...
quux_STEP_TO_PROG = mylang/$($(1)).qx
-...
-quux_RUNSTEP = ../$(2) $(3)
+```
+
+* Add a "run" script to you implementation directory that listens to
+ the "STEP" environment variable for the implementation step to run
+ and defaults to "stepA_mal". Make sure the run script has the
+ executable file permission set (or else the test runner might fail with a
+ permission denied error message). The following are examples of "run"
+ scripts for a compiled language and an interpreted language (where
+ the interpreter is named "quux"):
+
+```
+#!/bin/bash
+exec $(dirname $0)/${STEP:-stepA_mal} "${@}"
+```
+
+```
+#!/bin/bash
+exec quux $(dirname $0)/${STEP:-stepA_mal}.qx "${@}"
```
This allows you to run tests against your implementation like this:
```
-make test^quux^stepX
+make "test^quux^stepX"
```
+If your implementation language is a compiled language, then you
+should also add a Makefile at the top level of your implementation
+directory. This Makefile will define how to build the files pointed to
+by the quux_STEP_TO_PROG macro. The top-level Makefile will attempt to
+build those targets before running tests. If it is a scripting
+language/uncompiled, then no Makefile is necessary because
+quux_STEP_TO_PROG will point to a source file that already exists and
+does not need to be compiled/built.
+
## General hints
all the tests for a specific step in the process. Pick a failing test,
fix it, repeat until all the tests for that step pass.
+## Reference Code
+
The `process` directory contains abbreviated pseudocode and
-architecture images for each step of the make-a-lisp process. Use
+architecture diagrams for each step of the make-a-lisp process. Use
a textual diff/comparison tool to compare the previous pseudocode step
-with the one you are working on. The architecture images have changes
-from the previous step highlighted in red.
+with the one you are working on. The architecture diagram images have
+changes from the previous step highlighted in red. There is also
+a concise
+[cheatsheet](http://kanaka.github.io/mal/process/cheatsheet.html) that
+summarizes the key changes at each step.
If you get completely stuck and are feeling like giving up, then you
should "cheat" by referring to the same step or functionality in
does input and output in a way that can be captured by the test
harness. Go to the top level and run the following:
```
-make test^quux^step0
+make "test^quux^step0"
```
Add and then commit your new `step0_repl.qx` and `Makefile` to git.
interpreter REPL. Many languages have a library/module that provide
line editing support. Another option if your language supports it is
to use an FFI (foreign function interface) to load and call directly
- into GNU readline, editline, or libnoise library. Add line
+ into GNU readline, editline, or linenoise library. Add line
editing interface code to `readline.qx`
* If the target language has objects types (OOP), then the next step
is to create a simple stateful Reader object in `reader.qx`. This
object will store the tokens and a position. The Reader object will
- have two methods: `next` and `peek`. `next` returns the tokens at
+ have two methods: `next` and `peek`. `next` returns the token at
the current position and increments the position. `peek` just
returns the token at the current position.
```
[\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"|;.*|[^\s\[\]{}('"`,;)]*)
```
+* For each match captured within the parenthesis starting at char 6 of the
+ regular expression a new token will be created.
+
+ * `[\s,]*`: Matches any number of whitespaces or commas. This is not captured
+ so it will be ignored and not tokenized.
+
+ * `~@`: Captures the special two-characters `~@` (tokenized).
+
+ * ```[\[\]{}()'`~^@]```: Captures any special single character, one of
+ ```[]{}()'`~^@``` (tokenized).
+
+ * `"(?:\\.|[^\\"])*"`: Starts capturing at a double-quote and stops at the
+ next double-quote unless it was proceeded by a backslash in which case it
+ includes it until the next double-quote (tokenized).
+
+ * `;.*`: Captures any sequence of characters starting with `;` (tokenized).
+
+ * ```[^\s\[\]{}('"`,;)]*```: Captures a sequence of zero or more non special
+ characters (e.g. symbols, numbers, "true", "false", and "nil") and is sort
+ of the inverse of the one above that captures special characters (tokenized).
* Add the function `read_form` to `reader.qx`. This function
will peek at the first token in the Reader object and switch on the
subclass type. For example, if your language is object oriented,
then you can define a top level MalType (in `types.qx`) that all
your mal data types inherit from. The MalList type (which also
- inherits from MalType) will contains a list/array of other MalTypes.
+ inherits from MalType) will contain a list/array of other MalTypes.
If your language is dynamically typed then you can likely just
return a plain list/array of other mal types.
your language does not have a sequential data type that can hold mal
type values you may need to implement one (in `types.qx`). Note
that `read_list` repeatedly calls `read_form` rather than
- `read_atom`. This mutually recursive defintion between `read_list`
+ `read_atom`. This mutually recursive definition between `read_list`
and `read_form` is what allows lists to contain lists.
* Add the function `read_atom` to `reader.qx`. This function will
look at the contents of the token and return the appropriate scalar
(simple/single) data type value. Initially, you can just implement
- numbers (integers) and symbols . This will allow you to proceed
+ numbers (integers) and symbols. This will allow you to proceed
through the next couple of steps before you will need to implement
the other fundamental mal types: nil, true, false, and string. The
remaining mal types: keyword, vector, hash-map, and atom do not
the full suite of step 1 tests. Go to the top level and run the
following:
```
-make test^quux^step1
+make "test^quux^step1"
```
Fix any test failures related to symbols, numbers and lists.
#### Deferrable:
+* Add support for the other basic data type to your reader and printer
+ functions: string, nil, true, and false. These become mandatory at
+ step 4. When a string is read, the following transformations are
+ applied: a backslash followed by a doublequote is translated into
+ a plain doublequote character, a backslash followed by "n" is
+ translated into a newline, and a backslash followed by another
+ backslash is translated into a single backslash. To properly print
+ a string (for step 4 string functions), the `pr_str` function needs
+ another parameter called `print_readably`. When `print_readably` is
+ true, doublequotes, newlines, and backslashes are translated into
+ their printed representations (the reverse of the reader). The
+ `PRINT` function in the main program should call `pr_str` with
+ print_readably set to true.
+
* Add error checking to your reader functions to make sure parens
are properly matched. Catch and print these errors in your main
loop. If your language does not have try/catch style bubble up
exception handling, then you will need to add explicit error
handling to your code to catch and pass on errors without crashing.
-* Add support for the other basic data type to your reader and printer
- functions: string, nil, true, and false. These become mandatory at
- step 4. When a string is read, a slash followed by a doublequote is
- translated into a plain doublequote character and a slash followed by
- "n" is translated into a newline. To properly print a string (for
- step 4 string functions), the `pr_str` function needs another
- parameter called `print_readably`. When `print_readably` is true,
- doublequotes and newlines are translated into their printed
- representations (the reverse of the reader). The `PRINT` function in
- the main program should call `pr_str` with print_readably set to
- true.
-
-* Add support for the other mal types: keyword, vector, hash-map, and
- atom.
+* Add support for reader macros which are forms that are
+ transformed into other forms during the read phase. Refer to
+ `tests/step1_read_print.mal` for the form that these macros should
+ take (they are just simple transformations of the token stream).
+
+* Add support for the other mal types: keyword, vector, hash-map.
* keyword: a keyword is a token that begins with a colon. A keyword
can just be stored as a string with special unicode prefix like
0x29E (or char 0xff/127 if the target language does not have good
tokens are then used for keys with the corresponding even tokens
as the values.
-* Add support for reader macros which are forms that are
- transformed into other forms during the read phase. Refer to
- `tests/step1_read_print.mal` for the form that these macros should
- take (they are just simple transformations of the token stream).
-
* Add comment support to your reader. The tokenizer should ignore
tokens that start with ";". Your `read_str` function will need to
properly handle when the tokenizer returns no values. The simplest
`eval_ast` switches on the type of `ast` as follows:
* symbol: lookup the symbol in the environment structure and return
- the value or raise an error no value is found
+ the value or raise an error if no value is found
* list: return a new list that is the result of calling `EVAL` on
each of the members of the list
* otherwise just return the original `ast` value
* Modify `EVAL` to check if the first parameter `ast` is a list.
* `ast` is not a list: then return the result of calling `eval_ast`
on it.
+ * `ast` is a empty list: return ast unchanged.
* `ast` is a list: call `eval_ast` to get a new evaluated list. Take
the first item of the evaluated list and call it as function using
the rest of the evaluated list as its arguments.
Now go to the top level, run the step 2 tests and fix the errors.
```
-make test^quux^step2
+make "test^quux^step2"
```
You now have a simple prefix notation calculator!
+#### Deferrable:
+
+* `eval_ast` should evaluate elements of vectors and hash-maps. Add the
+ following cases in `eval_ast`:
+ * If `ast` is a vector: return a new vector that is the result of calling
+ `EVAL` on each of the members of the vector.
+ * If `ast` is a hash-map: return a new hash-map which consists of key-value
+ pairs where the key is a key from the hash-map and the value is the result
+ of calling `EVAL` on the corresponding value.
+
<a name="step3"></a>
(second parameter of `EVAL` called `env`) using the unevaluated
first parameter (second list element) as the symbol key and the
evaluated second parameter as the value.
- * symbol "let*": create a new environment using the current
+ * symbol "let\*": create a new environment using the current
environment as the outer value and then use the first parameter as
- a list of new bindings in the "let*" environment. Take the second
- element of the binding list, call `EVAL` using the new "let*"
+ a list of new bindings in the "let\*" environment. Take the second
+ element of the binding list, call `EVAL` using the new "let\*"
environment as the evaluation environment, then call `set` on the
- "let*" environment using the first binding list element as the key
+ "let\*" environment using the first binding list element as the key
and the evaluated second element as the value. This is repeated
for each odd/even pair in the binding list. Note in particular,
the bindings earlier in the list can be referred to by later
bindings. Finally, the second parameter (third element) of the
- original `let*` form is evaluated using the new "let*" environment
+ original `let*` form is evaluated using the new "let\*" environment
and the result is returned as the result of the `let*` (the new
let environment is discarded upon completion).
* otherwise: call `eval_ast` on the list and apply the first element
not at all) unlike the default apply case where all elements of the
list are evaluated before the first element is invoked. Lists which
contain a "special" as the first element are known as "special forms".
-The are special because the follow special evaluation rules.
+They are special because they follow special evaluation rules.
Try some simple environment tests:
Now go to the top level, run the step 3 tests and fix the errors.
```
-make test^quux^step3
+make "test^quux^step3"
```
You mal implementation is still basically just a numeric calculator
are checked when they are actually used at runtime).
As an aside-aside: The great debate between static and dynamic typing
-debate can be understood by following the money. Advocates of strict
-static typing use words like "correctness" and "safety" and thus get
+can be understood by following the money. Advocates of strict static
+typing use words like "correctness" and "safety" and thus get
government and academic funding. Advocates of dynamic typing use words
like "agile" and "time-to-market" and thus get venture capital and
commercial funding.
REPL environment (`repl_env`).
* Add the following functions to `core.ns`:
+ * `prn`: call `pr_str` on the first parameter with `print_readably`
+ set to true, prints the result to the screen and then return
+ `nil`. Note that the full version of `prn` is a deferrable below.
* `list`: take the parameters and return them as a list.
* `list?`: return true if the first parameter is a list, false
otherwise.
strings should be able to pass now.
```
-make test^quux^step4
+make "test^quux^step4"
```
Your mal implementation is already beginning to look like a real
after the "&" is bound to the rest of the `exprs` list that has not
been bound yet.
-* Defines a `not` function using mal itself. In `step4_if_fn_do.qx`
+* Define a `not` function using mal itself. In `step4_if_fn_do.qx`
call the `rep` function with this string:
"(def! not (fn* (a) (if a false true)))".
thing that they do before returning (tail call) you will just loop back
to the beginning of eval rather than calling it again. The advantage
of this approach is that it avoids adding more frames to the call
-stack. This is especially important in Lisp languages because they do
-not tend to have iteration control structures preferring recursion
-instead. However, with tail call optimization, recursion can be made
-as stack efficient as iteration.
+stack. This is especially important in Lisp languages because they tend
+to prefer using recursion instead of iteration for control structures.
+(Though some Lisps, such as Common Lisp, have iteration.) However, with
+tail call optimization, recursion can be made as stack efficient as
+iteration.
Compare the pseudocode for step 4 and step 5 to get a basic idea of
the changes that will be made during this step:
diff -urp ../process/step4_if_fn_do.txt ../process/step5_tco.txt
```
-* Copy `step4_env.qx` to `step5_tco.qx`.
+* Copy `step4_if_fn_do.qx` to `step5_tco.qx`.
* Add a loop (e.g. while true) around all code in `EVAL`.
* `env`: the current value of the `env` parameter of `EVAL`.
* `fn`: the original function value (i.e. what was return by `fn*`
in step 4). Note that this is deferrable until step 9 when it is
- needed for the `map` and `apply` core functions).
+ required for the `map` and `apply` core functions). You will also
+ need it in step 6 if you choose to not to defer atoms/`swap!` from
+ that step.
* The default "apply"/invoke case of `EVAL` must now be changed to
account for the new object/structure returned by the `fn*` form.
Now go to the top level, run the step 5 tests.
```
-make test^quux^step5
+make "test^quux^step5"
```
Look at the step 5 test file `tests/step5_tco.mal`. The `sum-to`
<a name="step6"></a>
-### Step 6: Files and Evil
+### Step 6: Files, Mutation, and Evil
(closed over from outside) as the second argument. The result of
the `EVAL` call is returned. This simple but powerful addition
allows your program to treat mal data as a mal program. For example,
- you can now to this:
+ you can now to this:
```
(def! mal-prog (list + 1 2))
(eval mal-prog)
* Call `eval` (the one in the REPL environment) on the AST returned
from `read-string` to "run" it.
+Besides adding file and eval support, we'll add support for the atom data type
+in this step. An atom is the Mal way to represent *state*; it is
+heavily inspired by [Clojure's atoms](http://clojure.org/state). An atom holds
+a reference to a single Mal value of any type; it supports reading that Mal value
+and *modifying* the reference to point to another Mal value. Note that this is
+the only Mal data type that is mutable (but the Mal values it refers to are
+still immutable; immutability is explained in greater detail in step 7).
+You'll need to add 5 functions to the core namespace to support atoms:
+
+ * `atom`: Takes a Mal value and returns a new atom which points to that Mal value.
+ * `atom?`: Takes an argument and returns `true` if the argument is an atom.
+ * `deref`: Takes an atom argument and returns the Mal value referenced by this atom.
+ * `reset!`: Takes an atom and a Mal value; the atom is modified to refer to
+ the given Mal value. The Mal value is returned.
+ * `swap!`: Takes an atom, a function, and zero or more function arguments. The
+ atom's value is modified to the result of applying the function with the atom's
+ value as the first argument and the optionally given function arguments as
+ the rest of the arguments. The new atom's value is returned. (Side note: Mal is
+ single-threaded, but in concurrent languages like Clojure, `swap!` promises
+ atomic update: `(swap! myatom (fn* [x] (+ 1 x)))` will always increase the
+ `myatom` counter by one and will not suffer from missing updates when the
+ atom is updated from multiple threads.)
+
+Optionally, you can add a reader macro `@` which will serve as a short form for
+`deref`, so that `@a` is equivalent to `(deref a)`. In order to do that, modify
+the conditional in reader `read_form` function and add a case which deals with
+the `@` token: if the token is `@` (at sign) then return a new list that
+contains the symbol `deref` and the result of reading the next form
+(`read_form`).
+
Now go to the top level, run the step 6 tests. The optional tests will
-need support from the reader for comments, vectors and hash-maps:
+need support from the reader for comments, vectors, hash-maps and the `@`
+reader macro:
```
-make test^quux^step6
+make "test^quux^step6"
```
Congratulations, you now have a full-fledged scripting language that
`eval` function is not just for running external programs. Because mal
programs are regular mal data structures, you can dynamically generate
or manipulate those data structures before calling `eval` on them.
-This isomorphisism (same shape) between data and programs is known as
+This isomorphism (same shape) between data and programs is known as
"homoiconicity". Lisp languages are homoiconic and this property
distinguishes them from most other programming languages.
* Add the rest of the command line arguments to your REPL environment
so that programs that are run with `load-file` have access to their
- calling environmnet. Add a new "\*ARGV\*" (symbol) entry to your REPL
+ calling environment. Add a new "\*ARGV\*" (symbol) entry to your REPL
environment. The value of this entry should be the rest of the
command line arguments as a mal list value.
`splice-unquote` also turns evaluation back on for its argument, but
the evaluated value must be a list which is then "spliced" into the
quasiquoted list. The true power of the quasiquote form will be
-manifest when it used together with macros (in the next step).
+manifest when it is used together with macros (in the next step).
Compare the pseudocode for step 6 and step 7 to get a basic idea of
the changes that will be made during this step:
a symbol named "quote" and `ast`.
2. else if the first element of `ast` is a symbol named "unquote":
return the second element of `ast`.
- 3. if `is_pair` of first element of `ast` is true and the first
+ 3. if `is_pair` of the first element of `ast` is true and the first
element of first element of `ast` (`ast[0][0]`) is a symbol named
"splice-unquote": return a new list containing: a symbol named
"concat", the second element of first element of `ast`
second through last element of `ast`.
4. otherwise: return a new list containing: a symbol named "cons", the
result of calling `quasiquote` on first element of `ast`
- (`ast[0]`), and result of calling `quasiquote` with the second
+ (`ast[0]`), and the result of calling `quasiquote` with the second
through last element of `ast`.
Now go to the top level, run the step 7 tests:
```
-make test^quux^step7
+make "test^quux^step7"
```
Quoting is one of the more mundane functions available in mal, but do
* token is "'" (single quote): return a new list that contains the
symbol "quote" and the result of reading the next form
(`read_form`).
- * token is "`" (back-tick): return a new list that contains the
+ * token is "\`" (back-tick): return a new list that contains the
symbol "quasiquote" and the result of reading the next form
(`read_form`).
* token is "~" (tilde): return a new list that contains the
-Your mal implementation is now ready for one of the most Lispy and
+Your mal implementation is now ready for one of the most lispy and
exciting of all programming concepts: macros. In the previous step,
quoting enabled some simple manipulation data structures and therefore
manipulation of mal code (because the `eval` function from step
section), perform macro expansion by calling the `macroexpand`
function with the current value of `ast` and `env`. Set `ast` to the
result of that call. If the new value of `ast` is no longer a list
- after macro expansion, then return `ast`, otherwise continue with
- the rest of the apply section (special forms switch).
+ after macro expansion, then return the result of calling `eval_ast`
+ on it, otherwise continue with the rest of the apply section
+ (special forms switch).
* Add a new special form condition for `macroexpand`. Call the
`macroexpand` function using the first `ast` argument (second list
Now go to the top level, run the step 8 tests:
```
-make test^quux^step8
+make "test^quux^step8"
```
There is a reasonably good chance that the macro tests will not pass
that most non-Lisp languages can only dream of (I have it on good
authority that languages dream when you are not using them). If you
are not already familiar with Lisp macros, I suggest the following
-excercise: write a recursive macro that handles postfixed mal code
+exercise: write a recursive macro that handles postfixed mal code
(with the function as the last parameter instead of the first). Or
not. I have not actually done so myself, but I have heard it is an
-interesting excercise.
+interesting exercise.
In the next step you will add try/catch style exception handling to
your implementation in addition to some new core functions. After
implementation. Let us continue!
-### Deferrable
+#### Deferrable
* Add the following new core functions which are frequently used in
macro functions:
control structures macros. Here are the string arguments for `rep`
to define these macros:
* `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)))))))"
+ * Note that `cond` calls the `throw` function when `cond` is
+ called with an odd number of args. The `throw` function is
+ implemented in the next step, but it will still serve it's
+ purpose here by causing an undefined symbol error.
* `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))))))))"
* Add the `try*/catch*` special form to the EVAL function. The
try catch form looks like this: `(try* A (catch* B C))`. The form
`A` is evaluated, if it throws an exception, then form `C` is
- evaluated with a new environment that binds the symbol B to the
+ evaluated with a new environment that binds the symbol `B` to the
value of the exception that was thrown.
* If your target language has built-in try/catch style exception
handling then you are already 90% of the way done. Add a
- (native language) try/catch block that calls evaluates `A` within
+ (native language) try/catch block that evaluates `A` within
the try block and catches all exceptions. If an exception is
caught, then translate it to a mal type/value. For native
exceptions this is either the message string or a mal hash-map
that contains the message string and other attributes of the
- exception. When a regular mal types/values is used as an
+ exception. When a regular mal type/value is used as an
exception, you will probably need to store it within a native
exception type in order to be able to convey/transport it using
the native try/catch mechanism. Then you will extract the mal
type/value from the native exception. Create a new mal environment
- that binds B to the value of the exception. Finally, evaluate `C`
+ that binds `B` to the value of the exception. Finally, evaluate `C`
using that new environment.
* If your target language does not have built-in try/catch style
exception handling then you have some extra work to do. One of the
chain). Yes, it is ugly, but you were warned in the section on
picking a language.
-* Add the `throw` core function.
+* Add the `throw` core function.
* If your language supports try/catch style exception handling, then
this function takes a mal type/value and throws/raises it as an
exception. In order to do this, you may need to create a custom
`fn*`, the you will need to do so now.
* `apply`: takes at least two arguments. The first argument is
a function and the last argument is list (or vector). The
- arguments between the function and the last arguemnt (if there are
+ arguments between the function and the last argument (if there are
any) are concatenated with the final argument to create the
arguments that are used to call the function. The apply
function allows a function to be called with arguments that are
Now go to the top level, run the step 9 tests:
```
-make test^quux^step9
+make "test^quux^step9"
```
Your mal implementation is now essentially a fully featured Lisp
satisfying and enlightening aspects of creating a mal implementation:
self-hosting.
-### Deferrable
+#### Deferrable
* Add the following new core functions:
* `symbol`: takes a string and returns a new symbol with the string
<a name="stepA"></a>
-### Step A: Mutation, Self-hosting and Interop
+### Step A: Metadata, Self-hosting and Interop
* Copy `step9_try.qx` to `stepA_mal.qx`.
-* Add meta-data support to mal functions. TODO. Should be separate
- from the function macro flag.
-
-* Add atom data type and supporting core functions. This is the only
- mal data type/value that is mutable. TODO
-
-* Add the `readline` core function. TODO
-
-
-Now go to the top level, run the step 9 tests:
+* Add the `readline` core function. This functions takes a
+ string that is used to prompt the user for input. The line of text
+ entered by the user is returned as a string. If the user sends an
+ end-of-file (usually Ctrl-D), then nil is returned.
+
+* Add meta-data support to mal functions by adding a new metadata
+ attribute on mal functions that refers to another mal value/type
+ (nil by default). Add the following metadata related core functions:
+ * `meta`: this takes a single mal function argument and returns the
+ value of the metadata attribute.
+ * `with-meta`: this function takes two arguments. The first argument
+ is a mal function and the second argument is another mal
+ value/type to set as metadata. A copy of the mal function is
+ returned that has its `meta` attribute set to the second argument.
+ Note that it is important that the environment and macro attribute
+ of mal function are retained when it is copied.
+ * Add a reader-macro that expands the token "^" to
+ return a new list that contains the symbol "with-meta" and the
+ result of reading the next next form (2nd argument) (`read_form`) and the
+ next form (1st argument) in that order
+ (metadata comes first with the ^ macro and the function second).
+
+* Add a new "\*host-language\*" (symbol) entry to your REPL
+ environment. The value of this entry should be a mal string
+ containing the name of the current implementation.
+
+* When the REPL starts up (as opposed to when it is called with
+ a script and/or arguments), call the `rep` function with this string
+ to print a startup header:
+ "(println (str \"Mal [\" \*host-language\* \"]\"))".
+
+
+Now go to the top level, run the step A tests:
```
-make test^quux^step9
+make "test^quux^stepA"
```
Once you have passed all the non-optional step A tests, it is time to
point while trying to run the mal in mal implementation steps above.
Debugging failures that happen while self-hosting is MUCH more
difficult and mind bending. One of the best approaches I have
-personally found is to add prn statements to the mal implementation
+personally found is to add prn statements to the mal implementation
step (not your own implementation of mal) that is causing problems.
Another approach I have frequently used is to pull out the code from
Once you can manually run all the self-hosted steps, it is time to run
all the tests in self-hosted mode:
```
-make MAL_IMPL=quux test^mal
+make MAL_IMPL=quux "test^mal"
```
When you run into problems (which you almost certainly will), use the
implementation to run a mal implementation which itself runs the mal
implementation.
-### Optional
-* Add metadata support to composite data types, symbols and native
- functions. TODO
-* `time-ms` TODO
-* `conj` TODO
+#### Optional: gensym
+
+The `or` macro we introduced at step 8 has a bug. It defines a
+variable called `or_FIXME`, which "shadows" such a binding from the
+user's code (which uses the macro). If a user has a variable called
+`or_FIXME`, it cannot be used as an `or` macro argument. In order to
+fix that, we'll introduce `gensym`: a function which returns a symbol
+which was never used before anywhere in the program. This is also an
+example for the use of mal atoms to keep state (the state here being
+the number of symbols produced by `gensym` so far).
+Previously you used `rep` to define the `or` macro. Remove that
+definition and use `rep` to define the new counter, `gensym` function
+and the clean `or` macro. Here are the string arguments you need to
+pass to `rep`:
+```
+"(def! *gensym-counter* (atom 0))"
-## TODO:
+"(def! gensym (fn* [] (symbol (str \"G__\" (swap! *gensym-counter* (fn* [x] (+ 1 x)))))))"
-* simplify: "X argument (list element Y)" -> ast[Y]
-* list of types with metadata: list, vector, hash-map, mal functions
-* more clarity about when to peek and poke in read_list and read_form
-* tokenizer: use first group rather than whole match (to eliminate
- whitespace/commas)
+"(defmacro! or (fn* (& xs) (if (empty? xs) nil (if (= 1 (count xs)) (first xs) (let* (condvar (gensym)) `(let* (~condvar ~(first xs)) (if ~condvar ~condvar (or ~@(rest xs)))))))))"
+```
+
+For extra information read [Peter Seibel's thorough discussion about
+`gensym` and leaking macros in Common Lisp](http://www.gigamonkeys.com/book/macros-defining-your-own.html#plugging-the-leaks).
+
+
+#### Optional additions
+
+* Add metadata support to other composite data types (lists, vectors
+ and hash-maps), and to native functions.
+* Add the following new core functions:
+ * `time-ms`: takes no arguments and returns the number of
+ milliseconds since epoch (00:00:00 UTC January 1, 1970), or, if
+ not possible, since another point in time (`time-ms` is usually
+ used relatively to measure time durations). After `time-ms` is
+ implemented, you can run the performance micro-benchmarks by
+ running `make perf^quux`.
+ * `conj`: takes a collection and one or more elements as arguments
+ and returns a new collection which includes the original
+ collection and the new elements. If the collection is a list, a
+ new list is returned with the elements inserted at the start of
+ the given list in opposite order; if the collection is a vector, a
+ new vector is returned with the elements added to the end of the
+ given vector.
+ * `string?`: returns true if the parameter is a string.
+ * `number?`: returns true if the parameter is a number.
+ * `fn?`: returns true if the parameter is a function (internal or
+ user-defined).
+ * `macro?`: returns true if the parameter is a macro.
+ * `seq`: takes a list, vector, string, or nil. If an empty list,
+ empty vector, or empty string ("") is passed in then nil is
+ returned. Otherwise, a list is returned unchanged, a vector is
+ converted into a list, and a string is converted to a list that
+ containing the original string split into single character
+ strings.
+* For interop with the target language, add this core function:
+ * `quux-eval`: takes a string, evaluates it in the target language,
+ and returns the result converted to the relevant Mal type. You
+ may also add other interop functions as you see fit; Clojure, for
+ example, has a function called `.` which allows calling Java
+ methods. If the target language is a static language, consider
+ using FFI or some language-specific reflection mechanism, if
+ available. The tests for `quux-eval` and any other interop
+ function should be added in `quux/tests/stepA_mal.mal` (see the
+ [tests for `lua-eval`](../lua/tests/stepA_mal.mal) as an example).
+
+### Next Steps
+
+* Join the #mal IRC channel. It's fairly quiet but there are bursts of
+ interesting conversation related to mal, Lisps, esoteric programming
+ languages, etc.
+* If you have created an implementation for a new target language (or
+ a unique and interesting variant of an existing implementation),
+ consider sending a pull request to add it into the main mal
+ repository. The [FAQ](../docs/FAQ.md#will-you-add-my-new-implementation)
+ describes general requirements for getting an implementation merged
+ into the main repository.
+* Take your interpreter implementation and have it emit source code in
+ the target language rather than immediately evaluating it. In other
+ words, create a compiler.
+* Pick a new target language and implement mal in it. Pick a language
+ that is very different from any that you already know.
+* Use your mal implementation to implement a real world project. Many
+ of these will force you to address interop. Some ideas:
+ * Web server (with mal as CGI language for extra points)
+ * An IRC/Slack chat bot
+ * An editor (GUI or curses) with mal as a scripting/extension
+ language.
+ * An AI player for a game like Chess or Go.
+* Implement a feature in your mal implementation that is not covered
+ by this guide. Some ideas:
+ * Namespaces
+ * Multi-threading support
+ * Errors with line numbers and/or stack traces.
+ * Lazy sequences
+ * Clojure-style protocols
+ * Full call/cc (call-with-current-continuation) support
+ * Explicit TCO (i.e. `recur`) with tail-position error checking
HCoop / jackhill / mal.git / blobdiff