CS 30 Homework 2

1. Read The Little Schemer Chapters 4-6.

2. Play around with the sentence generating program from class on Thursday. This code implements the Recursive Transition Networks discussed in the GEB handout (pages 131-133). Calling (sentence) generates a random sentence consisting of a fancy noun followed by a verb followed by a simple noun. For example:
   
   

   (sentence) => (((the cow) that ((the milk)) saw) drank bagels)
   

   It would be nice to get rid of all of the extra parentheses in the generated sentence. For example:

   (sentence) => (the cow that the milk saw drank bagels)
   

   To do this, we need a function called flatten that takes an arbitrarily-nested list of symbols and returns a simple "flat" list containing all of the symbols, without any extra parentheses. Assuming we had such a function, we could rewrite sentence as follows:
   

   (define sentence
     (lambda ()
       (flatten (list (fancy-noun) (verb) (noun)))))
   

   Your job is to write the function flatten.
   
   Hints: an arbitrarily-nested list of symbols always has one of the following general forms:
   • ()
   • (symbol ...rest of list...)
   • ((sublist ...) ...rest of list...)

   In other words, either the list is empty, or its car is a symbol, or its car is another arbitrarily-nested list. The built-in Scheme function symbol? can be used to test if something is a symbol. Don't hesitate to define other helping functions if you need them.

Turning in your homework