Due: Thursday Jan 31, 11:59pm via turnin (assignment
name hwk3)
Collaboration Policy:
Pairs Permitted
There are two parts to this assignment, one on programming in Haskell and a set of written questions about laziness. There is no Scheme programming (and hence no jousting component) for this assignment.
The Haskell Notes page provides pointers to language manuals and a mapping from common Scheme functions to their Haskell equivalents.
isPrime :: Integer -> Bool, which
determines whether a given integer is prime. primes :: [Integer], the list of all
primes. isPrime checks divisibility by all
factors, write a second version isPrime2 that only tests
divisibility by prime factors. (If your original definition
did this, you don't need to submit anything for this part.) buildList :: Int -> (Int -> a) ->
[a], where ((buildList n f) !! i) == (f i)
(for all i in [0 .. n-1]). buildTable :: Int -> Int -> (Int -> Int -> a) ->
[[a]], where (((buildTable n m f) !! i) !! j) == (f i
j) (for all i in [0 .. n-1], j in [0 .. m-1]). lcs :: String -> String -> String, which
computes the longest common subsequence of two strings s1 and s2.
Characters in subsequences need not be consecutive in the original
word, but they must occur in order. For example, lcs "baseball"
"fable" should be "abl". If a world has two subsequences of
the same maximal length, return either one.
A good solution to this will exploit laziness and compute the value
for an expression only once. The buildTable function will help with
the latter. Regarding the former, your submitted solution should not
simply generate all possible subsequences from all pairs of indices
then look for the longest (though if writing the code this way first
helps you get a feel for the problem, feel free). Your code should
only generate instances of the lcs problem that are
necessary to compute the longest subsequence.
As a hint, you could try computing lcs (take i s1) (take j
s2) from
lcs (take (i-1) s1) (take j s2), lcs (take i s1) (take (j-1) s2), and lcs (take (i-1) s1) (take (j-1) s2).
(s1 !! (i-1)) == (s2 !!
(j-1)).
In this exercise, you will implement a strategy to play a simple game. The game is called Mancala, but you don't need to understand the rules because we have implemented that part for you. Your job is to build a tree of possible move sequences and choose the move that appears best.
Download the support code, which provides the following set of data types and functions:
Player: values of this type represent the players
of the game (PlayerA or PlayerB).State: values of this type represent game
configurations.initialState :: Player -> State represents the
initial configuration of the game board (the given player goes
first).getPlayer: State -> Player: given a configuration,
returns the player who makes the next move.getScore :: Player -> State -> Int returns the score
for the given player in the given configuration. (Bigger numbers are
desirable for your player.)nextStates :: State -> [State] gives the possible
configurations after the next move. If the returned list is empty, then
the game is over.GameTree to represent the game
state after any sequence of moves. Each node should have its current
configuration and a list of trees, where each tree corresponds to
containing the configurations obtainable following a specific single
move.nextStates to the
initialState). prune :: Int -> GameTree -> GameTree, which
prunes a tree to a given height. minimax :: Player -> GameTree -> Int,
which consumes a (pruned) tree and evaluates the configuration by
looking ahead and applying the following minimax algorithm. If a node
has no children, it receives its own immediate score. If it
corresponds to Player's turn, it receives the maximum of
the recursively-computed child scores, otherwise it receives the
minimum.You do not need to understand the support code to do this assignment. The API given above is sufficient for solving these problems.
To use the support code, put the following two lines at the top of your file, where your file is called Filename.hs and Game.hs (the support code) is in the same directory as your file.
module Filename where import Game
This part asks you to provide prose solutions to two problems. You do not need to turn in an interpreter or other code for this assignment, but you might find it very helpful to implement and experiment with the lazy interpreter discussed in class as you think about these problems. Just because these are prose rather than code doesn't make them easy. You may need to let your brain chew on these for a couple of days to come up with good answers. Leave yourself enough time to think about these problems.
In our lazy interpreter, we identified three points in the
language where we need to force evaluation of expression closures (by
invoking strict): the function position of an
application, the test expression of a conditional, and arithmetic
primitives. Doug Dolittle, a fairly sedentary student, is rather taken
with the idea of laziness. He suggests that we can reduce the amount
of code we need to write by replacing all invocations of strict with
just one. In the lazy interpreter from class (PLAI chapter 8), he
removes all instances of strict and replaces
[id (v) (lookup v env)]with
[id (v) (strict (lookup v env))]
Doug’s reasoning is that the only time the interpreter returns an expression closure is on looking up an identifier in the environment. If we force its evaluation right away, we can be sure no other part of the interpreter will get an expression closure, so removing those other invocations of strict will do no harm. Being lazy himself, however, Doug fails to reason in the other direction, namely whether this will result in an overly eager interpreter.
Is it possible to write a program that will produce different results under the original
interpreter and Doug’s? Let the interpreted language feature arithmetic,
first-class functions, with, if0, and rec
(even though these are not in our in-class lazy interpreter).
If so, hand in an example program and the result under each interpreter, and clearly identify which interpreter will produce each result. Be sure to compare this behavior against that of the lazy interpreter of the sort we’ve written in class rather than the behavior of Haskell! Note: it should not be difficult to construct test interpreters from your solution to the Extended Interpreter assignment and the code we give you in the textbook. You may use these to help you test your conjectures.
If it's not possible, defend why one cannot exist, and then
consider the same language with cons, first,
and rest added. Also, keep in mind that the REPL is
always a strictness point. If you were running your lazy interpreter
from DrScheme, you would type the following into the interactions
window:
> (strict (interp (parse '{...}) (mtSub)))
...
You do not need to turn in any interpreters for this problem --
just submit the example program, what answer it _would_ produce
under each of the two interpreters, and any other explanation
requested in the problem.
No lazy language in history has also had state operations (such as mutating the values in boxes, or assigning values to variables). Why not?
The best answer to this question would include two things: a short program (which we assume will evaluate in a lazy regime) that uses state, and a brief explanation of what problem the execution of this program illustrates. Assume the non-caching (ie, original) notion of laziness. If you present a sufficiently illustrative example (which needn’t be very long!), your explanation can be quite short (a couple of sentences). Think carefully about whether your example program is really looking at laziness as opposed to other design decisions we've discussed this term.
Turn in one file for each part of the assignment. If you did the assignment with a partner, submit only one copy (the turnin software will handle this automatically if you tell us your pairings ahead of time).
For the Haskell programs, submit your actual test cases or clear statements of how you tested your code (describing, for example, what you computed for a test and your criterion for determining whether the test passed). Leave these in comments in your Haskell file.
For the written questions, turn in a text file with your answers. Please use text, rather than Word or something else that we need an application to open (we want to be able to spool your file directly to the printer). You could use DrScheme and put your answers inside a giant comment if you wish: the characters #| and |# delimit multi-line comments.