CS 254 Homework 1: Evaluating expressions

This written homework assignment is intended to give you some practice with both the syntax of expressions as they are written in Haskell and with their “semantics” (i.e., meaning) 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. (Note that && and || are used for the logical "and" (conjunction) and "or" (disjunction) operators; check the book or try a search on-line if you don’t know what that means ... or just wait on those parts until I get back.)

(Hmmm ... You should also know that expressions of the form:

if A then B else C
where A, B, and C are other expressions, work by first evaluating the A part: if it comes out to be True, then the result is just the B part; otherwise the result is the C part. I hope that makes sense, but if not, just hang loose until the 8th.)

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.

Try the following examples yourself. You don't have to write them 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.

  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