1 The Problem
2 A First Design
<crypt>
<encrypt>
<decrypt>
<rest>
<wave>
<en-body>
<de-body>
2.1 Waves
<wave-examples>
<other-imports>
<wave-body>
2.2 Additional Auxiliaries
<more-rest>
<reorder>
<transpose>
3 A Concise Version
<crypt-concise>
3.1 A New Wave
<auxiliaries>
<reorder-concise>
<wave-concise-body>
4 Linearity: Imperative Code
<crypt-linear>
4.1 Linear Decrypting
<decrypt-linear>
4.2 Linear Waves
<wave-linear-body>
4.3 Tests
<tests>
5 For the Impatient Reader
<crypt-impatient>
Version: 4.2.0.2

Fences and Encryption

Matthias Felleisen

In March 2009, Marek Kubica posted a problem concerning encryption on the plt-scheme mailing list. After studying his array-based attempt, I posted my own solution using the output-driven design recipe (beyond HtDP). Phil Bewig later posted my solution on his {Programming Praxis} blog as a sample "etude", which provoked various responses.

This essay continues this design exercise, explaining in detail how a mostly functional programmer would translate this first design into a linear imperative algorithm. The impatient reader may wish to jump to the last section and just look at the solution.

In addition, this essay is for me a first exercise in literate programming, an idea suggested by Knuth and implemented for PLT Scheme by Matthew, Eli, and Robby.

Note: While I am going to develop this program with a design recipe, the development takes place in a PLT Scheme module and uses the full language and its libraries. For the first solution, the differences to a program that a student could write in Intermediate Student Language are small and easy to overlook.

1 The Problem

The problem is easy to describe with a diagram. Suppose you’re given a string, such as,

"dies ist ein klar text"

and you wish to encrypt it via a rearrangement of its letters. Specifically, you pick a positive integer i and arrange the letters in a wave form whose height is determined by i. If the given number is 3 and the text is the above, the wave form looks like this:

                         d   _   _   _   r   x
                          i s i t e n k a _ e t
                           e   s   i   l   t

For clarification, the blank spaces in the original text have been turned into underscores. Once you have the wave form of height i, you read the i lines

                         d___rx
                         isitenka_et
                         esilt

and juxtapose them:

"d___rxisitenka_etesil"

The resulting string is the encrypted version of the given string. Conversely, given an encrypted string and some positive integer i, you decrypt it analogously.

Exercise: Encrypt the same string from above using wave forms of height 6.

Exercise: Make up some other strings and encrypt them using different integers.

Exercise: Ask a friend to encrypt some string using waves of height 3. Then decrypt it and confirm with your friend that you did so properly.

2 A First Design

Given that the goal of the development is to design two functions, encrypt and decrypt, the module consists of five sections:

<crypt> ::=

  (require scheme test-engine/scheme-tests) <other-imports>
  <encrypt>
  <decrypt>
  <rest>
  (test)

) The first section specifies the imports. Here the module imports the base language (scheme) and one of the numerous unit testing libraries. Sections two and three are about the two main functions; section four exists just in case the two need common auxiliaries; and the last section just runs the test suite.

The design recipe demands a concise description of what the functions compute and some examples, which are usually formulated as test cases. Assuming a code reader knows the problem statement, this header material for the two functions is straightforward:

<encrypt> ::=

  ; String Positive -> String
  ; encrypt str via waves of height h
  
  (check-expect (encrypt "diesisteinklartext" 6) "dkinleiasertittxse")
  
  (define (encrypt str h)
    <en-body>)

<decrypt> ::=

  ; String Positive -> String
  ; decrypt str, which was created via waves of height h
  
  (check-expect (decrypt "dkinleiasertittxse" 6) "diesisteinklartext")
  
  (define (decrypt str h)
    <de-body>)

