9The Urbit interpreter is built on a Nock runtime system written in C, `u3`. This
10document is a relatively complete description
12You should keep reading if (a) you're planning to work on the Urbit interpreter;
13(b) you're a language implementation geek; or (c) you don't really understand
14anything until you've seen the actual structs.
16## u3: noun processing in C
18`u3` is the C library that makes Urbit work. If it wasn't called `u3`, it might
19be called `libnoun` - it's a library for making and storing nouns.
21What's a noun? A noun is either a cell or an atom. A cell is an ordered pair of
22any two nouns. An atom is an unsigned integer of any size.
24To the C programmer, this is not a terribly complicated data structure, so why
25do you need a library for it?
27One: nouns have a well-defined computation kernel, Nock, whose spec fits on a
28page and gzips to 340 bytes. But the only arithmetic operation in Nock is
29increment. So it's nontrivial to compute both efficiently and correctly.
31Two: `u3` is designed to be a "solid-state interpreter," ie, a single-level
32store which is transparently snapshotted. This implies a specialized
33memory-management model, etc, etc.
35(Does `u3` depend on the higher levels of Urbit, Arvo and Hoon? Yes and no. `u3`
36expects you to load something shaped like an Arvo kernel, and use it as an
37event-processing function. But you don't need to use this feature if you don't
38want, and your kernel doesn't have to be Arvo proper - just Arvo-compatible.
39Think of `u3` as the BIOS and Arvo as the boot kernel. And there are no
40dependencies at all between Hoon the language and `u3`.)
44Under `u3` is the simple `c3` layer, which is just how we write C in Urbit.
46When writing C in u3, please of course follow the conventions of the code around
47you as regards indentation, etc. It's especially important that every function
48have a header comment, even if it says nothing interesting.
50But some of our idiosyncrasies go beyond convention. Yes, we've done awful
51things to C. Here's what we did and why we did.
55First, it's generally acknowledged that underspecified integer types are C's
56worst disaster. C99 fixed this, but the `stdint` types are wordy and annoying.
57We've replaced them with:
61 typedef uint64_t c3_d; // double-word
62 typedef int64_t c3_ds; // signed double-word
63 typedef uint32_t c3_w; // word
64 typedef int32_t c3_ws; // signed word
65 typedef uint16_t c3_s; // short
66 typedef int16_t c3_ss; // signed short
67 typedef uint8_t c3_y; // byte
68 typedef int8_t c3_ys; // signed byte
69 typedef uint8_t c3_b; // bit
71 typedef uint8_t c3_t; // boolean
72 typedef uint8_t c3_o; // loobean
73 typedef uint8_t c3_g; // 5-bit atom for a 32-bit log.
74 typedef uint32_t c3_l; // little; 31-bit unsigned integer
75 typedef uint32_t c3_m; // mote; also c3_l; LSB first a-z 4-char string.
79 typedef char c3_c; // does not match int8_t or uint8_t
80 typedef int c3_i; // int - really bad
81 typedef uintptr_t c3_p; // pointer-length uint - really really bad
82 typedef intptr_t c3_ps; // pointer-length int - really really bad
84Some of these need explanation. A loobean is a Nock boolean - Nock, for
85mysterious reasons, uses 0 as true (always say "yes") and 1 as false (always say
88Nock and/or Hoon cannot tell the difference between a short atom and a long one,
89but at the `u3` level every atom under `2^31` is direct. The `c3_l` type is
90useful to annotate this. A `c3_m` is a *mote* - a string of up to 4 characters
91in a `c3_l`, least significant byte first. A `c3_g` should be a 5-bit atom. Of
92course, C cannot enforce these constraints, only document them.
94Use the "bad" - ie, poorly specified - integer types only when interfacing with
95external code that expects them.
97An enormous number of motes are defined in `i/c/motes.h`. There is no reason to
98delete motes that aren't being used, or even to modularize the definitions. Keep
99them alphabetical, though.
101### c3: variables and variable naming
103The C3 style uses Hoon style TLV variable names, with a quasi Hungarian syntax.
104This is weird, but works really well, as long as what you're doing isn't
105hideously complicated. (Then it works badly, but we shouldn't need anything
108A TLV variable name is a random pronounceable three-letter string, sometimes
109with some vague relationship to its meaning, but usually not. Usually CVC
110(consonant-vowel-consonant) is a good choice.
112You should use TLVs much the way math people use Greek letters. The same concept
113should in general get the same name across different contexts. When you're
114working in a given area, you'll tend to remember the binding from TLV to concept
115by sheer power of associative memory. When you come back to it, it's not that
116hard to relearn. And of course, when in doubt, comment it.
118Variables take pseudo-Hungarian suffixes, matching in general the suffix of the
121 c3_w wor_w; // 32-bit word
123Unlike in standard Hungarian, there is no change for pointer variables. C
124structure variables take a `_u` suffix.
128The code (from `defs.h`) tells the story:
133 # define _(x) (c3y == (x))
134 # define __(x) ((x) ? c3y : c3n)
135 # define c3a(x, y) __(_(x) && _(y))
136 # define c3o(x, y) __(_(x) || _(y))
138In short, use `_()` to turn a loobean into a boolean, `__` to go the other way.
139Use `!` as usual, `c3y` for yes and `c3n` for no, `c3a` for and and `c3o` for
144The division between `c3` and `u3` is that you could theoretically imagine using
145`c3` as just a generic C environment. Anything to do with nouns is in `u3`.
147### u3: a map of the system
149There are two kinds of symbols in `u3`: regular and irregular. Regular symbols
153 -------------------------------------------------------
154 u3a_ allocation i/n/a.h n/a.c
155 u3e_ persistence i/n/e.h n/e.c
156 u3h_ hashtables i/n/h.h n/h.c
157 u3i_ noun construction i/n/i.h n/i.c
158 u3j_ jet control i/n/j.h n/j.c
159 u3m_ system management i/n/m.h n/m.c
160 u3n_ nock computation i/n/n.h n/n.c
161 u3r_ noun access (error returns) i/n/r.h n/r.c
162 u3t_ profiling i/n/t.h n/t.c
163 u3v_ arvo i/n/v.h n/v.c
164 u3x_ noun access (error crashes) i/n/x.h n/x.c
165 u3z_ memoization i/n/z.h n/z.c
166 u3k[a-g] jets (transfer, C args) i/j/k.h j/[a-g]/*.c
167 u3q[a-g] jets (retain, C args) i/j/q.h j/[a-g]/*.c
168 u3w[a-g] jets (retain, nock core) i/j/w.h j/[a-g]/*.c
170Irregular symbols always start with `u3` and obey no other rules. They're
171defined in `i/n/u.h`. Finally, `i/all.h` includes all these headers (fast
172compilers, yay) and is all you need to program in `u3`.
174### u3: noun internals
176A noun is a `u3_noun` - currently defined as a 32-bit `c3_w`.
178If your `u3_noun` is less than `(1 << 31)`, it's a direct atom. Every unsigned
179integer between `0` and `0x7fffffff` inclusive is its own noun.
181If bit `31` is set in a `u3_noun`, bit `30` is always set - this bit is
182reserved. Bit `29` is `1` if the noun is a cell, `0` if it's an atom. Bits `28`
183through `0` are a word pointer into the loom - see below. The structures are:
188 c3_w buf_w[0]; // actually [len_w]
197The only thing that should be mysterious here is `mug_w`, which is a 31-bit
198lazily computed nonzero short hash (FNV currently, soon Murmur3). If `mug_w` is
1990, the hash is not yet computed. We also hijack this field for various hacks,
200such as saving the new address of a noun when copying over.
202Also, the value `0xffffffff` is `u3_none`, which is never a valid noun. Use the
203type `u3_weak` to express that a noun variable may be `u3_none`.
205### u3: reference counts
207The only really essential thing you need to know about `u3` is how to handle
208reference counts. Everything else, you can skip and just get to work.
210u3 deals with reference-counted, immutable, acyclic nouns. Unfortunately, we are
211not Apple and can't build reference counting into your C compiler, so you need
214Every allocated noun (or any allocation object, because our allocator is
215general-purpose) contains a counter which counts the number of references to it
216- typically variables with type `u3_noun`. When this counter goes to 0, the noun
219To tell `u3` that you've added a reference to a noun, call the function
220`u3a_gain()` or its shorthand `u3k()`. (For your convenience, this function
221returns its argument.) To tell `u3` that you've destroyed a reference, call
222`u3a_lose()` or `u3z()`.
224(If you screw up by decrementing the counter too much, `u3` will dump core in
225horrible ways. If you screw up by incrementing it too much, `u3` will leak
226memory. To check for memory leaks, set the `bug_o` flag in `u3e_boot()` - eg,
227run `vere` with `-g`. Memory leaks are difficult to debug - the best way to
228handle leaks is just to revert to a version that didn't have them, and look over
231(You can gain or lose a direct atom. It does nothing.)
233### u3: reference protocols
235*THIS IS THE MOST CRITICAL SECTION IN THE `u3` DOCUMENTATION.*
237The key question when calling a C function in a refcounted world is what the
238function will do to the noun refcounts - and, if the function returns a noun,
239what it does to the return.
241There are two semantic patterns, `transfer` and `retain`. In `transfer`
242semantics, the caller "gives" a use count to the callee, which "gives back" any
243return. For instance, if I have
246 u3_noun foo = u3i_string("foobar");
254Suppose `u3f_futz()` has `transfer` semantics. At `[...]`, my code holds one
255reference to `bar` and zero references to `foo` - which has been freed, unless
256it's part of `bar`. My code now owns `bar` and gets to work with it until it's
257done, at which point a `u3z()` is required.
259On the other hand, if `u3f_futz()` has `retain` semantics, we need to write
262 u3_noun foo = u3i_string("foobar");
270because calling `u3f_futz()` does not release our ownership of `foo`, which we
271have to free ourselves.
273But if we free `bar`, we are making a great mistake, because our reference to it
274is not in any way registered in the memory manager (which cannot track
275references in C variables, of course). It is normal and healthy to have these
276uncounted C references, but they must be treated with care.
278The bottom line is that it's essential for the caller to know the refcount
279semantics of any function which takes or returns a noun. (In some unusual
280circumstances, different arguments or returns in one function may be handled
283Broadly speaking, as a design question, retain semantics are more appropriate
284for functions which inspect or query nouns. For instance, `u3h()` (which takes
285the head of a noun) retains, so that we can traverse a noun tree without
286constantly incrementing and decrementing.
288Transfer semantics are more appropriate for functions which make nouns, which is
289obviously what most functions do.
291In general, though, in most places it's not worth thinking about what your
292function does. There is a convention for it, which depends on where it is, not
293what it does. Follow the convention.
295### u3: reference conventions
297The `u3` convention is that, unless otherwise specified, *all functions have
298transfer semantics* - with the exception of the prefixes: `u3r`, `u3x`, `u3z`,
299`u3q` and `u3w`. Also, within jet directories `a` through `f` (but not `g`),
300internal functions retain (for historical reasons).
302If functions outside this set have retain semantics, they need to be commented,
303both in the `.h` and `.c` file, with `RETAIN` in all caps. Yes, it's this
306### u3: system architecture
308If you just want to tinker with some existing code, it might be enough to
309understand the above. If not, it's probably worth taking the time to look at
312`u3` is designed to work as a persistent event processor. Logically, it computes
313a function of the form
315 f(event, old state) -> (actions, new state)
317Obviously almost any computing model - including, but not limited to, Urbit -
318can be defined in this form. To create the illusion of a computer that never
319loses state and never fails, we:
321- log every event externally before it goes into u3
322- keep a single reference to a permanent state noun.
323- can abort any event without damaging the permanent state.
324- snapshot the permanent state periodically, and/or prune logs.
326### u3: the road model
328`u3` uses a memory design which I'm sure someone has invented somewhere before,
329because it's not very clever, but I've never seen it anywhere in particular.
331Every allocation starts with a solid block of memory, which `u3` calls the
332`loom`. How do we allocate on the loom? You're probably familiar with the Unix
333heap-stack design, in which the stack grows downward and the heap (malloc arena)
338 |------------#################################+++++++++++++|
342A road is a normal heap-stack system, except that the heap and stack can point
343in *either direction*. Therefore, inside a road, we can nest another road in the
346When the opposite road completes, its heap is left on top of the opposite heap's
347stack. It's no more than the normal behavior of a stack machine for all
348subcomputations to push their results on the stack.
350The performance tradeoff of "leaping" - reversing directions in the road - is
351that if the outer computation wants to preserve the results of the inner one,
352not just use them for temporary purposes, it has to *copy them*.
354This is a trivial cost in some cases, a prohibitive cost in others. The upside,
355of course, is that all garbage accrued in the inner computation is discarded at
358The goal of the road system is the ability to *layer* memory models. If you are
359allocating on a road, you have no idea how deep within a nested road system you
360are - in other words, you have no idea exactly how durable your result may be.
361But free space is never fragmented within a road.
363Roads do not reduce the generality or performance of a memory system, since even
364the most complex GC system can be nested within a road at no particular loss of
365performance - a road is just a block of memory.
367Each road (`u3a_road` to be exact) uses four pointers: `rut` is the bottom of
368the arena, `hat` the top of the arena, `mat` the bottom of the stack, `cap` the
369top of the stack. (Bear in mind that the road "stack" is not actually used as
370the C function-call stack, though it probably should be.)
372A "north" road has the stack high and the heap low:
376 |~~~~~~~~~~~~-------##########################+++++++$~~~~~|
380A "south" road is the other way around:
384 |~~~~~~~~~~~~$++++++##########################--------~~~~~|
388Legend: `-` is durable storage (heap); `+` is temporary storage (stack); `~` is
389deep storage (immutable); `$` is the allocation frame `#` is free memory.
391Pointer restrictions: pointers stored in `+` can point anywhere. Pointers in `-`
392can only point to `-` or `~`; pointers in `~` only point to `~`.
394To "leap" is to create a new inner road in the `###` free space. but in the
395reverse direction, so that when the inner road "falls" (terminates), its durable
396storage is left on the temporary storage of the outer road.
398`u3` keeps a global variable, `u3_Road` or its alias `u3R`, which points to the
399current road. (If we ever run threads in inner roads - see below - this will
400become a thread-local variable.) Relative to `u3R`, `+` memory is called
401`junior` memory; `-` memory is `normal` memory; `~` is `senior` memory.
403### u3: explaining the road model
407We're now ready to understand why the road system works so logically with the
408event and persistence model.
410The key is that *we don't update refcounts in senior memory.* A pointer from an
411inner road to an outer road is not counted. Also, the outmost, or `surface`
412road, is the only part of the image that gets checkpointed.
414So the surface road contains the entire durable state of `u3`. When we process
415an event, or perform any kind of complicated or interesting calculation, *we
416process it in an inner road*. If its results are saved, they need to be copied.
418Since processing in an inner road does not touch surface memory, (a) we can
419leave the surface road in a read-only state and not mark its pages dirty; (b) we
420can abort an inner calculation without screwing up the surface; and (c) because
421inner results are copied onto the surface, the surface doesn't get fragmented.
423All of (a), (b) and (c) are needed for checkpointing to be easy. It might be
424tractable otherwise, but easy is even better.
426Moreover, while the surface is most definitely single-threaded, we could easily
427run multiple threads in multiple inner roads (as long as the threads don't have
428pointers into each others' memory, which they obviously shouldn't).
430Moreover, in future, we'll experiment more with adding road control hints to the
431programmer's toolbox. Reference counting is expensive. We hypothesize that in
432many - if not most - cases, the programmer can identify procedural structures
433whose garbage should be discarded in one step by copying the results. Then,
434within the procedure, we can switch the allocator into `sand` mode, and stop
435tracking references at all.
437### u3: rules for C programming
439There are two levels at which we program in C: (1) above the interpreter; (2)
440within the interpreter or jets. These have separate rules which need to be
443### u3: rules above the interpreter
445In its relations with Unix, Urbit follows a strict rule of "call me, I won't
446call you." We do of course call Unix system calls, but only for the purpose of
449Above Urbit, you are in a normal C/Unix programming environment and can call
450anything in or out of Urbit. Note that when using `u3`, you're always on the
451surface road, which is not thread-safe by default. Generally speaking, `u3` is
452designed to support event-oriented, single-threaded programming.
454If you need threads which create nouns, you could use `u3m_hate()` and
455`u3m_love()` to run these threads in subroads. You'd need to make the global
456road pointer, `u3R`, a thread-local variable instead. This seems perfectly
457practical, but we haven't done it because we haven't needed to.
459### u3: rules within the interpreter
461Within the interpreter, your code can run either in the surface road or in a
462deep road. You can test this by testing
466ie: does the pier's home road equal the current road pointer?
468Normally in this context you assume you're obeying the rules of running on an
469inner road, ie, "deep memory." Remember, however, that the interpreter *can* run
470on surface memory - but anything you can do deep, you can do on the surface. The
471converse is by no means the case.
473In deep memory, think of yourself as if in a signal handler. Your execution
474context is extremely fragile and may be terminated without warning or cleanup at
475any time (for instance, by `ctrl-c`).
477For instance, you can't call `malloc` (or C++ `new`) in your C code, because you
478don't have the right to modify data structures at the global level, and will
479leave them in an inconsistent state if your inner road gets terminated.
480(Instead, use our drop-in replacements, `u3a_malloc()`, `u3a_free()`,
483A good example is the different meaning of `c3_assert()` inside and outside the
484interpreter. At either layer, you can use regular assert(), which will just kill
485your process. On the surface, `c3_assert()` will just... kill your process.
487In deep execution, `c3_assert()` will issue an exception that queues an error
488event, complete with trace stack, on the Arvo event queue. Let's see how this
493You produce an exception with
495 /* u3m_bail(): bail out. Does not return.
499 ** %exit :: semantic failure
500 ** %evil :: bad crypto
501 ** %intr :: interrupt
502 ** %fail :: execution failure
503 ** %foul :: assert failure
504 ** %need :: network block
505 ** %meme :: out of memory
506 ** %time :: timed out
507 ** %oops :: assertion failure
510 u3m_bail(c3_m how_m);
512Broadly speaking, there are two classes of exception: internal and external. An
513external exception begins in a Unix signal handler. An internal exception begins
514with a call to longjmp() on the main thread.
516There are also two kinds of exception: mild and severe. An external exception is
517always severe. An internal exception is normally mild, but some (like
518`c3__oops`, generated by `c3_assert()`) are severe.
520Either way, exceptions come with a stack trace. The `u3` nock interpreter is
521instrumented to retain stack trace hints and produce them as a printable
524Mild exceptions are caught by the first virtualization layer and returned to the
525caller, following the behavior of the Nock virtualizer `++mock` (in `hoon.hoon`)
527Severe exceptions, or mild exceptions at the surface, terminate the entire
528execution stack at any depth and send the cumulative trace back to the `u3`
531For instance, `vere` uses this trace to construct a `%crud` event, which conveys
532our trace back toward the Arvo context where it crashed. This lets any UI
533component anywhere, even on a remote node, render the stacktrace as a
534consequence of the user's action - even if its its direct cause was (for
535instance) a Unix SIGINT or SIGALRM.
537### u3: C structures on the loom
539Normally, all data on the loom is nouns. Sometimes we break this rule just a
540little, though - eg, in the `u3h` hashtables.
542To point to non-noun C structs on the loom, we use a `u3_post`, which is just a
543loom word offset. A macro lets us declare this as if it was a pointer:
545 typedef c3_w u3_post;
546 #define u3p(type) u3_post
548Some may regard this as clever, others as pointless. Anyway, use `u3to()` and
549`u3of()` to convert to and from pointers.
551When using C structs on the loom - generally a bad idea - make sure anything
552which could be on the surface road is structurally portable, eg, won't change
553size when the pointer size changes. (Note also: we consider little-endian,
554rightly or wrongly, to have won the endian wars.)
556## u3: API overview by prefix
558Let's run through the `u3` modules one by one. All public functions are
559commented, but the comments may be cryptic.
565 /* u3m_boot(): start the u3 system.
568 u3m_boot(c3_o nuu_o, c3_o bug_o, c3_c* dir_c);
570`nuu_o` is `c3y` (yes, `0`) if you're creating a new pier, `c3n` (no, `1`) if
571you're loading an existing one. `bug_o` is `c3y` if you want to test the
572garbage-collector, `c3n` otherwise. `dir_c` is the directory for the pier files.
574`u3m_boot()` expects an `urbit.pill` file to load the kernel from. It will try
575first `$dir/.urb.urbit.pill`, then `U3_LIB`.
577Any significant computation with nouns, certainly anything Turing complete,
578should be run (a) virtualized and (b) in an inner road. These are slightly
579different things, but at the highest level we bundle them together for your
580convenience, in `u3m_soft()`:
582 /* u3m_soft(): system soft wrapper. unifies unix and nock errors.
584 ** Produces [%$ result] or [%error (list tank)].
587 u3m_soft(c3_w sec_w, u3_funk fun_f, u3_noun arg);
589`sec_w` is the number of seconds to time out the computation. `fun_f` is a C
590function accepting `arg`.
592The result of `u3m_soft()` is a cell whose head is an atom. If the head is `%$`
593- ie, `0` - the tail is the result of `fun_f(arg)`. Otherwise, the head is a
594`term` (an atom which is an LSB first string), and the tail is a `(list tank)`
595(a list of `tank` printables - see `++tank` in `hoon.hoon`). Error terms should
596be the same as the exception terms above.
598If you're confident that your computation won't fail, you can use
599`u3m_soft_sure()`, `u3m_soft_slam()`, or `u3m_soft_nock()` for C functions, Hoon
600function calls, and Nock invocations. Caution - this returns just the result,
603All the `u3m_soft` functions above work *only on the surface*. Within the
604surface, virtualize with `u3m_soft_run()`. Note that this takes a `fly` (a
605namespace gate), thus activating the `11` super-operator in the nock
606virtualizer, `++mock`. When actually using the `fly`, call `u3m_soft_esc()`.
607Don't do either unless you know what you're doing!
609For descending into a subroad *without* Nock virtualization, use `u3m_hate()`
610and `u3m_love` respectively. Hating enters a subroad; loving leaves it, copying
613Other miscellaneous tools in `u3m`: `u3m_file()` loads a Unix file as a Nock
614atom; `u3m_water()` measures the boundaries of the loom in current use (ie,
615watermarks); and a variety of prettyprinting routines, none perfect, are
616available, mainly for debugging printfs: `u3m_pretty()`, `u3m_p()`, `u3m_tape()`
619It's sometimes nice to run a mark-and-sweep garbage collector, `u3m_grab()`,
620which collects the world from a list of roots, and asserts if it finds any leaks
621or incorrect refcounts. This tool is for debugging and long-term maintenance
622only; refcounts should never err.
626The jet system, `u3j`, is what makes `u3` and `nock` in any sense a useful
627computing environment. Except perhaps `u3a` (there is really no such thing as a
628trivial allocator, though `u3a` is dumber than most) - `u3j` is the most
629interesting code in `u3`.
631Let's consider the minor miracle of driver-to-battery binding which lets `u3j`
632work - and decrement not be `O(n)` - without violating the precisely defined
633semantics of pure Nock, *ever*.
635It's easy to assume that jets represent an architectural coupling between Hoon
636language semantics and Nock interpreter internals. Indeed such a coupling would
637be wholly wrongtious and un-Urbit. But the jet system is not Hoon-specific. It
638is specific to nock runtime systems that use a design pattern we call a `core`.
640#### u3j: core structure
642A core is no more than a cell `[code data]`, in which a `code` is either a Nock
643formula or a cell of `code`s, and `data` is anything. In a proper core, the
644subject each formula expects is the core itself.
646Except for the arbitrary decision to make a core `[code data]`, (or as we
647sometimes say, `[battery payload]`), instead of `[data code]`, any high-level
648language transforming itself to Nock would use this design.
650So jets are in fact fully general. Broadly speaking, the jet system works by
651matching a C *driver* to a battery. When the battery is invoked with Nock
652operator `9`, it must be found in associative memory and linked to its driver.
653Then we link the formula axis of the operation (`a` in `[9 a b]`) to a specific
654function in the driver.
656To validate this jet binding, we need to know two things. One, we need to know
657the C function actually is a perfect semantic match for the Nock formula. This
658can be developed with driver test flags, which work, and locked down with a
659secure formula hash in the driver, which we haven't bothered with just yet. (You
660could also try to develop a formal method for verifying that C functions and
661Nock formulas are equivalent, but this is a research problem for the future.)
663Two, we need to validate that the payload is appropriate for the battery. We
664should note that jets are a Nock feature and have no reference to Hoon. A driver
665which relies on the Hoon type system to only pair it with valid payloads is a
666broken driver, and breaks the Nock compliance of the system as a whole. So
669Now, a casual observer might look at `[battery payload]` and expect the simplest
670case of it to be `[formula subject]`. That is: to execute a simple core whose
671battery is a single formula, we compute
675Then, naturally, when we go from Hoon or a high-level language containing
676functions down to Nock, `[function arguments]` turns into `[formula subject]`.
677This seems like an obvious design, and we mention it only because it is
680Rather, to execute a one-armed core like the above, we run
684and the normal structure of a `gate`, which is simply Urbitese for "function,"
687 [formula [sample context]]
689where `sample` is Urbitese for "arguments" - and `context`, any Lisper will at
690once recognize, is Urbitese for "environment."
692To `slam` or call the gate, we simply replace the default sample with the
693caller's data, then nock the formula on the entire gate.
695What's in the context? Unlike in most dynamic languages, it is not some secret
696system-level bag of tricks. Almost always it is another core. This onion
697continues until at the bottom, there is an atomic constant, conventionally is
698the kernel version number.
700Thus a (highly desirable) `static` core is one of the form
703 [battery static-core]
705ie, a solid stack of nested libraries without any dynamic data. The typical gate
706will thus be, for example,
708 [formula [sample [battery battery battery constant]]]
710but we would be most foolish to restrict the jet mechanism to cores of this
711particular structure. We cannot constrain a payload to be
712`[sample static-core]`, or even `[sample core]`. Any such constraint would not
713be rich enough to handle Hoon, let alone other languages.
717There are two fundamental rules of computer science: (1) every system is best
718understood through its state; (2) less state is better than more state. Sadly, a
719pier has three different jet state systems: `cold`, `warm` and `hot`. It needs
722Hot state is associated with this particular Unix process. The persistent pier
723is portable not just between process and process, but machine and machine or OS
724and OS. The set of jets loaded into a pier may itself change (in theory, though
725not in the present implementation) during the lifetime of the process. Hot state
726is a pure C data structure.
728Cold state is associated with the logical execution history of the pier. It
729consists entirely of nouns and ignores restarts.
731Warm state contains all dependencies between cold and hot state. It consists of
732C structures allocated on the loom.
734Warm state is purely a function of cold and hot states, and we can wipe and
735regenerate it at any time. On any restart where the hot state might have
736changed, we clear the warm state with `u3j_ream()`.
738There is only one hot state, the global jet dashboard `u3j_Dash` or `u3D` for
739short. In the present implementation, u3D is a static structure not modified at
740runtime, except for numbering itself on process initialization. This structure -
741which embeds function pointers to all the jets - is defined in `j/tree.c`. The
744 /* u3j_harm: driver arm.
746 typedef struct _u3j_harm {
747 c3_c* fcs_c; // `.axe` or name
748 u3_noun (*fun_f)(u3_noun); // compute or 0 / semitransfer
749 c3_o ice; // perfect (don't test)
750 c3_o tot; // total (never punts)
751 c3_o liv; // live (enabled)
754 /* u3j_core: C core driver.
756 typedef struct _u3j_core {
757 c3_c* cos_c; // control string
758 struct _u3j_harm* arm_u; // blank-terminated static list
759 struct _u3j_core* dev_u; // blank-terminated static list
760 struct _u3j_core* par_u; // dynamic parent pointer
761 c3_l jax_l; // dynamic jet index
764 /* u3e_dash, u3_Dash, u3D: jet dashboard singleton
766 typedef struct _u3e_dash {
767 u3j_core* dev_u; // null-terminated static list
768 c3_l len_l; // ray_u filled length
769 c3_l all_l; // ray_u allocated length
770 u3j_core* ray_u; // dynamic driver array
773Warm and cold state is *per road*. In other words, as we nest roads, we also
774nest jet state. The jet state in the road is:
776 struct { // jet dashboard
777 u3p(u3h_root) har_p; // warm state
778 u3_noun das; // cold state
781In case you understand Hoon, `das` (cold state) is a `++dash`, and `har_p` (warm
782state) is a map from battery to `++calx`:
784 ++ bane ,@tas :: battery name
785 ++ bash ,@uvH :: label hash
786 ++ bosh ,@uvH :: local battery hash
787 ++ batt ,* :: battery
789 $: jax=,@ud :: hot core index
790 hap=(map ,@ud ,@ud) :: axis/hot arm index
791 lab=path :: label as path
792 jit=* :: arbitrary data
794 ++ calx (trel calf (pair bash cope) club) :: cached by battery
795 ++ clog (pair cope (map batt club)) :: identity record
796 ++ club (pair corp (map term nock)) :: battery pattern
797 ++ cope (trel bane axis (each bash noun)) :: core pattern
799 ++ corp (each core batt) :: parent or static
800 ++ dash (map bash clog) :: jet system
802The driver index `jax` in a `++calx` is an index into `ray_u` in the dashboard -
803ie, a pointer into hot state. This is why the warm state has to be reset when we
804reload the pier in a new process.
806Why is jet state nested? Nock of course is a functional system, so as we compute
807we don't explicitly create state. Jet state is an exception to this principle
808(which works only because it can't be semantically detected from Nock/Hoon) -
809but it can't violate the fundamental rules of the allocation system.
811For instance, when we're on an inner road, we can't allocate on an outer road,
812or point from an outer road to an inner. So if we learn something - like a
813mapping from battery to jet - in the inner road, we have to keep it in the inner
816Mitigating this problem, when we leave an inner road (with `u3m_love()`), we
817call `u3j_reap()` to promote jet information in the dying road. Reaping promotes
818anything we've learned about any battery that either (a) already existed in the
819outer road, or (b) is being saved to the outer road.
823Jet binding starts with a `%fast` hint. (In Hoon, this is produced by the runes
824`~%`, for the general case, or `~/` for simple functions.) To bind a jet,
825execute a formula of the form:
827 [10 [%fast clue-formula] core-formula]
829`core-formula` assembles the core to be jet-propelled. `clue-formula` produces
830the hint information, or `++clue` above, which we want to annotate it with.
832A clue is a triple of name, parent, and hooks:
834 ++ clue (trel chum nock (list (pair term nock)))
836The name, or `++chum`, has a bunch of historical structure which we don't need
837(cleaning these things up is tricky), but just gets flattened into a term.
839The parent axis is a nock formula, but always reduces to a simple axis, which is
840the address of this core's *parent*. Consider again an ordinary gate
842 [formula [sample context]]
844Typically the `context` is itself a library core, which itself has a jet
845binding. If so, the parent axis of this gate is `7`.
847If the parent is already bound - and the parent *must* be already bound, in this
848road or a road containing it - we can hook this core bottom-up into a tree
849hierarchy. Normally the child core is produced by an arm of the parent core, so
850this is not a problem - we wouldn't have the child if we hadn't already made the
853The clue also contains a list of *hooks*, named nock formulas on the core.
854Usually these are arms, but they need not be. The point is that we often want to
855call a core from C, in a situation where we have no type or other source
856information. A common case of this is a complex system in which we're mixing
857functions which are jet-propelled with functions that aren't.
859In any case, all the information in the `%fast` hint goes to `u3j_mine()`, which
860registers the battery in cold state (`das` in `jed` in `u3R`), then warm state
863It's essential to understand that the `%fast` hint has to be, well, fast -
864because we apply it whenever we build a core. For instance, if the core is a
865Hoon gate - a function - we will call `u3j_mine` every time the function is
868### u3j: the cold jet dashboard
870For even more fun, the jet tree is not actually a tree of batteries. It's a tree
871of battery *labels*, where a label is an \[axis term\] path from the root of the
872tree. (At the root, if the core pattern is always followed properly, is a core
873whose payload is an atomic constant, conventionally the Hoon version.)
875Under each of these labels, it's normal to have an arbitrary number of different
876Nock batteries (not just multiple copies of the same noun, a situation we *do*
877strive to avoid). For instance, one might be compiled with debugging hints, one
880We might even have changed the semantics of the battery without changing the
881label - so long as those semantics don't invalidate any attached driver.
883For instance, it's normal to have two equivalent Nock batteries at the same time
884in one pier: one battery compiled with debugging hints, one not.
886Rather, the jet tree is a semantic hierarchy. The root of the hierarchy is a
887constant, by convention the Hoon kernel version because any normal jet-propelled
888core has, at the bottom of its onion of libraries, the standard kernel. Thus if
891 [foo-battery [bar-battery [moo-battery 164]]]
893we can reverse the nesting to construct a hierarchical core path. The static
898extends the static core `164/moo/bar` by wrapping the `foo` battery (ie, in
899Hoon, `|%`) around it. With the core above, you can compute `foo` stuff, `bar`
900stuff, and `moo` stuff. Rocket science, not.
902Not all cores are static, of course - they may contain live data, like the
903sample in a gate (ie, argument to a function). Once again, it's important to
904remember that we track jet bindings not by the core, which may not be static,
905but by the battery, which is always static.
907(And if you're wondering how we can use a deep noun like a Nock formula or
908battery as a key in a key-value table, remember `mug_w`, the lazily computed
909short hash, in all boxed nouns.)
911In any case, `das`, the dashboard, is a map from `bash` to jet location record
912(`++clog`). A `clog` in turn contains two kinds of information: the `++cope`, or
913per-location noun; and a map of batteries to a per-battery `++club`.
915The `cope` is a triple of `++bane` (battery name, right now just a `term`);
916`++axis`, the axis, within *this* core, of the parent; and `(each bash noun)`,
917which is either `[0 bash]` if the parent is another core, or `[1 noun]`, for the
918constant noun (like `164`) if there is no parent core.
920A `bash` is just the noun hash (`++sham`) of a `cope`, which uniquely expresses
921the battery's hierarchical location without depending on the actual formulas.
923The `club` contains a `++corp`, which we use to actually validate the core.
924Obviously jet execution has to be perfectly compatible with Nock. We search on
925the battery, but getting the battery right is not enough - a typical battery is
926dependent on its context. For example, your jet-propelled library function is
927very likely to call `++dec` or other advanced kernel technology. If you've
928replaced the kernel in your context with something else, we need to detect this
931There are two cases for a jet-propelled core - either the entire core is a
932static constant, or it isn't. Hence the definition of `corp`:
934 ++ corp (each core batt) :: parent or static
936Ie, a `corp` is `[0 core]` or `[1 batt]`. If it's static - meaning that the jet
937only works with one specific core, ie, the parent axis of each location in the
938hierarchy is `3` - we can validate with a single comparison. Otherwise, we have
939to recurse upward by checking the parent.
941Note that there is at present no way to force a jet to depend on static *data*.
943### u3j: the warm jet dashboard
945We don't use the cold state to match jets as we call them. We use the cold state
946to register jets as we find them, and also to rebuild the warm state after the
949What we actually use at runtime is the warm state, `jed->har_p`, which is a
950`u3h` (built-in hashtable), allocated on the loom, from battery to `++calx`.
952A `calx` is a triple of a `++calf`, a `[bash cope]` cell, and a `club`. The
953latter two are all straight from cold state.
955The `calf` contains warm data dependent on hot state. It's a quadruple: of
956`jax`, the hot driver index (in `ray_u` in `u3j_dash`); `hap`, a table from arm
957axis (ie, the axis of each formula within the battery) to driver arm index (into
958`arm_u` in `u3j_core`); `lab`, the complete label path; and `jit`, any other
959dynamic data that may speed up execution.
961We construct `hap`, when we create the calx, by iterating through the arms
962registered in the `u3j_core`. Note the way a `u3j_harm` declares itself, with
963the string `fcs_c` which can contain either an axis or a name. Most jetted cores
964are of course gates, which have one formula at one axis within the core: `fcs_c`
967But we do often have fast cores with more complex arm structure, and it would be
968sad to have to manage their axes by hand. To use an `fcs_c` with a named arm,
969it's sufficient to make sure the name is bound to a formula `[0 axis]` in the
972`jit`, as its name suggests, is a stub where any sort of optimization data
973computed on battery registration might go. To use it, fill in the `_cj_jit()`
976### u3j: the hot dashboard
978Now it should be easy to see how we actually invoke jets. Every time we run a
979nock `9` instruction (pretty often, obviously), we have a core and an axis. We
980pass these to `u3j_kick()`, which will try to execute them.
982Because nouns with a reference count of 1 are precious, `u3j_kick()` has a
983tricky reference control definition. It reserves the right to return `u3_none`
984in the case where there is no driver, or the driver does not apply for this
985case; in this case, it retains argument `cor`. If it succeeds, though, it
988`u3j_kick()` searches for the battery (always the head of the core, of course)
989in the hot dashboard. If the battery is registered, it searches for the axis in
990`hap` in the `calx`. If it exists, the core matches a driver and the driver jets
991this arm. If not, we return `u3_none`.
993Otherwise, we call `fun_f` in our `u3j_harm`. This obeys the same protocol as
994`u3j_kick()`; it can refuse to function by returning `u3_none`, or consume the
997Besides the actual function pointer `fun_f`, we have some flags in the
998`u3j_harm` which tell us how to call the arm function.
1000If `ice` is yes (`&`, `0`), the jet is known to be perfect and we can just trust
1001the product of `fun_f`. Otherwise, we need to run *both* the Nock arm and
1002`fun_f`, and compare their results.
1004(Note that while executing the C side of this test, we have to set `ice` to yes;
1005on the Nock side, we have to set `liv` to no. Otherwise, many non-exponential
1006functions become exponential. When auto-testing jets in this way, the principle
1007is that the test is on the outermost layer of recursion.)
1009(Note also that anyone who multi-threads this execution environment has a slight
1010locking problem with these flags if arm testing is multi-threaded.)
1012If `tot` is yes, (`&`, `0`), the arm function is *total* and has to return
1013properly (though it can still return \*u3\_none*). Otherwise, it is*partial\*
1014and can `u3_cm_bail()` out with c3\_\_punt. This feature has a cost: the jet
1017Finally, if `liv` is no (`|`, 1), the jet is off and doesn't run.
1019It should be easy to see how the tree of cores gets declared - precisely, in
1020`j/dash.c`. We declare the hierarchy as a tree of `u3j_core` structures, each of
1021which comes with a static list of arms `arm_u` and sub-cores `dev_u`.
1023In `u3j_boot()`, we traverse the hierarchy, fill in parent pointers `par_u`, and
1024enumerate all `u3j_core` structures into a single flat array `u3j_dash.ray_u`.
1025Our hot state then appears ready for action.
1027### u3j: jet functions
1029At present, all drivers are compiled statically into `u3`. This is not a
1030long-term permanent solution or anything. However, it will always be the case
1031with a certain amount of core functionality.
1033For instance, there are some jet functions that we need to call as part of
1034loading the Arvo kernel - like `++cue` to unpack a noun from an atom. And
1035obviously it makes sense, when jets are significant enough to compile into `u3`,
1036to export their symbols in headers and the linker.
1038There are three interface prefixes for standard jet functions: `u3k`, `u3q`, and
1039`u3w`. All jets have `u3w` interfaces; most have `u3q`; some have `u3k`. Of
1040course the actual logic is shared.
1042`u3w` interfaces use the same protocol as `fun_f` above: the caller passes the
1043entire core, which is retained if the function returns `u3_none`, transferred
1044otherwise. Why? Again, use counts of 1 are special and precious for performance
1047`u3q` interfaces break the core into C arguments, *retain* noun arguments, and
1048*transfer* noun returns. `u3k` interfaces are the same, except with more use of
1049`u3_none` and other simple C variations on the Hoon original, but *transfer*
1050both arguments and returns. Generally, `u3k` are most convenient for new code.
1052Following `u3k/q/w` is `[a-f]`, corresponding to the 6 logical tiers of the
1053kernel, or `g` for user-level jets. Another letter is added for functions within
1054subcores. The filename, under `j/`, follows the tier and the function name.
1056For instance, `++add` is `u3wa_add(cor)`, `u3qa_add(a, b)`, or `u3ka_add(a, b)`,
1057in `j/a/add.c`. `++get` in `++by` is `u3wdb_get(cor)`, `u3kdb_get(a, b)`, etc,
1060For historical reasons, all internal jet code in `j/[a-f]` *retains* noun
1061arguments, and *transfers* noun results. Please do not do this in new `g` jets!
1062The new standard protocol is to transfer both arguments and results.
1064### u3a: allocation functions
1066`u3a` allocates on the current road (u3R). Its internal structures are
1067uninteresting and typical of a naive allocator.
1069The two most-used `u3a` functions are `u3a_gain()` to add a reference count, and
1070`u3a_lose()` to release one (and free the noun, if the use count is zero). For
1071convenience, `u3a_gain()` returns its argument. The pair are generally
1072abbreviated with the macros `u3k()` and `u3z()` respectively.
1074Normally we create nouns through `u3i` functions, and don't call the `u3a`
1075allocators directly. But if you do:
1077One, there are *two* sets of allocators: the word-aligned allocators and the
1078fully-aligned (ie, malloc compatible) allocators. For instance, on a typical OS
1079X setup, malloc produces 16-byte aligned results - needed for some SSE
1082These allocators are *not compatible*. For 32-bit alignment as used in nouns,
1085 /* u3a_walloc(): allocate storage measured in words.
1088 u3a_walloc(c3_w len_w);
1090 /* u3a_wfree(): free storage.
1093 u3a_wfree(void* lag_v);
1095 /* u3a_wealloc(): word realloc.
1098 u3a_wealloc(void* lag_v, c3_w len_w);
1100For full alignment, call:
1102 /* u3a_malloc(): aligned storage measured in bytes.
1105 u3a_malloc(size_t len_i);
1107 /* u3a_realloc(): aligned realloc in bytes.
1110 u3a_realloc(void* lag_v, size_t len_i);
1112 /* u3a_realloc2(): gmp-shaped realloc.
1115 u3a_realloc2(void* lag_v, size_t old_i, size_t new_i);
1117 /* u3a_free(): free for aligned malloc.
1120 u3a_free(void* tox_v);
1122 /* u3a_free2(): gmp-shaped free.
1125 u3a_free2(void* tox_v, size_t siz_i);
1127There are also a set of special-purpose allocators for building atoms. When
1128building atoms, please remember that it's incorrect to have a high 0 word - the
1129word length in the atom structure must be strictly correct.
1131Of course, we don't always know how large our atom will be. Therefore, the
1132standard way of building large atoms is to allocate a block of raw space with
1133`u3a_slab()`, then chop off the end with `u3a_malt()` (which does the measuring
1134itself) or `u3a_mint()` in case you've measured it yourself.
1136Once again, *do not call `malloc()`* (or C++ `new`) within any code that may be
1137run within a jet. This will cause rare sporadic corruption when we interrupt
1138execution within a `malloc()`. We'd just override the symbol, but `libuv` uses
1139`malloc()` across threads within its own synchronization primitives - for this
1140to work with `u3a_malloc()`, we'd have to introduce our own locks on the
1141surface-level road (which might be a viable solution).
1143### u3n: nock execution
1145The `u3n` routines execute Nock itself. On the inside, they have a surprising
1146resemblance to the spec proper (the only interesting detail is how we handle
1147tail-call elimination) and are, as one would expect, quite slow. (There is no
1148such thing as a fast tree interpreter.)
1150There is only one Nock, but there are lots of ways to call it. (Remember that
1151all `u3n` functions *transfer* C arguments and returns.)
1153The simplest interpreter, `u3n_nock_on(u3_noun bus, u3_noun fol)` invokes Nock
1154on `bus` (the subject) and `fol` (the formula). (Why is it`[subject formula]`,
1155not `[formula subject]`? The same reason `0` is true and `1` is false.)
1157A close relative is `u3n_slam_on(u3_noun gat, u3_noun sam)`, which slams a
1158*gate* (`gat`) on a sample (`sam`). (In a normal programming language which
1159didn't talk funny and was retarded, `u3n_slam_on()` would call a function on an
1160argument.) We could write it most simply as:
1163 u3n_slam_on(u3_noun gat, u3_noun sam)
1165 u3_noun pro = u3n_nock_on
1166 (u3nc(u3k(u3h(gat)),
1167 u3nc(sam, u3k(u3t(u3t(gat))))),
1173Simpler is `u3n_kick_on(u3_noun gat)`, which slams a gate (or, more generally, a
1174*trap* - because sample structure is not even needed here) without changing its
1178 u3n_kick_on(u3_noun gat, u3_noun sam)
1180 return u3n_nock_on(gat, u3k(u3h(gat)));
1183The `_on` functions in `u3n` are all defined as pure Nock. But actually, even
1184though we say we don't extend Nock, we do. But we don't. But we do.
1186Note that `u3` has a well-developed error handling system - `u3m_bail()` to
1187throw an exception, `u3m_soft_*` to catch one. But Nock has no exception model
1188at all. That's okay - all it means if that if an `_on` function bails, the
1189exception is an exception in the caller.
1191However, `u3`'s exception handling happens to match a convenient virtual
1192super-Nock in `hoon.hoon`, the infamous `++mock`. Of course, Nock is slow, and
1193`mock` is Nock in Nock, so it is (logically) super-slow. Then again, so is
1196With the power of `u3`, we nest arbitrary layers of `mock` without any
1197particular performance cost. Moreover, we simply treat Nock proper as a special
1198case of `mock`. (More precisely, the internal VM loop is `++mink` and the error
1199compiler is `++mook`. But we call the whole sandbox system `mock`.)
1201The nice thing about `mock` functions is that (by executing within
1202`u3m_soft_run()`, which as you may recall uses a nested road) they provide both
1203exceptions and the namespace operator - `.^` in Hoon, which becomes operator
1206`11` requires a namespace function, or `fly`, which produces a `++unit` - `~`
1207(`0`) for no binding, or `[0 value]`. The sample to a `fly` is a `++path`, just
1208a list of text `span`.
1210`mock` functions produce a `++toon`. Fully elaborated:
1212 ++ noun ,* :: any noun
1213 ++ path (list ,@ta) :: namespace path
1214 ++ span ,@ta :: text-atom (ASCII)
1215 ++ toon $% [%0 p=noun] :: success
1216 [%1 p=(list path)] :: blocking paths
1217 [%2 p=(list tank)] :: stack trace
1219 ++ tank :: printable
1220 $% [%leaf p=tape] :: flat text
1221 $: %palm :: backstep list
1222 p=[p=tape q=tape r=tape s=tape] :: mid cap open close
1223 q=(list tank) :: contents
1225 $: %rose :: straight list
1226 p=[p=tape q=tape r=tape] :: mid open close
1227 q=(list tank) :: contents
1231(Note that `tank` is overdesigned and due for replacement.)
1233What does a `toon` mean? Either your computation succeded (`[0 noun]`, or could
1234not finish because it blocked on one or more global paths (`[1 (list path)]`),
1235or it exited with a stack trace (`[2 (list tank)]`).
1237Note that of all the `u3` exceptions, only `%exit` is produced deterministically
1238by the Nock definition. Therefore, only `%exit` produces a `2` result. Any other
1239argument to `u3m_bail()` will unwind the virtualization stack all the way to the
1240top - or to be more exact, to `u3m_soft_top()`.
1242In any case, the simplest `mock` functions are `u3n_nock_un()` and
1243`u3n_slam_un()`. These provide exception control without any namespace change,
1244as you can see by the code:
1246 /* u3n_nock_un(): produce .*(bus fol), as ++toon.
1249 u3n_nock_un(u3_noun bus, u3_noun fol)
1251 u3_noun fly = u3nt(u3nt(11, 0, 6), 0, 0); // |=(a=* .^(a))
1253 return u3n_nock_in(fly, bus, fol);
1256 /* u3n_slam_un(): produce (gat sam), as ++toon.
1259 u3n_slam_un(u3_noun gat, u3_noun sam)
1261 u3_noun fly = u3nt(u3nt(11, 0, 6), 0, 0); // |=(a=* .^(a))
1263 return u3n_slam_in(fly, gat, sam);
1266The `fly` is added as the first argument to `u3n_nock_in()` and `u3n_slam_in()`.
1267Of course, logically, `fly` executes in the caller's exception layer.
1268(Maintaining this illusion is slightly nontrivial.) Finally, `u3n_nock_an()` is
1269a sandbox with a null namespace.
1273The only `u3e` function you should need to call is `u3e_save()`, which saves the
1274loom. As it can be restored on any platform, please make sure you don't have any
1275state in the loom that is bound to your process or architecture - except for
1276exceptions like the warm jet state, which is actively purged on reboot.
1278### u3r: reading nouns (weak)
1280As befits accessors they don't make anything, `u3r` noun reading functions
1281always retain their arguments and their returns. They never bail; rather, when
1282they don't work, they return a `u3_weak` result.
1284Most of these functions are straightforward and do only what their comments say.
1285A few are interesting enough to discuss.
1287`u3r_at()` is the familiar tree fragment function, `/` from the Nock spec. For
1288taking complex nouns apart, `u3r_mean()` is a relatively funky way of
1289deconstructing nouns with a varargs list of `axis`, `u3_noun *`. For cells,
1290triples, etc, decompose with `u3r_cell()`, `u3r_trel()`, etc. For the tagged
1291equivalents, use `u3r_pq()` and friends.
1293`u3r_sing(u3_noun a, u3_noun b)` (true if `a` and `b` are a *single* noun) are
1294interesting because it uses mugs to help it out. Clearly, different nouns may
1295have the same mug, but the same nouns cannot have a different mug. It's
1296important to understand the performance characteristics of `u3r_sing()`: the
1297worst possible case is a comparison of duplicate nouns, which have the same
1298value but were created separately. In this case, the tree is traversed
1300`u3r_sung()` is a deeply funky and frightening version of `u3r_sing()` that
1301unifies pointers to the duplicate nouns it finds, freeing the second copy.
1302Obviously, do not use `u3r_sung()` when you have live, but not reference
1303counted, noun references from C - if they match a noun with a refcount of 1 that
1304gets freed, bad things happen.
1306It's important to remember that `u3r_mug()`, which produces a 31-bit, nonzero
1307insecure hash, uses the `mug_w` slot in any boxed noun as a lazy cache. There
1308are a number of variants of `u3r_mug()` that can get you out of building
1311### u3x: reading nouns (bail)
1313`u3x` functions are like `u3r` functions, but instead of returning `u3_none`
1314when (for instance) we try to take the head of an atom, they bail with `%exit`.
1315In other words, they do what the same operation would do in Nock.
1317### u3h: hash tables.
1319We can of course use the Hoon `map` structure as an associative array. This is a
1320balanced treap and reasonably fast. However, it's considerably inferior to a
1321custom structure like an HAMT (hash array-mapped trie). We use `u3_post` to
1322allocate HAMT structures on the loom.
1324(Our HAMT implements the classic Bagwell algorithm which depends on the `gcc`
1325standard directive `__builtin_popcount()`. On a CPU which doesn't support
1326popcount or an equivalent instruction, some other design would probably be
1329There's no particular rocket science in the API. `u3h_new()` creates a
1330hashtable; `u3h_free()` destroys one; `u3h_put()` inserts, `u3h_get()`
1331retrieves. You can transform values in a hashtable with `u3h_walk()`.
1333The only funky function is `u3h_gut()`, which unifies keys with `u3r_sung()`. As
1334with all cases of `u3r_sung()`, this must be used with extreme caution.
1338Connected to the `~+` rune in Hoon, via the Nock `%memo` hint, the memoization
1339facility is a general-purpose cache.
1341(It's also used for partial memoization - a feature that'll probably be removed,
1342in which conservative worklist algorithms (which would otherwise be exponential)
1343memoize everything in the subject *except* the worklist. This is used heavily in
1344the Hoon compiler jets (j/f/\*.c). Unfortunately, it's probably not possible to
1345make this work perfectly in that it can't be abused to violate Nock, so we'll
1346probably remove it at a later date, instead making `++ut` keep its own monadic
1349Each `u3z` function comes with a `c3_m` mote which disambiguates the function
1350mapping key to value. For Nock itself, use 0. For extra speed, small tuples are
1351split out in C; thus, find with
1353 u3_weak u3z_find(c3_m, u3_noun);
1354 u3_weak u3z_find_2(c3_m, u3_noun, u3_noun);
1355 u3_weak u3z_find_3(c3_m, u3_noun, u3_noun, u3_noun);
1356 u3_weak u3z_find_4(c3_m, u3_noun, u3_noun, u3_noun, u3_noun);
1360 u3_noun u3z_save(c3_m, u3_noun, u3_noun);
1361 u3_noun u3z_save_2(c3_m, u3_noun, u3_noun, u3_noun);
1362 u3_noun u3z_save_3(c3_m, u3_noun, u3_noun, u3_noun, u3_noun);
1363 u3_noun u3z_save_4(c3_m, u3_noun, u3_noun, u3_noun, u3_noun, u3_noun);
1365where the value is the last argument. To eliminate duplicate nouns, there is
1371`u3z` functions retain keys and transfer values.
1373The `u3z` cache, built on `u3h` hashes, is part of the current road, and goes
1374away when it goes away. (In future, we may wish to promote keys/values which
1375outlive the road, as we do with jet state.) There is no cache reclamation at
1376present, so be careful.
1378### u3t: tracing and profiling.
1382### u3v: the Arvo kernel
1384An Arvo kernel - or at least, a core that compiles with the Arvo interface - is
1385part of the global `u3` state. What is an Arvo core? Slightly pseudocoded:
1389 ++ come |/ {yen/@ ova/(list ovum) nyf/pone} :: 11
1390 ^- {(list ovum) _+>}
1392 ++ keep |/ {now/@da hap/path} :: 4
1395 ++ load |/ {yen/@ ova/(list ovum) nyf/pane} :: 86
1396 ^- {(list ovum) _+>}
1398 ++ peek |/ {now/@da path} :: 87
1401 ++ poke |/ {now/@da ovo/ovum} :: 42
1402 ^- {(list ovum) _+>}
1404 ++ wish |/ txt/@ta :: 20
1408 ++ card {p/@tas q/*} :: typeless card
1409 ++ ovum {p/wire q/card} :: Arvo event
1410 ++ wire path :: event cause
1412This is the Arvo ABI in a very real sense. Arvo is a core with these six arms.
1413To use these arms, we hardcode the axis of the formula (`11`, `4`, `86`, etc)
1414into the C code that calls Arvo, because otherwise we'd need type metadata -
1415which we can get, by calling Arvo.
1417It's important to understand the Arvo event/action structure, or `++ovum`. An
1418`ovum` is a `card`, which is any `[term noun]` cell, and a `++wire`, a `path`
1419which indicates the location of the event. At the Unix level, the `wire`
1420corresponds to a system module or context. For input events, this is the module
1421that caused the event; for output actions, it's the module that performs the
1424`++poke` sends Arvo an event `ovum`, producing a cell of action ova and a new
1427`++peek` dereferences the Arvo namespace. It takes a date and a key, and
1428produces `~` (`0`) or `[~ value]`.
1430`++keep` asks Arvo the next time it wants to be woken up, for the given `wire`.
1431(This input will probably be eliminated in favor of a single global timer.)
1433`++wish` compiles a string of Hoon source. While just a convenience, it's a very
1434convenient convenience.
1436`++come` and `++load` are used by Arvo to reset itself (more precisely, to shift
1437the Arvo state from an old kernel to a new one); there is no need to call them
1440Now that we understand the Arvo kernel interface, let's look at the `u3v` API.
1441As usual, all the functions in `u3v` are commented, but unfortunately it's hard
1442to describe this API as clean at present. The problem is that `u3v` remains
1443design coupled to the old `vere` event handling code written for `u2`. But let's
1444describe the functions you should be calling, assuming you're not writing the
1445next event system. There are only two.
1447`u3v_wish(str_c)` wraps the `++wish` functionality in a cache (which is
1448read-only unless you're on the surface road).
1450`u3v_do()` uses `wish` to provide a convenient interface for calling Hoon kernel
1451functions by name. Even more conveniently, we tend to call `u3v_do()` with these
1454 #define u3do(txt_c, arg) u3v_do(txt_c, arg)
1455 #define u3dc(txt_c, a, b) u3v_do(txt_c, u3nc(a, b))
1456 #define u3dt(txt_c, a, b, c) u3v_do(txt_c, u3nt(a, b, c))
1457 #define u3dq(txt_c, a, b, c, d) u3v_do(txt_c, u3nt(a, b, c, d))
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list