Nana

Nana is a toy programming language. It’s an interpreted lisp and is turing complete.

It’s implemented using ReasonML and compiles to a small native binary.

It includes only true, false, =, +, -, *, first, println, and call/cc. Also the special forms def, if, quote, and lambda.

It supports recursion, tail call optimisation, and continuations.

There’s a branch that compiles to javascript. You can try it in your browser.

Example program

(def do
  (lambda (a b)
    b))

(def count-to-5
  (lambda (c)
    (do (println c)
        (if (= c 5)
          (quote worked)
          (count-to-5 (+ c 1))))))

(count-to-5 0)

Will output

Number(0)
Number(1)
Number(2)
Number(3)
Number(4)
Number(5)
Symbol(worked)

Implementation

Nana computes by repeatedly operating on a stack of frames. Frames represent data and steps within operations and as they’re evaluated they’ll emit more frames.

This style of computation should make it fairly straight forward to implement threads and continuations. Hopefully even serialisable continuations that can be persisted or transmitted and resumed on other machines.

Perhaps the simplest example is the number 1 which evaluates to itself:

1

[Start(env, Number(1))]
[Stop(env, Number(1))]
  
Result: Number(1)

Symbols evaluate to values from the environment:

foo

[Start(env, Symbol(foo))]
[Stop(env, Number(1))]

Result: Number(1)

if statements evaluate the condition expression and then the appropriate branch:

(if true 1 2)

[Start(env, List(Symbol(if), True, Number(1), Number(2)))]
[PushBranch(env, Number(1), Number(2)), Start(env, True)]
[PushBranch(env, Number(1), Number(2)), Stop(env, True)]
[Start(env, Number(1))]
[Stop(env, Number(1))]
  
Result: Number(1)

Function application evaluates the first position to find a function, and then each of the arguments in turn before applying the function to its arguments:

(+ 2 3)

[Start(env, List(Symbol(+), Number(2), Number(3)))]
[EvalFn(env, [Number(2), Number(3)]), Start(env, Symbol(+))]
[EvalFn(env, [Number(2), Number(3)]), Stop(env, Function(Plus))]
[EvalArgs(env, Function(Plus), [], [Number(2), Number(3)])]
[EvalArgs(env, Function(Plus), [], [Number(3)]), Start(env, Number(2))]
[EvalArgs(env, Function(Plus), [], [Number(3)]), Stop(env, Number(2))]
[EvalArgs(env, Function(Plus), [Number(2)], [Number(3)])]
[EvalArgs(env, Function(Plus), [Number(2)], []), Start(env, Number(3))]
[EvalArgs(env, Function(Plus), [Number(2)], []), Stop(env, Number(3))]
[EvalArgs(env, Function(Plus), [Number(3), Number(2)], [])]
[Stop(env, Number(5))]
  
Result: Number(5)

Nested function calls work too, producing satisfying peaks and valleys:

(def repeat-once
  (lambda (should-repeat?)
    (if should-repeat?
      (repeat-once false)
      (quote done))))

[Start(env, List(Symbol(def), Symbol(repeat-once), List(Symbol(lambda), List(Symbol(should-repeat?)), List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))))))]
[AddToEnv(env, repeat-once), Start(env, List(Symbol(lambda), List(Symbol(should-repeat?)), List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))))]
[AddToEnv(env, repeat-once), Stop(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]))]
[Stop(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]))]

Result: Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))])

(repeat-once true)

[Start(env, List(Symbol(repeat-once), True))]
[EvalFn(env, [True]), Start(env, Symbol(repeat-once))]
[EvalFn(env, [True]), Stop(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]))]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], [True])]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], []), Start(env, True)]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], []), Stop(env, True)]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [True], [])]
[Start(env, List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))))]
[PushBranch(env, List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))), Start(env, Symbol(should-repeat?))]
[PushBranch(env, List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))), Stop(env, True)]
[Start(env, List(Symbol(repeat-once), False))]
[EvalFn(env, [False]), Start(env, Symbol(repeat-once))]
[EvalFn(env, [False]), Stop(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]))]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], [False])]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], []), Start(env, False)]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [], []), Stop(env, False)]
[EvalArgs(env, Lambda(env, [should-repeat?], [List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done)))]), [False], [])]
[Start(env, List(Symbol(if), Symbol(should-repeat?), List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))))]
[PushBranch(env, List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))), Start(env, Symbol(should-repeat?))]
[PushBranch(env, List(Symbol(repeat-once), False), List(Symbol(quote), Symbol(done))), Stop(env, False)]
[Start(env, List(Symbol(quote), Symbol(done)))]
[Stop(env, Symbol(done))]

Result: Symbol(done)

Development environment