Tibru

Tibru is an alternative to the nonsense that is the Urbit project. By nonsense I mean poor implementation, unnecessarily obfuscated source code and generally poor design decisions leading to high runtime overheads with little advantage. It also suffers from academic elitism and lack of reference to prior art which is rampant throughout its design and documentation. Unfortunately despite its academic roots the chosen runtime language is arbitrary and poorly selected from hundreds of alternatives.

This project has two aims. The first is to allow easy access to systems of this type by using generally accepted coding standards and techniques. The target executable provides an interactive REPL environment with human readable qualities. The second is to go above and beyond what is reasonably capable with Nock (Urbit's runtime language). This technology is open for anyone to use and lends itself nicely to app container implementations since it is side effect free and runs on immutable data structures.

As of writing no further work is being done on the system as it has met its first goal to implement a basic runtime structure.

Build

To build the 2 main executables 'kcon' and 'ohno' run make within the src/cpp directory. G++ 4.9 or higher is required.

make

To start KCon in REPL mode use

./bin/kcon

To run a script

./bin/kcon <script name>

To show all the other command arguments available.

./bin/kcon -help

If you run a script rather than use the REPL environment then you'll only see the last expression evaluated. To see all expressions use the -noisy command line parameter.

KCon

The basic runtime language follows from Nock in that it takes primitives to be numbers and pairs. Pairs being pairs of numbers or other pairs. One critism of Nock is its use of unbounded integers for a number base. KCon on the other hand uses only bytes (0-255). This enables KCon to run without arithmetic operators (Nock is liberally supplied with infinitely many more arithmetic operators by supporting increment).

We write bytes base 10 and pairs use square bracket notation.

>>> 0
0
>>> [0 [1 2]]
[0 1 2]

Pairs are written right associatively so [0 [1 2]] is equivalent to [0 1 2]. Within the KCon environment we can assign names to elements.

>>> :def twenty 20
>>> :def primes [2 3 5 7 11]

Then type any expression to see the value. It will then be named it for future expressions.

>>> twenty
20
>>> 20
20
>>> [twenty twenty]
[20 20]
>>> it
[20 20]

It would be nice to see the named expressions by name. We can do that with:

>>> :names on
>>> it
[twenty twenty]

Several names are already defined in KCon. These can be listed:

>>> :defs
EXIT
F
GRAFT
IF
T
nil
qt
sel
>>> qt
0

Since the data is immutable and within KCon it's impossible to decide if two elements are identical we rely on the implementation to optimize for shared elements. This can be seen with the names turned on but it's an artefact of the implementation. Logically the data tree doesn't recombine but KCon can't decide that.

KCon accepts multi-line input:

>>>[1
... 2]
[1 2]

KCon provides operators that act on expressions to yield other expressions.

>>> :help
Evaluate an expression of the form <name>|byte|[<expr> <expr>+]|<reader><expr>|<expr><macro> and define 'it' as its value.
Or process an operator on an expression of the form <op><expr> and define 'it' as its value.
Or run a command.

Commands:
:def <name> <expr> - Define a named expression
:process <filename> - Process all statements in the specified file
:include <filename> - Silently process all statements in the specified file
:dec  - Show bytes in decimal notation (default)
:hex  - Show bytes in hex notation
:flat - Show cells as flattened right associative lists (default)
:deep - Show cells as pairs
:line - Show expressions on a single line (default)
:list - Show expressions over multiple lines in list format
:names [on|off] - Show named expressions as defined names (works best in debug modes)
:defs - Show all defined names
:sys  - Show information about the system
:gc   - Run the garbage collector
:help - Show this help
:exit - End the shell session
:quit - End the shell session
:trace [<limit>|off] - Turn tracing on or off for ! operator

Operators:
![[f x] v]            -> !*[v [f x]]
![0 x]                -> x
![1 c [k1 k2] v]      -> ![?[c k1 k2] v]
![2 v e r k]          -> ![v +[e r k]]
*[v [[x y] z0 .. zn]] -> [@[v zn] .. @[v z0] @[v [x y]]]
*[v e]                -> @[v e]
@[v 0 x]              -> .x
@[v 1 r]              -> /[v r]
.x                    -> x
/[v [t1 ..] h1]       -> head{h1}( tail{t1 + 256*t2 ...}(v) )
/[v [t1 ..] h1 r]     -> /[head{h1}( tail{t1 + 256*t2 ...}(v) ) r]
?[[a b] x y]          -> x
?[a x y]              -> y
+[v e r]              -> e++v|r where e++v|r := append e onto v at r

Readers:
# - Convert unsigned integer into [b1 b2 b3 b3] format e.g. #1000 -> [232 3 0 0]

Macros:
' - Convert <expr> into [0 <expr>] e.g. 3' -> [0 3]
< - Reverse preceeding list elements e.g. [1 2 3 < 4 5] -> [3 2 1 < 4 5]

The specification of KCon is the set of operators as defined by the help. The simplest operator is quote written as ..

>>> .21
21

The select operator / traverses a binary tree data expression and selects the relevant element. It has a non-standard path format. A path list has an even number of elements alternating between the number of tail traverses followed by head traverses. The tail traverses are multi-byte numbers constructed of lists of bytes. The n^th byte is the coefficient of 256ⁿ starting at n=0. The head traverses are simple bytes. Since writing out multi-byte numbers is a pain KCon provides a reader which is a special parser that generates data expressions. For 32-bit multi-byte numbers use the # reader:

>>> #1000
[232 3 0 0]

We can then easily use the select operator:

>>> /[21 #0 0]
21
>>> /[[1 2 3] #1 1]
2
>>> /[[[1 2] 3 4] #0 1 #1 0]
2
>>> :def hd [#0 1]
>>> :def tl [#1 0]
>>> /[[1 2 3] hd]
1
>>> /[[1 2 3] tl]
[2 3]

A path of [#0 0] acts like an identity function. This looks inefficient but a smart memory manager can tag contiguous cells in memory to allow O(1) lookups (see later notes on *). In addition four byte sequences can be compacted into single words converting the 32-bit multi-byte number into a first class 32-bit number.

The conditional operator if selects based on whether the test expression is a byte or a pair.

>>> T
[0 0]
>>> ?[T 0 1]
0
>>> F
0
>>> ?[F 0 1]
1

These are the 3 basic operators that reduce expressions based on selection. In implementation terms they don't allocate new cells and aren't recursive. The next operators reduce expressions by building new ones and are interpreters since their behaviour is modified by parameters. @ is called the reduce operator. It takes an environment, an instruction code and some parameters:

>>> :def nums [1 2 3]
>>> qt
0
>>> @[nums qt 21]
21
>>> sel
1
>>> @[nums sel tl]
[2 3]

It's common to need constant expressions using the quote operator so instead of having to write [qt 21] there is a macro:

>>> 21'
[qt 21]
>>> [1 2 3]'
[qt 1 2 3]

Analogously the evaluate operator * delegates to @ but can create pairs as well for which @ is not defined:

>>> *[nums [qt 21] [sel tl]]
[[2 3] 21]

Notice how it evaluates in reverse order. This increases performance as the list of arguments is evaluated from head to tail but the results are built up tail to head. Also since * delegates to @ it is not recursive, again, for performance reasons. The cells created by * will be in reverse order and uninterrupted by allocations from @ (which allocates none). This means * produces potentially contiguous lists in memory (see note on /).

This leaves the one recursive operator to explain but fortunately it's tail recursive. The execute operator ! takes a statement and an environment. It then executes the statement in that environment resulting in a new environment and a continuation. Continuations are built into KCon which necessarily uses CPS (continuation passing style).

The simplest form is the EXIT statement:

>>> EXIT
0
>>> ![EXIT 21]
21

Then we have the conditional form that selects one of two continuations based on whether the test element is a pair of not:

>>> IF
1
>>> ![IF T [[[sel tl] EXIT'] [[sel hd] EXIT']] nums]
[2 3]
>>> ![IF F [[[sel tl] EXIT'] [[sel hd] EXIT']] nums]
1

It's interesting for debugging purposes to see each step being executed:

>>> :trace 32
>>> ![IF F [[[sel tl] EXIT'] [[sel hd] EXIT']] nums]
1.	[[[sel hd] qt EXIT] nums]
2.	[EXIT 1]
1

That's all that is needed for functional programming. However, there is one more operator GRAFT which is redundant but allows tree manipulations without having to formally write out a recursive algorithm. It takes a data expression (the tree), a path and an element. The result is a new tree with the element attached at the path location:

>>>	 +[nums [3 4] [#2 0]]
[1 2 3 4]

In execute mode it takes a continuation:

>>> :def env [sel #0 0]
>>> GRAFT
2
>>> ![GRAFT nums [3 4] [#2 0] [env EXIT']]
1.	[[env qt nil] 1 2 3 4]
2.	[nil 1 2 3 4]
[1 2 3 4]

That's all there is but it's very powerful.

OhNo (Not that language)

All this is very unweildy so the OhNo interprerer defines a new shell command fn that parses a function definition and outputs an expression implementing it. The chosen runtime structure is to pass a heap object into every function call and back out again with the result. Since KCon requires CPS the order of execution is known so updates to this heap structure are well defined. This allows for imperative pr