CS217 Day 15 Friday, April 28, 2000

Mid Term Exam -- In Class Part

1. Let v[d:p] denote the lexical address of a variable v in a character syntax expression if it has depth d and position p, and v[F: ] if v occurs free in the expression. Complete the following conversions into lexical address expressions.

   1. let c = 5
          f = proc (x, y) +(x, y)
      in
        let c = 6
            b = 7
            g = proc (a, b)
                  proc (a)
                    (a b c)
        in
          ((g 3 4) f)
      
      =>
      
      let c = 5
          f = proc (x, y) +(x[0:0], y[0:1])
      in
        let c = 6
            b = 7
            g = proc (a, b)
                  proc (a)
                    (a[0:0] b[1:1] c[2:0])
        in
          ((g[0:2] 3 4) f[1:1])
      

   2. let a = 2
          b = 3
      in
        let a = 4
            p = proc (x) +(a, x)
        in
          let b = 5
              q = proc (x, y) (p (y a))
          in
            (q b p)
      
      =>
      
      let a = 2
          b = 3
      in
        let a = 4
            p = proc (x) +(a[_:_], x[_:_])
        in
          let b = 5
              q = proc (x, y) (p[_:_] (y[_:_] a[_:_]))
          in
            (q[_:_] b[_:_] p[_:_])
      

   3. What are the values of these expressions, assuming lexical binding?

      1. let c = 5
             f = proc (x, y) +(x, y)
         in
           let c = 6
               b = 7
               g = proc (a, b)
                     proc (a)
                       (a b c)
           in
             ((g 3 4) f)
         
         =>
             ______
         

      2. let a = 2
             b = 3
         in
           let a = 4
               p = proc (x) +(a, x)
           in
             let b = 5
                 q = proc (x, y) (p (y a))
             in
               (q b p)
         
         =>
             ______
         

      3. What are the values of these expressions, assuming dynamic binding?

         1. let c = 5
                f = proc (x, y) +(x, y)
            in
              let c = 6
                  b = 7
                  g = proc (a, b)
                        proc (a)
                          (a b c)
              in
                ((g 3 4) f)
            
            =>
                ______
            

         2. let a = 2
                b = 3
            in
              let a = 4
                  p = proc (x) +(a, x)
              in
                let b = 5
                    q = proc (x, y) (p (y a))
                in
                  (q b p)
            
            =>
                ______
            

         3. In the environment

                (extended-env-record
                  (i v x emptylist)
                  #4(1 5 10 ())
                  (empty-env-record))
            

            what is printed and what is the value of the following expression?

            let a = 2
            in
              let f = proc (x) *(a, add1(x))
              in
                let d = print(f)
                in
                  (f x)
            

            1. prints:

               (closure
                 (_)
                 (primapp-exp
                   (________)
                   (_______________________________________________________))
                 (extended-env-record
                   (_)
                   #1(_)
                   (extended-env-record
                     (i v x emptylist)
                     #4(1 5 10 ())
                     (empty-env-record))))
               

            2. has value:

               ______
               

            3. Evaluate, and draw the abstract syntax tree for the else of the if in

               letrec f(x) = if zero?(x)
                             then (g 3)
                             else +(x, (f -(x, 2)))
                      g(x) = *(x, x)
               in
                 (f 2)
               

               1. value:

                  __________
                  

               2. abstract syntax tree for the else:

                  +-------+
                  |add-exp|
                  +-------+
                    /    \