Problem Set Seven, CS 257

Write quickly and you will never write well; write well, and you will soon write quickly.

Clearness is the first essential, then brevity, and vigor.

Correct repeatedly and stoically.

Erasure is as important as writing.

Prune what is turgid, elevate what is commonplace, arrange what is disorderly, introduce rhythm where the language is harsh, modify where it is too absolute.

The best method of correction is to put aside for a time what we have written, so that when we come to it again it may have an aspect of novelty, as of being another man's work; in this way we may preserve ourselves from regarding our writings with the affection that we lavish upon a newborn child.

Marcus Fabius Quintilianus
Roman Poet, Circa 65 AD

1. Define my-append which is just like the system's append except that it only takes exactly two arguments. Your definition should be tail-recursive. (Hint: calling reverse once might be helpful.)

2. Define reverse-noah tail recursively. It behaves like this:

   (reverse-noah '(a b c d) '(1 2 3 4))    ; ((d 4) (c 3) (b 2) (a 1))
   

3. Define the Scheme-code-manipulation function tail-rec which takes an s-expression of a lambda form, and also a symbol, and check that the given symbol is used as a variable only in a tail-recursive fashion in the given chunk of code. Your code does not have to handle general scheme, only function calls, constants, and if. Here are some examples.

   (tail-rec '(lambda (what ever) (if (joe) (foo (bar)) (foo (sam)))) 'foo)
   ; returns #t
   (tail-rec '(lambda (what ever) (if (joe) (bar (bar 0)) (sam (sam 0)))) 'foo)
   ; returns #t
   (tail-rec '(lambda (what ever) (if (joe) (bar (foo 0)) (sam (sam 0)))) 'foo)
   ; returns #f
   (tail-rec '(lambda (what ever) (if (foo 0) (foo (bar 0)) (sam (sam 0)))) 'foo)
   ; returns #f
   

   Hint: this is not as hard as it might seem. Think about how you do it yourself, and break the problem down. Use a sensible helper function or two, for things like checking for the occurance of any call within a chunk of code where any call cannot be a tail-recursive one.

4. Use the mechanical process discussed in class to convert the following side-effecty pseudocode into tail-recursive Scheme code.

   function foo(x, y)
      a = x;
      b = y;
      c = '();
      d = 0;
    g1:
      if (null?(a)) {
        return list(d, c);
      }
      if (number?(car(a))) {
        c = cons(car(b), c);
        d = car(a) + d;
      }
      a = cdr(a);
      b = cdr(b);
      goto g1;
   end
   

5. For extra credit, define flatten as efficiently and tail-recursively as you can. (Note that the definition given in the solution to an earlier problem set is somewhat inefficient, as it calls append repeatedly in such a way that the total amount of work done can, in the worst case, grow quadratically in the size of the s-expression being flattened.)