Our next stop is to examine another use case of macros. You’re going to make the Clojure compiler work harder by doing some work that would otherwise have to be done by your program at runtime.
11.3.1 Example: Rotation ciphers without macros
So far in this book, you’ve seen several uses of macros and have written several macros yourself. In this section, you’re going to see another use of macros, and it has to do with performance. To illustrate the concept, we’ll examine a simple code cipher called ROT13. It stands for “rotate by 13 places” and is a simple cipher that can be broken quite easily. But its purpose is to hide text in a way that isn’t immediately obvious, so as not to communicate spy secrets. It’s commonly used as the online equivalent of text printed upside down (for example, in magazines and newspapers), to give out puzzle solutions, answers to riddles, and the like.
ABOUTTHE ROT13 CIPHER
Table 11.1 shows what each letter of the alphabet corresponds to.
The first row is the index for each letter of the alphabet, starting at 1. The second row is the alphabet itself. The last row is the alphabet shifted by 13 places. Each letter on this last row corresponds to the letter that will be used in place of the letter above it in a message encrypted using this cipher system. For example, the word abracadabra becomes noenpnqnoen.
Table 11.1 Alphabet rotated by 13 places
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
a b c d e f g h i j k l m n o p q r s t u v w x y z
n o p q r s t u v w x y z a b c d e f g h i j k l m
277 Shifting computation to compile time
Decrypting a rotation cipher is usually done by rotating each letter back the same number of times. ROT13 has the additional property of being a reciprocal cipher. A message encrypted using a reciprocal cipher can be decrypted by running it through the cipher system itself. The encryption process also works to decrypt encrypted mes- sages. In this section, you’ll implement a generalized rotation cipher by allowing the rotation length to be passed in as a parameter.
GENERALIZEDROTATIONCIPHERS
Let’s begin the implementation with the letters of the alphabet. Recall that Clojure has a convenient reader macro to represent literal characters:
(def ALPHABETS [\a \b \c \d \e \f \g \h \i \j \k \l \m \n \o \p \q \r \s \t
\u \v \w \x \y \z])
Let’s also define a few convenience values based on the alphabet shown:
(def NUM-ALPHABETS (count ALPHABETS)) (def INDICES (range 1 (inc NUM-ALPHABETS))) (def lookup (zipmap INDICES ALPHABETS))
Now, let’s talk about your approach. Because you want to implement a generic rota- tion mechanism, you’ll need to know at which numbered slot a letter falls when it’s rotated a specific number of times. You’d like to take a slot number such as 14, rotate it by a configurable number, and see where it ends up. For example, in the case of ROT13, the letter in slot 10 (which is the letter j) ends up in slot 23. You’ll write a func- tion called shift, which will compute this new slot number. You can’t add the shift-by number to the slot number because you’ll have to take care of overflow. Here’s the implementation of shift:
(defn shift [shift-by index]
(let [shifted (+ (mod shift-by NUM-ALPHABETS) index)]
(cond
(<= shifted 0) (+ shifted NUM-ALPHABETS)
(> shifted NUM-ALPHABETS) (- shifted NUM-ALPHABETS) :default shifted)))
There are a couple of points to note here. The first is that you calculated shifted by adding (modshift-byNUM-ALPHABETS) to the given index (and not shift-by) so that you can handle the cases where shift-by is more than NUM-ALPHABETS. Because you handle overflow by wrapping to the beginning, this approach works, for example:
(shift 10 13)
;=> 23
(shift 20 13)
;=> 7
Now that you have this function, you can use it to create a simple cryptographic tab- leau, a table of rows and columns with which you can decrypt or encrypt information.
In this case, for ROT13, the tableau would be the second and third rows from table 15.1.
Here’s a function that computes this:
(defn shifted-tableau [shift-by]
(->> (map #(shift shift-by %) INDICES) (map lookup)
(zipmap ALPHABETS)))
This creates a map where the keys are alphabets that need to be encrypted, and values are the cipher versions of the same. Here’s an example:
(shifted-tableau 13)
;=> {\a \n, \b \o, \c \p, \d \q, \e \r, \f \s, \g \t, \h \u, \i \v, \j \w, \k
\x, \l \y, \m \z, \n \a, \o \b, \p \c, \q \d, \r \e, \s \f, \t \g, \u
\h, \v \i, \w \j, \x \k, \y \l, \z \m}
Because this cipher is quite simple, a simple map such as this suffices. Now that you have your tableau, encrypting messages is as simple as looking up each letter. Here’s the encrypt function:
(defn encrypt [shift-by plaintext]
(let [shifted (shifted-tableau shift-by)]
(apply str (map shifted plaintext))))
Try it at the REPL:
(encrypt 13 "abracadabra")
;=> "noenpnqnoen"
That works as expected. Recall that ROT13 is a reciprocal cipher. Check to see if it works:
(encrypt 13 "noenpnqnoen")
;=> "abracadabra"
It does! If you rotate by anything other than 13, you’ll need a real decrypt function.
All you need to do to decrypt a message is to reverse the process. You’ll express that as follows:
(defn decrypt [shift-by encrypted]
(encrypt (- shift-by) encrypted))
decrypt works by rotating an encrypted message the other way by the same rotation.
This shows how it works at the REPL:
(decrypt 13 "noenpnqnoen")
;=> "abracadabra"
Great, so you have all the bare necessities in place. To implement a particular cipher, such as ROT13, you can define a pair of functions as follows:
(def encrypt-with-rot13 (partial encrypt 13)) (def decrypt-with-rot13 (partial decrypt 13))
279 Shifting computation to compile time
Now try it at the REPL:
(decrypt-with-rot13 (encrypt-with-rot13 "abracadabra"))
;=> "abracadabra"
So there you have it; you’ve implemented the simple cipher system. The complete code is shown in the following listing.
(ns clj-in-act.ch11.shifting)
(def ALPHABETS [\a \b \c \d \e \f \g \h \i \j \k \l \m \n \o \p \q \r \s \t
\u \v \w \x \y \z])
(def NUM-ALPHABETS (count ALPHABETS)) (def INDICES (range 1 (inc NUM-ALPHABETS))) (def lookup (zipmap INDICES ALPHABETS)) (defn shift [shift-by index]
(let [shifted (+ (mod shift-by NUM-ALPHABETS) index)]
(cond
(<= shifted 0) (+ shifted NUM-ALPHABETS)
(> shifted NUM-ALPHABETS) (- shifted NUM-ALPHABETS) :default shifted)))
(defn shifted-tableau [shift-by]
(->> (map #(shift shift-by %) INDICES) (map lookup)
(zipmap ALPHABETS ))) (defn encrypt [shift-by plaintext]
(let [shifted (shifted-tableau shift-by)]
(apply str (map shifted plaintext)))) (defn decrypt [shift-by encrypted]
(encrypt (- shift-by) encrypted))
(def encrypt-with-rot13 (partial encrypt 13)) (def decrypt-with-rot13 (partial decrypt 13))
The issue with this implementation is that you compute the tableau each time you encrypt or decrypt a message. This is easily fixed by memoizing the shifted-tableau function. This will take care of this problem, but in the next section, you’ll go one step further.
11.3.2 Making the compiler work harder
So far, you’ve implemented functions to encrypt and decrypt messages for any rotation cipher. Your basic approach has been to create a map that can help you code (or decode) each letter in a message to its cipher version. As discussed at the end of the previous sec- tion, you can speed up your implementation by memoizing the tableau calculation.
Even with memoize, the computation still happens at least once (the first time the function is called). Imagine, instead, if you created an inline literal map containing the appropriate tableau data. You could then look it up in the map each time, without having to compute it. Such a definition of encrypt-with-rot13 might look like this:
(defn encrypt-with-rot13 [plaintext]
(apply str (map {\a \n \b \o \c \p} plaintext)))
Listing 11.1 A general rotation cipher system to implement things like ROT13
In an implementation, the tableau would be complete for all the letters of the alpha- bet, not only for \a, \b, and \c. In any case, if you did have such a literal map in the code itself, it would obviate the need to compute it at runtime. Luckily, you’re coding in Clojure, and you can bend it to your will. Consider the following:
(defmacro def-rot-encrypter [name shift-by]
(let [tableau (shifted-tableau shift-by)]
`(defn ~name [~'message]
(apply str (map ~tableau ~'message)))))
This macro first computes the tableau for shifted-by as needed and then defines a function by the specified name. The function body includes the computed table, in the right place, as illustrated in the preceding code sample. Look at its expansion:
(macroexpand-1 '(def-rot-encrypter encrypt13 13))
;=> (clojure.core/defn encrypt13 [message] (clojure.core/apply clojure.core/
str (clojure.core/map {\a \n, \b \o, \c \p, \d \q, \e \r, \f \s, \g \t,
\h \u, \i \v, \j \w, \k \x, \l \y, \m \z, \n \a, \o \b, \p \c, \q \d, \r
\e, \s \f, \t \g, \u \h, \v \i, \w \j, \x \k, \y \l, \z \m} message)))
This looks almost exactly like the desired function, with an inline literal tableau map.
Figure 11.1 shows the flow of the code.
Code as data Reader
Macro expansion (callsshifted-tableaufunction)
Code with inline Clojure tableau map def-rot-encrypter
Evaluate Compile
Figure 11.1 As usual, the Clojure reader first converts the text of your programs into data structures. During this process, macros are expanded, including the def-rot-encrypter macro, which generates a tableau. This tableau is a Clojure map and is included in the final form of the source code as an inline lookup table.
281 Macro-generating macros
Now check to see if it works:
(def-rot-encrypter encrypt13 13)
;=> #'user/encrypt13 (encrypt13 "abracadabra")
;=> "noenpnqnoen"
And there you have it. The new encrypt13 function at runtime doesn’t do any tableau computation at all. If, for instance, you were to ship this code off to users as a Java library, they wouldn’t even know that shifted-tableau was ever called.
As a final item, you’ll create a convenient way to define a pair of functions that can be used to encrypt or decrypt functions in a rotation cipher:
(defmacro define-rot-encryption [shift-by]
`(do
(def-rot-encrypter ~(symbol (str "encrypt" shift-by)) ~shift-by) (def-rot-encrypter ~(symbol (str "decrypt" shift-by)) ~(- shift-by))))
And finally, here it is in action:
(define-rot-encryption 15)
;=> #'user/decrypt15
Here, it prints the decrypt function var, because it was the last thing the macro expan- sion did. Now use the new pair of functions:
(encrypt15 "abracadabra")
;=> "pqgprpspqgp"
(decrypt15 "pqgprpspqgp")
;=> "abracadabra"
Shifting computation to the compile cycle can be a useful trick when parts of the com- putation needed are known in advance. Clojure macros make it easy to run arbitrary code during the expansion phase and give the programmer the power of the full Clo- jure language itself. In this example, for instance, you wrote the shifted-tableau function with no prior intention of using it in this manner. Moving computation into macros this way can be quite handy at times, despite how simple it is to do.