First, both encrypt and decrypt consume a string and a positive number, and both produce a string. Second, the encrypt example from the problem statement is easily translated into a test case, and because the problem statement also specifies how this process works, the purpose statement for encrypt alludes to this background. A code reader can thus easily imagine how encrypt computes its results, not only what it computes. Concerning decrypt, however, a reader lacks such an understanding.

The next step is therefore to imagine how a person may go about decrypting the string "dkinleiasertittxse", given the knowledge that it is encrypted via waves of height 6. Here is the picture that explains it all:

               given:
                 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
               
               the wave:
                 1. 0         10                = (0 10)
                 2.  1       9  11              = (1 9 11)
                 3.   2     8     12            = (2 8 12)
                 4.    3   7        13      17  = (3 7 13 17)
                 5.     4 6           14  16    = (4 6 14 16)
                 6.      5              15      = (5 15)
               
               wanted:
                 0 10 1 9 11 2 8 12 3 7 13 17 4 6 14 16 5 15

If instead of strings encrypt dealt with lists of, say, numbers, decrypt could use it to determine the indices from which the various characters originated.

Conversely, both functions should employ an auxiliary function that scrambles any list according to the wave principle. That is, the function should consume a list of items l and a positive integer i, and its output should be a rearrangement of l via waves of height i as illustrated above.

Naturally, this common auxiliary function belongs into the rest section of the code:

<rest> ::=

  <wave>
  <more-rest>

<wave> ::=

  ; [Listof X] Positive -> [Listof X]
  ; rearrange items of list via intermediate waves of height h
  
  (check-expect (wave (list 1 2 3 4 5 6) 3)
                (list 1 5 2 4 6 3))
  (check-expect (wave (list 0 1 2 3 4 5 6 7 8 9) 6)
                (list 0 1 9 2 8 3 7 4 6 5))
  
  <wave-examples>
  
  (define (wave lox i)
    <wave-body>)

Using wave, the function bodies for encrypt and decrypt are straightforward:

<en-body> ::=

  (list->string (wave (string->list str) h))

<de-body> ::=

  (define i (wave (build-list (string-length str) (lambda (x) x)) h))
  (list->string (reorder (string->list str) i))

Both functions turn the given string into a list, rearrange the items of the list, and turn the resulting list back into a string. In particular, the body of encrypt employs wave on the list of characters, to compute the rearrangement. The body of decrypt uses wave too, but on a list of indices for the given string; once it has a rearrangement of the indices from wave, it uses an auxiliary function reorder to get the characters of the given string into their original order.

2.1 Waves

The wave function is the heart of the project. Its purpose is to create a wave of some given height from a list of items and then to create a new list of items from these waves. When confronted with such a complex task description, it is best to work through an example. Take

