[urbit] Fwd: Sketchings of a nock nibblecode

[Anton Dyudin]

So nock is backwards tree forth, right? Here's happens if you straighten

[-3'dup' .-2'swap' ]-4'cons' /0 ()1 ]*2 ^3 +4 ]=5 ]?{6 }{-1'jmp' }<label>

;<7> .]8 !9 ]~10 \11

Let us define a stack machine, operating on nouns. Nock operators
0,3,4,9,11 operate on the top value of the stack, representing the current
subject. Similarly, 1 replaces it.
Nibbles 12-14, hereafter -3,-2,-4 (d-up,e-xchg,c-ons), are introduced to
deal with formula cells [[b c] d]: the sequence [ <bc> . <d> ] first pushes
a duplicate of the current subject to the stack, computes *[a b c],
exchanges the result with the duplicate, uses this to compute *[a d], and
finally creates a cell of the two results.
8 is near-equivalent to cons;
2, 5, and 6 similarly use -2 and -3, but execute, compare, and branch on
the top two values instead of consing them.
6 acts as a conditional jump, popping a loobean and skipping forward to
immediately after the "else" if it is false. The else is assigned the
remaining opcode, -1(f_wd), and correspondingly jumps forward by the
specified number of nibbles unconditionally. 10 similarly saves the subject
when evaluating its first argument.
7 is represented by concatenation.

.*(42 [8 [1 0] 8 [1 6 [5 [0 7] 4 0 6] [0 6] 9 2 [0 2] [4 0 6] 0 7] 9 2 0

1])

41

Following the transformation outlined above, [8 a b] becomes [ <a> .] b, [1
a] is deferred for further compilation, [6 a b c] turns to [ <a> ]?{ <b> }{
<c> }, [5 a b] to [ <a> . <b> ]=, [4 a] to <a> +, and [9 n a] to <a> !n.
Axis access is largely unchanged.

[ ( 42 ) . [ ( 0 ) .] [ ( [ [ /7 . /6 ]= ]?{ /6 }{ [ /2 . [ /6 + . /7 ] ]

!2 } ) .] !2 ]*

42 and 0 can be compiled directly; the formula, however, is a reference to
a noun, resulting in two thunks.

x: [ [ /7 . /6 ]= ]?{ /6 }{ [ /2 . [ /6 + . /7 ] ] !2 }

Having flattened all operations, compilation is fairly straightforward. The
outer formula is directly encoded; the inner one requires some counting to
align if-else jumps((2+)2 and (2+)13 nibbles respectively), and
correspondingly discards the "fi" label after reaching it.

d 1_2a e d 1_0 8 d 1_21 8 9_2 2

Minutae:
• -1_n could alternately be represented as -2 0_1 6_n
• _ ties designate additional data encoded after an instruction; for
example, a literal nibble 0-14, with 15 demarking four following bytes of
u3_noun
• 10 also needs a "covers following n nibbles" parameter, used to track
when ~|s(and !_s) go out of scope.

Hoon/jet implementation is left as an exercise to the reader.