git.iko.soy/urbit.org
on 05941fa help sign in
urbit.org/tutorials/hoon/caesar.md
347 lines 12 kB history raw
1+++
2title = "1.7.1 Walkthrough: Caesar Cipher"
3weight = 16
4template = "doc.html"
5aliases = ["/docs/learn/hoon/hoon-tutorial/caesar/"]
6+++
8A Caesar cipher is a very simple way to obfuscate a message. The technique
9takes a string and swaps out each component letter with another letter that is
10a specified number of positions up or down in the alphabet. For example, with a
11"right-shift" of 1, `a` would become `b`, `j` would become `k`, and `z` would
12wrap around back to `a`.
14Consider the message below, and the cipher that results when we Caesar-shift the
15message to the right by 1.
17```
18Plaintext message: "do not give way to anger"
19Right-shifted cipher: "ep opu hjwf xbz up bohfs"
20```
22Note that the Caesar cipher is completely unsuitable for actually securing
23information. Implementing it in a program is just a fun exercise.
25## A Caesar Cipher In Hoon
27Below is a generator that performs a Caesar cipher on a tape. This example
28isn't the most compact implementation of such a cipher in Hoon, but it
29demonstrates important principles that more laconic code would not. Save it as
30`caesar.hoon` in your `/gen` directory.
32```hoon
33!:
34|= [msg=tape key=@ud]
35=<
36=. msg (cass msg)
37:- (shift msg key)
38(unshift msg key)
39|%
40++ alpha "abcdefghijklmnopqrstuvwxyz"
41++ shift
42 |= [message=tape key=@ud]
43 (operate message key (encoder key))
44++ unshift
45 |= [message=tape key=@ud]
46 (operate message key (decoder key))
47++ operate
48 |= [message=tape key=@ud encoder=(map @t @t)]
49 ^- tape
50 %+ turn message
51 |= a=@t
52 (~(got by encoder) a)
53++ encoder
54 |= [key=@ud]
55 =/ keytape=tape (rott alpha key)
56 (coder alpha keytape)
57++ decoder
58 |= [key=@ud]
59 =/ keytape=tape (rott alpha key)
60 (coder keytape alpha)
61++ coder
62 |= [a=tape b=tape]
63 (~(put by (zipper a b)) ' ' ' ')
64++ zipper
65 |= [a=tape b=tape]
66 ^- (map @t @t)
67 =| chart=(map @t @t)
68 ?. =((lent a) (lent b))
69 ~| %uneven-lengths !!
70 |-
71 ?: |(?=(~ a) ?=(~ b))
72 chart
73 $(chart (~(put by chart) i.a i.b), a t.a, b t.b)
74++ rott
75 |= [m=tape n=@ud]
76 =/ length=@ud (lent m)
77 =+ s=(trim (mod n length) m)
78 (weld q.s p.s)
79--
80```
82This generator takes two arguments: a `tape`, which is your plaintext message,
83and an unsigned integer, which is the shift-value of the cipher. It produces
84a cell of two `tapes`: one that has been shifted right by the value, and another
85that has been shifted left. It also converts any uppercase input into lowercase.
87Try it out in the Dojo:
89```
90> +caesar ["test" 2]
91["vguv" "rcqr"]
93> +caesar ["test" 26]
94["test" "test"]
96> +caesar ["test" 28]
97["vguv" "rcqr"]
99> +caesar ["test" 104]
100["test" "test"]
102> +caesar ["tESt" 2]
103["vguv" "rcqr"]
105> +caesar ["test!" 2]
106nest-fail
107```
109### Examining Our Code
111Let's examine our `caesar.hoon` code piece by piece. We won't necessarily go
112in written order; instead, we'll cover code in the intuitive order of the
113program. For each chunk that we cover, try to read and understand the code
114itself before reading the explanation.
116```hoon
117!:
118|= [msg=tape key=@ud]
119=<
120```
122The `!:` in the first line of the above code enables a full stack trace in the
123event of an error.
125`|= [msg=tape key=@ud]` creates a [gate](/docs/glossary/gate/) that takes a cell. The head of this cell
126is a `tape`, which is a string type that's a list of `cord`s. Tapes are represented
127as text surrounded by double-quotes, such as this: `"a tape"`. We give this input
128tape the face `msg`. The tail of our cell is a `@ud` -- an unsigned decimal [atom](/docs/glossary/atom/)
129-- that we give the face `key`.
131`=<` is the rune that evaluates its first child expression with respect to its
132second child expression as the subject. In this case, we evaluate the
133expressions in the code chunk below against the [core](/docs/glossary/core/) declared later, which
134allows us reference the core's contained [arms](/docs/glossary/arm/) before they are defined. Without
135`=<`, we would need to put the code chunk below at the bottom of our program.
137```hoon
138=. msg (cass msg)
139:- (shift msg key)
140(unshift msg key)
141|%
142```
144`=. msg (cass msg)` changes the input string `msg` to lowercases. `=.` changes
145the leg of the subject to something else. In our case, the leg to be changed is
146`msg`, and the thing to replace it is `(cass msg)`. `cass` is a standard-library
147gate that converts uppercase letters to lowercase.
149`:- (shift msg key)` and `(unshift msg key)` simply composes a
150cell of a right-shifted cipher and a left-shifted cell. This is the final output
151of our generator.
153`|%` creates a core.
155```hoon
156 ++ rott
157 |= [m=tape n=@ud]
158 =/ length=@ud (lent m)
159 =+ s=(trim (mod n length) m)
160 (weld q.s p.s)
161```
163The `rott` arm takes takes a specified number of characters off of a tape and
164puts them on the end of the tape.
166`|= [m=tape n=@ud]` creates a gate that takes two arguments: `m`, a `tape`,
167and `n`, a `@ud`.
169`=/ length=@ud (lent m)` stores the length of `m` to make the following
170code a little clearer.
172`trim` is a a gate from the standard library that splits a tape at into two
173parts at a specified position. So `=+ s=(trim (mod n length) m)` splits the
174tape `m` into two parts, `p` and `q`, and stores it in `s`. We call the modulus
175operation `mod` to make sure that we split our `tape` at the correct place, even
176if `n` is larger than `length`.
178`(weld q.s p.s)` uses `weld`, which combines two strings into one. In this
179instance, we are switching the two parts: the second part `q.s` is welded to the
180front, and the first part `p.s` is welded to the back.
182```hoon
183 ++ zipper
184 |= [a=tape b=tape]
185 ^- (map @t @t)
186 =| chart=(map @t @t)
187 ?. =((lent a) (lent b))
188 ~| %uneven-lengths !!
189 |-
190 ?: |(?=(~ a) ?=(~ b))
191 chart
192 $(chart (~(put by chart) i.a i.b), a t.a, b t.b)
193```
195The `zipper` arm takes two tapes and creates a `map` out of them -- an
196association between their elements.
198So then if `tapes` are easier to manipulate, why then are we producing `cords`?
199In this case what we are going to to be doing is mapping a single element of a `
200tape` to another element of a `tape`, which as we have established as being a
201`cord`. This will simplify our use of this method and we don't need to
202manipulate the keys or values, simply look them up.
204`|= [a=tape b=tape]` builds a gate that takes two tapes, `a` and `b`, as its
205sample.
207`^- (map @t @t)` casts the gate to a `map` with a `cord` key and a `cord`
208value. A `map` is a type equivalent to a dictionary in other languages: it's a
209data structure that associates a key with a value. If, for example, we wanted
210to have an association between `a` and 1 and `b` and 2, we could use a `map`.
212`=| chart=(map @t @t)` adds a [noun](/docs/glossary/noun/) to the subject with the default value of
213the `(map @t @t)` type, and gives that noun the face `chart`.
215`?. =((lent a) (lent b))` checks if the two tapes are the same length. If not,
216the program crashes.
218`|-` creates a [trap](/docs/glossary/trap/), a gate that is called immediately.
220`?: |(?=(~ a) ?=(~ b))` checks if either tape is empty. If this is true, we
221the program is finished and can return `chart`, the the `map` that we have been
222creating.
224If the above test finds that its condition to be false, we trigger a recursion
225that constructs our `map`: `$(chart (~(put by chart) i.a i.b), a t.a, b t.b)`.
226This code recursively adds an entry in our `map` where the head of the tape `a`
227maps to the value of the head of tape `b` with `~(put by chart)`, our calling
228of the `put` arm of the `by` map-engine core. The recursion also "consumes"
229those heads with every iteration by changing `a` and `b` to their tails.
231Perhaps now you can understand why this arm is named `zipper`. It's putting two
232tapes together by matching pieces from each side, something akin to a jacket zipper.
234We have three related arms to look at next, `coder`, `encoder`, and
235`decoder`. `coder` is the foundation of the other two, so we'll look at it
236first.
238```hoon
239 ++ coder
240 |= [a=tape b=tape]
241 (~(put by (zipper a b)) ' ' ' ')
242```
244`|= [a=tape b=tape]` creates a gate that takes two `tapes`.
246We use `put by` on the next line, giving it a `map` produced by the `zipper`
247arm that we created before. This adds an entry to the map where the space
248character (called `ace`) simply maps to itself. This is done to simplify
249the handling of spaces in `tapes` we want to encode, since we don't want to
250shift them.
252```hoon
253 ++ encoder
254 |= [key=@ud]
255 =/ keytape=tape (rott alpha key)
256 (coder alpha keytape)
257 ++ decoder
258 |= [key=@ud]
259 =/ keytape=tape (rott alpha key)
260 (coder keytape alpha)
261```
263`encoder` and `decoder` are implemented in terms of the `coder` arm. These gates
264are essentially identical, with the arguments reversed. They simplify the two
265common transactions you want to do in this program: producing `maps` that we can
266use to encode and decode messages.
268In both cases, we create a gate that accepts a `@ud` named `key`.
270`=/ keytape=tape (rott alpha key)` creates a `keytape` noun by calling `rott`
271on `alpha` our `key` input. `alpha` is our arm which contains a `tape` of the
272entire alphabet.
274`(coder alpha keytape)`, for `encoder`, and `(coder keytape alpha)`, for
275`decoder`, produce a `map` that has the first argument as the keys and the
276second as the values.
278If our two inputs to `coder` were `"abcdefghijklmnopqrstuvwxyz"` and
279`"bcdefghijklmnopqrstuvwxyza"` We would get a `map` where `'a'` maps to `'b'`,
280`'b'` to `'c'` and so on. By doing this we can produce a `map` that gives us a
281translation between the alphabet and our shifted alphabet, or vice versa.
283Still with us? Good. We are finally about to use all the stuff that we've
284walked through.
286```hoon
287 ++ shift
288 |= [message=tape key=@ud]
289 (operate message key (encoder key))
290 ++ unshift
291 |= [message=tape key=@ud]
292 (operate message key (decoder key))
293```
295Both `shift` and `unshift` take two arguments: our `message`, the `tape` that we
296want to manipulate; and our `key`, the value that we want to shift our message
297by.
299`shift` is for encoding, and `unshift` is for decoding. Thus, `shift` calls the
300`operate` arm with `(operate message key (encoder key))`, and `unshift` makes
301that call with `(operate message key (decoder key))`. These both produce the
302final output of the core, to be called in the form of `(shift msg key)`
303and `(unshift msg key)` at the bottom of the program.
305```hoon
306++ operate
307 |= [message=tape key=@ud encoder=(map @t @t)]
308 ^- tape
309 %+ turn message
310 |= a=@t
311 (~(got by encoder) a)
312```
314`operate` produces a `tape`. The `%+` rune allows us to pull an arm
315with a pair sample. The arm we are going to pull is `turn`. This arm
316takes two arguments, a `list` and a `gate` to apply to each element of the
317`list`.
319If we then give our arm Caesar's famous statement, and get our left- and
320right-ciphers.
322```
323> +caesar ["i came i saw i conquered" 4]
324["m geqi m wea m gsruyivih" "e ywia e ows e ykjmqanaz"]
325```
327Now, to decode, we can put either of our ciphers in with the appropriate key and
328look for the legible result.
330```
331> +caesar ["m geqi m wea m gsruyivih" 4]
332["q kium q aie q kwvycmzml" "i came i saw i conquered"]
334> +caesar ["e ywia e ows e ykjmqanaz" 4]
335["i came i saw i conquered" "a usew a kso a ugfimwjwv"]
336```
338### Exercises
3401. Take the example generator and modify it to add a second layer of shifts.
3422. Extend the example generator to allow for use of characters other than a-z.
3443. Build a gate that can take a Caesar shifted `tape` and produce
345possible unshifted `tapes`.
3474. Modify the example generator into a `%say` generator.