(wave '(a b c d e f) 3)

The wave form for these inputs looks like this:

                              a       e
                                b   d   f
                                  c

and the desired result is therefore '(a e b d f c).

One way to think of this wave form algorithmically is to split the list into "down waves" and "up waves," each consisting of two elements:

                              a                                   e
                               b                d                  f
                                               c

In terms of data this means turning the given list into a list of lists:

  (list (list 'a 'b)
        (list 'c 'd)
        (list 'e 'f))

With a reversal of the "up waves" the list of lists is almost the desired result:

  (list (list 'a 'b)
        (list 'd 'c)
        (list 'e 'f))

The problem is that "down waves" don’t reach the last line, and "up waves" don’t reach the top line. Such problems call for dummy items that are added to the lists now and removed at the end:

  (list (list 'a 'b '&)
        (list '& 'd 'c)
        (list 'e 'f '&))

With a simple transposition this matrix is basically the result of wave:

  (list (list 'a '& 'e)
        (list 'b 'd 'f)
        (list '& 'c '&))

More precisely, the result is the concatenation of the lists in this matrix and the removal of the special items.

Of course, it is equally correct to consider "down waves" of the given length combined with "up waves" that are missing two items and vice versa. The key is to see the eureka, the insight that the wave function must somehow split the given list into a list of lists and manipulate those. In sum, wave is a generative recursive function and, for now, uses the above process.

The design of generative recursive function is subtle and demands a good set examples, especially for border cases: <wave-examples> ::=

  ; the first "down wave" is all there is
  (check-expect (wave '(a b c) 3)
                '(a b c))
  ; there is just one more item for the "up wave"
  (check-expect (wave '(a b c d) 3)
                '(a b d c))
  ; ... and two more:
  (check-expect (wave '(a b c d e) 3)
                '(a e b d c))
  ; finally: a complete "down wave" and a complete "up wave"
  (check-expect (wave '(a b c d e f) 3)
                '(a e b d f c))

What these additional test cases show is that wave may run out of list items before the last "down-and-up wave" is complete. One natural solution is to pad the list with a sufficient number of unique items, which – as you should recall – are removed at the end anyway.

Here is the complete definition of wave, prefixed with two additional imports. The imported functions compute prefixes and suffixes of lists of some given length and are just what’s needed to turn the process into code:

<other-imports> ::=

  (require (only-in srfi/1 take drop))

<wave-body> ::=

  (define UNI '_)
  (define WVL (- (* 2 i) 2))
  ; [Listof X] -> [Listof [Listof (U X UNI)]]
  ; create lists of "down-and-up waves"
  ; termination: each recursion drops h items and (> h 0)
  (define (wave lox)
    (define L (length lox))
    (cond
      [(<= WVL L) (append (down-and-up lox) (wave (drop lox WVL)))]
      [else (down-and-up (append lox (make-list (- WVL L) UNI)))]))
  ; [Listof X] -> (list [Listof (U X UNI)] [Listof (U X UNI)])
  ; create one "down-and-up wave"
  (define (down-and-up lox)
    (list (take-and-pad lox) (reverse (take-and-pad (drop lox (- i 1))))))
  ; [Listof X] -> [Listof (U X UNI)]
  (define (take-and-pad lox)
    (append (take lox (- i 1)) (list UNI)))
  ; now transpose, concatenate, and remove the UNI item
  (filter (lambda (x) (not (eq? UNI x)))
          (apply append (transpose (wave lox))))

The first locally defined function, also called wave, is the workhorse. As long as the given list is long enough, it takes one "down wave" of length (- i 1) and an "up wave" of the same length. When it is about to run out of list items, the function pads it with just enough items and then creates one last "down-and-up wave." In the context of these local definitions, wave creates the list of pairs of waves, transposes the resulting matrix, and finally removes the padding items.

2.2 Additional Auxiliaries

This leaves two auxiliary functions to be designed:

<more-rest> ::=

  <reorder>
  <transpose>

The definition of the first one, reorder, exploits a standard functional programmng trick:

<reorder> ::=

  ; [Listof X] [Listof Nat] -> [Listof X]
  ; order list s according to indices in list i
  
  (check-expect (reorder '(a b c) '(1 2 0)) '(c a b))
  
  (define (reorder s i)
    (map second (sort (map list i s) <= #:key first)))

It first combines the indices with their corresponding items, then sorts this list of pairs with respect to the index component, and finally strips away the indices from the sorted list of pairs. The result is a list like s but ordered according to th indices in i.

The definition of the second function, transpose, apparently follows the standard design recipe for structural functions, though like reorder it uses map on its arguments:

<transpose> ::=

  ; [Listof [Listof X]] -> [Listof [Listof X]]
  ; transpose the matrix
  
  (check-expect (transpose '((1 2 3) (a b c) (^ & *)))
                '((1 a ^) (2 b &) (3 c *)))
  
  (define (transpose m)
    (cond
      [(empty? (first m)) '()]
      [else (cons (map first m) (transpose (map rest m)))]))

More precisely, transpose traverses the given list of list, extracting the first items at each step and using the rests of the lists as the argument for the recursion. Of course, the latter reveals that transpose is really generative recursive, creating a new matrix at each step and not using a structural component of the matrix.

An experienced Scheme programmer can see that transpose is just like map, except that it traverses many lists – all lists in m – at once. Since Scheme’s map – unlike ML’s or Haskell’s – is a multi-arity function, it is possible to define transpose as a one-line function:

  (define (transpose m) (apply map list m))

If this looks cryptic, use the example from above to figure out how it works.

3 A Concise Version

While the definition of wave follows the design recipe for generative recursion (identifying the generative idea and the "trivial problem" condition), it is complex and difficult to understand. Fortunately the development of the process for wave suggests an alternative view, which leads to a more concise definition than in the preceding section.

This section develops this idea, starting from the initial design of wave. Here is the context: <crypt-concise> ::=

  (require scheme test-engine/scheme-tests (only-in srfi/1 take drop))
  
  ; String Positive -> String
  ; encrypt str via waves of height h
  
  (check-expect (encrypt "diesisteinklartext" 6) "dkinleiasertittxse")
  
  (define (encrypt str h)
    (list->string (wave (string->list str) h)))
  
  ; String Positive -> String
  ; decrypt str, which was created via waves of height h
  
  (check-expect (decrypt "dkinleiasertittxse" 6) "diesisteinklartext")
  
  (define (decrypt str h)
    (define w (wave (build-list (string-length str) (lambda (x) x)) h))
    (list->string (reorder w (string->list str))))
  
  ; [Listof X] Positive -> [Listof X]
  ; rearrange items of list via intermediate waves of height h
  
  (check-expect (wave (list 1 2 3 4 5 6) 3)
                (list 1 5 2 4 6 3))
  (check-expect (wave (list 0 1 2 3 4 5 6 7 8 9) 6)
                (list 0 1 9 2 8 3 7 4 6 5))
  
  ; the first "down wave" is all there is
  (check-expect (wave '(a b c) 3) '(a b c))
  
  ; there is just one more item for the "up wave"
  (check-expect (wave '(a b c d) 3) '(a b d c))
  
  ; ... and two more:
  (check-expect (wave '(a b c d e) 3) '(a e b d c))
  
  ; finally: a complete "down wave" and a complete "up wave"
  (check-expect (wave '(a b c d e f) 3) '(a e b d f c))
  
  (define (wave lox i)
    <wave-concise-body>)
  
  <reorder-concise>
  
  <auxiliaries>
  
  (test)

It sets up the two primary functions and the header for wave, the common auxiliary function. Otherwise it leaves room for a new body for wave, an alternative definition of reorder if needed, plus other auxiliaries.

3.1 A New Wave

The design of decrypt motivated the design of the auxiliary function wave via the following example:

               given:
                 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
               
               the wave:
                 1. 0         10                = (0 10)
                 2.  1       9  11              = (1 9 11)
                 3.   2     8     12            = (2 8 12)
                 4.    3   7        13      17  = (3 7 13 17)
                 5.     4 6           14  16    = (4 6 14 16)
                 6.      5              15      = (5 15)
               
               wanted:
                 0 10 1 9 11 2 8 12 3 7 13 17 4 6 14 16 5 15

One way to read this image is to see the wave as an intermediate form that determines the order of the given items. When combined with the design of wave itself, an alternative view emerges. Instead of arranging the items directly in a wave form, it is possible to use the down-and-up pattern and its repetition:

                given:
                  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
               
                the wave:
               1. 0                    0
               2.   1               1     1
               3.     2           2          2
               4.       3       3               3           3
               5.         4   4                    4     4
               6.           5                         5
               
                wanted:
                  0 10 1 9 11 2 8 12 3 7 13 17 4 6 14 16 5 15

In this context the desired result is a re-arrangement of the given list according to the sine-wave of line indices from left to right: the two 0-index items are 0 an 10, the 1-indexed items are 1 and 11, all the way to the 5-indexed items, which are 5 and 15.

Put differently, if the program can create a sufficiently long sine-wave, the wave function can use it to reorder the given list appropriately.

At this point, it is critical to recall effects and one of the primary uses of effects: the creation of cyclic pieces of data. In PLT Scheme this isn’t only possible, there is a special form for it that does it all:

  > (shared ((x (list 1 2 3 x))) x)

  #0=(1 2 3 #0#)

Like letrec or local, shared sets up recursive definitions for a body. Unlike those forms, however, the recursive definitions of shared create cyclic pieces of data, not functions. In this example, shared sets up x as the list that starts with 1, 2, and 3 and then repeats itself forever.

Other than this, the only thing worth knowing is that PLT Scheme permits the use of many list constructors in shared. Thus, if i is some parameter,

  (share ((x (append (build-list i (lambda (x) x)) x))) ...)

defines x as (list 0 1 ... (math "i-1")) for the body of the shared. For the definition of wave the list must cycle through all line numbers twice – except for the bottom and the top – before it repeats. Doing so requires just one more list

  > (shared ((x (append (build-list i (lambda (x) x))
                        (build-list (- i 2) (lambda (x) (- i x 2)))
                        x)))
      x)

  #0=(0 1 2 3 4 5 4 3 2 1 . #0#)

Naturally the pattern of creating ranges of numbers (as lists) deserves its own function:

  ; Nat Nat -> [Listof Nat]
  
  (check-expect (range 2 5) '(2 3 4))
  (check-expect (range 5 2) '(4 3 2))
  
  (define (range lo hi)
    (if (>= hi lo)
        (build-list (+ (- hi lo) 1) (lambda (i) (+ lo i)))
        (build-list (+ (- lo hi) 1) (lambda (i) (- lo i)))))

Indeed, this function deserves to be included in a library:

<auxiliaries> ::=

  (require "range.ss")

Equipped with this prelude, the re-definition of wave looks straightforward:

  (define is (shared ((x (append (range 0 i) (range (- i 1) 1) x))) x))
  (reorder is lox)

The local definition sets up the sine wave, and the body proper uses reorder to re-arrange the given list (lox) according to the infinitely long sine-wave.

The above definition assumes that when reorder maps list over both the given list and the cyclic list of indices ends when the former is exhausted:

  (define (reorder s i)
    ... (map list i s) ...)

Unfortunately, this is not the case because Scheme’s map assumes all given lists are of the same length. PLT Scheme’s for/list construct, however, is made for just such situations. It permits functions to iterate over distinct sequences, including lists and vectors and cyclic lists, in parallel. Thus, the proper definition for reorder is this: <reorder-concise> ::=

  ; [Listof Nat] [Sequence Y] -> [Listof Y]
  ; sort lst according to indices in is
  
  (check-expect (reorder '(1 2 0) '(a b c)) '(c a b))
  
  (define (reorder is ls)
    (map first (sort (for/list ((i is) (l ls)) (list l i)) < #:key second)))

All that is left to do is to turn the cyclic list into a sequence for for/list and to hand it to reorder: <wave-concise-body> ::=

  (define is
     (in-list (shared ((x (append (range 0 i) (range (- i 1) 1) x))) x)))
  (reorder is lox)

Because lists such as lox are already sequences, this re-definition of wave concludes this section.

4 Linearity: Imperative Code

Both solutions are functional and use sort to reorder the items of a list according to some list of indices. As a result, the worst-case complexity of the decrypt function is O(n log n) where n is the length of the given string.

The starting point for this section is this outline:

<crypt-linear> ::=

  (require scheme test-engine/scheme-tests "range.ss")
  
  ; String Nat -> String
  ; encrypt str via waves of height h
  (define (encrypt str h)
    (list->string (wave str h)))
  
  <decrypt-linear>
  
  ; [Sequence X] Nat -> [Listof X]
  ; rearrange items of sox via intermediate waves of height h
  (define (wave sox i)
    <wave-linear-body>)
  
  <tests>
  
  (test)

Since the "concise" solution uses reorder in two places, decrypt and wave, the two functions must change if we wish to achieve performance linear in the given string.

4.1 Linear Decrypting

Avoiding the first use of reorder is an obvious exercise for a Scheme programmer who accepts the occasional need for imperative programming:

<decrypt-linear> ::=

  ; String Nat -> String
  ; decrypt str, which was created via waves of height h
  (define (decrypt str h)
    (define LL (string-length str))
    (define wv (list->vector (wave (range 0 LL) h)))
    (define rs (make-string LL))
    (for ((i wv) (c str)) (string-set! rs i c))
    rs)

This variant of decrypt sets up a result string, rs, and uses the sine-wave of indices to assign the corresponding character from the given string into the appropriate slot of rs. Assuming wave can be turned into a linear function, every step in decrypt’s computation is now linear.

4.2 Linear Waves

The transformation of decrypt into a linear algorithm is based on the insight that Scheme programs can mutate the resulting string in fixed places. Of course, this insight also applies to wave. This time, though, it is impossible to know how long the resulting list is, but it is clear that there are i "lines" and the items of these lines can be collected with a linear and parallel sweep along the "down-and-up wave" and the given list.

<wave-linear-body> ::=

  (define vc (make-vector i '()))
  (define is
    (in-list (shared ((x (append (range 0 i) (range (- i 1) 1) x))) x)))
  (for ((i is) (x sox)) (vector-set! vc i (cons x (vector-ref vc i))))
  (apply append (map reverse (vector->list vc)))

The rest of wave’s computation collects these lists – after reversing them – and then appends them all.

With this transformation wave is linear in the size of the sequence, even though the last line appears to run a loop (reverse) within a loop (map). Fortunately, the outer map loop iterates only over as i lists, while reverse approximately iterates over one ith of the length of sox. In sum, the apparently nested loops iterate over each item in sox once.

4.3 Tests

<tests> ::=

  (check-expect (wave (list 1 2 3 4 5 6) 3)
                (list 1 5 2 4 6 3))
  (check-expect (wave (list 0 1 2 3 4 5 6 7 8 9) 6)
                (list 0 1 9 2 8 3 7 4 6 5))
  (check-expect (wave '(a b c) 3) '(a b c))
  (check-expect (wave '(a b c d) 3) '(a b d c))
  (check-expect (wave '(a b c d e) 3) '(a e b d c))
  (check-expect (wave '(a b c d e f) 3) '(a e b d f c))
  (check-expect (encrypt "diesisteinklartext" 6) "dkinleiasertittxse")
  (check-expect (decrypt  "dkinleiasertittxse" 6) "diesisteinklartext")

5 For the Impatient Reader

  #lang "scheme"

<crypt-impatient> ::=

  (require scheme test-engine/scheme-tests "range.ss")
  
  ; String Nat -> String
  ; encrypt str via waves of height h
  (define (encrypt str h)
    (list->string (wave str h)))
  
  ; String Nat -> String
  ; decrypt str, which was created via waves of height h
  (define (decrypt str h)
    (define LL (string-length str))
    (define wv (list->vector (wave (range 0 LL) h)))
    (define rs (make-string LL))
    (for ((i wv) (c str)) (string-set! rs i c))
    rs)
  
  ; [Sequence X] Nat -> [Listof X]
  ; rearrange items of sox via intermediate waves of height h
  (define (wave sox i)
    (define vc (make-vector i '()))
    (define is
      (in-list (shared ((x (append (range 0 i) (range (- i 1) 1) x))) x)))
    (for ((i is) (x sox)) (vector-set! vc i (cons x (vector-ref vc i))))
    (apply append (map reverse (vector->list vc))))
  
  ;  test baby test
  (define text "dies ist ein klar text")
  (define dpth (+ 2 (random 5)))
  (check-expect (decrypt (encrypt text dpth) dpth) text)
  (test)