Homework #8

Assigned: March 31
Due: April 7, 4:30pm


  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' article 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 artificial intelligence, try implementing the search of §5 and presenting it to the instructor for extra credit.

    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. To give you an idea of what we are looking for here, in prior semesters students have curried a sorting routine parameterized on the list to be sorted and the type of items in the list or the comparison operator to be used, a root finding function parameterized by the degree and the number whose nth-root we desire, and a number convertor parameterized by the base from which to be converted and the base to which to be converted.

  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 Chameleon up to and including [EOPL] §3.8 and use it to stress test or, in other words, spin the wheels of your interpreter. Your program must be between at least 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. To give you an idea of what we are looking for here, in prior semesters students have used Chameleon to build a procedural representation of a stack and a converter from demical to binary numbers.

  8. (10 points extra credit) Write a program in Haskell using higher-order functions to solve a complex problem in very few lines of code (e.g., no more than 10). For inspiration, think of the function we wrote in class which reverses a list in linear-time in one line of code, the function which converts a string representation of an integer to a integer, the powerset function, or the function which enumerates all the permutations of a list.

Return Home