[2/24/99]

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

* Finish - Evaluation:

  To evaluate a Scheme expression you should simply follow these rules.  Note
  that they do not contradict the rules given earlier, they only make life
  easier by doing only the "obvious" things.

  The evaluation rules are divided for every possible Scheme expression.  We
  use the meta variables e1, e2, ... to denote expressions, v1, v2, ... to
  denote values and x1, x2, ... to denote symbols.  Note that vi's are values
  and there is no need for further evaluation, while ei's are expressions that
  should be evaluated.

  [*] EVAL_prim rule:
    Primitive value expressions have their obvious values.  To evaluate such an
    expression, you simply take its value.  These includes:
    - Numbers and strings.
    - Primitive operators and functions such as +, - and sin having function
      values that are given as built-ins (this means that primitive functions
      aren't actually symbols).
    - Lambda expressions are also values.

  [*] EVAL_var rule:
    Symbols denote variables.  To evaluate an expression x which is a symbol,
    you return this symbol's value which should be avalue that you *know* by
    the EVAL_define rule below.  Note that this does _not_ involve further
    evaluation.

  [*] EVAL rule:
    To evaluate a compound form (e1 e2 ... en), which is not a special form
    (see below), you evaluate each of its subexpressions recursively, getting
    the list (v1 v2 ... vn).  Then continue with one of the APPLY rules to
    apply the function v1 on the arguments v2, ..., vn.  Because this rule is
    the default that is used only when it is not one of the special form cases,
    then it's place is actually as the last of the EVAL rules, but it is here
    for clarity.

  These are the two application rules, it might be more appropriate to put them
  after the evaluation rules, but they're here for clarity.

  [*] APPLY_prim rule:
    To apply a primitive function f on arguments v1, ..., vn you simply compute
    the function result.
    Examples:
      (+ 3 4)  -->  7
      (head (cons v1 v2))  -->  v1  ; after _two_ APPLY_prim rules.

  [*] APPLY_lambda rule:
    To apply a lambda expression (lambda (x1 ... xn) e) on some given value
    arguments v1, ..., vn, you evaluate recursively the result of substituting
    every free occurrence of x_i in e by the corresponding v_i value.  See the
    EVAL_internal_def at the bottom to handle internal definitions.
    Examples:
      ((lambda (x y) (+ x y)) 3 4)  -->  (+ 3 4)
      ((lambda (x) (lambda (y) (+ x y))) 3)  -->  (lambda (y) (+ 3 y))

  The rest are special-form rules.  Here we have only a few basic rules, but
  the rest can be added easily.

  [*] EVAL_define rule:
    To evaluate a simple define rule (define x e) where x is a symbol, you
    evaluate e recursively to get a value v, and you mark to yourself that now
    you now *know* that the value of the symbol x is v.  Important: this rule
    can only be applied to top-level expressions.

  [*] EVAL_func_def rule:
    To evaluate a define rule (define (x1 ... xn) e) you continue by evaluating
    the form (define x1 (lambda (x2 ... xn) e)).  Note that this rules (and
    several others below) is a simple rewrite rule.

  [*] EVAL_if rule:
    To evaluate an "if" form (if e1 e2 e3), you evaluate recursively e1 to get
    a value v1.  If v1 is true (not #f) continue by evaluating e2, and if v1 is
    #f, continue by evaluating e3.  An if expression of the form (if e1 e2) is
    evaluated similarly.

  [*] EVAL_let rule:
    This is another rewrite rule:
      (let ((x1 e1) ... (xn en)) e)
    ==>
      ((lambda (x1 ... xn) e) e1 ... en)
    Essentially, what you get is to evaluate e with x_i bound to the result of
    evaluating e_i.  For this reason, it is ok to skip the rewritten form and
    go straight to the APPLY_lambda rule.
    Example:
      instead of writing:
        (let ((x 1) (y 2)) (+ x y))
          -->  ((lambda (x y) (+ x y)) 1 2)
          -->  (+ 1 2)
      you can write:
        (let ((x 1) (y 2)) (+ x y))  -->  (+ 1 2)
      But keep in mind that you should in both these cases evaluate the
      expressions 1 and 2 before you do the substitutions.  Also, note that the
      translation step makes things more verbose but makes it harder to get
      mistakes, for example, it is clear using them, that if you replace the
      "2" in the original expression by "x", then this "x" is a free variable.

  [*] EVAL_let* rule:
    Another rewrite:
      (let* ((x1 e1) (x2 e2) ... (xn en)) e)
    ==>
      (let ((x1 e1)) (let* ((x2 e2) ... (xn en)) e))
    and if there is only one binding then you have this rewrite:
      (let* ((x1 e1)) e)
    ==>
      (let ((x1 e1)) e)
    Again, you can use your intuition here, and bind the variables, keeping in
    mind that you do it ine by one - and you can skip this rewrite and the
    EVAL_let ruels.
    Example:
      instead of writing:
        (let* ((x 1) (y x)) (+ x y))
          -->  (let ((x 1)) (let* ((y x)) (+ x y)))
          -->  ((lambda (x) (let* ((y x)) (+ x y))) 1)
          -->  (let* ((y 1)) (+ 1 y))
          -->  (let ((y 1)) (+ 1 y))
          -->  ((lambda (y) (+ 1 y)) 1)
          -->  (+ 1 1)
      you can write:
        (let* ((x 1) (y x)) (+ x y))
          -->  (let* ((y 1)) (+ 1 y))
          -->  (+ 1 1)
      The same notes as above hold here.

  [*] EVAL_letrec rule:
    This is sort of a rewrite rule - to evaluate:
      (letrec ((x1 e1) ... (xn en)) e)
    you pick fresh variables (unique new symbols) y1, ..., yn, and consistently
    rename any free occurences of x1, ..., xn in e to these symbols, then the
    rewrite of the above expression is to apply the toplevel EVAL_define on
    these expressions:
      (define x1 e1)[yi/xi]
      ...
      (define xn en)[yi/xi]
      e[yi/xi]
    Note that by unique, we mean symbols that are not used anywhere in the
    whole program (even part that we did not evaluate yet).
    We need to rename the variables x1 ... xn in case there's a top-level
    variable already with that name.  Usually, we can ignore the renaming if
    it's not relevant.  For example, to evaluate:
      (letrec ((fact (lambda (x) (if (<= x 1) 1 (* x (fact (- x 1)))))))
        (fact 3))
    there's no variable in our context named fact, so we can just evaluate:
      (define fact (lambda (x) (if (<= x 1) 1 (* x (fact (- x 1))))))
      (fact 3)
    For another program, we might run into trouble:
      (define f (lambda (y) y))
      (letrec ((f (lambda (x) (if (<= x 1) 1 (* x (f (- x 1)))))))
        (f 3))
    Here, we can't just pull the letrec out to the top-level because we already
    have a definition for f.  So we just rename it to g when we pull the new
    definition form:
      (define f (lambda (y) y))
      (letrec ((g (lambda (x) (if (<= x 1) 1 (* x (g (- x 1)))))))
        (g 3))
    (Notice changes in the definition of g as well as the body of the letrec.)
    Then we can evaluate the letrec by pulling the definition out as a define:
      (define f 3)
      (define g (lambda (x) (if (<= x 1) 1 (* x (g (- x 1))))))
      (g 3)

  [*] EVAL_cond rule:
    Rewrite:
      (cond (e11 e12) (e21 e22) ... (en1 en2))
    ==>
      (if e11 e12 (cond (e21 e22) ... (en1 en2)))
    and if there is only one subform then we rewrite:
      (cond (e11 e12))
    ==>
      (if e11 e12 #f)
    note that this makes cond return false when no condition match - this is
    different than Scheme, but we use this due to the lack of undefined values
    and errors.
    The last rewrite case is:
      (cond (else e))
    ==>
      e

  [*] EVAL_and rule:
    To evaluate (and e1 e2 ... en), evaluate e1 to get a value v1, if v1 is #f,
    return #f, otherwise continue by recursively evaluating (and e2 ... en).
    To evaluate (and e1), continue by evaluating e1.
    Evaluating (and) returns #t.

  [*] EVAL_or rule:
    To evaluate (or e1 e2 ... en), evaluate e1 to get a value v1, if v1 is
    not-#f, return v1, otherwise continue by recursively evaluating (or e2 ...
    en).
    To evaluate (or e1), continue by evaluating e1.
    Evaluating (or) returns #f.

  [*] EVAL_internal_def:
    This rule can be plugged into the APPLY_lambda rule to handle internal
    definitions.  By using it only in this context, we guarantee that correct
    programs can only use internal definitions as a block of definitions that
    comes only at the beginning of a function body.
    This is merely a rewrite - we rewrite a function body:
      (define x1 e1)
      ...
      (define xn en)
      e
    ==>
      (letrec ((x1 e1) ... (xn en)) e)
    This can be even further extended to handle internal definitions like
    (define (x1 ... xn) e) in the obvious way.  Note that the letrec rule will
    simply evaluate the same definitions as top-level expressions, only with
    fresh variables, so this follows the intuition that we are trying to get
    here, and you can skip this intermediate rule and go straight to evaluate
    the definitions, as long as you remember to rename problematic variables.

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