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