[3/17/99]

===============================================================================
SKIP THIS (only mention that it is here).

* Take these definitions of nth-deriv (by now you should be able to know that
  they all work properly):

  --------------------
    (define (nth-deriv f n)
      (lambda (x)
        (if (= n 0)
          (f x)
          ((nth-deriv (deriv f) (- n 1)) x))))

    (define (nth-deriv f n)
      (if (= n 0)
        f
        (lambda (x)
          ((nth-deriv (deriv f) (- n 1)) x))))

    (define (nth-deriv f n)
      (if (= n 0)
        f
        (deriv (nth-deriv f (- n 1)))))

    (define (nth-deriv f n)
      (if (= n 0)
        f
        (nth-deriv (deriv f) (- n 1))))
  --------------------

  What are the differences between them?
    1 & 2 - very similar, 1 is doing a little less when applied - the first if
            is evaluated in the output function.
    3 & 4 - are also very similar - 4 is the tail-recursive version of 3
    A big difference is that 1/2 are deferring the computation of the
    nth-derivative but 3/4 construct the whole thing immediately.
  This is the same difference between the two repeated versions that we saw
  last time:

  --------------------
    (define identity (lambda (x) x))
    (define (repeated1 f n)
      (if (zero? n)
        identity
        (lambda (x) ((repeated f (- n 1)) (f n)))))
    (define (repeated2 f n)
      (letrec ((iter (lambda (n f-acc)
                       (if (zero? n)
                         f-acc
                         (iter (- n 1) (lambda (x) (f (f-acc x)))))))
        (iter n identity))))
  --------------------

  Define:

  --------------------
    (define inc (lambda (x) (+ x 1)))
    (define inc3a (repeated1 inc 3))
    (define inc3b (repeated2 inc 3))
  --------------------

  Compare the evaluation of:

  --------------------
    (inc3a 10)
  --------------------

  and

  --------------------
    (inc3b 10)
  --------------------

   You should now know why (repeated2 inc 1000) is better than the same using
   repeated1.

===============================================================================
SKIP THIS (only mention that it is here).

* Note on proving correctness:

  Proving the correctness of a recursive function is a little more complicated.
  The point in these proofs is to find a fact that is always true, an
  _invariant_, then show that:

  1. This _is_ the case - this is usually by induction, show that it holds
     initially, then, if it holds in one step, it'll also hold in the next (or
     use strong induction).

  2. Then show that if this is true, then the program _is_ correct.

  Example - proving:

  --------------------
    (define fact
      (lambda (n)
        (if (zero? n)
          1
          (* n (fact (- n 1))))))
  --------------------

  here the invariant is "(fact n) = 1 * 2 * ... * n for any natural n", it is
  easily shown that it always hold (using induction), and, it also implies the
  correctness of fact.

  A tail-recursive different example:

  --------------------
    (define (fact n)
      (letrec ((iter (lambda (m acc)
                       (if (zero? m)
                         acc
                         (iter (- m 1) (* m acc))))))
        (iter n 1)))
  --------------------

  here the invariant that we use is "(iter m acc) = 1 * 2 * ... * m * acc", it
  is again proved by induction, and it also implies the correctness of fact.
  BTW, if we consider iter as a C loop, then our invariant can be a variation
  of the above, like "whenever we're at the start of the iter loop, acc = m+1 *
  m+2 * ... * n" (and in the beginning, we have a product of zero arguments
  that is defined to be one).  These two statements are actually equivalent.

===============================================================================

* defstruct example - just go over this with explanations:

  ;;; The toplevel structure, useful for adding information that appears on all
  ;;; components, such as name, serial number, etc.
  (defstruct <component>)

  ;;; Define a generic function object with one input.
  ;;; Note that this does nothing with the types!
  (defgeneric (compute-output (c <component>)))

  ;;; A subclass that has a constant boolean output.
  (defstruct (<signal> <component>)
    (value <boolean>))

  ;;; The value of a signal component is its constant value.
  (defmethod (compute-output (s <signal>))
    (get-signal-value s))

  ;;; Another object - a wire object.
  (defstruct (<wire> <component>)
    (input <component>))

  ;;; Its output is simply the output of its input.
  (defmethod (compute-output (w <wire>))
    (compute-output (get-wire-input w)))

  ;;; Now another gate - an and gate.
  (defstruct (<and-gate> <component>)
    (input1 <component>)
    (input2 <component>))

  ;;; And the way that we get its output...
  (defmethod (compute-output (a <and-gate>))
    (and (compute-output (get-and-gate-input1 a))
         (compute-output (get-and-gate-input2 a))))

  ;;; Test that this is all working:
  (compute-output
   (make-and-gate (make-signal #t)
                  (make-wire (make-signal #t))))
  (compute-output
   (make-and-gate (make-signal #t)
                  (make-wire (make-signal #f))))

  ;;; Now, instead of implementing an or-gate, we can simply generalize:
  (defstruct (<op-gate> <component>)
    (op <procedure>))

  (defstruct (<binary-gate> <op-gate>)
    (input1 <component>)
    (input2 <component>))
  (defmethod (compute-output (b <binary-gate>))
    ((get-op-gate-op b) (compute-output (get-binary-gate-input1 b))
                        (compute-output (get-binary-gate-input2 b))))

  ;;; This is the way we make an and gate - note that "and" is not a function.
  (define (make-and-gate x y)
    (make-binary-gate (lambda (x y) (and x y)) x y))
  ;;; An or gate is similar.
  (define (make-or-gate x y)
    (make-binary-gate (lambda (x y) (or x y)) x y))

  ;;; And now a unary gate:
  (defstruct (<unary-gate> <op-gate>)
    (input <component>))
  (defmethod (compute-output (u <unary-gate>))
    ((get-op-gate-op u) (compute-output (get-unary-gate-input u))))

  ;;; A not gate ("not" is a function).
  (define (make-not-gate x)
    (make-unary-gate not x))

  ;;; And now we can test a composed implication circuit:
  (define (make-implies-gate x y)
    (make-or-gate (make-not-gate x) y))
  (define (test-imp b1 b2)
    (compute-output (make-implies-gate (make-signal b1) (make-signal b2))))
  (test-imp #t #f)
  (test-imp #f #t)

===============================================================================