LEARNING LISP

Contents | Maps | FEXPRS: Unevaluating Functions

Isplay Ogrammingpray

You now have all the tools needed to solve some reasonably large problems in Lisp. [You've actually had most of them for a while.] This chapter demonstrates the steps that can be taken to solve such problems. These steps are, of course, dependent upon the exact problem specified, but there are some general rules which we will emphasize.

The problems we will attack are those of a pig Latin translator. The system [a collection of functions and help functions all intented to solve one problem] will take a sentence in English and return the sentence in pig Latin. It will do this:

:(PIGLATIN '(TAKE OUT THE TRASH)))

  (AKETAY OUTWAY ETHAY ASHTRAY )
The first step in designing a system is: Take out a piece of paper and a pen or pencil.

You will need paper to keep notes [and doodle while you think]. If the system will have many functions in it you're definitely going to need a scorecard to keep track of the functions and their arguments. Because of the environment nature of Lisp, it's not easy to comment the functions so notes are important!

Next, define the problem and lay out exact specifications.

In this case, the specifications are fairly easy. The user will enter his sentence as a list of words, and the program will return the sentence with each word "pigized".

The next step is to decide on an algorithm.

The standard pig Latin algorithm works in the following manner.

Look at each word in the sentence. If its first letter is a vowel, simply add "way" to it. Otherwise, remove all the letters from the beginning of the word, and up to the first vowel. Put them after the word. Then add "ay".

There are a few assumptions in this description. It is very important to specify your assumptions so that you know which cases you won't have to deal with. A well-defined set of assumptions can make a programming task quite a bit simpler.

We have assumed that all words have vowels in them. We will ignore the case of "words" (actually syllables) with no vowels. Also, we assume that only vowels can be one-letter words ("a", "I"). By examining some sample cases, we can fill in blanks in the algorithms.

WATER --> ATERWAY
WEEPS --> EEPSWAY

Thus, "W" is not a vowel.

YELLOW --> YELLOWAY
YAKS --> YAKSWAY

So "Y" is a vowel. Obviously, "A", "E", "I", "O", and "U" are vowels also.

We've now specified the problem. How do we go about programming it? The most useful technique to learn is called top down programming. It means that the main programs are written before the help functions. By using the top down style we can organize our thoughts. Let's start at the very beginning. The first part of the algorithm says: "Look at each word in the sentence." Because our sentence is a list, the words are the atoms in that list. Looking at each word is similar to the MAPCAR operator. Let's define our main function to use MAPCAR and cause each word in the sentence to be processed.

:(DEFINE (PIGLATIN (LAMBDA (SENTENCE)

:  (MAPCAR 'PIGWORD SENTENCE)))))

  PIGLATIN
This is the main function. There are two important factors to note in the definition of this function. The first is its name [and the name of the help function it calls] have meaning. We could have called this function "xyzzy" but then we would never be able to remember what it did!

The second point is more subtle. The main function and all the functions that we'll write are very short. We took a single idea [mapping down the sentence] and turned it into a function. The help function [PIGWORD] will also implement one little part of the whole. By slowly adding parts of the algorithm, we can build the entire system in very small, easily manageable increments. There are many advantages to this, not the least of which is that simpler and smaller functions are easier to edit or retype.

Let's get on to the first help function: the processing of each word. The PIGWORD function will take a word and turn it into pig Latin. The I/O [Input/Output] behavior of this function should be

:(PIGWORD 'THIS)

  ISTHAY
There's a problem here. We have functions that modify lists but not functions for modifying the letters in an atom. The solution is to make the atom a list and then turn the processed list back into an atom:
THIS -> (T H I S) -> (I S T H A Y) -> ISTHAY

Of course, Lisp conveniently provides functions for doing this. EXPLODE turns an atom into a list of its letters, and IMPLODE does the opposite.

Here we have a new concept not specified in the algorithm, but implicit in the nature of Lisp. We need to have some intermediate processing step that does this explosion, and subsequent implosion. We will define PIGWORD as follows:

:(DEFINE (PIGWORD (LAMBDA (WORD)

:    (IMPLODE (PIGLISTEDWORD (EXPLODE WORD)))

:    )))

  PIGWORD
PIGLATIN calls PIGWORD via MAPCAR and passes it to each word. PIGWORD, in turn, explodes the word and processes it using another help function [with a meaningful name] called PIGLISTEDWORD. PIGLISTEDWORD will return the list of the "pigized" word, and PIGWORD will implode it to an atom again and return the new word to PIGLATIN.

All that remains now is write PIGLISTEDWORD. Which part of the problem does this one implement? Here is the definition.

:(DEFINE (PIGLISTEDWORD (LAMBDA (WORD)

:  (COND

:    ((ISAVOWEL (CAR WORD)) (PIGVOWEL WORD))

:    (T (PIGNOVOWEL WORD))))))

  PIGLISTEDWORD
Several things are still missing from the system. PIGVOWEL will translate a word that starts with a vowel into its pig Latin equivalent. PIGNOVOWEL will translate all other words, and the predicate ISAVOWEL will tell us whether the letter it received is a vowel or not.

Let's write the simple ones first:

:(DEFINE (ISAVOWEL (LAMBDA (LETTER)

:   (MEMBER LETTER '(A E I O U Y))))

:)

  ISAVOWEL

:(DEFINE (PIGVOWEL (LAMBDA (WORD)

:   (CONC WORD '(W A Y))))))

  PIGVOWEL

:(PIGVOWEL '(A F T E R))))

  (A F T E R W A Y )
We should now be able to test the simple part of the system--sentences where all the words begin with a vowel.
:(PIGLATIN '(ALERT AIRMEN ARE ONTIME))

  (ALERTWAY AIRMENWAY AREWAY ONTIMEWAY )
[What would happen if we tried to "pigize" a sentence with words that began with consonants? Try it.]

Great! Most of our system finished in only 5 functions. All we have to do now is write the hard one. PIGNOVOWEL. Let's describe the responsibility of that function in detail.

Since we can only deal with one letter of the exploded word at a time, we have to search for the first vowel [ISAVOWEL will be useful here]. When we find the vowel, we will attach the first letters [which we will have been collecting up along the way] to the end of the word and tack on an "ay".

How can we recur down a list and keep the information as we go? The answer is to pass the list of collected letters along with the recursion, and just tack on letters along the way. This is the function. Follow it by hand, and see what it does.

:(DEFINE (PIGNOVOWEL (LAMBDA (WORD LETS)

:  (COND

:    ((ISAVOWEL (CAR WORD))

:       (CONC WORD (CONC LETS '(A Y))))

:    (T (PIGNOVOWEL (CDR WORD) (APPEND LETS (CAR WORD))))))))

  PIGNOVOWEL
Note that there are two arguments to this function. We will always have to supply both of them, or this function will not work. O.K., let's try it out:
:(PIGNOVOWEL '(T H I S) ())

  (ISTHAY)
That looks good, we should now be able to try the whole system:
:(PIGLATIN '(EVERY GOOD BOY DOES FINE))

  ** ERROR: TOO FEW ARGS **
  PIGNOVOWEL :: (WORD)

+()

  NIL
Oops! Something went wrong. The error message said we called PIGNOVOWEL with one argument instead of two. The call was from PIGLISTEDWORD. We hadn't forseen that we'd need two arguments in PIGNOVOWEL when we wrote PIGLISTEDWORD. Oh well, we can now go and edit it or retype it.
:(DEFINE (PIGLISTEDWORD (LAMBDA (WORD)

:  (COND

:    ((ISAVOWEL (CAR WORD)) (PIGNOVOWEL WORD))

:    (T (PIGNOVOWEL WORD NIL))))))

  PIGLISTEDWORD


:(PIGLATIN '(STICKS AND STONES ARE PAINFUL))

  (ICKSTAY ANDWAY ONESSTAY AREWAY AINFULPAY)
Looks good!

We've now completed the design of our pig Latin system to specification. You should SAVE it so that you can recover it later.

The lessons of this chapter are summarized in the following list:

Designing a system in Lisp or any other programming language, is like designing in general. You take it step by step and fill in the unknowns when you come across them. Always have the final goal in mind.

Exercises to Translate Into Thoughts

  1. Explain how a function that sorts words in a list would work. Think about each function and describe the entire system in English.
  2. Practice taking a paper and pencil [or pen] out before starting to write things into Lisp. Do this until it becomes automatic.
  3. There is a simplification that can be made in our Pig Latin system. It is possible to do it without a function because its action is performed by a special use of another function. What are we talking about? Fix the system accordingly. Think about the advantages and, especially, the disadvantages of doing things this way.
  4. How is top down programming like recursive tree traversal? Design a Lisp system [in English but with possible real help functions] that would take a problem specification. Write the program using top down tree traversal.
  5. Adjust the pig Latin translator to work with words such as, "nth", "cwm" and "crwth".

Answers

  1. PIGVOWEL is a special case of PIGNOVOWEL. We can redefine PIGLISTEDWORD as
    (DEFINE (PIGLISTEDWORD (LAMBDA (WORD)
      (COND
       ((ISAVOWEL (CAR WORD))
          (PIGNOVOWEL WORD '(W)))
       (T (PIGNOVOWEL WORD '()))
      )
    )))
    
  2. Put a termination condition in PIGNOVOWEL to watch for vowelless words.
    (DEFINE (PIGNOVOWEL (LAMBDA (WORD LETS)
      (COND
        ((NULL WORD) (CONC LETS '(A Y)))
        ((ISAVOWEL (CAR WORD))
          (CONC WORD (CONC LETS '(A Y))) )
        (T (PIGNOVOWEL (CDR WORD)
          (APPEND (LETS (CAR WORD))) )
      )
    )))
    

Contents | Maps | FEXPRS: Unevaluating Functions