Homework #8

1. (2+2+2=6 points) Consider the following program written in C syntax:

   void swap(int a, int b) {
      int temp;
      temp = a;
      a = b;
      b = temp;
   }
   
   main() {
      int value = 2, list[5] = {1, 3, 5, 7, 9};
      swap(value, list[0]);
      swap(list[0], list[1]);
      swap(value, list[value]);
   }
   

   For each of the following parameter-passing methods, what are all of the values of the variables value and list after each of the three calls to swap?
   
   
   1. call-by-value
   2. call-by-reference
   3. call-by-value-result
   
   
2. (10 points) [EOPL] Exercise 3.56 on p. 117. Add a division ("/") primitive to your interpreter so the interpreter can evaluate the following classical program for lazy evaluation:

   >(run "let
             p = proc (x, y) if (zero? (x), x, y)
          in
             (p 0 /(1,0))")
   0
   

3. (10 points) Read John Hughes' essay Why Functional Programming Matters, The Computer Journal, 32(2), 98-107, 1989. Read it with your HUGS98 Haskell interpreter open so you can enter the expressions as you read them so to better understand them (you may need to make some minor adjustments, e.g., replace cons with :). Know §§1-3 inside out. Then implement one of the numerical algorithms from §4 in Haskell. If you are ambitious and interested in AI, try implementing the search of §5.
   
   Turn in your code for one of the examples from §4 (Newton-Raphson square roots, numerical differentiation, or numerical integration). Your program must work with the HUGS98 interpreter.
   
   
4. (10 points) [EOPL] Exercise 3.63 on p. 121.
   
   
5. (5 points) Define a function in Haskell and then curry it to create a new function. For full credit your unspecialized and specialized functions must be practical and not toy applications.
   
   
6. (3+6=9 points) Define a Haskell datatype for boolean expressions. Boolean expressions are made up of boolean values, boolean variables, and operators. There are two boolean values: True or False. A boolean variable (e.g., "p") is one which can take on any of the two boolean values. Boolean expressions are constructed from boolean variables and values using the operators AND, OR, and NOT (with their obvious meanings). An example of a boolean expression is (AND (OR p q) (NOT q)), where p and q are boolean variables. Another is (AND p True). Do the following:
   
   
   1. Define a Haskell datatype named Boolexp whose values represent legal boolean expressions. You may assume that boolean variables (but not the expressions themselves) are represented as strings.
      
      
   2. Define a function (eval exp env) (akin to eval-expression in your Scheme interpreter) which takes a boolean expression exp and a list of true boolean variables env, and determines the truth value of exp on the assumption that the boolean variables in env are true and all other boolean variables are false.
      
      
   For instance, if exp represents (AND (OR p q) (NOT q)) and env is the list [p], then the result of (eval exp env) must be True. Keep in mind that exp is not a string but a value constructed from the Boolexp datatype:

   Main> eval (Variable "q") []
   False
   Main> eval (Literal True) ["p","q","r"]
   True
   Main> eval (AND (OR (Variable "p") (Variable "q")) (NOT (Variable "q"))) ["p"]
   True
   

   You may assume the following Haskell list member function is available to you (and need not include its definition in your solution).

   member x [] = False
   member x (y:ys) = (x == y) || (member x ys)
   

   This problem must be solved with at most one datatype definition and one short (5 line) Haksell eval function. Credit will not be awarded for anything more elaborate.
   
   
7. (5 points) Write a program in the language up to and including [EOPL] §3.8 and use it to spin the wheels of your interpreter. Your program must be between 10-20 lines of code and original, i.e., not lifted from the textbook. You are welcome to re-write a program you wrote in the past and use it to flex the muscles of your interpreter.