CS 254 Homework 2: Evaluating expressions

A short break from evaluating by computer

This lab is intended to be worked out "by hand": you don't have to write the answers out on paper (i.e., you can type them in), but be careful of cut-and-paste errors, and show all the steps as you go.

On the other hand, using the computer is a great way to verify the results you should get ... you just won't get any verification of the techniques you used!

Consider the following declarations (or definitions) of variables in terms of certain expressions, and then evaluate the given expression by rewriting it, one step at a time, until you reach a final value.

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 (as would be typed in WinHugs) 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, as it makes it more clear why each step is taking place. You should write down a reason for each of your steps, folliwng 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
   

---