Homework #8Assigned: March 31
Due: April 7, 4:30pm
 (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 parameterpassing methods, what are
all of the values of the variables value and
list after each of the three calls to
swap?
 callbyvalue
 callbyreference
 callbyvalueresult
 (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
 (10 points) Read John Hughes' article
Why Functional Programming Matters, The
Computer Journal, 32(2), 98107, 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 §§13
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
(NewtonRaphson square roots, numerical
differentiation, or numerical integration). Your
program must work with the HUGS98 interpreter.
 (10 points) [EOPL] Exercise 3.63 on p. 121.
 (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
nthroot we desire, and a number convertor
parameterized by the base from which to be
converted and the base to which to be converted.
 (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:
 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.
 Define a function (eval exp env)
(akin to evalexpression 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.
 (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 rewrite 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.
 (10 points extra credit) Write a program in
Haskell using higherorder 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
lineartime 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.
