git.iko.soy/urbit.org
on 492ae2f help sign in
urbit.org/docs/programming/deep/1-twigs.md
286 lines 8.8 kB history raw
1---
2next: true
3sort: 1
4spam: true
5title: Hoon 101.1: twigs and legs
6---
7# Hoon 101.1: twigs and legs
9In the [last chapter](0-nouns), we learned how to make nouns. In
10this chapter we'll get into Hoon expressions, or *twigs*.
12## How to use this tutorial
14Ideally, you've installed an Urbit planet (if you have a ticket)
15or comet (if you don't). See the [user doc](../../../user).
17We recommend opening up the dojo and just typing the examples;
18you don't know a language until you know it in your fingers.
19Also, make sure you've worked through the chapters in order.
21## Nock for Hoon programmers
23Hoon compiles itself to a pico-interpreter called
24[Nock](../../nock), a combinator algebra defined in 200 words. This
25isn't the place to explain Nock (which relates to Hoon much as
26assembly language relates to C), but Nock is just a way to
27express a function as a noun.
29Nock is a Turing-complete interpreter shaped like (pseudocode):
30```
31Nock(problem) => product
32```
33The `problem` is always a cell `[subject formula]`. The
34function is the `formula`. The input to the function is the
35`subject`. The output is the `product`.
37## From Hoon to Nock
39The Hoon parser turns a source expression (even one as simple as
40`42` from the last chapter) into a noun called a `twig`. If you
41know what an AST is, a twig is an AST. (If you don't know what
42an AST is, it's not necessarily worth the student loans.)
44To simplify slightly, the Hoon compiler is shaped like:
45```
46Hoon(subject-span function-twig) => [product-span formula-nock]
47```
48Hoon, like Nock, is a *subject-oriented* language. Your code is
49always executed against one input noun, the subject. For any
50subject noun in `subject-span` (ie, argument type), the compiler
51produces a Nock formula that computes `function-twig` on that
52subject, and a `product-span` that is the span of the product
53(ie, result type).
55> This is really a nontrivial difference. In a normal,
56non-subject-oriented language, your code executes against a
57scope, stack, environment, or other variable context, probably
58not even a regular user-level value. For ordinary coders,
59"subject-oriented programming" is one of the hardest things to
60understand about Hoon; for some reason, your brain keeps wanting
61the interpreter state to be more interesting.
63## From constants to twigs
65In the last chapter we were entering degenerate twigs like `42`.
66Obviously a numeric constant doesn't use the subject at all, so
67it's not a very interesting example.
69Let's save a test subject as a dojo variable:
70```
71~tasfyn-partyv:dojo> =test [[[8 9] 5] [6 7]]
72```
73The `=test` command tells the dojo to rearrange its stock subject
74to include this `test` noun. Let's check that it's there:
75```
76~tasfyn-partyv:dojo> test
77[[[8 9] 5] 6 7]
78```
79> If you're wondering why `[6 7]` got printed as `6 7`, remember
80that `[]` associates to the right. Also, `=test` is not in any
81way Hoon syntax; it's dojo syntax. Every Hoon twig is a valid
82dojo command, but not vice versa.
84We want to use `test`, this harmless little noun, as the subject
85for some equally harmless twigs. We can do this with the `:`
86syntax, which composes twigs in the functional sense. The twig
87`a:b` uses the product of twig `b` as the subject of twig `a`.
88Trivial cases:
89```
90~tasfyn-partyv:dojo> 42:test
9142
92~tasfyn-partyv:dojo> 42:420
9342
94```
96## Tree addressing
98The simplest twigs produce a subtree, or "leg", of the subject.
99A cell, of course, is a binary tree. The very simplest twig is
100`.`, which produces the root of the tree - the whole subject:
101```
102~tasfyn-partyv:dojo> .:test
103[[[8 9] 5] 6 7]
104```
105Like human languages, Hoon is full of irregular abbreviations.
106The `.` syntax is a shorthand for `+1`:
107```
108~tasfyn-partyv:dojo> +1:test
109[[[8 9] 5] 6 7]
110```
111Hoon has a simple tree addressing scheme (inherited from Nock):
112the root is `1`, the head of `n` is `2n`, the tail is `2n+1`.
113The twig syntax for a tree address is `+n`.
115In our example noun, each leaf is its own tree address:
116```
117~tasfyn-partyv:dojo> +2:test
118[[8 9] 5]
119~tasfyn-partyv:dojo> +3:test
120[6 7]
121~tasfyn-partyv:dojo> +4:test
122[8 9]
123~tasfyn-partyv:dojo> +5:test
125~tasfyn-partyv:dojo> +6:test
127~tasfyn-partyv:dojo> +7:test
129```
130> An instinct for binary tree geometry develops over time as you
131use the system, rather the way most programmers learn to do
132binary math. No, really.
134## Lark syntax
136This alternative syntax for a tree address maps noun geometry
137directly to a glyph. Lark syntax creates a recognizable
138geometric shape by alternating between two head/tail pairs, read
139left to right: `-` and `+`, `<` and `>`.
141Thus `-` is `+2`, `+` is `+3`, `+<` is `+6`, `->` is `+5`, `-<+`
142is `+9`, etc.
144> Why lark syntax? Code full of numbers is ugly and distracting,
145and looks like hardcoded constants. We actually almost never use
146the `+` syntax.
148## Simple faces
150Tree addressing is cool, but it would be pretty tough to program
151in Hoon if it was the only way of getting data out of a subject.
153Let's introduce some new syntax:
154```
155~tasfyn-partyv:dojo> foo=42
156foo=42
157~tasfyn-partyv:dojo> ? foo=42
158 foo=@ud
159foo=42
160~tasfyn-partyv:dojo> ?? foo=42
161 [%face %foo [%atom %ud]]
162foo=42
163```
164To extend our `++span` mold from the last chapter:
165```
166++ span
167 $% [%atom p=@tas]
168 [%cell p=span p=span]
169 [%cube p=* q=span]
170 [%face p=@tas q=span]
171 ==
172```
173The `%face` span wraps a label around a noun. Then we can
174get a leg by name. Let's make a new dojo variable:
175```
176~tasfyn-partyv:dojo> =test [[[8 9] 5] foo=[6 7]]
177```
178The syntax is what you might expect:
179```
180~tasfyn-partyv:dojo> test
181[[[8 9] 5] foo=[6 7]]
182~tasfyn-partyv:dojo> foo:test
183[6 7]
184```
185Does this do what you expect it to do?
186```
187~tasfyn-partyv:dojo> +3:test
188foo=[6 7]
189~tasfyn-partyv:dojo> ? +3:test
190 foo=[@ud @ud]
191foo=[6 7]
192~tasfyn-partyv:dojo> ?? +3:test
193 [%face %foo [%cell [%atom %ud] [%atom %ud]]]
194foo=[6 7]
195```
197## Interesting faces; wings
199Let's look at a few more interesting face cases. First, suppose
200we have two cases of `foo`?
201```
202~tasfyn-partyv:dojo> =test [[foo=[8 9] 5] foo=[6 7]]
203~tasfyn-partyv:dojo> foo:test
204[8 9]
205```
206In the tree search, the head wins. We can overcome this with a
207`^` prefix, which tells the search to skip its first hit:
208```
209~tasfyn-partyv:dojo> ^foo:test
210[6 7]
211```
212`^^foo` will skip two foos, `^^^foo` three, *ad infinitum*.
213But what about nested labels?
214```
215~tasfyn-partyv:dojo> =test [[[8 9] 5] foo=[6 bar=7]]
216~tasfyn-partyv:dojo> bar:test
217/~tasfyn-partyv/home/~2015.11.7..21.40.21..1aec:<[1 1].[1 9]>
218-find-limb.bar
219find-none
220```
221We can't search *through* a label. If we want to get our `bar`
222out, we need to search *into* it:
223```
224~tasfyn-partyv:dojo> bar.foo:test
226```
227`bar.foo` is what we call a `wing`, a search path in a noun.
228Note that the wing runs from left to right, ie, the opposite of
229most languages: `bar.foo` means "bar within foo."
231Each step in a wing is a `limb`. (Most languages use metaphors;
232Hoon abuses them.) A limb can be a tree address, like `+3` or
233`.`, or a label like `foo`. We can combine them in one wing:
234```
235~tasfyn-partyv:dojo> bar.foo.+3:test
237```
238It's important to note the difference between `bar.foo:test`
239and `bar:foo:test`, even though they produce the same product:
240```
241~tasfyn-partyv:dojo> bar:foo:test
243```
244`bar.foo` is one twig, which we run on the product of `test`.
245That's different from running `bar` on the product of `foo` on
246the product of `test`.
248> You're probably used to name resolution in variable scopes
249and flat records, but not in trees. Partly this is because the
250tradition in language design is to prefer semantics that make it
251easy to build simple symbol tables, because linear search of a
252nontrivial tree is a bad idea on '80s hardware.
254## Mutation
256Mutation? Well, not really. We can't modify nouns; the concept
257doesn't even make sense in Hoon (or Nock).
259Rather, we build new nouns which are copies of old ones, but
260with mutations. Let's build a "mutated" copy of our test noun:
261```
262~tasfyn-partyv:dojo> test
263[[[8 9] 5] foo=[6 bar=7]]
264~tasfyn-partyv:dojo> test(foo 42)
265[[[8 9] 5] foo=42]
266~tasfyn-partyv:dojo> test(+8 %eight, bar.foo [%hello %world])
267[[[%eight 9] 5] foo=[6 [%hello %world]]]
268```
269As we see, there's no need for the mutant noun to be shaped
270anything like the old noun. They're different nouns.
272A mutation, like `+8 %eight`, specifies a wing and a twig.
273The wing, like `+8` or `bar.foo`, defines a leg to replace.
274The twig runs against the original subject.
276Can we use mutation to build a cyclical noun? Nice try, but no:
277```
278~tasfyn-partyv:dojo> test(+8 test)
279[[[[[[8 9] 5] foo=[6 bar=7]] 9] 5] foo=[6 bar=7]]
280```
282## Progress
284Now, not only can you build a noun, you can get data out of it and
285even evolve new, related nouns. We've still seen only two very
286restricted kinds of twigs: constants and legs. In the [next chapter](2-syntax), we'll actually write some interesting expressions.