Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

narju

narju is a lisp whose evaluator is written in itself and handed to every procedure as an ordinary value. it descends from Nada Amin and Tiark Rompf’s Collapsing Towers of Interpreters, and from the 3-lisps before that.

this book assumes lisp. it covers what narju has that your lisp does not.

the interpreter is a value. (interp-of f) gives the semantics f runs under, an association list of handlers. (with-interp f m) rebuilds f under different semantics. reflection, tracing, sandboxing and stage control are all written on those two.

there is no level counter. a level is a closure chain. a handler that is itself an object closure gets interpreted by the interpreter it closed over, and the regress bottoms out at the compiled floor. going up a level is calling a function.

compilation is a form. clambda is lambda that compiles its body against the semantics in force. the reflective machinery stages away, leaving no interpretive overhead and no tower.

tasks are the concurrency. BEAM-style: heaps, mailboxes, turn budgets, monitors, supervisors. a task’s semantics is a field of its closure, so two tasks in one world can be running different languages.

the outside world is a peer. stdout, the clock, the filesystem and the network gate are addresses of the shape ('host stdout). there is no i/o primitive.

the floor underneath is λ↑↓, the stage-polymorphic language from the Collapsing Towers paper, written in rust in src/floor/. naj/tower.naj, naj/prelude.naj and naj/repl.naj are object programs it runs.

read the four parts in order the first time. staging leans on semantics-as-a-value, and the concurrency chapters lean on both.

no example here is checked by the build. each was run through naj while writing; if one has rotted, trust the binary.

Getting started

$ nix run git+https://git.avery.garden/thorn/narju

naj with no argument is the prompt, naj FILE runs a file and exits. the other forms are naj --lock, which resolves naj.deps into naj.lock (see Modules), and --modules DIR, which says where fetched modules live.

narju> (+ 1 2)
3

narju> (define (double n) (* n 2))
'double

narju> (map double '(1 2 3))
(2 4 6)

the prompt is naj/repl.naj, an object program running as a task with its environment as task state. hence a definition surviving to the next line, and a throw not killing the session.

Surface

lambda, let, if, quote, cond, case, and, or, begin, define, quasiquote. lambda takes an optional self name before the parameter list, so recursion needs no letrec:

narju> ((lambda loop (n) (if (eq? n 0) 'done (loop (- n 1)))) 3)
'done

falsity is 0 and '(). everything else is true, including "". predicates answer 1 or 0.

narju> (if 0 'a 'b)
'b

narju> (if '() 'a 'b)
'b

let destructures, and a pattern that does not match throws:

narju> (let (((a b . rest) '(1 2 3 4))) (list a b rest))
(1 2 (3 4))

there is no print. say sends a line to the stdout capability:

narju> (say (list 1 "two" 'three))
(1 "two" 'three)
'ok

the 'ok is the value of say itself, which the prompt shows like any other.

A file

; hello.naj
(define (fib n)
  (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))

(say (fib 20))

$ naj hello.naj
6765

a file’s definitions nest into the body that follows them, so a file is one expression and there is no top level.

a world stays alive while any task can still run, so a script that spawns a server and never stops it does not exit. see Tasks and messages.

Interpreters are values

an interpreter is an association list from handler name to handler:

narju> (map car (interpreter))
('base-eval 'eval-lit 'eval-var 'eval-quote 'eval-if 'eval-lambda 'eval-rlambda 'eval-clambda 'eval-let 'eval-import 'eval-args 'eval-app)

twelve entries, and that is the whole language. base-eval dispatches on the shape of a form and calls one of the others. every handler has the same arity:

(lambda h (m l e r k) ...)

m is the interpreter itself, l the stage dictionary, e the form, r the environment, k the continuation. m being an argument is the entire trick: a handler does not look up its evaluator in a global, it was handed one.

interp-of and with-interp

a closure carries the interpreter in force where it was written. interp-of reads that field, with-interp rebuilds the closure with a different one:

(define (inc n) (+ n 1))

(define (shifted i)
  (with-handler i 'eval-lit
    (lambda h (m l e r k) (apply-cont k ((l 'lift) (+ e 10))))))

(say (inc 0))
(say ((with-interp inc (shifted (interp-of inc))) 0))
(say (inc 0))

1
11
1

inc did not move. a change of semantics is a new closure, so everything else in scope still means what it meant.

with-handler conses the new entry onto the front rather than replacing, so the shadowed one is still reachable through handler-of. that is how to wrap instead of replace:

(define (traced i)
  (with-handler i 'eval-app
    (lambda h (m l e r k)
      (begin (say (car e))
             ((handler-of i 'eval-app) m l e r k)))))

(define (add a b) (+ (* a 2) b))

(say ((with-interp add (traced (interp-of add))) 3 4))

'+
'*
10

The boundary is the closure

(define (helper x) (* x 2))
(define (add a b) (+ (helper a) b))

(say ((with-interp add (traced (interp-of add))) 3 4))

'+
'helper
10

the trace names helper and stops. helper was written under the base interpreter and carries it, so applying it switches back. an alteration covers exactly the closure that was rebuilt, and spreading it means rebuilding the callees too.

interpreter and environment

both are reflective procedures, so they take no arguments and answer something about the call site:

narju> (length (interpreter))
12

narju> (length (environment))
3

narju> (eval-in (environment) '(+ 1 2))
3

eval without a magic global environment. the environment is a value obtained from somewhere, and without one there is nothing to evaluate in.

What is built on this

(define (with-handler i name h) (cons (cons name h) i))
(define (spawn-with mut f) (spawn (with-interp f (mut (interp-of f)))))
(define (become mut state) `(become ,mut ,state))

spawn-with starts a task whose semantics is (mut I) for the I that f was written under, so the child forks rather than shares. become does the same to a running task between turns. neither needed a primitive.

Reflective procedures

a reflective procedure is written (lambda reflect (m l e r k) body). it is applied to its own call site rather than to values: the five things a handler gets, except that e is the list of operand forms, unevaluated.

(define twice
  (lambda reflect (m l e r k)
    (meta m l 'base-eval (car e) r
          (cont-in k (lambda (v) (apply-cont k (+ v v)))))))

(say (twice (+ 1 2)))

6

meta evaluates something: interpreter, stage, handler name, form, environment, continuation. cont-in k f builds a continuation whose normal arm is f and whose raise arm is k’s. apply-cont k v hands v to the call site.

never evaluating the operand gives a macro, near enough:

(define quoted (lambda reflect (m l e r k) (apply-cont k (car e))))

(say (quoted (+ 1 2)))

('+ 1 2)

except that this is not a rewriting pass. it runs at the meta level when the call is reached, with the environment and continuation in hand, neither of which a macro can see.

Not calling k

the normal arm of a reflective body’s continuation is the identity, not k. a body that returns without going through apply-cont returns to the nearest prompt instead of to the call site:

(define bail (lambda reflect (m l e r k) (car e)))

(say (prompt (lambda () (+ 1 (bail this-is-syntax)))))

'this-is-syntax

the (+ 1 _) is gone. that is abort, which in the prelude is exactly this:

(define abort
  (lambda reflect (m l e r k)
    (meta m l 'base-eval (car e) r id-cont)))

What is built this way

none of the following is a special form. all are naj/prelude.naj.

(define call/cc
  (lambda reflect (m l e r k)
    (meta m l 'base-eval (car e) r
          (cont-in k (lambda (f) (apply l f (list k) k))))))

narju> (call/cc (lambda (k) (+ 1 (k 41))))
41

narju> (+ 1 (call/cc (lambda (k) 41)))
42

prompt delimits by applying its thunk under id-cont rather than the caller’s k. it must be reflective for that: an ordinary function would already be running under the continuation it means to delimit.

attempt runs a thunk under a continuation whose two arms tag their answers:

narju> (attempt (lambda () (+ 1 (throw 'boom))))
('throw . 'boom)

narju> (attempt (lambda () (+ 1 2)))
('ok . 3)

await reifies the call site and hands it to whoever runs the prompt, which is how an RPC suspends a task without blocking a thread. see Calls and replies.

(define interpreter (lambda reflect (m l e r k) (apply-cont k m)))
(define environment (lambda reflect (m l e r k) (apply-cont k r)))

Second class

a reflective procedure handles a call site, so it needs one. in operator position eval-app sees the tag and routes to apply-reflective before evaluating operands. reached any other way, by a floor application or from compiled code, there is no syntax to hand it and static-apply throws ('no-call-site . f).

this is the one thing compiling does not preserve. by the time compiled code applies an operator the operands are values and the tag is gone, so a reflective call site inside a clambda resolves while staging or not at all.

The tower

naj/tower.naj is 572 lines of narju that evaluates narju. it is CPS, so a continuation is an ordinary value, which is what lets call/cc hand one to an object procedure without machinery.

value = number | symbol | nil | pair | floor closure | code
      | ('clo self param body env . m)
      | ('rclo params body env . m)
      | ('cfun . f)
      | ('cont f . h)
env   = list of frames, a frame an immutable assoc list
m     = assoc list from handler name to handler
l     = concrete-l, or (staged-l frames)

Dispatch

everything goes through one function:

(define (meta m l name e r k)
  (let ((h (mget m name)))
    (if (has-tag? h 'clo)
        (meta (clo-m h) concrete-l 'base-eval (clo-body h)
              (clo-frame h (list m l e r k))
              (cont-in k (lambda (v) v)))
        (h m l e r k))))

two arms. a floor closure is applied. an object closure needs interpreting, and the interpreter it gets is (clo-m h), the one it closed over.

that is the entire tower. there is no level counter in this repository. a level exists where somebody wrote a handler in the object language, and the regress terminates where handlers stop being object closures.

Two levels, visibly

(define (shifted i)
  (with-handler i 'eval-lit
    (lambda h (m l e r k) (apply-cont k (+ e 10)))))

(define (bump m l e r k) (apply-cont k (+ e 100)))

(define lvl1
  (with-handler (interpreter) 'eval-lit
                (with-interp bump (shifted (interp-of bump)))))

(define (f) 1)
(say ((with-interp f lvl1)))

111

from the inside out: f’s body is the literal 1, evaluated by bump, which answers (+ e 100). bump is an object closure written under shifted, so its literals get ten added and its 100 is a 110.

Open recursion

(define (eval-if m l e r k)
  (meta m l 'base-eval (cadr e) r
        (cont-in k (lambda (c)
                     (if c
                         (meta m l 'base-eval (caddr e) r k)
                         (meta m l 'base-eval (cadddr e) r k))))))

nothing here names base-eval’s definition. it names the entry in whatever dictionary it was handed, which is why shadowing one entry changes the meaning of every form that reaches it.

the three simplest handlers are worth reading for what they omit:

(define (eval-lit m l e r k) (apply-cont k e))
(define (eval-var m l e r k) (apply-cont k (env-get r e)))
(define (eval-quote m l e r k) (apply-cont k (cadr e)))

no mention of staging. an evaluator written over floor operations is stage-polymorphic without saying so, because what belongs in a residual is decided by the values an operation meets. l is there for the handlers that want to override that, and most do not.

What the file exports

(lambda (sel)
  (cond ((eq? sel 'eval) ...)
        ((eq? sel 'compile) ...)
        ((eq? sel 'task) ...)
        ((eq? sel 'm) base-m)
        ((eq? sel 'env) base-env)
        (else (throw (cons 'no-export sel)))))

eval and compile differ in one argument, concrete-l against (staged-l '()). compiling is the same evaluator started in the other stage state. task is that again with the task’s own address bound to self.

clambda

clambda has lambda’s shape and compiles its body against the semantics in force. it answers a floor closure under a tag:

narju> (clambda f (n) (+ n 1))
('cfun . #<closure>)

narju> ((clambda f (n) (* n 2)) 21)
42

the tag matters at a call site and nowhere else. the base environment binds the primitives to floor closures too, and a call site treats the two oppositely: a primitive handed code unfolds into it, a compiled function is called. nothing in the value says which, so clambda says it.

it is an annotation, not a restriction. the same body works either way and callers cannot tell which they got.

(define ifib (lambda fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))
(define cfib (clambda fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2))))))

(ifib 22) takes about eight seconds here, (cfib 22) about thirty milliseconds. an interpreted call allocates a frame per level per step, and compiling removes every level between the body and the floor.

What happens to the tower

everything reflective in a compiled body resolves while staging:

(say ((clambda f (n) (+ 1 (call/cc (lambda (k) (+ 100 (k n)))))) 5))

6

the call/cc, the escape and the abandoned (+ 100 _) are gone. the residual is (+ 1 n).

the flip side: an operator that only becomes reflective at run time cannot be recovered, and static-apply throws ('no-call-site . f). that is the whole of what compiling does not preserve.

Interpreted callees get inlined

a call from a compiled region into an interpreted closure unfolds the callee into the code being emitted:

(let ((g (lambda g (x) (+ x 1))))
  (say ((clambda f (n) (g (g n))) 1)))

3

the emitted body is two additions. g is not called at run time.

which is fine until the callee recurses:

(say (attempt (lambda ()
  (let ((g (lambda g (x) (if (< x 1) 0 (g (- x 1))))))
    (clambda f (n) (g n))))))

('throw 'inlines-forever 'g)

unfolding would not stop, so it is refused rather than attempted. the check is not a depth limit. it looks for the same closure reached with statically equal arguments, which is exactly when the next unfolding cannot differ from this one, so a recursion whose static arguments do change still unfolds. that case is the one worth having: an interpreter staged against a static program is precisely it.

a cycle through several functions names them all:

('inlines-forever 'g 'h)

Compiled callees get called

(define down (clambda down (n) (if (< n 1) 0 (down (- n 1)))))
(define go (clambda go (n) (down n)))
(say (go 5))

0

a call to a compiled function is emitted, not unfolded, so its recursion is its own business. the two ways down can reach the call site emit the same thing: staged in the same region as its caller it is still code, and already run it is a cfun reached through a reference. either way go’s residual is one call.

a self-call never needs any of this. lift-fun binds the function’s own name to a code variable before the body is staged, so recursion residualizes as a call by construction.

Static data still unfolds

(let ((walk (lambda walk (xs n)
              (if (nil? xs) n (walk (cdr xs) (+ n 1))))))
  (clambda f (n) (walk '(1 2 3) n)))

the list is known while compiling, so walk runs three times at staging time and the residual is three additions with no list in it. this is the Futamura direction: a general procedure plus static data becomes a specialised one.

What a residual carries

the prompt will not show a residual. clambda runs the code it emitted, so what comes back is ('cfun . #<closure>). to see the code, use the rust API Tower::compile, which stops one step earlier. the shapes below are the assertions in src/tower.rs.

(clambda f (n) (+ n 1))
  =>  (let (lambda (let (+ x1 1) x2)) x0)

floor code in A-normal form. every intermediate is let-bound and named positionally: x0 is the lambda, x1 its parameter, x2 the sum.

arity is preserved rather than curried:

(clambda g (a b) (+ (* a b) 1))
  =>  (let (lambda/2 (let (* x1 x2) (let (+ x3 1) x4))) x0)

recursion comes out as a call to x0, the function’s own residual variable:

(clambda fib (n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
  =>  (let (lambda (let (< x1 2)
        (let (if x2 x1
          (let (- x1 1) (let (x0 x3)
          (let (- x1 2) (let (x0 x5)
          (let (+ x4 x6) x7)))))) x3))) x0)

It carries its semantics

a residual is the meaning of the body under the interpreter in force when it was compiled, and that meaning is baked in:

(define (mk) (clambda f (n) (+ n 1)))

(define (marked i)
  (with-handler i 'eval-lit (lambda h (m l e r k) (apply-cont k (+ e 100)))))

(say ((mk) 1))
(say (((with-interp mk (marked (interp-of mk)))) 1))
(say ((mk) 1))

2
102
2

under the marked interpreter the literal 1 was worth 101 while compiling, and the addition that made 101 left nothing behind:

compiled under base    (let (lambda (let (+ x1 1) x2)) x0)
compiled under marked  (let (lambda (let (+ x2 101) x3)) x1)

changing the interpreter afterwards does nothing to code already emitted.

Putting something in on purpose

(l 'lift) forces a value into the residual that nothing at the site would have put there. under concrete-l it is the identity, under (staged-l _) it lifts:

(lambda h (m l e r k) (apply-cont k (+ e ((l 'lift) 100))))

(let (lambda (let (+ 1 100) (let (+ x1 x2) x3))) x0)

the 100 is now in the emitted code, so (+ 1 100) is a run-time addition. the same handler without the lift folded it away.

Cross-stage persistence

a value that exists at staging time and is needed at run time crosses by reference, never by structure. that is lift-ref, and it is the only crossing that works for everything: a closure crosses intact and keeps its identity, where lifting would try to expand it, and an interpreter cannot be expanded at all.

it shows up in the residual for a call whose operator is unknown:

(clambda f (g n) (g n))
  =>  (let (lambda/2 (let (cons x2 ())
        (let (#<closure> #<closure> x1 x3 #<('cont #<closure> . #<closure>)>) x4))) x0)

code? said the operator is unknown, not that it is applicable, so the dispatch itself is emitted. those #<closure> operands are static-apply, concrete-l and id-cont, persisted by reference. the site then works for any representation the operator turns out to have:

(say ((clambda f (g n) (g n)) (lambda h (x) (+ x 1)) 5))
(say ((clambda f (g n) (g n)) (clambda h (x) (+ x 1)) 5))
(say ((clambda f (g n) (g n)) car (cons 1 2)))

6
6
1

interpreted, compiled, floor primitive. one call site, and the answer does not depend on which arrives. deciding at run time is what makes clambda an annotation: the callee names its own semantics in clo-m, so an alteration made after the caller was compiled is still seen.

What cannot cross out

a compiled region builds structure fine:

(say ((clambda f (n) (cons (cons n n) n)) 1))
(say ((clambda f (n) "hi") 1))

((1 . 1) . 1)
hi

a closure it made is another matter:

(say (attempt (lambda () (clambda f (n) (lambda g (x) (+ x n))))))

('throw 'unreturnable . 'closure)

the closure captured a code variable, so it means something only inside the region that emitted it. letting it out would let a residual variable escape its binder. ('unpersistable . 'pair) is the same refusal for structure built the wrong side of the boundary.

Errors are values

throw takes any value. there is no error type and no condition hierarchy:

narju> (attempt (lambda () (throw 3)))
('throw . 3)

narju> (attempt (lambda () 3))
('ok . 3)

attempt tags because a thrown 3 and a returned 3 are the same value.

the built-in failures are pairs of a symbol and whatever detail there was:

narju> (attempt (lambda () (car 'nope)))
('throw 'wrong-type . 'car)

narju> (attempt (lambda () (assert (< 2 1) 'ordering)))
('throw 'assert-failed . 'ordering)

narju> (attempt (lambda () (check 'sum (+ 1 1) 3)))
('throw 'check-failed 'sum 2 3)

matching on one is tagged? and cdr:

(let ((r (attempt (lambda () (throw '(no-such-key . b))))))
  (if (tagged? r 'throw) (cdr r) 'fine))

('no-such-key . 'b)

Two arms

a continuation is ('cont f . h): what to do with a value, and what to do with what a raise carried.

(define (cont f h) (cons 'cont (cons f h)))
(define (cont-in k f) (cont f (cont-raise k)))

cont-in inherits the raise arm unchanged, so the arms behave like a stack without one existing. a raise walks the object-level continuation chain as an ordinary value.

if the floor unwound instead, a protected region would be delimited by floor frames and a computation inside one could not suspend. since a task suspends on every RPC, that would make attempt and call mutually exclusive:

(define attempt
  (lambda reflect (m l e r k)
    (meta m l 'base-eval (car e) r
          (cont-in k
                   (lambda (th)
                     (apply l th '()
                            (cont (lambda (v) (apply-cont k (cons 'ok v)))
                                  (lambda (v) (apply-cont k (cons 'throw v))))))))))

both arms continue into k, so attempt protects without delimiting. prompt delimits without protecting:

narju> (attempt (lambda () (prompt (lambda () (throw 'through)))))
('throw . 'through)

a continuation captured outside an attempt still works from inside one:

(say (call/cc (lambda (k)
  (attempt (lambda () (+ 1 (k 'escaped)))))))

'escaped

Uncaught

a raise nobody catches ends the task. in a script that is the exit:

(say 'before)
(throw '(gave-up 7))

'before
naj: task 0 failed: ('throw 'gave-up 7)
$ echo $?
1

at the prompt it is shown and the session continues, because naj/repl.naj wraps each line in attempt and prints ('error . v). a decision the repl made, not a language rule.

Across a message

a task that refuses a request sends ('throw . why) back, and call re-raises it in the caller, so an RPC failure is caught like a local one:

narju> (attempt (lambda () (call t '(get b))))
('throw 'no-such-key . 'b)

(define (refuse req why) (reply req (cons 'throw why)))

what a task does when a peer dies is a different question, there being no continuation to raise into. see Supervision.

Tasks and messages

narju schedules like the BEAM. tasks have their own heap, a mailbox, a turn budget and an address. the scheduler is src/sched.rs; the object language gets six primitives and builds the rest in the prelude.

(spawn f)          start a task running (f addr), answer its address
(spawn-monitor f)  the same, and watch it, in one step
(send to msg)      put a message in a mailbox
(receive)          take the next one, blocking the task if empty
(monitor to)       ask to be told when `to` ends
(limit-turns t n)  cap how long one of t's turns may run
self               this task's address, bound by the scheduler

self is a name the scheduler puts in scope, not a procedure:

narju> self
#<task 0>

The raw loop

receive blocks the task, not a thread. an empty mailbox is the only reason a task ever blocks, which is what makes deadlock analysis tractable.

(define echo
  (spawn (lambda (me)
           (task-loop me
                      (lambda h (n msg)
                        (if (eq? msg 'done)
                            (cons 'stop n)
                            (begin (say (list 'got msg)) (+ n 1))))
                      0))))
(send echo 'hello)
(send echo '(structured 1 2))
(send echo 'done)

('got 'hello)
('got ('structured 1 2))

task-loop is the prelude’s dispatch loop. it takes the task’s own address, a handler and an initial state. the handler answers with the next state, or with one of:

('stop . v)          end the task with v
(become mut state)   go on with the semantics (mut I) instead
(hand handler state) go on with a different handler entirely

the loop owns the only prompt in a task, which is what makes call work. see Calls and replies.

Messages are data

a message must be a value the scheduler can copy between heaps. a closure is not:

(define r (attempt (lambda () (send self (lambda (x) x)))))
(say (list (car r) (verb (cdr r))))

('throw 'not-data)

do not say that raise value in full. it carries the offending closure, and printing a closure prints its captured environment, which is the entire prelude.

an address is copyable and a closure is not, so behaviour crosses a task boundary as a name to send to, never as code to run. it is the same restriction that lets an address be rewritten when it crosses a network link.

Deaths

monitor asks to be told, and the telling is a message:

(define kid
  (spawn-monitor (lambda (me)
                   (task-loop me (lambda h (s msg) (cons 'stop 'finished)) '()))))
(send kid 'go)
(say (receive))

('task-down #<task 1> 'ok . 'finished)

a task that raised says so instead:

('task-down #<task 2> 'throw . 'oops)

('ok . v) or ('throw . v), the same pair attempt answers with. a task is the outermost protected region and its exit is that region’s result.

spawn and monitor as separate steps would leave a window where the child dies before the watch lands, and the monitor then reports noproc about a task that had something to say. spawn-monitor is one scheduler step for that reason.

Turn budgets

a turn that never ends is not a hang, it is a ('throw . 'unresponsive):

(define greedy
  (spawn-monitor (lambda (me) ((lambda spin (n) (spin (+ n 1))) 0))))
(limit-turns greedy 1)
(send greedy 'go)
(say (receive))

('task-down #<task 1> 'throw . 'unresponsive)

the limit is imposed by whoever spawned the task rather than chosen by it, since what it catches is a task that cannot be trusted to report on itself.

Two tasks, two languages

a task’s semantics is a field of the closure it runs, so spawn-with starts one under altered semantics without touching the spawner’s:

(define (body me)
  (task-loop me
             (lambda h (n msg)
               (if (eq? (verb (req-body msg)) 'stop)
                   (begin (reply msg n) (cons 'stop n))
                   (begin (reply msg (+ n 1)) (+ n 1))))
             0))

(define (shifted i)
  (with-handler i 'eval-lit
    (lambda h (m l e r k) (apply-cont k (+ e 10)))))

(define plain (spawn body))
(define odd (spawn-with shifted body))
(say (call plain '(add)))
(say (call odd '(add)))

1
21

same source, two languages. the odd one starts at 10 because its 0 is a 10, and adds 11 because its 1 is an 11.

an alteration this blunt needs care. case desugars to (if (eq? ...) 1 0), and under shifted that 0 is a 10, which is true. the odd task above uses if for that reason.

When a world ends

a world runs until no task can make progress. a script that spawns a server and never stops it does not exit, it parks, so examples that terminate all stop what they started.

a task that ended by raising is reported at exit and makes naj exit 1, even if somebody was monitoring it and dealt with it:

naj: task 1 failed: ('throw . 'oops)

Calls and replies

(define (call to msg) (await (cons to msg)))

that is the whole request half. await reifies the call site’s continuation and hands it to whoever is running the prompt, as ('await to body k). the dispatch loop is running the prompt, so what it gets back from a turn is either the turn’s answer or a suspended call.

nothing blocks. the loop sends ('req me id body), records (id to . k) and goes back to receive. when ('reply id v) lands it resumes k with v.

(define counter
  (spawn (lambda (me)
           (task-loop me
                      (lambda h (n msg)
                        (case (verb (req-body msg))
                          ((bump) (begin (reply msg (+ n 1)) (+ n 1)))
                          ((read) (begin (reply msg n) n))
                          ((stop) (begin (reply msg 'bye) (cons 'stop n)))
                          (else (begin (refuse msg (bad-request (req-body msg))) n))))
                      0))))

(say (call counter '(bump)))
(say (call counter '(bump)))
(say (call counter '(read)))
(say (attempt (lambda () (call counter '(frobnicate)))))
(say (call counter '(stop)))

1
2
2
('throw 'bad-request 'frobnicate)
'bye

the server side is three accessors and two senders:

(define (req-from r) (cadr r))
(define (req-id r) (caddr r))
(define (req-body r) (cadddr r))
(define (reply req v) (send (req-from req) `(reply ,(req-id req) ,v)))
(define (refuse req why) (reply req (cons 'throw why)))

a reply is an ordinary message, so it need not come from the callee, or during the turn that received the request, or from a task at all:

((slow) (begin (send '(host clock)
                     `(after 20 ,(req-from msg) (reply ,(req-id msg) later)))
               n))

narju> (call server '(slow))
'later

the clock replied. the caller cannot tell.

A reply that is a failure

('throw . why) as a reply raises at the call site, which is what makes a refused request fail in the caller like a local error. the cost: you cannot return the pair ('throw . v) as data across an RPC. wrap it if you mean it.

One turn at a time

while a call is outstanding the loop still receives, but anything that is not its reply goes to a backlog and waits. a second turn started beside a suspended one would work from the state the suspended one still means to update, and whichever finished last would silently overwrite the other.

the backlog is read before the mailbox, so a message that has already waited once is not overtaken by one that just arrived.

to serve while a call is outstanding, put a different task’s state at stake:

(define f (future slow '(work)))
(say 'not-waiting-yet)
(say (call f '(read)))

'not-waiting-yet
42

future spawns a task that makes the call and then becomes a reference holding the answer. a future never ends on its own, so a program that must exit should not leave one parked.

When a call cannot be answered

the callee dying is not a hang. the loop monitors any address it calls, one monitor per callee, and turns the death into a raise at the call site:

(define dies
  (spawn (lambda (me) (task-loop me (lambda h (s msg) (throw 'nope)) '()))))
(say (attempt (lambda () (call dies '(hi)))))

(define gone (spawn (lambda (me) 'ok)))
(say (attempt (lambda () (call gone '(hi)))))

('throw 'callee-down #<task 1> 'throw . 'nope)
('throw 'callee-down #<task 2> 'ok . 'ok)
naj: task 1 failed: ('throw . 'nope)

the second finished normally rather than raising, and the caller is told which. the exit pair is carried whole, so callee-down says what a monitor would.

a callee that was already gone before the watch was armed answers ('throw . 'noproc) in that position, there being no exit left to report. the watch is armed before the request is sent, since the other order leaves a window where the monitor reports noproc about a task that died with something to say.

Timeouts

(call-within 50 slow '(anything))

('throw . 'timeout)

this arms a clock timer carrying the same id the real reply would, so whichever arrives second is dropped by the path a duplicate reply already takes.

giving up is not cancelling. the callee is still working and its eventual reply is discarded. nothing here can stop a task that is not listening.

Calling yourself

(call self '(anything))

naj: task 0 failed: ('throw 'self-call 'anything)

a deadlock, refused rather than parked, since parking would look like a peer taking its time. attempt around it does not help: the throw happens in the loop after the turn suspended, not inside the turn, so there is no protected region left to catch it.

Supervision

supervise is a task-loop with a particular handler, and that handler with its helpers is seventy lines of the prelude. there is no supervisor behaviour in the scheduler.

(define (supervise me specs)
  (task-loop me (lambda h (st msg) (supervisor-turn st msg)) (start-all specs)))

a spec is (id limit . make), dotted, where make is the procedure a task runs. a list of one spec is written:

(list (cons 'w (cons 2 worker)))

children start when the supervisor does, so a tree is running as soon as its root is.

(define (worker me)
  (task-loop me
             (lambda h (n msg)
               (let ((ask (req-body msg)))
                 (case (verb ask)
                   ((ping) (begin (reply msg 'pong) n))
                   ((die) (begin (reply msg 'ok) (throw 'sad)))
                   ((stop) (begin (reply msg 'ok) (cons 'stop 'ok)))
                   (else (begin (refuse msg (bad-request ask)) n)))))
             0))

(define sup (spawn (lambda (me) (supervise me (list (cons 'w (cons 2 worker)))))))
(say (call sup '(which-children)))
(define w (call sup '(child w)))
(say (call w '(ping)))
(say (attempt (lambda () (call sup '(child nope)))))
(say (call w '(stop)))

(('w . #<task 2>))
'pong
('throw 'no-such-child . 'nope)
'ok

a supervisor answers ('which-children) and ('child id). it answers by id because a restart is a new task and so a new address: the id is what makes a restarted child the same child.

Transient, and only transient

a child that raised is started again. a child that returned did what it was for and is not. that is OTP’s transient strategy, and the only one of the three that needs no extra field, since the exit pair already says which happened.

(define sup (spawn (lambda (me) (supervise me (list (cons 'w (cons 1 worker)))))))
(define w (call sup '(child w)))
(call w '(die))
(define w2 (call sup '(child w)))
(say (list 'was w 'now w2))
(say (call w2 '(ping)))

('was #<task 2> 'now #<task 3>)
'pong

a restart is a fresh (make me), so initial state comes back from the spec. there is no snapshot anywhere.

spend the budget and the supervisor gives up and stops, which anyone calling the child learns about the usual way:

(call w2 '(die))
(say (attempt (lambda () (call sup '(child w)))))

('throw 'callee-down #<task 1> 'ok 'give-up 'w 'throw . 'sad)

the supervisor exited ('ok . ('give-up 'w ('throw . 'sad))), naming the child and what it died of. a supervisor with no children left also stops.

naj reports any task that ended by raising, so a script exercising restarts exits 1 even when the supervisor handled everything correctly.

Limits

the limit field is a count of restarts left, or a rate (n . ms):

(cons 'w (cons 2 worker))                ; two restarts, ever
(cons 'w (cons (cons 3 1000) worker))    ; three per second

the count is the default because it needs no clock, and a tree built out of counts runs in a world that registers no ('host clock) peer at all. see Host capabilities.

Trees

a supervisor is a task, so a supervisor’s child can be a supervisor:

(define (branch me) (supervise me (list (cons 'a (cons 1 worker)))))
(define root (spawn (lambda (me) (supervise me (list (cons 'b (cons 1 branch)))))))

(define b (call root '(child b)))
(define a (call b '(child a)))
(say (call a '(ping)))
(call a '(stop))

'pong

nothing special happens for the nested case. branch is a procedure of one address, which is all start-child wanted.

Spawn and watch are one step

(define (start-child id limit stamps make)
  (list id (spawn-monitor make) limit stamps make))

written as two steps, a turn ending between them would let the child die before the watch landed, and the supervisor would be told noproc instead of what actually happened.

Stock handlers

the prelude ships four handlers to hand a task. only two of them answer ('stop): a table and a greeter do, a ref and a future do not, and a task running one never ends on its own. that is why the examples below are at the prompt. a script that spawns a ref and finishes parks rather than exits.

ref

the object language has no mutable cell. a ref stands in its place: the state is a task’s and the name for it is an address.

narju> (define r (spawn (lambda (me) (ref me 0))))
'r

narju> (call r '(read))
0

narju> (call r '(write 7))
'ok

narju> (call r '(read))
7

not a cell with extra steps. it crosses a network link unchanged, it can be monitored, and a write to one that has died raises rather than succeeding quietly against nothing.

there is deliberately no update-by-function. a closure cannot be sent, which puts read-modify-write out of reach of one message, and two messages are not atomic against another caller. an operation that must be atomic belongs in the task’s own handler.

table

(define t (spawn (lambda (me) (table-at me '()))))
(say (call t '(put a 1)))
(say (call t '(get a)))
(say (call t '(keys)))
(say (attempt (lambda () (call t '(get b)))))
(say (call t '(drop a)))
(say (call t '(keys)))
(say (call t '(stop)))

'ok
1
('a)
('throw 'no-such-key . 'b)
'ok
nil
'ok

put also works as a cast, so a task can add itself to a table without making a call.

greeter

a table with a rendezvous protocol on top, meant for task 0 of a node. it is the one thing a peer arriving over a link cannot do for itself: turn a name into an address.

narju> (define hall (spawn (lambda (me) (greet me '()))))
'hall

narju> (define r (spawn (lambda (me) (ref me 'hello))))
'r

narju> (call hall (list 'register 'store r))
'ok

narju> (call hall '(names))
('store)

narju> (call (call hall '(lookup store)) '(read))
'hello

narju> (attempt (lambda () (call hall '(lookup nope))))
('throw 'no-such-name . 'nope)

register is also a cast, because the task most likely to want it cannot make a call yet: a call suspends into a loop, and a child naming itself on its way into its own loop has nothing to suspend into.

it is a rendezvous and not a guard. a link posts to a task by number, so a peer can already reach anything in the heap. trust is per link, not per task.

future

covered in Calls and replies. a task that holds one outstanding call and then becomes a reference on the answer.

Changing behaviour

hand replaces the handler. what waited in the backlog goes with it, which is what makes it more than a convenience: a task is addressable from the instant it is spawned, so requests that arrived before it was ready are answered by what it became.

narju> (define t
         (spawn (lambda (me)
                  (begin (send me 'boot)
                         (task-loop me
                                    (lambda h (st msg)
                                      (begin (if (eq? msg 'boot) 'ok (send me msg))
                                             (hand reference 'ready)))
                                    0)))))
't

narju> (call t '(read))
'ready

narju> (call t '(write 9))
'ok

narju> (call t '(read))
9

the kick may lose the race, since the task is addressable the instant it is spawned, so the first turn hands back whatever woke it rather than spending that message on booting. future does the same dance for the same reason.

become replaces the semantics:

(define (loud i)
  (with-handler i 'eval-var
    (lambda h (m l e r k)
      (begin (say (list 'read e)) ((handler-of i 'eval-var) m l e r k)))))

(define t
  (spawn (lambda (me)
           (task-loop me
                      (lambda h (n msg)
                        (if (eq? (verb (req-body msg)) 'loud)
                            (begin (reply msg 'ok) (become loud n))
                            (begin (reply msg n) (cons 'stop n))))
                      7))))
(say (call t '(loud)))
(say (call t '(read)))

'ok
('read 'eq?)
('read 'verb)
('read 'req-body)
('read 'msg)
('read 'reply)
('read 'msg)
('read 'n)
('read 'cons)
7
('read 'n)

from the next turn on, that task’s handler runs under (loud I) and announces every variable it reads. the turn that asked for it is unaffected, having already been given its semantics. this is the answer to a turn rather than something inside one, on purpose: a change of meaning mid-computation is the thing most hostile to compilation. only the handler changes, so the loop, the prompt and any suspended continuation keep the semantics they were made under, which is why the trace stops at the handler’s own body.

Host capabilities

there is no print and no open. the outside world is a set of peers, and a peer is an address:

(say (call '(host stdout) '(line "hello")))

hello
'ok

('host name) has the same shape as a task’s address on purpose. a call site cannot tell a peer written in rust from one written here, so anything doable to a task is doable to the world: call it, send to it, monitor it, hand its address to somebody else.

The set

('host stdout)   ('write v)  ('line v)
('host stdin)    ('read)  ('read prompt)
('host files)    ('read path)  ('root)
('host disk)     ('write path text)
('host clock)    ('now)  ('sleep ms)  ('after ms to msg)
('host gate)     ('dial spec)  ('listen spec)
('host modules)  ('fetch url ref)

each is a tokio task holding one end of a channel, and naj decides which to register. a peer is the unit of granting. a world that registers no clock does not have a slower clock, it has none, and a program built out of restart counts rather than restart rates runs in that world.

('host modules) is the one thing in the tree that reaches the network, and only naj --lock registers it:

(say (attempt (lambda () (call '(host modules) '(fetch "https://x/y" "HEAD")))))

('throw 'callee-down ('host 'modules) 'throw . 'noproc)

the same callee-down a dead task gives. a capability that was not granted fails where it was used, not at startup.

Clock

(define t0 (call '(host clock) '(now)))
(call '(host clock) '(sleep 30))
(say (> (- (call '(host clock) '(now)) t0) 20))
(send '(host clock) (list 'after 10 self 'ding))
(say (receive))

1
'ding

after is a message posted later to somebody else, which is why the timeout in Calls and replies needs nothing in the loop: it arms an after carrying the same reply id the real answer would. each timer is a task that sleeps and then sends. nothing is polled.

Reading and writing

files reads and disk writes. two peers rather than two verbs on one, because a peer is what gets granted and read-only is worth granting.

(say (call '(host disk) '(write "/tmp/naj-out.txt" "written by narju\n")))
(say (call '(host files) '(read "/tmp/naj-out.txt")))
(say (call '(host files) '(root)))

'ok
written by narju

/home/thorn/.cache/narju/modules

root is the module store, the only path need joins against. see Modules.

failures come back as ('io . text):

(say (attempt (lambda () (call '(host files) '(read "/tmp/definitely-not-here")))))

('throw 'io . "/tmp/definitely-not-here: No such file or directory (os error 2)")

Two adapters wear the stdout name

down a pipe, stdout and stdin are separate adapters. at a terminal, one console is registered under both names, so the channel’s order is the screen’s order. two channels would let a print land in the middle of a line somebody was typing.

('read prompt) therefore shows the prompt at a terminal and ignores it down a pipe. an object program says the same thing either way.

Gate

(say (call '(host gate) '(listen (tcp "127.0.0.1:0"))))
(say (attempt (lambda () (call '(host gate) '(dial (carrier "pigeon"))))))

127.0.0.1:43731
('throw 'no-transport 'carrier "pigeon")

listen answers the address it bound, since port 0 says you do not care which and you still have to be told. what a dial answers is Distribution.

Anything else

(say (attempt (lambda () (call '(host stdout) '(frobnicate)))))
(say (attempt (lambda () (call '(host nope) '(anything)))))

('throw 'bad-request 'frobnicate)
('throw 'callee-down ('host 'nope) 'throw . 'noproc)

a peer refuses an unknown request the way a task does, and an unregistered name fails like a task that is not there.

monitor works on a peer too:

(monitor '(host nope))
(say (receive))

('task-down ('host 'nope) 'throw . 'noproc)

Modules

a module is a file, and what it is is the value of its last form. there is no export list and no namespace:

; lib/math.naj
(define (double x) (* x 2))
(list (cons 'double double))

(define math (load "lib/math.naj"))
(say ((cdr (assq 'double math)) 21))

42

an assoc list is convenient, not required. a module may answer a single procedure, a number, or a task’s address.

Two ways in

load takes a path, need takes a name. a name is resolved against naj.lock, an ordinary file the program reads:

((narju-lock 1)
 (modules
  (json
   (url "https://github.com/thorn/naj-json")
   (rev "a1b2c3...")
   (path "github.com/thorn/naj-json")
   (file "json.naj"))))

rev is the identity. a module is a git revision, never a version number and never a semantics. two revisions of one repository are two directories in the store, and ('host files) '(root) says where the store is.

resolution is a read and an assq. nothing here fetches, which is what lets a program run under a build system with no network.

(say (attempt (lambda () (need 'nope))))

('throw 'no-such-module 'nope)

A module resolves against its own lock

main.naj locks json to one repository. the module one carries its own naj.lock, which locks json to a different one.

(say (cdr (assq 'which (need 'json))))
(say (cdr (assq 'mine (need 'one))))

'v1
'v2

a name means what the module that wrote it meant. one flat lock would make a name global, turning a diamond into a conflict and a conflict into version solving. here a diamond is two directories and nobody solves anything. what makes that affordable is that there are no cells: two instances of one module cannot drift apart, so having two costs disk and nothing else.

load is module-relative for the same reason. inside a loaded file, load and need are rebound to that module’s own directory, so a module’s paths mean the same thing wherever the store put it.

Writing the lock

naj --lock reads naj.deps and writes naj.lock. it is the only entry point that registers ('host modules).

((json (url "https://github.com/thorn/naj-json")
       (ref "main")
       (file "json.naj")))

ref defaults to HEAD. naming a branch pins what it points at now rather than tracking it: what gets written down is the resolved revision.

naj --lock also fetches the whole reachable graph, since a dependency’s own dependencies must be in the store before it can resolve them. nothing is merged. each was already pinned by whoever named it, so the closure is a graph walk rather than a solver.

the manifest has no version marker and the lock does, because the manifest is written by hand and the lock is read by a program that must be able to refuse a format it does not know.

The other reader

naj --lock and nix build are the split nix flake lock and nix build already are, so the flake reads the same file:

naj-modules = narju.lib.najModules pkgs ./naj.lock;
# ...
naj --modules ${naj-modules} main.naj

najModules walks the same graph with builtins.fetchGit and symlinks each revision to $out/<path>/<rev>, the layout need joins. the sandbox then needs no network, and the binary running in it has no peer registered that could reach one.

readLock matches the file with a regex instead of parsing it. narju’s reader is four lines of assq and nix has no reader for s-expressions, so writing one there would be a second implementation of the format. the cost is that a hand-reflowed lock is not read by it.

Distribution

a node dials another and gets one address back. everything after that is send, call and monitor, unchanged.

(define echo
  (spawn (lambda (me)
           (task-loop me
                      (lambda h (st msg)
                        (case (verb (req-body msg))
                          ((ping) (begin (reply msg 'pong) st))
                          ((stop) (begin (reply msg 'ok) (cons 'stop 'ok)))
                          (else (begin (refuse msg (bad-request (req-body msg))) st))))
                      '()))))

(define at (call '(host gate) '(listen (tcp "127.0.0.1:0"))))

(define driver
  (spawn (lambda (me)
           (task-loop me
                      (lambda h (st msg)
                        (let ((there (call '(host gate) (list 'dial (list 'tcp at)))))
                          (let ((e (call there '(lookup echo))))
                            (begin
                              (say (list 'far e))
                              (say (call e '(ping)))
                              (call e '(stop))
                              (call there '(stop))
                              (cons 'stop 'ok)))))
                      '()))))

(send driver 'go)
(hand greeter (list (cons 'echo echo)))

('far #<task 1 on 16>)
'pong

a node dialling itself, which is why one file shows the whole round trip. two processes differ in nothing.

hand greeter as the last form of a file is how a script becomes a node’s task 0. greet is a handler, not a loop, because which task runs it is not its business. registrations that arrived before the file reached its last form are in the loop’s backlog by then, so they go to the table rather than to the file’s body.

Task 0 is a convention

an address is only ever learned by being told, so a node just dialled is unreachable unless one address on it is known in advance. dial answers task 0 there, and the greeter is what conventionally sits in it.

a rendezvous, not a guard. once a link exists the peer can post to any task on the node by number. trust is per link, not per task.

everything else crosses as itself. an address cannot:

  • one the sender called its own becomes one of ours through this link
  • one the sender reached through this link becomes one of ours directly

the two cases swap, and the sender’s connection number, a name in the sender’s numbering, is discarded. this is exact rather than heuristic because an address is a host type a program cannot forge. ('task 1) written by hand is a two-element list and stays one.

an address naming a third node has no image on the far side, and sending one is refused with ('throw . 'third-party-address) rather than half-built. forwarding it would mean proxying for a link the receiver does not hold.

Two ways for a call to fail

('throw 'callee-down #<task 1 on 16> 'throw . 'noproc)
('throw 'callee-down #<task 1 on 16> 'throw . 'noconnection)

the first is the far node saying that task is not there. the second is not hearing from the far node at all.

a remote death carries its exit value:

(monitor e)
(call e '(stop))
(say (receive))

('task-down #<task 1 on 16> 'ok . 'bye)

when the value cannot be encoded the death is still reported, with ('throw . 'third-party-address) in its place.

Watching is a node frame, not a service

a link carries two frames addressed to the node itself rather than to a task on it: ('watch id) and ('down id result).

deliberately not a table held by some task. a task’s table is lost when the task restarts and nothing happens to say so, whereas the node knows about its own links because it is what holds them. the id used is one a task id can never be, so a frame for the node cannot be addressed to a task.

a watch set on a task that is already gone is answered at once. the round trip is the window, so a late watch would otherwise never be answered.

The gate

('dial (tcp "host:port"))     answers task 0 on the new link
('listen (tcp "host:port"))   answers the address it bound, and casts
                              ('peer addr) to the caller per connection

the gate is the only thing that opens a link, so it is the only thing that names one. the counter it hands out needs neither sharing nor an atomic, which is why a listener’s accepts come back through the gate instead of becoming links where they arrive.

(say (attempt (lambda () (call '(host gate) '(dial (carrier "pigeon"))))))

('throw 'no-transport 'carrier "pigeon")

there is no policy flag. what a program may open is what the world it runs in registers, and an embedding with a fixed set of peers dials them itself and serves no gate at all.

On the wire

a frame is a task id, a length and a payload. the length is the one field a peer can make arbitrarily large without sending anything, so it is checked before it is believed.

the payload encoding is not the printer. it carries what a printer could not:

  • sharing. a graph naming one pair a thousand times decodes to one pair, and the decoded side shares what the sender shared.
  • host types. a string travels as its type name and its own bytes, decoded by whatever the far node registered under that name. a type the far node does not have is a deployment fact, reported as such rather than as a corrupt frame.
  • the shapes that do not print back. a symbol prints as 'a, which reads as a two-element list.

a closure has no encoding, the same judgement send makes at the primitive. see Tasks and messages.

a frame this end cannot read ends the link rather than the message: the two sides disagree about the protocol, which is not something one message went wrong at.