Recursive Operations

Brian Harvey University of California, Berkeley MIT Press web page for Computer Science Logo Style

So far, the recursive procedures we've seen have all been commands, not operations.  Remember that an operation is a procedure that has an output rather than an effect.  In other words, an operation computes some value that is then used as the input to some other procedure.  In the instruction

  println first "hello

println is a command, because it does something: It prints its input (whatever that may be) on the screen.  But first is an operation, because it computes something: With the word hello as input, it computes the letter h, which is the first letter of the input.

A Simple Substitution Cipher

I'm going to write a program to produce secret messages.  The program will take an ordinary English sentence (in the form of a Logo list) and change each letter into some other letter.  For example, we can decide to replace the letter E with the letter J every time it occurs in the message.  The program will need two inputs: the message and the correspondence between letters.  The latter will take the form of a word of 26 letters, representing the coded versions of the 26 letters in alphabetical order.  For example, the word

qwertyuiopasdfghjklzxcvbnm

indicates that the letter A in the original text will be represented by Q in the secret version, B will be represented by W, and so on.

In order to encipher a sentence, we must go through it word by word.  (Strictly speaking, what we're doing is called a cipher rather than a code because the latter is a system that substitutes something for an entire word at a time, like a foreign language, whereas we're substituting for a single letter at a time, like the Elvish alphabet in The Lord of the Rings.)  In order to encipher a word we must go through it letter by letter.  So I'll begin by writing a procedure to translate a single letter to its coded form.

  to codematch :letter :clear :code
    if empty? :clear [output :letter]        ; punctuation character
    if equal? :letter first :clear [output first :code]
    output codematch :letter butfirst :clear butfirst :code
    end

  to codelet :letter :code
    output codematch :letter "abcdefghijklmnopqrstuvwxyz :code
    end

Codelet is an operation that takes two inputs.  The first input must be a single-letter word, and the second must be a code, that is, a word with the 26 letters of the alphabet rearranged.  The output from codelet is the enciphered version of the input letter.  (If the first input is a character other than a letter, such as a punctuation mark, then the output is the same as that input.)

Codelet itself is a very simple procedure.  It simply passes its two inputs on to a subprocedure, codematch, along with another input that is the alphabet in normal order.  The idea is that codematch will compare the input letter to each of the letters in the regular alphabet; when it finds a match, it will output the letter in the corresponding position in the scrambled alphabet.  Be sure you understand the use of the output command in codelet; it says that whatever codematch outputs should become the output from codelet as well.

The job of codematch is to go through the alphabet, letter by letter, looking for the particular letter we're trying to encode.  The primary tool that Logo provides for looking at a single letter in a word is first.  So codematch uses first to compare its input letter with the first letter of the input alphabet:

  if equal? :letter first :clear ...

If the first input to codematch is the letter A, then equal? will output true and codematch will output the first letter of :code (Q in the example I gave earlier).  But suppose the first input isn't an A.  Then codematch has to solve a smaller subproblem: Find the input letter in the remaining 25 letters of the alphabet.  Finding a smaller, similar subproblem means that we can use a recursive solution.  Codematch invokes itself, but for its second and third inputs it uses the butfirsts of the original inputs because the first letter of the alphabet (A) and its corresponding coded letter (Q) have already been rejected.

Here is a trace of an example of codematch at work, to help you understand what's going on.

Entering codematch "e "abcdefghijklmnopqrstuvwxyz "qwertyuiopasdfghjklzxcvbnm
 Entering codematch "e "bcdefghijklmnopqrstuvwxyz "wertyuiopasdfghjklzxcvbnm
  Entering codematch "e "cdefghijklmnopqrstuvwxyz "ertyuiopasdfghjklzxcvbnm
   Entering codematch "e "defghijklmnopqrstuvwxyz "rtyuiopasdfghjklzxcvbnm
    Entering codematch "e "efghijklmnopqrstuvwxyz "tyuiopasdfghjklzxcvbnm
    Exiting codematch, output: "t
   Exiting codematch, output: "t
  Exiting codematch, output: "t
 Exiting codematch, output: "t
Exiting codematch, output: "t

The fifth, innermost invocation of codematch succeeds at matching its first input (the letter E) with the first letter of its second input.  That invocation therefore outputs the first letter of its third input, the letter T.  Each of the higher-level invocations outputs the same thing in turn.

