Tutorial 5                   CSC324--F02                   Eric Joanis

This week is Thanksgiving, so there is no tutorial.  These notes cover
material that we would have seen in tutorial this week, and which can be
useful for the project.  Some of this material will be reviewed in class
or in tutorial next week, as necessary.

apply/eval/regular procedure call

   We've seen regular procedure calls in class.  Now, what if I want to
   call + on a list of numbers?

   We can use eval:
      (define lst '(1 2 3 4))
      (eval (cons + lst) ()) => 10
   (cons + lst) constructs the expression (+ 1 2 3 4), and then eval
   evaluates it.

   Alternatively, we can use the higher-order procedure apply (see Dybvig
   p. 85), which is built in to Scheme.  apply takes two arguments, a
   procedure and a list, and applies the procedure with the elements of
   the list as its arguments.  For example:
      (apply + '(1 2 3 4)) => 10
   So if you need to apply a procedure and you already have the arguments
   in a list, instead of reconstructing the correct expression and use
   eval, you can call apply and it will do the work for you.

   I called apply a higher-order procedure above because it takes a
   procedure as one of its arguments, and applies it in some way.  map is
   another higher-order procedure we saw in class.

   To summarize.  Normal procedure application:
      (+ 1 2 3 4)          - use this under most circumstances
      (apply + '(1 2 3 4)) - use this if the arguments are already in a list
      (eval (cons + '(1 2 3 4)) ()) - use this only if you need to make a
                             more complicated construct, e.g., when you
                             need to dynamically build an expression based
                             on some input from the user, and then
                             evaluate it, as in the project.

map

   We saw map in class.  For a couple more examples, have a look at the
   solutions to PS2, and read Dybvig p. 92 (section 5.5).  We'll talk
   about map and higher-order procedures more in next week's tutorial.
   When you get comfortable using map, you will find that you can write
   more elegant and concise code.

   Another example:  We can rewrite deep-properlist? using map:
      (define deep-properlist?
         (lambda (lst)
            (cond ((pair? lst) (and (list? lst)
                                    (applyand (map deep-properlist? lst))))
                  (else #t))))

      ; (applyand lst) returns true iff all the elements of lst are true
      ; Pre: lst is a list
      (define applyand
         (lambda (lst)
            (eval (cons 'and lst) ())))

   Try to answer these questions about this code:
    - Why did I write a helper procedure applyand instead of simply using
      apply and passing it "and", as we did with + above?
    - Why does it work?
      To help answer this one, by hand or using (trace deep-properlist?)
      and (trace applyand), trace these calls:
      (deep-properlist? '(1 2))
      (deep-properlist? '(1 . 2))
      (deep-properlist? '(1 2 (3 4) (5 (6 . 7) 8)))
      (deep-properlist? '(1 2 (3 4) (5 (6 7) 8)))

let/let*/letrec

   The syntactic forms let, let*, and letrec all allow you to define
   variables that will be visible in the body of the let expression.

   Syntax:
      (let ((var1 value1)
            (var2 value2)
            ...
           )
         body  ; body can make use of var1, var2, ...
      )


   For example:
      (let ((x 5) (y 7)) (+ x y)) => 12

   A more interesting example:  say you want to write f(x) + (f(x))^2 in
   Scheme.  We don't want to call f three times, so
      (+ (f x) (* (f x) (f x)))
   is not a good idea.  Instead, we can use:
      (let ((fx (f x))) (+ fx (* fx fx)))

   Have a look at the second solution to deep-swap-first-third on Problem
   Set 2 for another practical use of let.

   When let is evaluated, value1, value2, ... are evaluated first, and
   then the results are mapped to var1, var2, etc.  This means that the
   values can't depend on the vars.  If you need to use the vars in the
   values, use let* or letrec.

 - With let*, the values are evaluated in order, and one value can access
   the vars that were defined beforehand.  Use let* if you have
   dependencies between your variables, or if the values must be evaluated
   in order.

   For example:
      (let* ((x 5) (y (+ x 7)) (z (* x y)))
         (list x y z)
      )
   returns:
      (5 12 60)
   whereas if you try this with let instead of let*, you get the error
   message "Unbound variable: y", since y doesn't exist when you are
   evaluating (* x y) (and neither does x).

 - With letrec, circular dependencies are allowed, so that you can define
   recursive (and mutually recursive) procedures.

   Example: A very inefficient way to write a predicate (odd? x) is to use
   mutually recursive odd? and even? predicates.  This can all be embedded
   in a letrec:
      ; (odd? x) returns true of x is odd
      ; Pre: x >= 0 is an integer.
      (define odd?
         (lambda (x)
            (letrec ((odd (lambda (x) (if (= x 1) #t (not (even (- x 1))))))
                     (even (lambda (x) (if (= x 0) #t (not (odd (- x 1)))))))
               (odd x))))

   Example: the helper procedure to fast-fib can be hidden using letrec.

   We saw this code for fast-fib last week--we used with an accumulator to
   make the code more efficient.

      ; (fast-fib p1 p2 i n) returns the nth Fibonacci number
      ; Pre:  n>=0 is an integer, 0<=i<=n is an integer, p1 is the (i-1)th
      ; Fibonnaci number (or 0 if i is 0), and p2 is the ith Fib number.
      (define fast-fib
         (lambda (p1 p2 i n)
            (if (= i n)
                p2
                (fast-fib p2 (+ p1 p2) (+ i 1) n))))

      ; (fib n) returns the nth Fibonacci number
      ; Pre: n is a non-negative integer
      (define fib
         (lambda (n)
            (fast-fib 0 1 0 n)))

   The disadvantage of the above solution is that the helper procedure is
   visible to anyone else, and we have to come up with a name that won't
   conflict with helpers to other procedures.

   We can rewrite the above two procedures in a single procedure using
   letrec to define the helper procedure.  This way, we don't have an
   extra procedure name defined that won't be used for anything else, and
   we don't clutter the namespace.

      ; (fib n) returns the nth Fibonacci number
      ; Pre: n is a non-negative integer
      (define fib
         (lambda (n)
            (letrec ((helper (lambda (p1 p2 i n)
                                  (if (= i n)
                                      p2
                                      (helper p2 (+ p1 p2) (+ i 1) n)))))
               (helper 0 1 0 n))
         )
      )