CSE 428: Solutions of exercises on expressions

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.

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
Solution
1. ```
   if e1 then e2 else false
```
2. Only call-by-name allows to define the non-strict "&&" as a function. The declaration would be as follows:
```
   function non_strict_and(name e1, e2: boolean):boolean;
      begin
      if e1 then e2 else false
      end;
```
  Note: in Pascal syntax we should write the conditional as follows:
```
   if e1 then non_strict_and := e2 else non_strict_and := false
```
  Call by value would not do the job, because the parameters have to be evaluated before the function is executed (hence we would get a strict semantics). Call by reference and call by value-result are out of question, because they cannot allow as actual parameters generic expressions (only variables).

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.
Solution
1. The operator is strict: the semantics prescribes that both operands are to be evaluated, in all cases.
2. If x is negative then the result is false. If x is 0 then the expression gives an error (division by 0). If x is positive then the result is true .

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?
2. What is the result of the expression?
Solution
1. During the evaluation of x + y the environment is env[0/x][0/y][1/x]. (The second association for x , i.e. [1/x], shelters the first.) During the evaluation of ... + x the environment is env[0/x][0/y].
2. The result of the expression is 1.