13 1 :: A noun is an atom or a cell.
14 2 :: An atom is a natural number.
15 3 :: A cell is an ordered pair of nouns.
17An **atom** is a natural number - ie, an unsigned integer. Nock does not
18limit the size of **atoms**, or know what an **atom** means.
20For instance, the **atom** `97` might mean the number `97`, or it might
21mean the letter `a` (ASCII 97). A very large **atom** might be the
22number of grains of sand on the beach - or it might be a GIF of your
23children playing on the beach. Typically when we represent strings or
24files as **atoms**, the first byte is the low byte. But even this is
25just a convention. An **atom** is an **atom**.
27A **cell** is an ordered pair of any two **nouns** - **cell** or
28**atom**. We group cells with square brackets:
35*Nouns* are the dumbest data model ever. **Nouns** make JSON look like
36XML and XML look like ASN.1. It may also remind you of Lisp's
37S-expressions - you can think of nouns as "S-expressions without the S."
39To be exact, a *noun* is an S-expression, except that classic
40S-expressions have multiple **atom** types ("S" is for "symbol"). Since
41Nock is designed to be used with a higher-level type system (such as
42Hoon's), it does not need low-level types. An **atom** is just an
43unsigned integer of any size.
45For instance, it's common to represent strings (or even whole text
46files) as atoms, arranging them LSB first - so "foo" becomes `0x6f6f66`.
47How do we know to print this as "foo", not `0x6f6f66`? We need external
48information - such as a Hoon type. Similarly, other common atomic
49types - signed integers, floating point, etc — are all straightforward
52It's also important to note that, unlike Lisp, Nock cannot create
53cyclical data structures. It is normal and common for **nouns** in a
54Nock runtime system to have acyclic structure - shared subtrees. But
55there is no Nock computation that can make a child point to its parent.
56One consequence: Nock has no garbage collector. (Nor can dag structure
57be detected, as with Lisp eq.)
59There is also no single syntax for **nouns**. If you have **nouns** you
60have Nock; if you have Nock you have Hoon; if you have Hoon, you can
61write whatever parser you like.
63------------------------------------------------------------------------
70Nock is a pure (stateless) function from **noun** to **noun**. In our
71pseudocode (and only in our pseudocode) we express this with the prefix
74A Nock program is given meaning by a process of reduction. To compute
75`nock(x)`, where `x` is any **noun**, we step through the rules from the
76top down, find the first left-hand side that matches `x`, and reduce it
77to the right-hand side (in more mathematical notation, we might write
78line 5 as `nock(a) -> *a`, a style we do use in documentation)
80When we use variable names, like `a`, in the pseudocode spec, we simply
81mean that the rule fits for any **noun** `a`.
83So `nock(x)` is `*x`, for any **noun** `x`. And how do we reduce `*x`?
84Looking up, we see that lines 23 through 39 reduce `*x` - for different
87Normally `a` in `nock(a)` is a **cell** `[s f]`, or
91Intuitively, the formula is your function and the subject is its
92argument. Hoon, or any other high-level language built on Nock, will
93build its own function calling convention which does not map directly to
96------------------------------------------------------------------------
101 6 :: [a b c] [a [b c]]
103Brackets associate to the right.
109 [2 [6 [[28 29] [30 31]]]]
110 [2 [6 [[28 29] [30 [62 63]]]]]
117 [2 6 [28 29] 30 62 63]
119While this notational convenience is hardly rocket science, it's
120surprising how confusing it can be, especially if you have a Lisp
121background. Lisp's "S-expressions" are very similar to **nouns**, except
122that Lisp has multiple types of **atom**, and Lisp's syntax
123automatically adds list terminators to groups.
125For those with Lisp experience, it's important to note that Nock and
126Hoon use tuples or "improper lists" much more heavily than Lisp. The
127list terminator, normally 0, is never automatic. So the Lisp list
131becomes the Nock **noun**
135which is equivalent to
139Note that we can and do use unnecessary brackets anyway, for emphasis.
141------------------------------------------------------------------------
153Here we define three of Nock's four axiomatic functions: **Cell-test**,
154**Increment** and **Equals** (the fourth axiomatic function, called
155**Address**, is defined in lines 16 through 21). These functions are
156just pseudocode, not actual Nock syntax, and are only used to define the
157behaviour of certain Nock operators.
159We should note that in Nock and Hoon, `0` (pronounced "yes") is true,
160and `1` ("no") is false. This convention is the opposite of
161old-fashioned booleans, so we try hard to say "yes" and "no" instead of
164------------------------------------------------------------------------
168`?` (pronounced "wut") tests whether is a **noun** is a **cell**. Again,
169`0` means "yes", `1` means "no":
174------------------------------------------------------------------------
178`+` (pronounced "lus") adds `1` to an **atom**:
183------------------------------------------------------------------------
187`=` (pronounced "tis") tests a cell for equality. `0` means "yes", `1`
194Testing an **atom** for equality makes no sense and logically fails to
197Because `+` works only for **atoms**, whereas `=` works only for
198**cells**, the error rules match first for `+` and last for `=`.
200------------------------------------------------------------------------
208 19 :: /[(a + a) b] /[2 /[a b]]
209 20 :: /[(a + a + 1) b] /[3 /[a b]]
212We define a **noun** as a binary tree - where each node branches to a
213left and right child - and assign an address, or **axis**, to every
214element in the tree. The root of the tree is `/1`. The left child
215(**head**) of every node at `/a` is `/2a`; the right child (**tail**) is
216`/2a+1`. (Writing `(a + a)` is just a clever way to write `2a`, while
217minimizing the set of pseudocode forms.)
219`1` is the root. The **head** of every **axis** `n` is `2n`; the
220**tail** is `2n+1`. Thus a simple tree:
227If the value of every leaf is its tree address, this tree is
231Let's use the example `[[97 2] [1 42 0]]`. So
233 /[1 [97 2] [1 42 0]] -> [[97 2] [1 42 0]]
235because `/1` is the root of the tree, ie, the whole **noun**.
237Its left child (**head**) is `/2` (i.e. `(1 + 1)`):
239 /[2 [97 2] [1 42 0]] -> [97 2]
241And its right child (**tail**) is `/3` (i.e. `(1 + 1 + 1)`):
243 /[3 [97 2] [1 42 0]] -> [1 42 0]
245And delving into `/3`, we see `/(3 + 3)` and `/(3 + 3 + 1)`:
247 /[6 [97 2] [1 42 0]] -> 1
248 /[7 [97 2] [1 42 0]] -> [42 0]
250It's also fun to build nouns in which every atom is its own axis:
257 [[4 5] [12 13] 14 15]
258 [[4 [10 11]] [12 13] 14 15]
259 [[[8 9] [10 11]] [12 13] 14 30 31]
261------------------------------------------------------------------------
266 23 :: *[a [b c] d] [*[a b c] *[a d]]
268The practical domain of the Nock function is always a **cell**. When `a`
269is an **atom**, `*a`, or `nock(a)`, is always an error. Conventionally,
270Nock proper is always a function of a **cell**. The **head** of this
271**cell** is the **subject**, the **tail** is the **formula**
275and the result of passing a **noun** through the Nock function is called
278 nock([subject formula]) => product
282 *[subject formula] => product
284The **subject** is your data and the **formula** is your code. And the
285**product** is your code's output.
287Notice that `a` in the Nock rules is always the **subject**, except line
28839, which is a crash default for malformed **nouns** that do not
291A **formula** is always a **cell**. But when we look inside that
292**cell**, we see two basic kinds of **formulas**:
295 [formula-x formula-y]
297An **operator** is always an **atom** (`0` through `10`). A **formula**
298is always a **cell**. Line 23 distinguishes these forms:
300 23 :: *[a [b c] d] [*[a b c] *[a d]]
302If your code contains multiple **formulas**, the **subject** will
303distribute over those **formulas**.
305In other words, if you have two Nock **formulas** `x` and `y`, a
306**formula** that computes the pair of them is just the **cell** `[x y]`.
308 *[subject [x y]] -> [*[subject x] *[subject y]]
310No **atom** is a valid **formula**, and every **formula** that does not
311use line 23 has an atomic **head**.
313Suppose you have two **formulas** `f` and `g`, each of which computes
314some function of the **subject** `s`. You can then construct the
315**formula** `h` as `[f g]`; and `h(s) = [f(s) g(s)]`.
321The **subject** `s` is `[19 42]`. The **formula** `h` is `[[0 3] 0 2]`.
325The **head** of `h` is `f`, which is `[0 3]`. The **tail** of `h` is
326`g`, which is `[0 2]`.
330by the distribution rule, `*[s [f g]]` is
336 [*[[19 42] [0 3]] *[[19 42] 0 2]]
338`*[s f]` is `f(s)` and produces `42`. `*[s g]` is `g(s)` and produces
341Since `h(s)` is `[f(s) g(s)]`, `h(s)` is `[42 19]`:
343 *[[19 42] [0 3] 0 2] -> [42 19]
345------------------------------------------------------------------------
350 25 :: *[a 0 b] /[b a]
352Operator 0 is Nock's tree address or **axis** operator, using the tree
353addressing structure defined in lines 16 through 20. `*[a 0 b]` simply
354returns the value of the part of `a` at **axis** `b`. For any subject
355`a`, the formula `[0 b]` produces `/[b a]`.
359 *[[19 42] 0 3] -> /[3 19 42] -> 42.
361------------------------------------------------------------------------
368`1` is the constant, or **Just operator**. It produces its operand `b`
369without reference to the **subject**.
375**Operator 1** is named **Just** because it produces "just" its operand.
377------------------------------------------------------------------------
382 27 :: *[a 2 b c] *[*[a b] *[a c]]
384**Operator 2** is the **Fire operator**, which brings us the essential
385magic of recursion. Given the **formula** `[2 b c]`, `b` is a
386**formula** for generating a new **subject**; `c` is a **formula** for
387generating a new **formula**. To compute `*[a 2 b c]`, we evaluate both
388`b` and `c` against the current **subject** `a`.
390A common use of **Fire** is to evaluate data inside the **subject** as
395 *[[[40 43] [4 0 1]] [2 [0 4] [0 3]]] -> 41
397 *[[[40 43] [4 0 1]] [2 [0 5] [0 3]]] -> 44
399**Operator 2** is called **Fire** because it "fires" Nock **formulas**
400at its (possibly modified) **subject**.
402------------------------------------------------------------------------
407 28 :: *[a 3 b] ?*[a b]
409**Operator 3** applies the **Cell-test** function defined in lines 8 and
4109 to the product of `*[a b]`.
412**Operator 3** is called **Depth** because it tests the "depth" of a
413noun. **Cell-test** properly refers to the pseudocode function `?`.
415------------------------------------------------------------------------
420 29 :: *[a 4 b] +*[a b]
422**Operator 4** applies the **Increment** function defined in lines 10
423and 11 to the product of `*[a b]`.
425**Operator 4** is called **Bump** because it "bumps" the atomic product
426`*[a b]` up by 1. **Increment** properly refers to the pseudocode
429------------------------------------------------------------------------
434 30 :: *[a 5 b] =*[a b]
436**Operator 5** applies the Equals function defined in lines 12, 13 and
43714 to the product of \*[a b].
439**Operator 5** is called the **Same** operator, because it tests if the
440head and tail of the product of `*[a b]` are the same. "Equals" properly
441refers to the pseudocode function "=".
443------------------------------------------------------------------------
448 32 :: *[a 6 b c d] *[a 2 [0 1] 2 [1 c d] [1 0] 2 [1 2 3] [1 0] 4 4 b]
450**Operator 6** is a primitive known to every programmer - **If**. Its
451operands, a **test formula** `b`, a **then formula** `c` and an **else
454If the **test** `b` applied to the **subject** evaluates to `0` ("yes"),
458then **If** produces the result of `c`, the **then formula**, applied to
463Else, if applying the **test** to the **subject** produces `1` ("no"),
467**Operator 6** produces the result of `d`, the **else formula**, applied
472If `*[a b]` produces any value other than `0` ("yes") or `1` ("no"),
475Let's examine the internals of **Operator 6**:
477**If** could have been defined as a built-in pseudocode function, like
483Then **Operator 6** could have been restated quite compactly:
485 :: *[a 6 b c d] *[a $[*[a b] c d]]
487However, this is unnecessary complexity. **If** can be written as a
488macro using the primitive operators:
490 32 :: *[a 6 b c d] *[a 2 [0 1] 2 [1 c d] [1 0] 2 [1 2 3] [1 0] 4 4 b]
492Reducing the right-hand side (an excellent exercise for the reader)
495 *[a *[[c d] [0 *[[2 3] [0 ++*[a b]]]]]]
497Which is the reduced pseudocode form of **Operator 6**.
499Additionally, we could simplify the semantics of **If**, at the expense
500of breaking the system, by creating a macro that works as if and only if
501`*[a b]` produces either `0` or `1`.
503This simpler **If** would be:
505 :: *[a 6 b c d] *[a 2 [0 1] 2 [1 c d] [1 0] [4 4 b]]
509 *[a *[[c d] [0 ++*[a b]]]]
511Let's examine the internals of this macro with a test example:
513 *[[40 43] [6 [3 0 1] [4 0 2] [4 0 1]]]
515Fitting this to the reduced form:
517 *[[40 43] *[[4 0 2] [4 0 3]] [0 ++*[[40 43] [3 0 1]]]]]
525 *[[40 43] *[[[4 0 2] [4 0 3]] [0 ++0]]]]
527which gets incremented twice
529 *[[40 43] *[[[4 0 2] [4 0 3]] [0 2]]]
531and is used as an axis to select the head of [[4 0 2] [4 0 3]]
535which increments `40` to produce `41`. Had the **test** produced a "no"
536instead of a "yes", **If** would have incremented the **tail** of the
537subject instead of the **head**.
539The real **If** is only slightly more complicated:
541 :: *[a 6 b c d] *[a *[[c d] [0 *[[2 3] [0 ++*[a b]]]]]]
543There is an extra step in the real **If** to prevent unexpected
544behaviour if the test produces a value other than 0 ("yes") or 1 ("no").
545The real **If** will crash if this happens and the naive **If** may not
546(the reader will find it a useful exercise to figure out why).
548It's worth noting that practical, compiler-generated Nock never does
549anything as funky as these **Operator 6** macro internals.
551------------------------------------------------------------------------
556 33 :: *[a 7 b c] *[a 2 b 1 c]
558**Operator 7** implements function composition. To use a bit of math
559notation, if we define the formula `[7 b c]` as a function `d(x)`:
563This is apparent from the reduced pseudocode form of **Operator 7**:
569 *[[42 44] [7 [4 0 3] [3 0 1]]] -> 1
571The above sequentially applies the **formulas** `[4 0 3]` and `[3 0 1]`
572to our subject `[42 44]`, first incrementing the **head**, then testing
575------------------------------------------------------------------------
580 34 :: *[a 8 b c] *[a 7 [[7 [0 1] b] 0 1] c]
582**Operator 8** pushes a new **noun** onto our **subject**, not at all
583unlike pushing a new variable onto the stack.
585The internals of **Operator 8** are similar to **Operator 7**, except
586that the **subject** for `c` is not simply the **product** of `b`, but
587the ordered pair of the **product** of `b` and the original **subject**.
589This is apparent from the reduced pseudocode form of **Operator 8**:
593**Operator 8** evaluates the **formula** `c` with the **cell** of
594`*[a b]` and the original **subject** `a`. In math notation, if we
595define `[8 b c]` as `d(x)`:
599Suppose, for the purposes of the **formula** `c`, we need not just the
600**subject** `a`, but some intermediate **noun** computed from the
601**subject** that will be useful in the calculation of `c`. **Operator
6028** applies **formula** `c` to a new **subject** that is the pair of the
603intermediate value and the old **subject**.
605In higher-level languages that compile to Nock, variable declarations
606are likely to generate an **Operator 8**, because the variable is
607computed against the present **subject**, and used in a calculation
608which depends both on the original **subject** and the new variable.
610------------------------------------------------------------------------
615 35 :: *[a 9 b c] *[a 7 c 2 [0 1] 0 b]
617**Operator 9** is the **Call** operator and is used for calling and
618applying **formulas** inside **noun** structures called **cores**
620A **noun** can contain both data and code. By convention, all
621interesting flow control in Nock is done with **cores**, which are
622**cells** whose head is code (containing one or more **formulas**) and
623whose **tail** is data (possibly containing other **cores**):
627All flow structures in other languages not built on Nock correspond to
628**cores**. Functions and/or closures are **cores**, objects are
629**cores**, modules are **cores**, even loops are **cores** (Nock, of
630course, does not have a loop operator).
632The head of a **core** is called the **battery** and the tail is called
637The **payload** of a core is any useful data needed for computation.
639The **battery** of a **core** is a **noun** containing one or more
640**arms**, which are **formulas** whose **subject** is the entire
643For example, in the case of the **battery** containing three **arms**:
647Where `arm1` is at **axis** `/2` in the **battery**, `arm2` is at `/6`,
648and `arm3` is at `/7`. The **axes** will differ depending on the number
651Of course, because the **subject** of an **arm** is the entire **core**,
652an **arm** can invoke itself (or any other **arm** in the **battery**).
653Hence, it can loop. And this is what a loop is - the simplest of
656Also, by convention, we have terms for different kinds of **cores**,
657depending on their structure:
659A **trap** is a **core** whose battery contains a single **arm**. By
660convention, this arm is called `$` (pronounced 'buc'), which is the
661empty-name. All **traps** have the following structure:
665A **door** is a **core** with a **payload** of the form
666`[sample context]`. The **sample** is dynamic data (such as the
667arguments of a function) and the **context** is any data that might be
668useful (such as other **cores**, variables, or the entire kernel of your
669OS). All **doors** have the following structure:
671 [battery [sample context]]
673A **gate** is a **core** that is both a **door** and a **trap**.
674**Gates** are the Nock equivalent of lambdas or functions. All **gates**
679**Operator 9** constructs a **core** and activates it by calling one of
682Looking reduced pseudocode form of **Call**:
684 *[*[a c] *[*[a c] 0 b]]
686**Call** applies a **formula** `c` to the **subject** `a`, where
687`*[a c]` produces a **core**. **Call** then calls an **arm** `b` of the
688**core** produced by `*[a c]` and reflexively applies it to the same
691------------------------------------------------------------------------
696 36 :: *[a 10 [b c] d] *[a 8 c 7 [0 3] d]
697 37 :: *[a 10 b c] *[a c]
699**Operator 10** serves a hint to the interpreter.
701If `b` is an atom and `c` is a **formula**, the **formula** `[10 b c]`
702appears to be equivalent to `c`. Likewise if `[b c]` is a **cell**,
703`[10 [b c] d]` appears to be equivalent to `d`. **Operator 10** is
704actually a hint operator. The `b` or `[b c]`is discarded information -
705it is not used, formally, in the computation. It may help the
706interpreter compute the expression more efficiently, however.
708Every Nock computes the same result - but not all at the same speed.
709What hints are supported? What do they do? Hints are a higher-level
710convention which do not, and should not, appear in the Nock spec. Some
711are defined in Hoon. Indeed, a naive Nock interpreter not optimized for
712Hoon will run Hoon quite poorly. When it gets the product, however, the
713product will be right. (Why is the `c` in `[b c]` computed? Because `c`
714could crash. A correct Nock cannot simply ignore it, and treat both
715variants of `10` as equivalent.)
717------------------------------------------------------------------------
722**operator 11** retrieves data from the global namespace at the path it is given.
724nock 11 is an additional nock operation provided by arvo to provide access to the global namespace. It's provided by arvo, so even though it's not technically a part of the nock, any code that arvo runs has access to it. When nock running on top of arvo hits nock 11, it either produces a value or blocks. The most common usage is with clay, where ^(%cx /path/to/file) will produce the referred-to-file.
731The nock function is defined for every **noun**, but on many **nouns**
732it does nothing useful. For instance, if `a` is an **atom**, `*a`
733reduces to... `*a`. In theory, this means that Nock spins forever in an
734infinite loop. In other words, Nock produces no result - and in
735practice, your interpreter will stop.
737Another way to see this is that Nock has "crash-only" semantics. There
738is no exception mechanism. The only way to catch Nock errors is to
739simulate Nock in a higher-level virtual Nock - which, in fact, we do all
740the time. A simulator (or a practical low-level interpreter) can report,
741out of band, that Nock would not terminate. It cannot recognize all
742infinite loops, of course (cf. Halting problem), but it can recognize
743common and obvious ones, which is usually sufficient in practice.
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