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)
SHOULD find the most similar target language implementation and refer
to it frequently.
-If you want a fairly long list of programming languages with an
-approximate measure of popularity, try the [Programming Language
-Popularity Chart](http://langpop.corger.nl/)
+If you want a list of programming languages with an
+approximate measure of popularity try the [RedMonk Programming
+Language
+Rankings](https://redmonk.com/sogrady/2019/03/20/language-rankings-1-19/)
+or the [GitHut 2.0 Project](https://madnight.github.io/githut).
## Getting started
* 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". The following are examples of "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"):
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
+[cheatsheet](http://kanaka.github.io/mal/cheatsheet.html) that
summarizes the key changes at each step.
If you get completely stuck and are feeling like giving up, then you
returns the token at the current position.
* Add a function `read_str` in `reader.qx`. This function
- will call `tokenizer` and then create a new Reader object instance
+ will call `tokenize` and then create a new Reader object instance
with the tokens. Then it will call `read_form` with the Reader
instance.
-* Add a function `tokenizer` in `reader.qx`. This function will take
+* Add a function `tokenize` in `reader.qx`. This function will take
a single string and return an array/list
of all the tokens (strings) in it. The following regular expression
(PCRE) will match all mal tokens.
```
-[\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"|;.*|[^\s\[\]{}('"`,;)]*)
+[\s,]*(~@|[\[\]{}()'`~^@]|"(?:\\.|[^\\"])*"?|;.*|[^\s\[\]{}('"`,;)]*)
```
* For each match captured within the parenthesis starting at char 6 of the
regular expression a new token will be created.
* `~@`: Captures the special two-characters `~@` (tokenized).
* ```[\[\]{}()'`~^@]```: Captures any special single character, one of
- ```[]{}'`~^@``` (tokenized).
+ ```[]{}()'`~^@``` (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).
+ * `"(?:\\.|[^\\"])*"?`: Starts capturing at a double-quote and stops at the
+ next double-quote unless it was preceded by a backslash in which case it
+ includes it until the next double-quote (tokenized). It will also
+ match unbalanced strings (no ending double-quote) which should be
+ reported as an error.
* `;.*`: Captures any sequence of characters starting with `;` (tokenized).
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.
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
- need to be implemented until step 9 (but can be implemented at any
+ remaining scalar mal type, keyword does not
+ need to be implemented until step A (but can be implemented at any
point between this step and that). BTW, symbols types are just an
object that contains a single string name value (some languages have
symbol types already).
* 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
+ functions: string, nil, true, and false. Nil, true, and false
+ become mandatory at step 4, strings at step 6. 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
`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
of the binds list to the respective element of the `exprs` list.
* Add support to `printer.qx` to print functions values. A string
- literal like "#<function>" is sufficient.
+ literal like "#\<function>" is sufficient.
* Add the following special forms to `EVAL`:
Try out the basic functionality you have implemented:
- * `(fn* [a] a)` -> `#<function>`
- * `( (fn* [a] a) 7)` -> `7`
- * `( (fn* [a] (+ a 1)) 10)` -> `11`
- * `( (fn* [a b] (+ a b)) 2 3)` -> `5`
+ * `(fn* (a) a)` -> `#<function>`
+ * `( (fn* (a) a) 7)` -> `7`
+ * `( (fn* (a) (+ a 1)) 10)` -> `11`
+ * `( (fn* (a b) (+ a b)) 2 3)` -> `5`
* Add a new file `core.qx` and define an associative data structure
`ns` (namespace) that maps symbols to functions. Move the numeric
* `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.
* Define a `load-file` function using mal itself. In your main
program call the `rep` function with this string:
- "(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \")\")))))".
+ "(def! load-file (fn* (f) (eval (read-string (str \"(do \" (slurp f) \"\nnil)\")))))".
Try out `load-file`:
* `(load-file "../tests/incA.mal")` -> `9`
The `load-file` function does the following:
* Call `slurp` to read in a file by name. Surround the contents with
"(do ...)" so that the whole file will be treated as a single
- program AST (abstract syntax tree).
+ program AST (abstract syntax tree). Add a new line in case the files
+ ends with a comment. The `nil` ensures a short and predictable result,
+ instead of what happens to be the last function defined in the loaded file.
* Call `read-string` on the string returned from `slurp`. This uses
the reader to read/convert the file contents into mal data/AST.
* Call `eval` (the one in the REPL environment) on the AST returned
* Copy `step6_file.qx` to `step7_quote.qx`.
* Before implementing the quoting forms, you will need to implement
-* some supporting functions in the core namespace:
+ some supporting functions in the core namespace:
* `cons`: this function takes a list as its second
parameter and returns a new list that has the first argument
prepended to it.
Quoting is one of the more mundane functions available in mal, but do
not let that discourage you. Your mal implementation is almost
-complete, and quoting sets the stage for the next very exiting step:
+complete, and quoting sets the stage for the next very exciting step:
macros.
* `rest`: this function takes a list (or vector) as its argument and
returns a new list containing all the elements except the first.
-* In the main program, use the `rep` function to define two new
- 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)))))))"
- * `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))))))))"
+* In the main program, call the `rep` function with the following
+ string argument to define a new control structure.
+```
+"(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.
<a name="step9"></a>
* `vector?`: takes a single argument and returns true (mal true
value) if the argument is a vector, otherwise returns false (mal
false value).
+ * `sequential?`: takes a single argument and returns true (mal true
+ value) if it is a list or a vector, otherwise returns false (mal
+ false value).
* `hash-map`: takes a variable but even number of arguments and
returns a new mal hash-map value with keys from the odd arguments
and values from the even arguments respectively. This is basically
all the keys in the hash-map.
* `vals`: takes a hash-map and returns a list (mal list value) of
all the values in the hash-map.
- * `sequential?`: takes a single arguments and returns true (mal true
- value) if it is a list or a vector, otherwise returns false (mal
- false value).
<a name="stepA"></a>
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. TODO. Should be separate
- from the function macro flag.
-
* Add a new "\*host-language\*" (symbol) entry to your REPL
environment. The value of this entry should be a mal string
- containing thename of the current implementation.
+ 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* \"]\"))".
+ "(println (str \"Mal [\" \*host-language\* \"]\"))".
+* Ensure that the REPL environment contains definitions for `time-ms`,
+ `meta`, `with-meta`, `fn?`
+ `string?`, `number?`, `seq`, and `conj`. It doesn't really matter
+ what they do at this stage: they just need to be defined. Making
+ them functions that raise a "not implemented" exception would be
+ fine.
Now go to the top level, run the step A tests:
```
implementation.
-#### 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))"
-
-"(def! gensym (fn* [] (symbol (str \"G__\" (swap! *gensym-counter* (fn* [x] (+ 1 x)))))))"
-
-"(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 composite data types, symbols and native
- functions. TODO
-* Add the following new core functions:
+* Add meta-data support to composite data types (lists, vectors
+ and hash-maps), and to functions (native or not), by adding a new
+ metadata attribute that refers to another mal value/type
+ (nil by default). Add the following metadata related core functions
+ (and remove any stub versions):
+ * `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).
+ * If you implemented as `defmacro!` to mutate an existing function
+ without copying it, you can now use the function copying mechanism
+ used for metadata to make functions immutable even in the
+ defmacro! case...
+
+* Add the following new core functions (and remove any stub versions):
* `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 mal implementation performance
- benchmarks by running `make perf^quux`.
+ 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 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
function should be added in `quux/tests/stepA_mal.mal` (see the
[tests for `lua-eval`](../lua/tests/stepA_mal.mal) as an example).
-
-## TODO:
-
-* 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)
+### 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