kanaka/minimal

A Delightfully Diminutive Lisp. Implemented in < 1 KB of JavaScript with JSON source, macros, tail-calls, JS interop, error-handling, and more.

miniMAL

A Delightfully Dimuntive Lisp.

The miniMAL core interpreter is implemented in less than 1024 bytes of JavaScript (uglify/regpack). There is also an implementation of miniMAL in python (1.1K as a pyz file) and ClojureScript (1.8K after minification).

The design of miniMAL started with mal (a Clojure-insipred pedagogical Lisp interpreter with implementations in over eighty languages). And in fact, in the miniMAL repository you can see the incremental steps to build up the interpreter just like for each of the mal implementations. However, the syntax and functionality of miniMAL is fairly different from mal so it is a standalone project.

Even though miniMAL is tiny it is actually a very powerful Lisp with advanced features including: higher-order functions, tail-call optimization, macros, JavaScript interop, and error-handling. miniMAL is powerful enough that it has been used to create a full implementation of mal.

Usage

You can try out miniMAL with the online REPL.

Install the miniMAL binary using npm:

sudo npm install -g minimal-lisp

There are several different ways to use and/or integrate miniMAL:

• Start a REPL: run the miniMAL REPL (read-eval-print-loop). Requires Node.js.

miniMAL

• Run a miniMAL program: run a miniMAL program and then exit. Requires Node.js.

miniMAL hello.json

• As a shebang script: add a shebang line to the top of your miniMAL program and turn it into an executable script. Requires Node.js.

echo "#!/usr/bin/env miniMAL" > hello2.json
cat hello.json >> hello2.json
chmod +x hello2.json
./hello2.json

To use miniMAL as a library in another project, first install the module locally using npm:

sudo npm install minimal-lisp

• Node.js library: you can use the miniMAL Node.js library to evaluate miniMAL source code in a regular Node.js program.

var miniMAL = require('minimal-lisp'),
    m = miniMAL(global);
m.eval(["+", 2, 3]);

• Web library: you can use the miniMAL web library to evaluate miniMAL code in your web application.

<script src="node_modules/minimal-lisp/js/web/miniMAL-min.js"></script>
<script>
var m = miniMAL();
m.eval(["+", 2, 3]);
</script>

Features and Examples

• JSON source: the source code of miniMAL programs is just plain JSON (JavaScript object notation).

["+", 2, 3]
=>5
["if", ["=", 5, 5], 7, 8]
=>7
["+", 2, ["*", 3, 4]]
=>14

• "Lisp-0": Functions, symbols and strings are all in the same namespace making miniMAL a "Lisp-0". In contrast, Lisp-2 languages have functions and symbols (and strings) that are in separate namespaces. In Lisp-1 languages functions and symbols are in the same namespace (and strings are still separate). Strings in miniMAL are just quoted symbols.

["def", "a_symbol", 3]
=>3
"a_symbol"
=>3
["*", "a_symbol", 6]
=>18
["`", "a quoted symbol is a string"]
=>"a quoted symbol is a string"

• Lambdas: miniMAL has anonymous and named functions.

[ ["fn", ["a"], ["*", "a", "a"]], 8]
=>64
["def", "sqr", ["fn", ["a"], ["*", "a", "a"]]]
["sqr", 7]
=>49

• Variadic Functions: miniMAL functions/lambdas can support variable numbers of parameters using the Clojure style "&" delimeter.

["def", "drop1", ["fn", ["a", "&", "b"], "b"]]
["drop1", 1, 2, 3]
=>[2,3]

• Lexical scope and let blocks: miniMAL has full lexical scoping within let blocks and lambdas. In the following example, "add5" is defined as a function that refers to a lexicallly scoped variable "x". The "x" variable is available to the function because the definition of the function happened within same lexical scope (it is a function closure), but it is not accessible outside the "let" block lexical scope.

["def", "add5", ["let", ["x", 5], ["fn", ["a"], ["+", "x", "a"]]]]
["add5", 7]
=>12
"x"
=>__ERROR__

• First class functions/lambdas: functions/lambdas are first class values in miniMAL. They can be bound to variables, passed into and returned from functions just like normal values.

["def", "addX", ["fn", ["X"], ["fn", ["a"], ["+", "X", "a"]]]]
["def", "add9", ["addX", 9]]
["add9", 20]
=>29
["map", "add9", ["`", [2, 3, 4]]]
=>[11,12,13]

• Automatic tail call optimization (TCO): when a function calls itself (recursion) as the very last thing it does (tail call), this is automatically optimized so that the call does not consume any stack. This allows recursion to be as efficient as iteration. In this example, "sum1" is not tail optimized because an addition happens after the recursive call to "sum1". "sum2" is tail optimized by miniMAL because the recursive "sum2" call happens in tail position.

["def", "sum1", ["fn", ["n"], ["if", ["=", "n", 0], 0, ["+", "n", ["sum1", ["-", "n", 1]]]]]]
["sum1", 10000]
=>__ERROR: stack overflow__
["def", "sum2", ["fn", ["n", "a"], ["if", ["=", "n", 0], "a", ["sum2", ["-", "n", 1], ["+", "n", "a"]]]]]
["sum2", 10000, 0]
=>500500

