mal (Make a Lisp)

mal is a Clojure-inspired Lisp interpreter designed as a learning tool. It provides 11 incremental, self-contained, and testable steps that demonstrate core Lisp concepts. The final step (stepA) is capable of self-hosting, meaning it can run its own implementation of mal.

The 11 steps are:

• step0_repl: The REPL
• step1_read_print: Read and print
• step2_eval: Eval
• step3_env: Environments
• step4_if_fn_do: If, fn, and do
• step5_tco: Tail call optimization
• step6_file: Files, mutation, and evil
• step7_quote: Quoting
• step8_macros: Macros
• step9_try: Try
• stepA_mal: Metadata, self-hosting, and interop

Beyond the core implementations, several community projects extend the MAL (Make A Lisp) ecosystem, including compilers, language variants, and specialized tools:

• malc: A compiler that translates Mal programs to LLVM assembly and then to binary.
• malcc: An incremental compiler implementation using the Tiny C Compiler backend. It supports macros, tail-call elimination, and run-time eval.
• frock: A Clojure-flavored PHP implementation that utilizes mal/php.
• flk: A Lisp implementation designed to run in Bash environments.
• glisp: A self-bootstrapping graphic design tool built on Lisp.
• mal2py-compiler: A MAL-to-Python compiler (a fork of the python3 implementation) that compiles Mal to Python, offering significant performance improvements on synthetic benchmarks.

In this implementation, all Mal objects are subclasses of Mal::Type. They can be treated as Perl scalar, array, or hash references depending on their type.

Metadata is managed via Hash::Util::FieldHash, allowing external metadata to be attached to objects without imposing overhead on normal object usage.

The Truffle Mal implementation is organized into steps (0 through E), where each step introduces specific Truffle-based optimizations to improve performance via partial evaluation and specialization:

• Step 0 to Step A: Avoids Truffle-specific optimizations. Step A is a 'pure' interpreter using Truffle AST nodes without specialization.
• Step B: Specializes function calls by assuming monomorphic call sites (the same function is always called).
• Step C: Optimizes and specializes environment lookups for symbols in static scope (arguments and let bindings).
• Step D: Further specializes environment lookups for closed-over environments by skipping lookups if symbols haven't been rebound.
• Step E: Specializes macro expansion, allowing macro results to replace the apply form entirely (extending Mal's macro semantics).

To run mal on RISC OS, you must first transfer the files to your system and tokenize the BASIC source files. It is recommended to use a filing system that does not truncate filenames (e.g., HostFS supplied with ArcEm).

1. Navigate to the RISC OS setup directory: *Dir bbc-basic.riscos
2. Run the setup script: *Run setup
3. Invoke the interpreter: *Run stepA_mal

Note: The slurp function currently lacks filename translation, so some example mal programs may fail to load core.mal.

For symbols that are not in the current lexical scope (such as core functions), you can further optimize performance by caching their looked-up values.

Create a Truffle Assumption for each cached lookup to represent the assumption that the symbol has not been redefined. When def! is called, invalidate the corresponding assumption. This allows the compiler to effectively eliminate the lookup overhead for frequently used global symbols.

To execute .mal scripts via a web server, build the mal-web.php entry point and create a symlink from mal-web.php to a file with a .php extension. This allows the server to treat the .mal logic as a PHP script.

Local Development Steps:

1. Build the entry point:

   cd mal/php
   make mal-web.php

2. Create a script and a symlink:

   echo '(println "Hello world!")' > myscript.mal
   ln -s mal-web.php myscript.php

3. Run a local PHP server:

   php -S 0.0.0.0:8000

4. Access the script at http://localhost:8000/myscript.php.

Live Hosting: Copy mal.php to your live server and create a symlink for each .mal file you wish to make web-executable.

While any Turing complete language can implement mal, the process is significantly easier if your chosen language supports the following features:

High Importance:

• Sequential compound data structures (arrays, lists, vectors, etc.)
• Associative compound data structures (dictionaries, hash-maps, etc.)
• Function references (first-class functions, function pointers)
• Real exception handling (try/catch, raise, throw)
• Variable argument functions (variadic, splats, apply)
• Function closures
• PCRE regular expressions

Helpful Features:

• Dynamic typing / boxed types (the ability to store different types in structures and have the language track types automatically)
• Support for arbitrary runtime "hidden" data (metadata, metatables, dynamic fields, attributes)

If your language lacks closure/anonymous function capabilities, you must implement functions using the approach intended for step5.

Functions should be treated as a normal data type that stores:

• The function body (AST)
• The parameter list
• The environment at the time the function was defined.

When a function is invoked, EVAL will evaluate these stored items rather than invoking a native language closure.

Quoting allows for meta-programming by manipulating Mal code as data.

quote

The quote special form prevents the evaluator from evaluating its argument. It simply returns the argument as-is.

quasiquote

The quasiquote special form allows for a quoted list to contain elements that are evaluated. It relies on two internal symbols:

• unquote: Turns evaluation back on for a specific argument within a quasiquoted list.
• splice-unquote: Turns evaluation back on and 'splices' the resulting list into the parent list (requires the result to be a list).

Required Core Functions

To implement quoting, you must first implement:

• cons: Prepends an element to a list.
• concat: Concatenates zero or more lists.