CS 254 Lab 1: Evaluating expressions

This lab is intended to give you some practice with both the syntax of expressions s they are written in Haskell and with their "semantics" as determined by how they are evaluated (a more traditional semantics is just the result, viewed abstractly, e.g., a number or truth value). You should work out the reductions (evaluations) "by hand": you may write the answers out on paper or type them in, but be especially careful of cut-and-paste errors if you use a computer. In any case, remember to show all the steps as you go.

Using a computer is, however, a great way to verify the results you should get ... it just won't verify the process you use!

Consider the following definitions of variables in terms of certain expressions, then evaluate the given expression by rewriting it, one step at a time, until you reach a final value. (Recall that && and || are used for the logical "and" (conjunction) and "or" (disjunction) operators.)

For example, give these two definitions (as they would be written in a script file):

x = 2 + 3

f y = x * (y - 1)

you could rewrite the expression below like this:

    f (x - 2)

=   f ((2 + 3) - 2)     { definition of x }

=   f (5 - 2)           { addition fact }

=   f (3)               { subtraction fact }

=   x * (3 - 1)         { definition of f, with y = 3 }

=   (2 + 3) * (3 - 1)   { definition of x }

=   (2 + 3) * 2         { subtraction fact }

=   5 * 2               { addition fact }

=   10                  { multiplication fact }

(Here I have used reasons in "comments" on the right of each step, as our textbook does. I won't always write these down on the blackboard during lecture, but it's a good idea for the homework, as it makes it more clear why each step is taking place. You should write down a reason for each of your steps, following this example and picking reasons as best you can.)

Notice that there are sometimes choices about the order in which we apply rules. We might even apply a function to its arguments before resolving the arguments completely: for example, we might have applied f above to (5-2) before doing the subtraction.

---

1. Given these definitions:

   a = b + 3
   
   b = 7
   
   f x = b * x + x - 3
   

   reduce this expression:

   	f (2 * a)
   

---

2. Given these definitions:

   x = 3 * y
   
   y = 7
   
   f x = x + 2
   
   z = x + f x
   
       where x = y + f 3
   

   reduce this expression:

   z * x - 2
   

   (Note: the x on the right-hand side of the definition of z is the one defined locally in the where clause, not the one defined globally above it!)

---

3. Given these definitions:

   k = True
   
   h x = (x && k) || not x
   
   m x = if x < 5 then h False else h (k || x==1)
   

   reduce this expression:

   m 5
   

---

4. Given these definitions:

   p = g 5
   
   q = g (p - 4)
   
   g x = if x > 3 then x+2 else g (x-5)
   

   reduce this expression:

   (p * 2) - q
   

---

5. Given these definitions:

   zap f x = if x < 20 then f (x + 3) else f (zap f x)
   
   w y = y * 2 - 1
   
   r = 5
   

   reduce this expression:

   zap w r
   

---