Homework #5

Assigned: March 7
Due: March 17, 4:30pm

  1. (10 points) [EOPL2] Exercise 2.5 on p. 47.

  2. (15 points) [EOPL2] Exercise 2.7 on p. 52. Your lexical-address function must be defined as:
    (define lexical-address
      (lambda (expr)
        (unparse-expression (parse-expression expr))))
  3. (24 points) [EOPL2] Exercise 2.24 on p. 64.

  4. (25 points) [EOPL2] Exercise 2.25 on pp. 64-65. John Robinson's development of the concept of unification was one of the most seminal contributions to automatic theorem proving and logic programming. PROLOG, the most widely used logic programming language, binds values to variables through unification. However, most implementations of PROLOG, including SWI-PROLOG, do not perform the occurs-check and, therefore, their unification algorithm is optimistic and incorrect. For what reasons might they decide not to perform the occurs-check?

  5. (3+6=9 points) [CPL] Programming Exercise 8.4.4 (ML) or 8.4.5 (Haskell).
Note on submitting: Submit two files subst-proc.scm and subst-asr.scm which each contain the definitions of the 5 functions in the substitution interface: (empty-subst), (extend-subst), (apply-subst), (unit-subst), and (compose-substs). Also include subst-in-term and subst-in-terms in each file, even though it is client code and must work in either representation.
Return Home