Programming Languages (CS 328) Midterm review 2000-02-18 Computer Science and Engineering Soumen Chakrabarti Indian Institute of Technology Bombay

1. What is the result of evaluating in dynamically-scoped pass-by-name FL the following expression:

    (let ((foo (let ((a 5)) (lambda (x) (- a x)))))
        (let ((b 3))
            (foo b)))

Answer: The interpreter will evaluate to error because a will be found undefined.

2. What will the following evaluate to under statically scoped pass-by-reference FLK!

    (let ( (x (ref 0))
           (foo (lambda (y z) (begin (:= y 2) (/ 4 z)))) )
        (foo x x))

Answer: The expression will evaluate to 2. Multiple names can refer to the same location in the store.

3. Evaluate using statically scoped pass-by-value FL:

    (let ((foo (lambda (x) (rec x x)))
          (bar (lambda (y) 2)))
        (bar foo))

Answer: Evaluates to 2. Even in pass-by-value the body of a Procedure is not evaluated before the call-point.

4. Evaluate using dynamically scoped pass-by-value FL:

    (let ((x 1))
        (let ((f (lambda () x))
              (g (lambda (h) (h))))
            (let ((x 2))
                (g f))))

Answer: 2.

5. Evaluate (rec camel (pair 4 (left camel))).

Answer: (pair 4 4). Remember that pair and left are, informally speaking, “normal order constructs,” i.e., they work on the parameters without evaluating them.

6. We wish to add a new construct (try E_{1} E_{2}) to FLK! The informal semantics of this construct is that E_{1} is first evaluated starting from the current store; if it evaluates to true the try expression returns true. Otherwise, all the changes made to the store are undone, and the result of the try is the evaluation of E_{2} with respect to the original store. Give operational and denotational semantics for this language extension.

Answer: Denotational semantics is simple. For operational semantics, we define a new configuration of the form

⟨(*trying* E_{1} E_{2} S_{1}), S_{2}⟩,  (1)

and the following additional rewrite rules.

⟨(try E_{1} E_{2}), S⟩ ⇒ ⟨(*trying* E_{1} E_{2} S), S⟩  (2)
\frac{⟨E_{1}, S_{2}⟩ ⇒ ⟨E′_{1}, S′_{2}⟩}{⟨(*trying* E_{1} E_{2} S_{1}), S_{2}⟩ ⇒ ⟨(*trying* E′_{1} E_{2} S_{1}), S′_{2}⟩}  (3)
⟨(*trying* #t E_{2} S_{1}), S_{2}⟩ ⇒ ⟨#t, S_{2}⟩  (4)
⟨(*trying* #f E_{2} S_{1}), S_{2}⟩ ⇒ ⟨E_{2}, S_{1}⟩  (5)