5title: Hoon 101.3: an algorithm
7# Hoon 101.3: an algorithm
9In [chapter 0](0-nouns), we read about nouns. In [chapter 1](1-twigs),
10we discovered twigs and legs. In [chapter 2](2-syntax), we learned
11Hoon syntax and created our first source file.
13Now it's time for an actual, meaningful *algorithm*.
15## How to use this tutorial
17Ideally, you've installed an Urbit planet (if you have a ticket)
18or comet (if you don't). See the [user doc](../../../user).
20We recommend opening up the dojo and just typing the examples;
21you don't know a language until you know it in your fingers.
22Also, make sure you've worked through the chapters in order.
24## Goal: a decrement generator
26Our algorithm is the classic Urbit example: decrement.
28If you learned [Nock](../../nock) before Hoon, you've already
29written decrement. If not, all you need to know is that the only
30built-in arithmetic operator in Nock is increment. To decrement,
31we need to count up to the result with a simple loop.
35As we've seen, Hoon works by running a twig against a subject.
36In chapter 1, we made a simple test subject that was just a few
37constants, and applied some simple twigs to it.
39This time, we'll actually put useful working data in the subject,
40building up more and more complex subjects as we go.
44We'll start with the empty subject `~`:
50The `=>` rune ("tisgar", `%tsgr`)), for `=>(p q)` executes `p`
51against the subject, then uses that product as the subject of
54> We've already used an irregular form of `=>`, or to be more
55precise its mirror `=<` ("tisgal", `%tsgl`). In chapter 1, when we wrote
56`+3:test`, we meant `=>(test +3)` or `=<(+3 test)`.
58What is `~`? It's Hoon `nil`, a zero atom:
60~tasfyn-partyv:dojo/sandbox> ?? ~
64We use `~` for list terminators and the like. Obviously, since
65`[%hello %world]` is just a constant, a nil subject works as
69~tasfyn-partyv:dojo/sandbox> +test
75Above, we used an empty subject to avoid the very complex,
76interesting subject your generator twig gets by default.
78But a decrement generator needs to get an argument from the
79command line -- the number we're trying to decrement.
81This involves changing the `test.hoon` boilerplate a little.
82Again, don't worry about the boilerplate line just yet:
84:- %say |= [* [[arg=@ud ~] ~]] :- %noun
88~tasfyn-partyv:dojo/sandbox> +test 42
91> `=> arg=arg` looks a little odd. We wouldn't ordinarily do
92this; we're just trying to keep the subject simple.
94In case there's any doubt about the subject (remember from
95chapter 1 that `.` means `+1`, the whole subject):
97:- %say |= [* [[arg=@ud ~] ~]] :- %noun
101~tasfyn-partyv:dojo/sandbox> +test 42
105## An increment generator
107We can even write a trivial increment generator using `.+`,
108or even better its irregular form `+`:
110:- %say |= [* [[arg=@ud ~] ~]] :- %noun
114~tasfyn-partyv:dojo/sandbox> +test 42
117We'll assume these same first two lines for the rest of the
118examples in this chapter.
120## Cores: one more kind of span
122To decrement, we need a loop. To write a loop, we need yet
123another kind of noun: the *core*. Briefly, a core is a `[code
124data]` pair. Our new `span` mold:
128 [%cell p=span p=span]
129 [%core p=span q=(map ,@tas twig)]
131 [%face p=@tas q=span]
135### Structure of a core
137The core is a cell `[battery payload]`. The payload is data, the
138battery is code -- a tree of Nock formulas.
140In the `%core` span, the payload is described by an arbitrary
141span. The battery is described by a map of symbol to twig.
143> Yes, the span contains the complete AST of the whole core.
144This is a very different approach from most typed languages,
145which compute function signatures. To infer the product of an
146arm, we retrace the code in theory, but cache in practice.
148### Arms are computed attributes
150How do we use a core? Remember that Nock is a function
152Nock(subject formula) -> product
154To activate a core, we pull one formula from the battery, and
155execute with the whole core as the subject. Coincidentally,
156Nock has one macro instruction, `9`, that does just this.
158So the formula defines an arbitrary function on the core. The
159name of this function (as defined in the twig map) is a computed
162> Is a core an object? Not quite, because an arm is not a method.
163Methods in an OO language have arguments. Arms are functions
164only of the payload. (A method in Hoon is an arm that produces a
165gate, which is another core -- but we're getting too far ahead.)
166However, the battery does look a lot like a classic "vtable."
168### Arms and wing resolution
170It might be a good time to brush up on your [chapter 1](1-twigs).
171The wing resolution algorithm gets a little more complicated.
173Hoon overloads computed attributes (arms) and literal attributes
174(legs) in the same namespace. A label in a wing may refer to
175either. when searching a core, we look for a matching arm. If
176we find it we're done. If we don't, or if a `^` mark makes us
177skip, we search into the payload.
179Only the last limb in the wing can activate an arm. If a name
180resolves to a core arm, but it's not the last limb in the wing,
181the arm produces the core itself. Similarly, when the wing is
182not an access but a mutation, the arm refers to the core. Only
183the end of the wing is activated.
185> Suppose `foo` is a core. `bar` is an arm on foo. Then `bar.foo`
186computes the `bar` arm. Perhaps the product is another core.
187Even if `moo` is an arm in this new core, `bar.foo`, the wing
188`moo.bar.foo` does not compute `moo` on the core `bar.foo`.
189Instead, it looks for `moo` within the payload of the core `foo`.
190(You're looking for `moo:bar.foo`, ie, `=>(bar.foo moo)`.)
192Does this sound too tricky? Hopefully not, but it's about the
193most complicated semantic rule you'll find in Hoon.
195## Increment with a core
197Keeping our two-line boilerplate, let's increment with a core:
205~tasfyn-partyv:dojo/sandbox> +test 42
208What's going on? We used the `|%` rune ("barcen") to produce a
209core. (There are a lot of runes which create cores; they all
210start with `|`, and are basically macros that turn into `|%`.)
212The payload of a core produced with `|%` is the subject with
213which `|%` is compiled. We might say that `|%` wraps a core
214around its subject. In this case, the subject of the `|%`,
215and thus payload, is our `arg=@ud` argument.
217Then we used this core as the subject of the simple wing `inc`.
219> Remember that `=<(a b)` is just `=>(b a)`. The core is heavy
220and `inc` is light, so we use `=<` to put the heavy part last.
222The prettyprinter can even print a core, sort of. Take out the
230~tasfyn-partyv:dojo/sandbox> +test 42
233~tasfyn-partyv:dojo/sandbox> ? +test 42
237In this notation, `1` means the number of arms in the core, `bgq`
238is a very short fingerprint, and `arg=42` is the payload (and
239`arg=@ud` is the payload span).
241> Cores can be large and complex, and we obviously can't render all
242the data in them, either when printing a type or a value. At
243some point, you'll probably make the mistake of printing a big
244core, maybe even the whole kernel, as an untyped noun. Just
249To decrement, we need to count up to the argument. So we need a
250counter in our subject, because where else would it go?
252Let's change the subject to add a counter, `pre`:
261~tasfyn-partyv:dojo/sandbox> +test 42
264Once again, `.` is the whole subject, so we're wrapping it in a
265cell whose head is `pre=0`. This doesn't change the way we use
266`arg`, even though it's one level deeper in the subject tree.
267Let's look at the subject again:
272~tasfyn-partyv:dojo/sandbox> +test 42
274~tasfyn-partyv:dojo/sandbox> ? +test 42
278There's a less cluttered way to write `=>([a .] b)`. In wide
279mode, `=+(a b)`. A tall example:
284~tasfyn-partyv:dojo/sandbox> +test 42
287This rune `=+`, "tislus", `%tsls`, is of course the "variable
288declaration" we saw in chapter 2.
290## We actually decrement
292Now we can write our actual decrement program, combining the
293features we've explored above:
304~tasfyn-partyv:dojo/sandbox> +test 42
307`=(a b)` is an irregular form of `.=(a b)`, ie, "dottis" or the
308noun `[%dtts a b]`. Likewise, `+(a)` is `.+(a)`, ie, "dotlus"
311`?:`, "wuttis", `%wtts`, does exactly what it does in C.
313The real action is in `dec(pre +(pre))`. We saw this same
314mutation form in chapter 1. It's an irregular form of the `%=`
315rune, "centis", `%cnts`.
317Here, of course, we're computing an arm of a mutated core. We're
318recomputing the loop arm, `dec`, against a new core with an
319incremented `pre` leg. Basically, everything interesting in Hoon
320happens when you compute an arm of a mutated core.
322The whole program, using only regular forms, wide and tall:
334~tasfyn-partyv:dojo/sandbox> +test 42
337A good illustration of why we need irregular forms.
341Now we've actually done something useful. Well, if you count
342O(n) decrement as something useful.
344We've actually seen most of the major tools in Hoon's toolbox,
345just in a super-minimalist selection. But we'll need a few more
346runes to get to something that looks like real programming.
348For instance, we have a decrement algorithm, but we don't have a
349decrement *function* - in the Hoon sense of the word, anyway. We
350don't see `(dec arg)` in this code. That'll be the next chapter.
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