9The Urbit interpreter is built on a Nock runtime system written
10in C, `u3`. This document is a relatively complete description
12You should keep reading if (a) you're planning to work on the
13Urbit interpreter; (b) you're a language implementation geek; or
14(c) you don't really understand anything until you've seen the
17## u3: noun processing in C
19`u3` is the C library that makes Urbit work. If it wasn't called
20`u3`, it might be called `libnoun` - it's a library for making
23What's a noun? A noun is either a cell or an atom. A cell is an
24ordered pair of any two nouns. An atom is an unsigned integer of
27To the C programmer, this is not a terribly complicated data
28structure, so why do you need a library for it?
30One: nouns have a well-defined computation kernel, Nock, whose
31spec fits on a page and gzips to 340 bytes. But the only
32arithmetic operation in Nock is increment. So it's nontrivial
33to compute both efficiently and correctly.
35Two: `u3` is designed to be a "solid-state interpreter," ie, a
36single-level store which is transparently snapshotted. This
37implies a specialized memory-management model, etc, etc.
39(Does `u3` depend on the higher levels of Urbit, Arvo and Hoon?
40Yes and no. `u3` expects you to load something shaped like an
41Arvo kernel, and use it as an event-processing function. But you
42don't need to use this feature if you don't want, and your kernel
43doesn't have to be Arvo proper - just Arvo-compatible. Think of
44`u3` as the BIOS and Arvo as the boot kernel. And there are no
45dependencies at all between Hoon the language and `u3`.)
49Under `u3` is the simple `c3` layer, which is just how we write C
52When writing C in u3, please of course follow the conventions of
53the code around you as regards indentation, etc. It's especially
54important that every function have a header comment, even if it
55says nothing interesting.
57But some of our idiosyncrasies go beyond convention. Yes, we've
58done awful things to C. Here's what we did and why we did.
62First, it's generally acknowledged that underspecified integer
63types are C's worst disaster. C99 fixed this, but the `stdint`
64types are wordy and annoying. We've replaced them with:
68 typedef uint64_t c3_d; // double-word
69 typedef int64_t c3_ds; // signed double-word
70 typedef uint32_t c3_w; // word
71 typedef int32_t c3_ws; // signed word
72 typedef uint16_t c3_s; // short
73 typedef int16_t c3_ss; // signed short
74 typedef uint8_t c3_y; // byte
75 typedef int8_t c3_ys; // signed byte
76 typedef uint8_t c3_b; // bit
78 typedef uint8_t c3_t; // boolean
79 typedef uint8_t c3_o; // loobean
80 typedef uint8_t c3_g; // 5-bit atom for a 32-bit log.
81 typedef uint32_t c3_l; // little; 31-bit unsigned integer
82 typedef uint32_t c3_m; // mote; also c3_l; LSB first a-z 4-char string.
86 typedef char c3_c; // does not match int8_t or uint8_t
87 typedef int c3_i; // int - really bad
88 typedef uintptr_t c3_p; // pointer-length uint - really really bad
89 typedef intptr_t c3_ps; // pointer-length int - really really bad
91Some of these need explanation. A loobean is a Nock boolean -
92Nock, for mysterious reasons, uses 0 as true (always say "yes")
93and 1 as false (always say "no").
95Nock and/or Hoon cannot tell the difference between a short atom
96and a long one, but at the `u3` level every atom under `2^31` is
97direct. The `c3_l` type is useful to annotate this. A `c3_m` is
98a *mote* - a string of up to 4 characters in a `c3_l`, least
99significant byte first. A `c3_g` should be a 5-bit atom. Of
100course, C cannot enforce these constraints, only document them.
102Use the "bad" - ie, poorly specified - integer types only when
103interfacing with external code that expects them.
105An enormous number of motes are defined in `i/c/motes.h`. There
106is no reason to delete motes that aren't being used, or even to
107modularize the definitions. Keep them alphabetical, though.
109### c3: variables and variable naming
111The C3 style uses Hoon style TLV variable names, with a quasi
112Hungarian syntax. This is weird, but works really well, as long
113as what you're doing isn't hideously complicated. (Then it works
114badly, but we shouldn't need anything hideous in u3.)
116A TLV variable name is a random pronounceable three-letter
117string, sometimes with some vague relationship to its meaning,
118but usually not. Usually CVC (consonant-vowel-consonant) is a
121You should use TLVs much the way math people use Greek letters.
122The same concept should in general get the same name across
123different contexts. When you're working in a given area, you'll
124tend to remember the binding from TLV to concept by sheer power
125of associative memory. When you come back to it, it's not that
126hard to relearn. And of course, when in doubt, comment it.
128Variables take pseudo-Hungarian suffixes, matching in general the
129suffix of the integer type:
131 c3_w wor_w; // 32-bit word
133Unlike in standard Hungarian, there is no change for pointer
134variables. C structure variables take a `_u` suffix.
138The code (from `defs.h`) tells the story:
143 # define _(x) (c3y == (x))
144 # define __(x) ((x) ? c3y : c3n)
145 # define c3a(x, y) __(_(x) && _(y))
146 # define c3o(x, y) __(_(x) || _(y))
148In short, use `_()` to turn a loobean into a boolean, `__` to go
149the other way. Use `!` as usual, `c3y` for yes and `c3n` for no,
150`c3a` for and and `c3o` for or.
154The division between `c3` and `u3` is that you could theoretically
155imagine using `c3` as just a generic C environment. Anything to do
156with nouns is in `u3`.
158### u3: a map of the system
160There are two kinds of symbols in `u3`: regular and irregular.
161Regular symbols follow this pattern:
164 -------------------------------------------------------
165 u3a_ allocation i/n/a.h n/a.c
166 u3e_ persistence i/n/e.h n/e.c
167 u3h_ hashtables i/n/h.h n/h.c
168 u3i_ noun construction i/n/i.h n/i.c
169 u3j_ jet control i/n/j.h n/j.c
170 u3m_ system management i/n/m.h n/m.c
171 u3n_ nock computation i/n/n.h n/n.c
172 u3r_ noun access (error returns) i/n/r.h n/r.c
173 u3t_ profiling i/n/t.h n/t.c
174 u3v_ arvo i/n/v.h n/v.c
175 u3x_ noun access (error crashes) i/n/x.h n/x.c
176 u3z_ memoization i/n/z.h n/z.c
177 u3k[a-g] jets (transfer, C args) i/j/k.h j/[a-g]/*.c
178 u3q[a-g] jets (retain, C args) i/j/q.h j/[a-g]/*.c
179 u3w[a-g] jets (retain, nock core) i/j/w.h j/[a-g]/*.c
181Irregular symbols always start with `u3` and obey no other rules.
182They're defined in `i/n/u.h`. Finally, `i/all.h` includes all
183these headers (fast compilers, yay) and is all you need to
186### u3: noun internals
188A noun is a `u3_noun` - currently defined as a 32-bit `c3_w`.
190If your `u3_noun` is less than `(1 << 31)`, it's a direct atom.
191Every unsigned integer between `0` and `0x7fffffff` inclusive is
194If bit `31` is set in a `u3_noun`, bit `30` is always set - this
195bit is reserved. Bit `29` is `1` if the noun is a cell, `0` if
196it's an atom. Bits `28` through `0` are a word pointer into the
197loom - see below. The structures are:
202 c3_w buf_w[0]; // actually [len_w]
211The only thing that should be mysterious here is `mug_w`, which
212is a 31-bit lazily computed nonzero short hash (FNV currently,
213soon Murmur3). If `mug_w` is 0, the hash is not yet computed.
214We also hijack this field for various hacks, such as saving the
215new address of a noun when copying over.
217Also, the value `0xffffffff` is `u3_none`, which is never a valid
218noun. Use the type `u3_weak` to express that a noun variable may
221### u3: reference counts
223The only really essential thing you need to know about `u3` is
224how to handle reference counts. Everything else, you can skip
227u3 deals with reference-counted, immutable, acyclic nouns.
228Unfortunately, we are not Apple and can't build reference
229counting into your C compiler, so you need to count by hand.
231Every allocated noun (or any allocation object, because our
232allocator is general-purpose) contains a counter which counts the
233number of references to it - typically variables with type
234`u3_noun`. When this counter goes to 0, the noun is freed.
236To tell `u3` that you've added a reference to a noun, call the
237function `u3a_gain()` or its shorthand `u3k()`. (For your
238convenience, this function returns its argument.) To tell `u3`
239that you've destroyed a reference, call `u3a_lose()` or `u3z()`.
241(If you screw up by decrementing the counter too much, `u3` will
242dump core in horrible ways. If you screw up by incrementing it
243too much, `u3` will leak memory. To check for memory leaks,
244set the `bug_o` flag in `u3e_boot()` - eg, run `vere` with `-g`.
245Memory leaks are difficult to debug - the best way to handle
246leaks is just to revert to a version that didn't have them, and
247look over your code again.)
249(You can gain or lose a direct atom. It does nothing.)
251### u3: reference protocols
253*THIS IS THE MOST CRITICAL SECTION IN THE `u3` DOCUMENTATION.*
255The key question when calling a C function in a refcounted world
256is what the function will do to the noun refcounts - and, if the
257function returns a noun, what it does to the return.
259There are two semantic patterns, `transfer` and `retain`. In
260`transfer` semantics, the caller "gives" a use count to the
261callee, which "gives back" any return. For instance, if I have
264 u3_noun foo = u3i_string("foobar");
272Suppose `u3f_futz()` has `transfer` semantics. At `[...]`, my
273code holds one reference to `bar` and zero references to `foo` -
274which has been freed, unless it's part of `bar`. My code now
275owns `bar` and gets to work with it until it's done, at which
276point a `u3z()` is required.
278On the other hand, if `u3f_futz()` has `retain` semantics, we
282 u3_noun foo = u3i_string("foobar");
290because calling `u3f_futz()` does not release our ownership of
291`foo`, which we have to free ourselves.
293But if we free `bar`, we are making a great mistake, because our
294reference to it is not in any way registered in the memory
295manager (which cannot track references in C variables, of
296course). It is normal and healthy to have these uncounted
297C references, but they must be treated with care.
299The bottom line is that it's essential for the caller to know
300the refcount semantics of any function which takes or returns a
301noun. (In some unusual circumstances, different arguments or
302returns in one function may be handled differently.)
304Broadly speaking, as a design question, retain semantics are more
305appropriate for functions which inspect or query nouns. For
306instance, `u3h()` (which takes the head of a noun) retains, so
307that we can traverse a noun tree without constantly incrementing
310Transfer semantics are more appropriate for functions which make
311nouns, which is obviously what most functions do.
313In general, though, in most places it's not worth thinking about
314what your function does. There is a convention for it, which
315depends on where it is, not what it does. Follow the convention.
317### u3: reference conventions
319The `u3` convention is that, unless otherwise specified, *all
320functions have transfer semantics* - with the exception of the
321prefixes: `u3r`, `u3x`, `u3z`, `u3q` and `u3w`. Also, within
322jet directories `a` through `f` (but not `g`), internal functions
323retain (for historical reasons).
325If functions outside this set have retain semantics, they need to
326be commented, both in the `.h` and `.c` file, with `RETAIN` in
327all caps. Yes, it's this important.
329### u3: system architecture
331If you just want to tinker with some existing code, it might be
332enough to understand the above. If not, it's probably worth
333taking the time to look at `u3` as a whole.
335`u3` is designed to work as a persistent event processor.
336Logically, it computes a function of the form
338 f(event, old state) -> (actions, new state)
340Obviously almost any computing model - including, but not limited
341to, Urbit - can be defined in this form. To create the illusion
342of a computer that never loses state and never fails, we:
344- log every event externally before it goes into u3
345- keep a single reference to a permanent state noun.
346- can abort any event without damaging the permanent state.
347- snapshot the permanent state periodically, and/or prune logs.
349### u3: the road model
351`u3` uses a memory design which I'm sure someone has invented
352somewhere before, because it's not very clever, but I've never
353seen it anywhere in particular.
355Every allocation starts with a solid block of memory, which `u3`
356calls the `loom`. How do we allocate on the loom? You're
357probably familiar with the Unix heap-stack design, in which the
358stack grows downward and the heap (malloc arena) grows upward:
362 |------------#################################+++++++++++++|
366A road is a normal heap-stack system, except that the heap
367and stack can point in *either direction*. Therefore, inside
368a road, we can nest another road in the *opposite direction*.
370When the opposite road completes, its heap is left on top of
371the opposite heap's stack. It's no more than the normal
372behavior of a stack machine for all subcomputations to push
373their results on the stack.
375The performance tradeoff of "leaping" - reversing directions in
376the road - is that if the outer computation wants to preserve the
377results of the inner one, not just use them for temporary
378purposes, it has to *copy them*.
380This is a trivial cost in some cases, a prohibitive cost in
381others. The upside, of course, is that all garbage accrued
382in the inner computation is discarded at zero cost.
384The goal of the road system is the ability to *layer* memory
385models. If you are allocating on a road, you have no idea
386how deep within a nested road system you are - in other words,
387you have no idea exactly how durable your result may be.
388But free space is never fragmented within a road.
390Roads do not reduce the generality or performance of a memory
391system, since even the most complex GC system can be nested
392within a road at no particular loss of performance - a road
393is just a block of memory.
395Each road (`u3a_road` to be exact) uses four pointers: `rut` is
396the bottom of the arena, `hat` the top of the arena, `mat` the
397bottom of the stack, `cap` the top of the stack. (Bear in mind
398that the road "stack" is not actually used as the C function-call
399stack, though it probably should be.)
401A "north" road has the stack high and the heap low:
405 |~~~~~~~~~~~~-------##########################+++++++$~~~~~|
409A "south" road is the other way around:
413 |~~~~~~~~~~~~$++++++##########################--------~~~~~|
417Legend: `-` is durable storage (heap); `+` is temporary storage
418(stack); `~` is deep storage (immutable); `$` is the allocation
419frame `#` is free memory.
421Pointer restrictions: pointers stored in `+` can point anywhere.
422Pointers in `-` can only point to `-` or `~`; pointers in `~`
425To "leap" is to create a new inner road in the `###` free space.
426but in the reverse direction, so that when the inner road
427"falls" (terminates), its durable storage is left on the
428temporary storage of the outer road.
430`u3` keeps a global variable, `u3_Road` or its alias `u3R`, which
431points to the current road. (If we ever run threads in inner
432roads - see below - this will become a thread-local variable.)
433Relative to `u3R`, `+` memory is called `junior` memory; `-`
434memory is `normal` memory; `~` is `senior` memory.
436### u3: explaining the road model
440We're now ready to understand why the road system works so
441logically with the event and persistence model.
443The key is that *we don't update refcounts in senior memory.*
444A pointer from an inner road to an outer road is not counted.
445Also, the outmost, or `surface` road, is the only part of the
446image that gets checkpointed.
448So the surface road contains the entire durable state of `u3`.
449When we process an event, or perform any kind of complicated or
450interesting calculation, *we process it in an inner road*. If
451its results are saved, they need to be copied.
453Since processing in an inner road does not touch surface memory,
454(a) we can leave the surface road in a read-only state and not
455mark its pages dirty; (b) we can abort an inner calculation
456without screwing up the surface; and (c) because inner results
457are copied onto the surface, the surface doesn't get fragmented.
459All of (a), (b) and (c) are needed for checkpointing to be easy.
460It might be tractable otherwise, but easy is even better.
462Moreover, while the surface is most definitely single-threaded,
463we could easily run multiple threads in multiple inner roads
464(as long as the threads don't have pointers into each others'
465memory, which they obviously shouldn't).
467Moreover, in future, we'll experiment more with adding road
468control hints to the programmer's toolbox. Reference counting is
469expensive. We hypothesize that in many - if not most - cases,
470the programmer can identify procedural structures whose garbage
471should be discarded in one step by copying the results. Then,
472within the procedure, we can switch the allocator into `sand`
473mode, and stop tracking references at all.
475### u3: rules for C programming
477There are two levels at which we program in C: (1) above the
478interpreter; (2) within the interpreter or jets. These have
479separate rules which need to be respected.
481### u3: rules above the interpreter
483In its relations with Unix, Urbit follows a strict rule of "call
484me, I won't call you." We do of course call Unix system calls,
485but only for the purpose of actually computing.
487Above Urbit, you are in a normal C/Unix programming environment
488and can call anything in or out of Urbit. Note that when using
489`u3`, you're always on the surface road, which is not thread-safe
490by default. Generally speaking, `u3` is designed to support
491event-oriented, single-threaded programming.
493If you need threads which create nouns, you could use
494`u3m_hate()` and `u3m_love()` to run these threads in subroads.
495You'd need to make the global road pointer, `u3R`, a thread-local
496variable instead. This seems perfectly practical, but we haven't
497done it because we haven't needed to.
499### u3: rules within the interpreter
501Within the interpreter, your code can run either in the surface
502road or in a deep road. You can test this by testing
506ie: does the pier's home road equal the current road pointer?
508Normally in this context you assume you're obeying the rules of
509running on an inner road, ie, "deep memory." Remember, however,
510that the interpreter *can* run on surface memory - but anything
511you can do deep, you can do on the surface. The converse is by
514In deep memory, think of yourself as if in a signal handler.
515Your execution context is extremely fragile and may be terminated
516without warning or cleanup at any time (for instance, by `ctrl-c`).
518For instance, you can't call `malloc` (or C++ `new`) in your C
519code, because you don't have the right to modify data structures
520at the global level, and will leave them in an inconsistent state
521if your inner road gets terminated. (Instead, use our drop-in
522replacements, `u3a_malloc()`, `u3a_free()`, `u3a_realloc()`.)
524A good example is the different meaning of `c3_assert()` inside
525and outside the interpreter. At either layer, you can use
526regular assert(), which will just kill your process. On the
527surface, `c3_assert()` will just... kill your process.
529In deep execution, `c3_assert()` will issue an exception that
530queues an error event, complete with trace stack, on the Arvo
531event queue. Let's see how this happens.
535You produce an exception with
537 /* u3m_bail(): bail out. Does not return.
541 ** %exit :: semantic failure
542 ** %evil :: bad crypto
543 ** %intr :: interrupt
544 ** %fail :: execution failure
545 ** %foul :: assert failure
546 ** %need :: network block
547 ** %meme :: out of memory
548 ** %time :: timed out
549 ** %oops :: assertion failure
552 u3m_bail(c3_m how_m);
554Broadly speaking, there are two classes of exception: internal
555and external. An external exception begins in a Unix signal
556handler. An internal exception begins with a call to longjmp()
559There are also two kinds of exception: mild and severe. An
560external exception is always severe. An internal exception is
561normally mild, but some (like `c3__oops`, generated by
562`c3_assert()`) are severe.
564Either way, exceptions come with a stack trace. The `u3` nock
565interpreter is instrumented to retain stack trace hints and
566produce them as a printable `(list tank)`.
568Mild exceptions are caught by the first virtualization layer and
569returned to the caller, following the behavior of the Nock
570virtualizer `++mock` (in `hoon.hoon`)
572Severe exceptions, or mild exceptions at the surface, terminate
573the entire execution stack at any depth and send the cumulative
574trace back to the `u3` caller.
576For instance, `vere` uses this trace to construct a `%crud`
577event, which conveys our trace back toward the Arvo context where
578it crashed. This lets any UI component anywhere, even on a
579remote node, render the stacktrace as a consequence of the user's
580action - even if its its direct cause was (for instance) a Unix
583### u3: C structures on the loom
585Normally, all data on the loom is nouns. Sometimes we break this
586rule just a little, though - eg, in the `u3h` hashtables.
588To point to non-noun C structs on the loom, we use a `u3_post`,
589which is just a loom word offset. A macro lets us declare this
590as if it was a pointer:
592 typedef c3_w u3_post;
593 #define u3p(type) u3_post
595Some may regard this as clever, others as pointless. Anyway, use
596`u3to()` and `u3of()` to convert to and from pointers.
598When using C structs on the loom - generally a bad idea - make
599sure anything which could be on the surface road is structurally
600portable, eg, won't change size when the pointer size changes.
601(Note also: we consider little-endian, rightly or wrongly, to
602have won the endian wars.)
604## u3: API overview by prefix
606Let's run through the `u3` modules one by one. All public
607functions are commented, but the comments may be cryptic.
613 /* u3m_boot(): start the u3 system.
616 u3m_boot(c3_o nuu_o, c3_o bug_o, c3_c* dir_c);
618`nuu_o` is `c3y` (yes, `0`) if you're creating a new pier,
619`c3n` (no, `1`) if you're loading an existing one. `bug_o`
620is `c3y` if you want to test the garbage-collector, `c3n`
621otherwise. `dir_c` is the directory for the pier files.
623`u3m_boot()` expects an `urbit.pill` file to load the kernel
624from. It will try first `$dir/.urb.urbit.pill`, then `U3_LIB`.
626Any significant computation with nouns, certainly anything Turing
627complete, should be run (a) virtualized and (b) in an inner road.
628These are slightly different things, but at the highest level we
629bundle them together for your convenience, in `u3m_soft()`:
631 /* u3m_soft(): system soft wrapper. unifies unix and nock errors.
633 ** Produces [%$ result] or [%error (list tank)].
636 u3m_soft(c3_w sec_w, u3_funk fun_f, u3_noun arg);
638`sec_w` is the number of seconds to time out the computation.
639`fun_f` is a C function accepting `arg`.
641The result of `u3m_soft()` is a cell whose head is an atom. If
642the head is `%$` - ie, `0` - the tail is the result of
643`fun_f(arg)`. Otherwise, the head is a `term` (an atom which is
644an LSB first string), and the tail is a `(list tank)` (a list of
645`tank` printables - see `++tank` in `hoon.hoon`). Error terms
646should be the same as the exception terms above.
648If you're confident that your computation won't fail, you can
649use `u3m_soft_sure()`, `u3m_soft_slam()`, or `u3m_soft_nock()`
650for C functions, Hoon function calls, and Nock invocations.
651Caution - this returns just the result, and asserts globally.
653All the `u3m_soft` functions above work *only on the surface*.
654Within the surface, virtualize with `u3m_soft_run()`. Note that
655this takes a `fly` (a namespace gate), thus activating the `11`
656super-operator in the nock virtualizer, `++mock`. When actually
657using the `fly`, call `u3m_soft_esc()`. Don't do either unless
658you know what you're doing!
660For descending into a subroad *without* Nock virtualization,
661use `u3m_hate()` and `u3m_love` respectively. Hating enters
662a subroad; loving leaves it, copying out a product noun.
664Other miscellaneous tools in `u3m`: `u3m_file()` loads a Unix
665file as a Nock atom; `u3m_water()` measures the boundaries of
666the loom in current use (ie, watermarks); and a variety of
667prettyprinting routines, none perfect, are available, mainly for
668debugging printfs: `u3m_pretty()`, `u3m_p()`, `u3m_tape()` and
671It's sometimes nice to run a mark-and-sweep garbage collector,
672`u3m_grab()`, which collects the world from a list of roots,
673and asserts if it finds any leaks or incorrect refcounts. This
674tool is for debugging and long-term maintenance only; refcounts
679The jet system, `u3j`, is what makes `u3` and `nock` in any sense
680a useful computing environment. Except perhaps `u3a` (there is
681really no such thing as a trivial allocator, though `u3a` is
682dumber than most) - `u3j` is the most interesting code in `u3`.
684Let's consider the minor miracle of driver-to-battery binding
685which lets `u3j` work - and decrement not be `O(n)` - without
686violating the precisely defined semantics of pure Nock, *ever*.
688It's easy to assume that jets represent an architectural coupling
689between Hoon language semantics and Nock interpreter internals.
690Indeed such a coupling would be wholly wrongtious and un-Urbit.
691But the jet system is not Hoon-specific. It is specific to nock
692runtime systems that use a design pattern we call a `core`.
694#### u3j: core structure
696A core is no more than a cell `[code data]`, in which a `code` is
697either a Nock formula or a cell of `code`s, and `data` is anything.
698In a proper core, the subject each formula expects is the core
701Except for the arbitrary decision to make a core `[code data]`,
702(or as we sometimes say, `[battery payload]`), instead of `[data
703code]`, any high-level language transforming itself to Nock would
706So jets are in fact fully general. Broadly speaking, the jet
707system works by matching a C *driver* to a battery. When the
708battery is invoked with Nock operator `9`, it must be found in
709associative memory and linked to its driver. Then we link the
710formula axis of the operation (`a` in `[9 a b]`) to a specific
711function in the driver.
713To validate this jet binding, we need to know two things. One,
714we need to know the C function actually is a perfect semantic
715match for the Nock formula. This can be developed with driver
716test flags, which work, and locked down with a secure formula
717hash in the driver, which we haven't bothered with just yet.
718(You could also try to develop a formal method for verifying
719that C functions and Nock formulas are equivalent, but this is
720a research problem for the future.)
722Two, we need to validate that the payload is appropriate for the
723battery. We should note that jets are a Nock feature and have no
724reference to Hoon. A driver which relies on the Hoon type system
725to only pair it with valid payloads is a broken driver, and
726breaks the Nock compliance of the system as a whole. So don't.
728Now, a casual observer might look at `[battery payload]` and
729expect the simplest case of it to be `[formula subject]`. That
730is: to execute a simple core whose battery is a single formula,
735Then, naturally, when we go from Hoon or a high-level language
736containing functions down to Nock, `[function arguments]` turns
737into `[formula subject]`. This seems like an obvious design, and
738we mention it only because it is *completely wrong*.
740Rather, to execute a one-armed core like the above, we run
744and the normal structure of a `gate`, which is simply Urbitese
747 [formula [sample context]]
749where `sample` is Urbitese for "arguments" - and `context`, any
750Lisper will at once recognize, is Urbitese for "environment."
752To `slam` or call the gate, we simply replace the default sample
753with the caller's data, then nock the formula on the entire gate.
755What's in the context? Unlike in most dynamic languages, it is
756not some secret system-level bag of tricks. Almost always it is
757another core. This onion continues until at the bottom, there is
758an atomic constant, conventionally is the kernel version number.
760Thus a (highly desirable) `static` core is one of the form
763 [battery static-core]
765ie, a solid stack of nested libraries without any dynamic data.
766The typical gate will thus be, for example,
768 [formula [sample [battery battery battery constant]]]
770but we would be most foolish to restrict the jet mechanism to
771cores of this particular structure. We cannot constrain a
772payload to be `[sample static-core]`, or even `[sample core]`.
773Any such constraint would not be rich enough to handle Hoon,
774let alone other languages.
778There are two fundamental rules of computer science: (1) every
779system is best understood through its state; (2) less state is
780better than more state. Sadly, a pier has three different jet
781state systems: `cold`, `warm` and `hot`. It needs all of them.
783Hot state is associated with this particular Unix process. The
784persistent pier is portable not just between process and process,
785but machine and machine or OS and OS. The set of jets loaded
786into a pier may itself change (in theory, though not in the
787present implementation) during the lifetime of the process. Hot
788state is a pure C data structure.
790Cold state is associated with the logical execution history of
791the pier. It consists entirely of nouns and ignores restarts.
793Warm state contains all dependencies between cold and hot
794state. It consists of C structures allocated on the loom.
796Warm state is purely a function of cold and hot states, and
797we can wipe and regenerate it at any time. On any restart where
798the hot state might have changed, we clear the warm state
801There is only one hot state, the global jet dashboard
802`u3j_Dash` or `u3D` for short. In the present implementation,
803u3D is a static structure not modified at runtime, except for
804numbering itself on process initialization. This structure -
805which embeds function pointers to all the jets - is defined
806in `j/tree.c`. The data structures:
808 /* u3j_harm: driver arm.
810 typedef struct _u3j_harm {
811 c3_c* fcs_c; // `.axe` or name
812 u3_noun (*fun_f)(u3_noun); // compute or 0 / semitransfer
813 c3_o ice; // perfect (don't test)
814 c3_o tot; // total (never punts)
815 c3_o liv; // live (enabled)
818 /* u3j_core: C core driver.
820 typedef struct _u3j_core {
821 c3_c* cos_c; // control string
822 struct _u3j_harm* arm_u; // blank-terminated static list
823 struct _u3j_core* dev_u; // blank-terminated static list
824 struct _u3j_core* par_u; // dynamic parent pointer
825 c3_l jax_l; // dynamic jet index
828 /* u3e_dash, u3_Dash, u3D: jet dashboard singleton
830 typedef struct _u3e_dash {
831 u3j_core* dev_u; // null-terminated static list
832 c3_l len_l; // ray_u filled length
833 c3_l all_l; // ray_u allocated length
834 u3j_core* ray_u; // dynamic driver array
837Warm and cold state is *per road*. In other words, as we nest
838roads, we also nest jet state. The jet state in the road is:
840 struct { // jet dashboard
841 u3p(u3h_root) har_p; // warm state
842 u3_noun das; // cold state
845In case you understand Hoon, `das` (cold state) is a `++dash`,
846and `har_p` (warm state) is a map from battery to `++calx`:
848 ++ bane ,@tas :: battery name
849 ++ bash ,@uvH :: label hash
850 ++ bosh ,@uvH :: local battery hash
851 ++ batt ,* :: battery
853 $: jax=,@ud :: hot core index
854 hap=(map ,@ud ,@ud) :: axis/hot arm index
855 lab=path :: label as path
856 jit=* :: arbitrary data
858 ++ calx (trel calf (pair bash cope) club) :: cached by battery
859 ++ clog (pair cope (map batt club)) :: identity record
860 ++ club (pair corp (map term nock)) :: battery pattern
861 ++ cope (trel bane axis (each bash noun)) :: core pattern
863 ++ corp (each core batt) :: parent or static
864 ++ dash (map bash clog) :: jet system
866The driver index `jax` in a `++calx` is an index into `ray_u` in the
867dashboard - ie, a pointer into hot state. This is why the warm
868state has to be reset when we reload the pier in a new process.
870Why is jet state nested? Nock of course is a functional system,
871so as we compute we don't explicitly create state. Jet state is
872an exception to this principle (which works only because it can't
873be semantically detected from Nock/Hoon) - but it can't violate
874the fundamental rules of the allocation system.
876For instance, when we're on an inner road, we can't allocate on
877an outer road, or point from an outer road to an inner. So if we
878learn something - like a mapping from battery to jet - in the
879inner road, we have to keep it in the inner road.
881Mitigating this problem, when we leave an inner road (with
882`u3m_love()`), we call `u3j_reap()` to promote jet information in
883the dying road. Reaping promotes anything we've learned about
884any battery that either (a) already existed in the outer road, or
885(b) is being saved to the outer road.
889Jet binding starts with a `%fast` hint. (In Hoon, this is
890produced by the runes `~%`, for the general case, or `~/`
891for simple functions.) To bind a jet, execute a formula of the
894 [10 [%fast clue-formula] core-formula]
896`core-formula` assembles the core to be jet-propelled.
897`clue-formula` produces the hint information, or `++clue`
898above, which we want to annotate it with.
900A clue is a triple of name, parent, and hooks:
902 ++ clue (trel chum nock (list (pair term nock)))
904The name, or `++chum`, has a bunch of historical structure which
905we don't need (cleaning these things up is tricky), but just gets
906flattened into a term.
908The parent axis is a nock formula, but always reduces to a simple
909axis, which is the address of this core's *parent*. Consider
910again an ordinary gate
912 [formula [sample context]]
914Typically the `context` is itself a library core, which itself
915has a jet binding. If so, the parent axis of this gate is `7`.
917If the parent is already bound - and the parent *must* be already
918bound, in this road or a road containing it - we can hook this core
919bottom-up into a tree hierarchy. Normally the child core is
920produced by an arm of the parent core, so this is not a problem -
921we wouldn't have the child if we hadn't already made the parent.
923The clue also contains a list of *hooks*, named nock formulas on
924the core. Usually these are arms, but they need not be. The
925point is that we often want to call a core from C, in a situation
926where we have no type or other source information. A common case
927of this is a complex system in which we're mixing functions which
928are jet-propelled with functions that aren't.
930In any case, all the information in the `%fast` hint goes to
931`u3j_mine()`, which registers the battery in cold state (`das` in
932`jed` in `u3R`), then warm state (`har_p` in `jed`).
934It's essential to understand that the `%fast` hint has to be,
935well, fast - because we apply it whenever we build a core. For
936instance, if the core is a Hoon gate - a function - we will call
937`u3j_mine` every time the function is called.
939### u3j: the cold jet dashboard
941For even more fun, the jet tree is not actually a tree of
942batteries. It's a tree of battery *labels*, where a label is
943an [axis term] path from the root of the tree. (At the root,
944if the core pattern is always followed properly, is a core whose
945payload is an atomic constant, conventionally the Hoon version.)
947Under each of these labels, it's normal to have an arbitrary
948number of different Nock batteries (not just multiple copies
949of the same noun, a situation we *do* strive to avoid). For
950instance, one might be compiled with debugging hints, one not.
952We might even have changed the semantics of the battery without
953changing the label - so long as those semantics don't invalidate
956For instance, it's normal to have two equivalent Nock batteries
957at the same time in one pier: one battery compiled with
958debugging hints, one not.
960Rather, the jet tree is a semantic hierarchy. The root of the
961hierarchy is a constant, by convention the Hoon kernel version
962because any normal jet-propelled core has, at the bottom of its
963onion of libraries, the standard kernel. Thus if the core is
965 [foo-battery [bar-battery [moo-battery 164]]]
967we can reverse the nesting to construct a hierarchical core
972extends the static core `164/moo/bar` by wrapping the `foo`
973battery (ie, in Hoon, `|%`) around it. With the core above,
974you can compute `foo` stuff, `bar` stuff, and `moo` stuff.
977Not all cores are static, of course - they may contain live data,
978like the sample in a gate (ie, argument to a function). Once
979again, it's important to remember that we track jet bindings not
980by the core, which may not be static, but by the battery, which
983(And if you're wondering how we can use a deep noun like a Nock
984formula or battery as a key in a key-value table, remember
985`mug_w`, the lazily computed short hash, in all boxed nouns.)
987In any case, `das`, the dashboard, is a map from `bash` to jet
988location record (`++clog`). A `clog` in turn contains two kinds
989of information: the `++cope`, or per-location noun; and a map of
990batteries to a per-battery `++club`.
992The `cope` is a triple of `++bane` (battery name, right now just
993a `term`); `++axis`, the axis, within *this* core, of the parent;
994and `(each bash noun)`, which is either `[0 bash]` if the parent
995is another core, or `[1 noun]`, for the constant noun (like
996`164`) if there is no parent core.
998A `bash` is just the noun hash (`++sham`) of a `cope`, which
999uniquely expresses the battery's hierarchical location without
1000depending on the actual formulas.
1002The `club` contains a `++corp`, which we use to actually validate
1003the core. Obviously jet execution has to be perfectly compatible
1004with Nock. We search on the battery, but getting the battery
1005right is not enough - a typical battery is dependent on its
1006context. For example, your jet-propelled library function is
1007very likely to call `++dec` or other advanced kernel technology.
1008If you've replaced the kernel in your context with something
1009else, we need to detect this and not run the jet.
1011There are two cases for a jet-propelled core - either the entire
1012core is a static constant, or it isn't. Hence the definition
1015 ++ corp (each core batt) :: parent or static
1017Ie, a `corp` is `[0 core]` or `[1 batt]`. If it's static -
1018meaning that the jet only works with one specific core, ie, the
1019parent axis of each location in the hierarchy is `3` - we can
1020validate with a single comparison. Otherwise, we have to recurse
1021upward by checking the parent.
1023Note that there is at present no way to force a jet to depend on
1026### u3j: the warm jet dashboard
1028We don't use the cold state to match jets as we call them. We
1029use the cold state to register jets as we find them, and also to
1030rebuild the warm state after the hot state is reset.
1032What we actually use at runtime is the warm state, `jed->har_p`,
1033which is a `u3h` (built-in hashtable), allocated on the loom,
1034from battery to `++calx`.
1036A `calx` is a triple of a `++calf`, a `[bash cope]` cell, and a
1037`club`. The latter two are all straight from cold state.
1039The `calf` contains warm data dependent on hot state. It's a
1040quadruple: of `jax`, the hot driver index (in `ray_u` in
1041`u3j_dash`); `hap`, a table from arm axis (ie, the axis of each
1042formula within the battery) to driver arm index (into `arm_u` in
1043`u3j_core`); `lab`, the complete label path; and `jit`, any
1044other dynamic data that may speed up execution.
1046We construct `hap`, when we create the calx, by iterating through
1047the arms registered in the `u3j_core`. Note the way a `u3j_harm`
1048declares itself, with the string `fcs_c` which can contain either
1049an axis or a name. Most jetted cores are of course gates, which
1050have one formula at one axis within the core: `fcs_c` is `".3"`.
1052But we do often have fast cores with more complex arm structure,
1053and it would be sad to have to manage their axes by hand. To use
1054an `fcs_c` with a named arm, it's sufficient to make sure the
1055name is bound to a formula `[0 axis]` in the hook table.
1057`jit`, as its name suggests, is a stub where any sort of
1058optimization data computed on battery registration might go. To
1059use it, fill in the `_cj_jit()` function.
1061### u3j: the hot dashboard
1063Now it should be easy to see how we actually invoke jets. Every
1064time we run a nock `9` instruction (pretty often, obviously), we
1065have a core and an axis. We pass these to `u3j_kick()`, which
1066will try to execute them.
1068Because nouns with a reference count of 1 are precious,
1069`u3j_kick()` has a tricky reference control definition. It
1070reserves the right to return `u3_none` in the case where there is
1071no driver, or the driver does not apply for this case; in this
1072case, it retains argument `cor`. If it succeeds, though, it
1075`u3j_kick()` searches for the battery (always the head of the
1076core, of course) in the hot dashboard. If the battery is
1077registered, it searches for the axis in `hap` in the `calx`.
1078If it exists, the core matches a driver and the driver jets this
1079arm. If not, we return `u3_none`.
1081Otherwise, we call `fun_f` in our `u3j_harm`. This obeys the
1082same protocol as `u3j_kick()`; it can refuse to function by
1083returning `u3_none`, or consume the noun.
1085Besides the actual function pointer `fun_f`, we have some flags
1086in the `u3j_harm` which tell us how to call the arm function.
1088If `ice` is yes (`&`, `0`), the jet is known to be perfect and we
1089can just trust the product of `fun_f`. Otherwise, we need to run
1090*both* the Nock arm and `fun_f`, and compare their results.
1092(Note that while executing the C side of this test, we have to
1093set `ice` to yes; on the Nock side, we have to set `liv` to no.
1094Otherwise, many non-exponential functions become exponential.
1095When auto-testing jets in this way, the principle is that the
1096test is on the outermost layer of recursion.)
1098(Note also that anyone who multi-threads this execution
1099environment has a slight locking problem with these flags if arm
1100testing is multi-threaded.)
1102If `tot` is yes, (`&`, `0`), the arm function is *total* and has
1103to return properly (though it can still return *u3_none*).
1104Otherwise, it is *partial* and can `u3_cm_bail()` out with
1105c3__punt. This feature has a cost: the jet runs in a subroad.
1107Finally, if `liv` is no (`|`, 1), the jet is off and doesn't run.
1109It should be easy to see how the tree of cores gets declared -
1110precisely, in `j/dash.c`. We declare the hierarchy as a tree
1111of `u3j_core` structures, each of which comes with a static list
1112of arms `arm_u` and sub-cores `dev_u`.
1114In `u3j_boot()`, we traverse the hierarchy, fill in parent
1115pointers `par_u`, and enumerate all `u3j_core` structures
1116into a single flat array `u3j_dash.ray_u`. Our hot state
1117then appears ready for action.
1119### u3j: jet functions
1121At present, all drivers are compiled statically into `u3`. This is
1122not a long-term permanent solution or anything. However, it will
1123always be the case with a certain amount of core functionality.
1125For instance, there are some jet functions that we need to call
1126as part of loading the Arvo kernel - like `++cue` to unpack a
1127noun from an atom. And obviously it makes sense, when jets are
1128significant enough to compile into `u3`, to export their symbols
1129in headers and the linker.
1131There are three interface prefixes for standard jet functions:
1132`u3k`, `u3q`, and `u3w`. All jets have `u3w` interfaces; most
1133have `u3q`; some have `u3k`. Of course the actual logic is
1136`u3w` interfaces use the same protocol as `fun_f` above: the
1137caller passes the entire core, which is retained if the function
1138returns `u3_none`, transferred otherwise. Why? Again, use
1139counts of 1 are special and precious for performance hackers.
1141`u3q` interfaces break the core into C arguments, *retain* noun
1142arguments, and *transfer* noun returns. `u3k` interfaces are the
1143same, except with more use of `u3_none` and other simple C
1144variations on the Hoon original, but *transfer* both arguments
1145and returns. Generally, `u3k` are most convenient for new code.
1147Following `u3k/q/w` is `[a-f]`, corresponding to the 6 logical
1148tiers of the kernel, or `g` for user-level jets. Another letter
1149is added for functions within subcores. The filename, under
1150`j/`, follows the tier and the function name.
1152For instance, `++add` is `u3wa_add(cor)`, `u3qa_add(a, b)`, or
1153`u3ka_add(a, b)`, in `j/a/add.c`. `++get` in `++by` is
1154`u3wdb_get(cor)`, `u3kdb_get(a, b)`, etc, in `j/d/by_get.c`.
1156For historical reasons, all internal jet code in `j/[a-f]`
1157*retains* noun arguments, and *transfers* noun results. Please
1158do not do this in new `g` jets! The new standard protocol is to
1159transfer both arguments and results.
1161### u3a: allocation functions
1163`u3a` allocates on the current road (u3R). Its internal
1164structures are uninteresting and typical of a naive allocator.
1166The two most-used `u3a` functions are `u3a_gain()` to add a
1167reference count, and `u3a_lose()` to release one (and free the
1168noun, if the use count is zero). For convenience, `u3a_gain()`
1169returns its argument. The pair are generally abbreviated with
1170the macros `u3k()` and `u3z()` respectively.
1172Normally we create nouns through `u3i` functions, and don't call
1173the `u3a` allocators directly. But if you do:
1175One, there are *two* sets of allocators: the word-aligned
1176allocators and the fully-aligned (ie, malloc compatible)
1177allocators. For instance, on a typical OS X setup, malloc
1178produces 16-byte aligned results - needed for some SSE
1181These allocators are *not compatible*. For 32-bit alignment
1182as used in nouns, call
1184 /* u3a_walloc(): allocate storage measured in words.
1187 u3a_walloc(c3_w len_w);
1189 /* u3a_wfree(): free storage.
1192 u3a_wfree(void* lag_v);
1194 /* u3a_wealloc(): word realloc.
1197 u3a_wealloc(void* lag_v, c3_w len_w);
1199For full alignment, call:
1201 /* u3a_malloc(): aligned storage measured in bytes.
1204 u3a_malloc(size_t len_i);
1206 /* u3a_realloc(): aligned realloc in bytes.
1209 u3a_realloc(void* lag_v, size_t len_i);
1211 /* u3a_realloc2(): gmp-shaped realloc.
1214 u3a_realloc2(void* lag_v, size_t old_i, size_t new_i);
1216 /* u3a_free(): free for aligned malloc.
1219 u3a_free(void* tox_v);
1221 /* u3a_free2(): gmp-shaped free.
1224 u3a_free2(void* tox_v, size_t siz_i);
1226There are also a set of special-purpose allocators for building
1227atoms. When building atoms, please remember that it's incorrect
1228to have a high 0 word - the word length in the atom structure
1229must be strictly correct.
1231Of course, we don't always know how large our atom will be.
1232Therefore, the standard way of building large atoms is to
1233allocate a block of raw space with `u3a_slab()`, then chop off
1234the end with `u3a_malt()` (which does the measuring itself)
1235or `u3a_mint()` in case you've measured it yourself.
1237Once again, *do not call `malloc()`* (or C++ `new`) within any
1238code that may be run within a jet. This will cause rare sporadic
1239corruption when we interrupt execution within a `malloc()`. We'd
1240just override the symbol, but `libuv` uses `malloc()` across
1241threads within its own synchronization primitives - for this to
1242work with `u3a_malloc()`, we'd have to introduce our own locks on
1243the surface-level road (which might be a viable solution).
1245### u3n: nock execution
1247The `u3n` routines execute Nock itself. On the inside, they have
1248a surprising resemblance to the spec proper (the only interesting
1249detail is how we handle tail-call elimination) and are, as one
1250would expect, quite slow. (There is no such thing as a fast tree
1253There is only one Nock, but there are lots of ways to call it.
1254(Remember that all `u3n` functions *transfer* C arguments and
1257The simplest interpreter, `u3n_nock_on(u3_noun bus, u3_noun fol)`
1258invokes Nock on `bus` (the subject) and `fol` (the formula).
1259(Why is it`[subject formula]`, not `[formula subject]`? The same
1260reason `0` is true and `1` is false.)
1262A close relative is `u3n_slam_on(u3_noun gat, u3_noun sam)`,
1263which slams a *gate* (`gat`) on a sample (`sam`). (In a normal
1264programming language which didn't talk funny and was retarded,
1265`u3n_slam_on()` would call a function on an argument.) We could
1266write it most simply as:
1269 u3n_slam_on(u3_noun gat, u3_noun sam)
1271 u3_noun pro = u3n_nock_on
1272 (u3nc(u3k(u3h(gat)),
1273 u3nc(sam, u3k(u3t(u3t(gat))))),
1279Simpler is `u3n_kick_on(u3_noun gat)`, which slams a gate (or,
1280more generally, a *trap* - because sample structure is not even
1281needed here) without changing its sample:
1284 u3n_kick_on(u3_noun gat, u3_noun sam)
1286 return u3n_nock_on(gat, u3k(u3h(gat)));
1289The `_on` functions in `u3n` are all defined as pure Nock. But
1290actually, even though we say we don't extend Nock, we do. But we
1293Note that `u3` has a well-developed error handling system -
1294`u3m_bail()` to throw an exception, `u3m_soft_*` to catch one.
1295But Nock has no exception model at all. That's okay - all it
1296means if that if an `_on` function bails, the exception is an
1297exception in the caller.
1299However, `u3`'s exception handling happens to match a convenient
1300virtual super-Nock in `hoon.hoon`, the infamous `++mock`. Of
1301course, Nock is slow, and `mock` is Nock in Nock, so it is
1302(logically) super-slow. Then again, so is decrement.
1304With the power of `u3`, we nest arbitrary layers of `mock`
1305without any particular performance cost. Moreover, we simply
1306treat Nock proper as a special case of `mock`. (More precisely,
1307the internal VM loop is `++mink` and the error compiler is
1308`++mook`. But we call the whole sandbox system `mock`.)
1310The nice thing about `mock` functions is that (by executing
1311within `u3m_soft_run()`, which as you may recall uses a nested
1312road) they provide both exceptions and the namespace operator -
1313`.^` in Hoon, which becomes operator `11` in `mock`.
1315`11` requires a namespace function, or `fly`, which produces a
1316`++unit` - `~` (`0`) for no binding, or `[0 value]`. The sample
1317to a `fly` is a `++path`, just a list of text `span`.
1319`mock` functions produce a `++toon`. Fully elaborated:
1321 ++ noun ,* :: any noun
1322 ++ path (list ,@ta) :: namespace path
1323 ++ span ,@ta :: text-atom (ASCII)
1324 ++ toon $% [%0 p=noun] :: success
1325 [%1 p=(list path)] :: blocking paths
1326 [%2 p=(list tank)] :: stack trace
1328 ++ tank :: printable
1329 $% [%leaf p=tape] :: flat text
1330 $: %palm :: backstep list
1331 p=[p=tape q=tape r=tape s=tape] :: mid cap open close
1332 q=(list tank) :: contents
1334 $: %rose :: straight list
1335 p=[p=tape q=tape r=tape] :: mid open close
1336 q=(list tank) :: contents
1340(Note that `tank` is overdesigned and due for replacement.)
1342What does a `toon` mean? Either your computation succeded (`[0
1343noun]`, or could not finish because it blocked on one or more
1344global paths (`[1 (list path)]`), or it exited with a stack trace
1347Note that of all the `u3` exceptions, only `%exit` is produced
1348deterministically by the Nock definition. Therefore, only
1349`%exit` produces a `2` result. Any other argument to
1350`u3m_bail()` will unwind the virtualization stack all the way to
1351the top - or to be more exact, to `u3m_soft_top()`.
1353In any case, the simplest `mock` functions are `u3n_nock_un()`
1354and `u3n_slam_un()`. These provide exception control without
1355any namespace change, as you can see by the code:
1357 /* u3n_nock_un(): produce .*(bus fol), as ++toon.
1360 u3n_nock_un(u3_noun bus, u3_noun fol)
1362 u3_noun fly = u3nt(u3nt(11, 0, 6), 0, 0); // |=(a=* .^(a))
1364 return u3n_nock_in(fly, bus, fol);
1367 /* u3n_slam_un(): produce (gat sam), as ++toon.
1370 u3n_slam_un(u3_noun gat, u3_noun sam)
1372 u3_noun fly = u3nt(u3nt(11, 0, 6), 0, 0); // |=(a=* .^(a))
1374 return u3n_slam_in(fly, gat, sam);
1377The `fly` is added as the first argument to `u3n_nock_in()` and
1378`u3n_slam_in()`. Of course, logically, `fly` executes in the
1379caller's exception layer. (Maintaining this illusion is slightly
1380nontrivial.) Finally, `u3n_nock_an()` is a sandbox with a null
1385The only `u3e` function you should need to call is `u3e_save()`,
1386which saves the loom. As it can be restored on any platform,
1387please make sure you don't have any state in the loom that is
1388bound to your process or architecture - except for exceptions
1389like the warm jet state, which is actively purged on reboot.
1391### u3r: reading nouns (weak)
1393As befits accessors they don't make anything, `u3r` noun reading
1394functions always retain their arguments and their returns. They
1395never bail; rather, when they don't work, they return a `u3_weak`
1398Most of these functions are straightforward and do only what
1399their comments say. A few are interesting enough to discuss.
1401`u3r_at()` is the familiar tree fragment function, `/` from the
1402Nock spec. For taking complex nouns apart, `u3r_mean()` is a
1403relatively funky way of deconstructing nouns with a varargs list
1404of `axis`, `u3_noun *`. For cells, triples, etc, decompose with
1405`u3r_cell()`, `u3r_trel()`, etc. For the tagged equivalents, use
1406`u3r_pq()` and friends.
1408`u3r_sing(u3_noun a, u3_noun b)` (true if `a` and `b` are a
1409*single* noun) are interesting because it uses mugs to help it
1410out. Clearly, different nouns may have the same mug, but the
1411same nouns cannot have a different mug. It's important to
1412understand the performance characteristics of `u3r_sing()`:
1413the worst possible case is a comparison of duplicate nouns,
1414which have the same value but were created separately. In this
1415case, the tree is traversed
1417`u3r_sung()` is a deeply funky and frightening version of
1418`u3r_sing()` that unifies pointers to the duplicate nouns it
1419finds, freeing the second copy. Obviously, do not use
1420`u3r_sung()` when you have live, but not reference counted, noun
1421references from C - if they match a noun with a refcount of 1
1422that gets freed, bad things happen.
1424It's important to remember that `u3r_mug()`, which produces a
142531-bit, nonzero insecure hash, uses the `mug_w` slot in any boxed
1426noun as a lazy cache. There are a number of variants of
1427`u3r_mug()` that can get you out of building unneeded nouns.
1429### u3x: reading nouns (bail)
1431`u3x` functions are like `u3r` functions, but instead of
1432returning `u3_none` when (for instance) we try to take the head
1433of an atom, they bail with `%exit`. In other words, they do what
1434the same operation would do in Nock.
1436### u3h: hash tables.
1438We can of course use the Hoon `map` structure as an associative
1439array. This is a balanced treap and reasonably fast. However,
1440it's considerably inferior to a custom structure like an HAMT
1441(hash array-mapped trie). We use `u3_post` to allocate HAMT
1442structures on the loom.
1444(Our HAMT implements the classic Bagwell algorithm which depends
1445on the `gcc` standard directive `__builtin_popcount()`. On a CPU
1446which doesn't support popcount or an equivalent instruction, some
1447other design would probably be preferable.)
1449There's no particular rocket science in the API. `u3h_new()`
1450creates a hashtable; `u3h_free()` destroys one; `u3h_put()`
1451inserts, `u3h_get()` retrieves. You can transform values in a
1452hashtable with `u3h_walk()`.
1454The only funky function is `u3h_gut()`, which unifies keys with
1455`u3r_sung()`. As with all cases of `u3r_sung()`, this must be
1456used with extreme caution.
1460Connected to the `~+` rune in Hoon, via the Nock `%memo` hint,
1461the memoization facility is a general-purpose cache.
1463(It's also used for partial memoization - a feature that'll
1464probably be removed, in which conservative worklist algorithms
1465(which would otherwise be exponential) memoize everything in the
1466subject *except* the worklist. This is used heavily in the Hoon
1467compiler jets (j/f/*.c). Unfortunately, it's probably not
1468possible to make this work perfectly in that it can't be abused
1469to violate Nock, so we'll probably remove it at a later date,
1470instead making `++ut` keep its own monadic cache.)
1472Each `u3z` function comes with a `c3_m` mote which disambiguates
1473the function mapping key to value. For Nock itself, use 0. For
1474extra speed, small tuples are split out in C; thus, find with
1476 u3_weak u3z_find(c3_m, u3_noun);
1477 u3_weak u3z_find_2(c3_m, u3_noun, u3_noun);
1478 u3_weak u3z_find_3(c3_m, u3_noun, u3_noun, u3_noun);
1479 u3_weak u3z_find_4(c3_m, u3_noun, u3_noun, u3_noun, u3_noun);
1483 u3_noun u3z_save(c3_m, u3_noun, u3_noun);
1484 u3_noun u3z_save_2(c3_m, u3_noun, u3_noun, u3_noun);
1485 u3_noun u3z_save_3(c3_m, u3_noun, u3_noun, u3_noun, u3_noun);
1486 u3_noun u3z_save_4(c3_m, u3_noun, u3_noun, u3_noun, u3_noun, u3_noun);
1488where the value is the last argument. To eliminate duplicate
1494`u3z` functions retain keys and transfer values.
1496The `u3z` cache, built on `u3h` hashes, is part of the current
1497road, and goes away when it goes away. (In future, we may wish
1498to promote keys/values which outlive the road, as we do with jet
1499state.) There is no cache reclamation at present, so be careful.
1501### u3t: tracing and profiling.
1505### u3v: the Arvo kernel
1507An Arvo kernel - or at least, a core that compiles with the Arvo
1508interface - is part of the global `u3` state. What is an Arvo
1509core? Slightly pseudocoded:
1513 ++ come |= [yen=@ ova=(list ovum) nyf=pone] :: 11
1514 ^- [(list ovum) _+>]
1516 ++ keep |= [now=@da hap=path] :: 4
1519 ++ load |= [yen=@ ova=(list ovum) nyf=pane] :: 86
1520 ^- [(list ovum) _+>]
1522 ++ peek |= [now=@da path] :: 87
1525 ++ poke |= [now=@da ovo=ovum] :: 42
1526 ^- [(list ovum) _+>]
1528 ++ wish |= txt=@ta :: 20
1532 ++ card ,[p=@tas q=*] :: typeless card
1533 ++ ovum ,[p=wire q=card] :: Arvo event
1534 ++ wire path :: event cause
1536This is the Arvo ABI in a very real sense. Arvo is a core with
1537these six arms. To use these arms, we hardcode the axis of the
1538formula (`11`, `4`, `86`, etc) into the C code that calls Arvo,
1539because otherwise we'd need type metadata - which we can get, by
1542It's important to understand the Arvo event/action structure, or
1543`++ovum`. An `ovum` is a `card`, which is any `[term noun]`
1544cell, and a `++wire`, a `path` which indicates the location of
1545the event. At the Unix level, the `wire` corresponds to a system
1546module or context. For input events, this is the module that
1547caused the event; for output actions, it's the module that
1550`++poke` sends Arvo an event `ovum`, producing a cell of action
1551ova and a new Arvo core.
1553`++peek` dereferences the Arvo namespace. It takes a date and a
1554key, and produces `~` (`0`) or `[~ value]`.
1556`++keep` asks Arvo the next time it wants to be woken up, for the
1557given `wire`. (This input will probably be eliminated in favor
1558of a single global timer.)
1560`++wish` compiles a string of Hoon source. While just a
1561convenience, it's a very convenient convenience.
1563`++come` and `++load` are used by Arvo to reset itself (more
1564precisely, to shift the Arvo state from an old kernel to a new
1565one); there is no need to call them from C.
1567Now that we understand the Arvo kernel interface, let's look at
1568the `u3v` API. As usual, all the functions in `u3v` are
1569commented, but unfortunately it's hard to describe this API as
1570clean at present. The problem is that `u3v` remains design
1571coupled to the old `vere` event handling code written for `u2`.
1572But let's describe the functions you should be calling, assuming
1573you're not writing the next event system. There are only two.
1575`u3v_wish(str_c)` wraps the `++wish` functionality in a cache
1576(which is read-only unless you're on the surface road).
1578`u3v_do()` uses `wish` to provide a convenient interface for
1579calling Hoon kernel functions by name. Even more conveniently,
1580we tend to call `u3v_do()` with these convenient aliases:
1582 #define u3do(txt_c, arg) u3v_do(txt_c, arg)
1583 #define u3dc(txt_c, a, b) u3v_do(txt_c, u3nc(a, b))
1584 #define u3dt(txt_c, a, b, c) u3v_do(txt_c, u3nt(a, b, c))
1585 #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