The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.

The superscript "(s)" stands for "solution provided". You can find the solution of these exercises here.

1. ^(s) Consider a Pascal-like language with strict logical operators, and in which it is possible to write boolean conditional expressions, like

      if e then e1 else e2
   

   where e, e1, and e2 are boolean expression, and the if-then-else has the usual (non-strict) semantics. Assume that we want to write, in this language, an expression like e1 && e2 in C, namely a non-strict conjunction with the following semantics:

         r |- e1  eval  false 
      ----------------------------
       r |- (e1 && e2) eval false
   
   
       r |- e1  eval  true    r |- e2  eval  v
      ------------------------------------------
            r |- (e1 && e2)  eval  v
   

   1. How can we express the e1 && e2 using the if-then-else construct?
   2. Suppose that we want to define the operator "&&" as a function in our language. Discuss which of the following parameter-passing methods is sufficient/necessary to this purpose.
      • call by value
      • call by value-result
      • call by reference
      • call by name
2. ^(s) Consider the logical operator "nor", defined as follows:

       r |- e1  eval  v1     r |- e2  eval  v2  
      -----------------------------------------  if v1 = true or v2 = true
            r |- (e1 nor e2) eval false
   
   
       r |- e1  eval  v1     r |- e2  eval  v2  
      -----------------------------------------  if v1 = v2 = false
            r |- (e1 nor e2) eval true
   

   1. Is nor (with the above semantics) strict or non-strict?
   2. Consider the expression

      x < 0 nor (x = 0 nor 1/x > 0) 
      

      where x is an identifier of type integer. Say what are the results (true, false, or error) of the above expression, depending on the possible values of x.
3. ^(s) Consider the expression

      let x = 0
      in let y = x
         in let x = y + 1
            in x + y
            end
            + x
         end
      end
   

   1. Assuming that the initial environment is env, what is the environment at the moment of the evaluation of x + y? And at the moment of the evaluation of ... + x?
   You can use a drawing if you prefer. Assume that we have a pure language of expressions, i.e. the state is not needed.
   2. What is the result of the expression?