• JavaScript Interop: miniMAL uses native JavaScript types (e.g. lists are implemented as arrays) and supports JavaScript interop using the method call function (".") and the property get/set function (".-").

["def", "randInt", ["fn", ["max"], ["parseInt", ["*", "max", [".", "Math", ["`", "random"]]]]]]
["randInt", 100]
=>16
["def", "rand-hsl", ["fn", [], ["+", ["+", ["`", "hsl("], ["randInt", 360]], ["`", ", 50%, 70%)"]]]]
["def", "set-style", ["fn", ["o", "k", "v"],  [".-",  [".-", "o", ["`", "style"]], "k", "v"]]]
["def", "by-tag", ["fn", ["tag"], [".", "document", ["`", "getElementsByTagName"], "tag"]]]
["set-style", [".-", ["by-tag", ["`", "body"]],0], ["`", "backgroundColor"], ["rand-hsl"]]
=>__background color set to random hsl value__

The following features are omitted from JS1K version of the implementation in order to make space for example code.

• Exception Handling: miniMAL supports try/catch/throw style exception handling. The thrown exceptions can be any arbitrary type.

["try", "abc", ["catch", "exc", ["list", ["`", "exc was:"], "exc"]]]
=>["exc was:","abc not found"]
["try", ["throw", 123], ["catch", "exc", ["list", ["`", "exc was:"], "exc"]]]
=>["exc was:",123]
["try", ["throw", 123], ["catch", "exc", ["list", ["`", "exc was:"], "exc"]]]
=>["exc was:",123]

• Macros: miniMAL has the ability to define macros. Macros allow a program to create new syntactic structures. When a normal function call is handled, the arguments to the function are all evaluated first before the function is called. A macro receives all its arguments unevaluated and can manipulate the raw arguments. Whatever value is returned from the macro (perhaps a re-written function call) is evaluated again. In the following example, the "unless" macro reverses the logic of the if statement. If "unless" was a defined as a regular function both of the true and false positions would all be evaluated before the "unless" function was called. However, defining "unless" as a macro allows either the true or false position to be evaluated but not both .

["def", "unless", ["~", ["fn", ["p", "a", "b"], ["list", ["`", "if"], "p", "b", "a"]]]]
["unless", false, 7, 8]
=>7
["unless", true, 7, 8]
=>8

Rationale

I originally started implementing a tiny Lisp interpreter as a quick hack to submit to the 2015 JS1K competition (demo 2209). However, I soon realized that I could fit far more functionality into 1024 bytes of JavaScript than I expected and so miniMAL was born as a "full-fledged" Lisp in its own right.

License

miniMAL is licensed under the MPL 2.0 (Mozilla Public License 2.0). See LICENSE for more details.

minimal's Issues

Questions about license/copyright of miniMAL specifications

Hello.

I'm trying to develop another implementation for miniMAL language
adding some more features, not using your original source code except unit tests.

Questions:

1. Is there any license or copyright as if miniMAL's langage SPECIFICATIONS?
   • Of course I know your miniMAL IMPLEMENTATION is distributed undef MPL 2.0.
2. Is there any limitations to publish my miniMAL implementation to NPM
   under MIT license?
3. Can I still call or name my implementation as `miniMAL' language?
   My implementation will not be small as your awesome code, but
   trying to pass most of unit tests (which are converted to Jest format).
4. Can I refer your web pages from my documents?

Regards,

////
Note: I've also sent a e-mail to to your address written
on https://github.com/kanaka. You might get some more
detail about my plan if you have any chance to check the
mail.

Feature request: Ability to control side effects

I would very much like to be able to control the environment that miniMAL instructions can execute in. The ability to set miniMAL({}) does not prevent access to the whole of JS, including the dangerous global function eval.

Being able to have control, or prevent any crazy stuff potentially executing from a miniMAL program, would enable this library to be used for user customizable dynamic rules, like access rules, event rules etc, that can be stored as JSON in a database.

I guess that some second argument to miniMAL() preventing just the "js" feature, would do most of the trick? (But there would probably be a more general way to do it)

Not able to run miniMAL as a library

I only get:

TypeError: Object prototype may only be an Object or null: undefined

when running node test.js.
Where test.js is:

const miniMAL = require('minimal-lisp');
const m = miniMAL();
m.eval(["+", 2, 3]);

Parser?

Seems like it would be (reasonably) trivial to write a parser for Lisp code (that was Lisp-0 compliant anyhow) by a simple regex.

Someone on Hacker News mentioned this for python:

`def parse(s): return json.loads('['+re.sub('([")])\s*(["(])','\g<1>,\g<2>',re.sub('[^()\s]+','"\g<0>"',s)).replace('(','[').replace(')',']')+']')``

Seems like most of that should go 1-to-1 into a JSON regex (as naive as it is).

Just a thought....

Modulus?

Is there a good reason why modulus ("%") is not among the available operators?

Should it be, or is there an easy way around it?