Homework #5

Assigned: February 24
Due: March 10, 4:30pm


  1. (2+2+2=6 points) Consider the following JavaScript program:
    function sub1() {
       var x;
       
       function sub2() {
          // creates a popup box with the value of x
          alert(x);
       };
    
       function sub3() {
          var x;
          x = 3;
          sub4(sub2);
       };
    
       function sub4(subx) {
          var x;
          x = 4;
          subx();
       };
    
       x = 1;
       sub3();
    }
    sub1();
    
    Give the output of this program when executed using (i) deep, (ii) shallow, and (iii) ad-hoc binding.

  2. (24 points) [EOPL] Exercise 2.24 on p. 64.

  3. (25 points) [EOPL] 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?
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). Since subst-in-term and subst-in-terms is client code and, therefore, must work in either representation, only include subst-in-term and subst-in-terms in one of the above two files.
Return Home