Homework #5

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?