The pattern of doing something to the first of an input, then invoking the same procedure recursively with the butfirst as the new input, is a familiar one from recursive commands.  If we only wanted to translate single letters, we could have written codelet and codematch as commands, like this:

  to codematch :letter :clear :code               ;; command version
    if empty? :clear [println :letter stop]
    if equal? :letter first :clear [println first :code stop]
    codematch :letter butfirst :clear butfirst :code
    end

  to codelet :letter :code                        ;; command version
    codematch :letter "abcdefghijklmnopqrstuvwxyz :code
    end

You may find this version a little easier to understand, because it's more like the recursive commands we've examined in the past.  But making codelet an operation is a much stronger technique.  Instead of being required to print the computed code letter, we can make that letter part of a larger computation.  In fact, we have to do that in order to encipher a complete word.  Each word is made up of letters, and the task of codeword will be to go through a word, letter by letter, using each letter as input to codelet.  The letters output by codelet must be combined into a new word, which will be the output from codeword.

Recall the structure of a previous procedure that went through a word letter by letter:

  to printPiecePerLine :word
    if empty? :word [stop]
    println first :word
    printPiecePerLine butfirst :word
    end

Compare this to the structure of the recursive codeword:

  to codeword :word :code
    if empty? :word [output "]
    output word (codelet first :word :code) (codeword butfirst :word :code)
    end

There are many similarities. Both procedures have a stop rule that tests for an empty input.  Both do something to the first of the input (either println or codelet), and each invokes itself recursively on the butfirst of the input.  (Codeword has an extra input for the code letters, but that doesn't really change the structure of the procedure.  If that's confusing to you, you could temporarily pretend that code is a global variable and eliminate it as an input.)

The differences have to do with the fact that codeword is an operation instead of a command.  The stop rule invokes output rather than stop and must therefore specify what is to be output when the stop condition is met.  (In this case, when the input word is empty, the output is also the empty word.)  But the main thing is that the action step (the println in printPiecePerLine) and the recursive call (the printPiecePerLine instruction) are not two separate instructions in codeword.  Instead they are expressions (the two in parenthesis) that are combined by word to form the complete output.  Here's a picture:

Remember what you learned in Chapter 2 about the way in which Logo instructions are evaluated.  Consider the output instruction in codeword.  Before output can be invoked, Logo must evaluate its input.  That input comes from the output from word.  Before word can be invoked, Logo must evaluate its inputs.  There are two of them.  The first input to word is the expression

codelet first :word :code

This expression computes the coded version of the first letter of the word we want to translate.  The second input to word is the expression

codeword butfirst :word :code

This expression invokes codeword recursively, solving the smaller subproblem of translating a smaller word, one with the first letter removed.  When both of these computations are complete, word can combine the results to form the translation of the complete input word.  Then output can output that result.

Here's an example of how codeword is used.

? println codeword "hello "qwertyuiopasdfghjklzxcvbnm
itssg

Notice that we have to say println, not just start the instruction line with codeword; a complete instruction must have a command.  Suppose you had the idea of saving all that typing by changing the output instruction in codeword to a println.  What would happen?  The answer is that codeword wouldn't be able to invoke itself recursively as an operation.  (If you don't understand that, try it!)  Also, it's generally a better idea to write an operation when you have to compute some result.  That way, you aren't committed to printing the result; you can use it as part of a larger computation.

For example, right now I'd like to write a procedure code that translates an entire sentence into code.  Like codeword, it will be an operation with two inputs, the second of which is a code (a word of 26 scrambled letters).  The difference is that the first input will be a sentence instead of a word and the output will also be a sentence.

Just as codeword works by splitting up the word into letters, code will work by splitting up a sentence into words.  The structure will be very similar.  Here it is:

  to code :sent :code
    if empty? :sent [output []]
    output sentence (codeword first :sent :code) (code butfirst :sent :code)
    end

The main differences are that code outputs the empty sentence, instead of the empty word, for an empty input and that sentence is used as the combining operation instead of word.  Here's an example of code at work.

? println code [meet at midnight, under the dock.] "qwertyuiopasdfghjklzxcvbnm
dttz qz dorfouiz, xfrtk zit rgea.