You will do this problem set by modifying the source files in ps4.zip and submitting the program that results. The program that you submit must compile without any warnings. Programs that do not compile or compile with warnings will receive an automatic zero.
Several parts of this assignment require that you implement a specification (and in some cases finish designing the specification). For each part, we expect you to provide the following documentation in an attached file for each part.
We will be evaluating your problem set on several different criteria: the specifications you write (where appropriate), the correctness of your implementation, code style, efficiency, and validation strategy. Correctness is worth about half the total score and the importance of the other criteria varies from part to part.
As the Internet has grown in popularity, so has online gaming. Most online games require some element of chance, which they often obtain by using dice roll generators. They have code to simulate the rolling of a single die, and then build some kind of dice rolling scheme upon which the game's result depends. The problem of course is where to run this code. If an individual gamer is allowed to run the code on his home machine, this allows the possibility of cheating by fabricating dice rolls. One solution to this problem is Internet-based dice-rolling servers. These servers accept an input expression in a predefined dice-rolling language and return the result to one or more computers.
There are many different games that require rolling dice, some requiring more complex actions than simply rolling a couple of six-sided dice. For example, Yahtzee, Risk, Dungeons & Dragons, and Warhammer also have more complicated dice-rolling protocols. To support these games, dice-rolling languages need a number of additional features, such as summing and counting dice, repeated rolling, and discarding or selecting rolled dice based on a condition.
In this problem set you will implement an interpreter for a subset of a simple dice-rolling language called Roll.
The Roll language is a functional language. When the interpreter (in evaluate mode) reads an expression in Roll, it computes a possible value and prints the output. Possible expressions exp in the subset of Roll we are implementing include the following:
| a positive integer constant | Examples: 3, 5, 2. |
| a bag of values | Examples: {3,4,2}, {1,2,3,4,5,6}, {}, {4} |
d exp |
d is the fundamental expression in
Roll. dn means roll an n-sided die and return the result. For example,
d6 evaluates to any of the integers 1–6. The
expression after d need not be an integer, but it should
evaluate to an integer; for example, d(d6) is a valid
expression. To compute this expression, the interpreter will roll
a six-sided die to get a value n, then roll an n-sided die and return
the result. |
exp # exp |
# is the "n
times" operator. The interpreter evaluates the first
expression to get an integer n. Then it
evaluates the second expression n times and unions the result into a
single bag of integers. For example, 3#d6 rolls 3 six-sided dice
and returns a bag containing the results. Evaluation of this expression will always result in bags of integers; it will never result in bags of bags. For example, 3#(2#d6) is equivalent to 6#d6. |
exp @ exp |
The result of this is the union of the two
subexpressions. For example, (2#d4)@(3#d6) returns
the value from rolling 2 four-sided dice and 3 six-sided dice. Both
expressions should evalutate to bags; 2 @ (2#d12) should cause a Runtime
error. |
exp + exp |
This expression acts differently depending on the results of the subexpressions. If both of the operands are integers, it computes the sum of the two integers. If one operand is an integer and the other is a bag, it adds the integer value to each element of the bag and returns the result. It is a run-time type error for both operands to be bags. |
sum exp |
If the subexpression is a bag, the result
is to sum the elements of the bag. If it is an integer, this
expression returns that integer. So, sum(3#d6) would
return the sum of 3 six-sided dice. |
count exp |
Similar to sum, but it returns the number of elements in the subexpression. If the subexpression is an integer, it returns 1. |
least exp exp |
Given operands n and
b respectively, returns the least
n elements of b. b
must be a bag. An example is least 2 (3#d6), which rolls
3 six-sided dice and returns the two least values rolled. |
let id=exp
in exp end |
Binds the result of evaluating the first
subexpression to the identifier id and uses the
binding to evaluate the second subexpression. Identifiers start
with a letter and consist of letters, underscores, and primes.
For example, let x = d6 in x+x end will roll a six-sided
die and double the result. Notice that the d6 in this expression
is evaluated only once. |
if exp relop exp then exp else exp |
Very similar to the ML
if/then/else expression. If the conditional returns
true, returns the result of evaluating the first expression, otherwise
returns the result of evaluating the second expression. For example,
if d6 < 4 then d4 else d5: Roll a 6-sided dice. If the
result is less than 4, then roll a 4-sided dice else roll a 5-sided
dice. The list of relational operators is mentioned below. Note: since
each element of the test is parsed separately, it is NOT possible to
put parentheses around the comparison as in if (exp op exp) then
.... Relational operators relop may be any of <,
<=, =, !=, >=, > |
filter relop exp
exp |
filter op
e1
e2
will perform the
following: evaluate e1
and e2
to get result v1
and v2. v1
must be an integer; v2
must be a bag. Then compute (v1
op v) for
each element v
of bag v2
and return the bag with all elements for which (v1
op
v) evaluated to true.
This is easiest to see with an example. filter < 4 3#d6 will
roll 3 six-sided dice and return any values greater than or equal to
4. If the 3#d6 evaluates to {1,2,6}, the result will be
{6}. |
You should experiment with the interpreter to get a feel for the language
syntax. At the command prompt, enter parse to enter the
parser mode where the expressions are parsed and displayed but not
evaluated. Use this mode to familiarize yourself with the abstract syntax tree that will be passed in as input to the eval functions.
Some sample dice expressions:
d6 : Roll a 6 sided die
2 # d6 : Roll two 6 sided dice
d(d 6) : Roll a 6 sided die to get 'n', and then role an
'n' sided die
d(sum(2#d6)) : Roll an 'n' sided die where n is the
sum of two six-sided die rolls.
if d6 < 4 then 4 else 2#d4 Roll a d6, and if that
is less than 4 return 4, otherwise return a bag consisting of the results
of rolling 2 d4's.least 2 (3#d5) : Return the smallest 2 values after
rolling 3 five-sided dice. least 2 (3#(if d6 < d6 then 1 else 2)) : Roll
two dice. If the first is smaller, return 1 else 2. Do this three times
and select the lowest two values.
(2#d6) # d6 : Error. First argument to # must be an int.
d(2#d6) : Error. Argument to d should be an int.
least 2 5 : Error. Second argument to least should be a bag.
least 2 d5 : Error. Second argument to least should be a bag.
(2#d6) + (2#d6) : Error. Cannot add two bags.
let x = d6 in x + y end : Error. Unbound identifier y.
You will also want to study the abstract syntax tree for expressions as
defined in AbSyn.sml. Here you will find the datatype
exp, which represents an expression in Roll, and the datatype
value, which represents the result of evaluating a Roll
expression. Notice that values in Roll can be either integers or
collections of integers. To represent collections of integers, we will
use multisets. You should reuse your implementation from Problem Set 3,
fixing it if necessary to address correctness or performance problems.
The datatype for value is:
type 'a bag = 'a Multiset.multiset
datatype value = Int_v of
int | Bag_v of int bag
You are allowed to add to the multiset signature as you see fit for this problem set. You are also allowed to change your multiset implementation for this problem set as you see fit. We will not be testing you on your multiset implementation directly; we will be testing it indirectly through its use by the rest of your implementation. Note: the usual specification and documentation is still required for the multiset as for all of your code!
Central to dice rolling is the concept of probability. Probability is the branch of mathematics that is concerned with analyzing experiments, that is, processes that return outcomes. Generally, an experiment has multiple possible outcomes, and which outcome will occur is not known beforehand. Rolling a 6 sided die is an experiment whose outcome is a number between 1 and 6. However, one does not know beforehand what the outcome is going to be . The set of all possible outcomes is called the sample space. For example, the sample space of rolling a 6 sided dice is {1, 2, 3, 4, 5, 6}.
Some outcomes may correspond to an event; for example, winning a game. Each event is defined by the favorable outcomes in which the event is said to occur. For example, you might win the game by rolling any number less than or equal to 2. In this case, the set of favorable outcomes for the event would be {1, 2}. The likelihood of any of the favorable outcomes occurring is the probability of the event. If all outcomes are equally likely, we can define the probability of an event A, denoted by Pr(A), as
Pr(A) = (number of favorable outcomes for A) / (number of all possible outcomes)
Hence, the probability of winning in the above example would be Pr(Win) = 2/6.
There are more complicated examples. Suppose the game requires you to toss a coin 3 times. You win if there are exactly two heads. Here, flipping a coin three times is the experiment. Each toss can turn up either a head (H) or a tail (T), so one possible outcome is THT. That is, the first toss is a tail, the second a head, and the third another tail. The sample space is {TTT, TTH, THT, THH, HTT, HTH, HHT, HHH}, and among these, the favorable outcomes are { THH, HTH, HHT }. The probability of winning therefore is 3/8. Notice HTH, THH and HHT are counted as 3 distinct outcomes even though both have 2 heads and 1 tail.
After compiling the problem set, to start the interpreter simply run the
function Roll.interpreter(). You should see the following:
CS312 Roll Interpreter (c) 2003 Cornell University >
From here, you can type in Roll expressions, and they will be evaluated
in the current mode. There are three different modes,
eval, dist, and sample.
eval mode - evaluates the expression and returns a
single result. This is done by running the eval function. (See Part 1 for more details )dist mode - evaluates the expression, but this time
instead of giving out a single result, returns all possible values of
the expression, with their frequency distribution. (See Part 2 and Part 3)sample mode - evaluates the expression multiple times
and returns all of the results. Run with a large enough sample size, the
frequency of certain results should approach those returned in
dist mode. (See Part 4) To view the current mode, type mode at the interpreter
prompt. To switch modes, type eval, dist, or
sample, depending on which mode you wish to switch to. The
interpreter starts in eval mode. Typing help gives
you help on how to use the interpreter, and q quits the
interpreter.
Implement the function Evaluator.eval of type
AbSyn.exp -> AbSyn.value. This function will take in a Roll
expression, and output a Roll value based on the expression. For example,
eval(d6) will return an Int_v that has a value
between 1 and 6. And eval(3#d6) will return a
Bag_v that contains 3 numbers, each between 1 and 6
inclusive.
The evaluator must be able to handle all of the Roll expressions described above, and be able to return all possible valid values for any given expression. In order to return bag values, you must add your multiset implementation from Problem Set 3. The code we have given you in multiset/ms.sml is only for compilation and does not implement any of the multiset functions. You should replace this file with your multiset implementation.
You may
also notice that efficiency in your program depends largely on the
efficiency of your multiset implementation. Your program should be able to
handle (2000 # (2000 # d1)) in less than 2 minutes
without running out of memory on a Pentium 4, 1.7 GHz machine with 256 MB
RAM (where the reference solution runs in under
23 seconds). If you find your code running slowly, which may be the
case with the previous expression, you will have to improve your multiset
implementation to achieve better performance. To accurately check your
running time, you may want to disable the pretty-printing since printing the
result of the previous expression could take a while.
To generate random die rolls, you will need to implement a random number generator as described in Part 5.
You will also need to figure out a way to handle variables and
declarations in let expressions. For example, let x = d3 in x#x
end should return either {1}, or {2,2} or
{3,3,3} depending on the random number. This is because
d3 returns one of x = 1, 2 or 3. Hence
x#x is interpreted respectively as 1#1, 2#2, or
3#3. One way to accomplish this would be to keep an environment (like
the ML scratch paper) to store the latest bound values for a variable. A
different way to do it would be to use the substitution model learned in
class where unbound occurrences of a variable are replaced with its value
after evaluation. Note that because the same expression can evaluate
to more than one value (for example, d6), we must evaluate before
substituting.
Hint: If your code starts to crawl for
(2000 # (2000 # d1)), consider optimizing the multiset
functions that are involved.
If optimizing doesn't help, you may need to change your multiset
representation to a more compact form.
eval/Evaluator.sml and multiset/ms.sml.
Attach additional documentation in an ASCII file doc1.txt.
Implement the function Distribution.eval :
AbSyn.exp -> AbSyn.value AbSyn.Bag
The returned bag should represent the distribution for the roll expression. We will define the distribution as a multiset with the following property.
sum(2#d6). The sample space is {2, 3, ..., 12}. Consider I =
4. Then Ai is the event that sum(2#d6) = 4. Pr(Ai) = 3/36 since the only favorable cases
among the 36 possible combinations are sum({1,3}), sum({3,1}) and
sum({2,2}). Hence the
frequency of 4 in the distribution should be 3.
Expression |
Sample Space |
d6 |
{1, 2, 3, 4, 5, 6} |
2#d3 |
{{1, 1}, {1, 2}, {1, 2}, {1, 3}, {1, 3}, {2, 2}, {2, 3},
{2, 3}, {3, 3}}
|
sum(2#d6) |
{2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 7, 7, 7, 7,
7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 11, 11, 12}
|
d3#d3 |
{{1}, {2}, {3}, {1}, {2}, {3}, {1}, {2}, {3}, {1}, {2}, {3},
{1}, {2}, {3}, {1}, {2}, {3}, {1}, {2}, {3}, {1}, {2}, {3},
{1}, {2}, {3}, {1, 1}, {1, 2}, {1, 2}, {1, 3}, {1, 3}, {2, 2},
{2, 3}, {2, 3}, {3, 3}, {1, 1}, {1, 2}, {1, 2}, {1, 3}, {1, 3}, {2, 2},
{2, 3}, {2, 3}, {3, 3}, {1, 1}, {1, 2}, {1, 2}, {1, 3}, {1, 3}, {2, 2},
{2, 3}, {2, 3}, {3, 3}, {1, 1, 1}, {1, 1, 2}, {1, 1, 2},
{1, 1, 2}, {1, 1, 3}, {1, 1, 3}, {1, 1, 3}, {1, 2, 2}, {1,
2, 2
}, {1, 2, 2}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3}, {1, 2, 3},
{1, 2, 3}, {1, 2, 3}, {1, 3, 3}, {1, 3, 3}, {1, 3, 3}, {2,
2, 2}, {2, 2, 3}, {2, 2, 3}, {2, 2, 3}, {2, 3, 3}, {2, 3,
3}, {2, 3, 3}, {3, 3, 3}}
|
sum(d3#d3) |
{1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 9}
|
if d3=3 then d2 else d1 |
{1, 1, 1, 1, 1, 2} |
d3#d3 by hand and figure out why it is what it is.
Also note that the sets given in these examples are the the smallest sets that
yield the correct probabilities. Your distribution may return a larger set
with extra copies of the elements, as long as it represents the correct
probabilities.
Hint: If you seem to be rewriting large chunks of code that you already wrote in Part 1, there is likely a better and shorter way to do this; look for ways to share code between the two parts. You are encouraged to make heavy use of the basis library.
Your Task: Complete eval/Distribution.sml. Attach
additional documentation in an ASCII file doc2.txt.
Implement DistributionPrinter, which prints the
distribution of a Roll expression in the following format. For every unique item
i with the frequency n in the distribution, it prints i
: ######## where the number of # marks is n.
When we are using bags for representing outcomes, remember
that ordering does not matter; for example, {1,2} is the same as {2,1}. Hence it
should only be printed once with the appropriate number of # marks.
Contents of the bags should be sorted, hence {2,1} should be printed as {1,2}. Also, integers should be printed before bags, and smaller bags should be printed before larger bags. In case of equal sized bags, they should be printed in the order of the smallest element; e.g., {1,2} comes before {1,3} and {1,1,4} comes before {1,2,3}.
Example: sum(d3#d3)
1 : #########
2 : ############
3 : ################
4 : ############
5 : ############
6 : ##########
7 : ######
8 : ###
9 : #
Example: let x = d6 in if x < 3 then least x {1,2,3} else d6 end (thanks Joel)
1 : ####
2 : ####
3 : ####
4 : ####
5 : ####
6 : ####
{1} : ######
{1, 2} : ######
Example: d(d2)
1 : ###
2 : #
Example: d(d6)
1 : ###################################################################################################################################################
2 : #######################################################################################
3 : #########################################################
4 : #####################################
5 : ######################
6 : ##########
Example: 2#d2
{1, 1} : #
{1, 2} : ##
{2, 2} : #
Example: d3#d2
{1} : ####
{2} : ####
{1, 1} : ##
{1, 2} : ####
{2, 2} : ##
{1, 1, 1} : #
{1, 1, 2} : ###
{1, 2, 2} : ###
{2, 2, 2} : #
Your Task: Modify toplevel/Util.sml to achieve the desired behavior.
Attach additional documentation in an ASCII file doc3.txt.
Implement the function Sample.eval :
AbSyn.exp -> AbSyn.value AbSyn.Bag
In Part 2, you implemented a brute force method for finding the
distribution. Even though the brute force method is accurate, it can
be slow. Sampling can be a more efficient way to approximate the
distribution. The idea is to generate many independent samples from the
distribution and use the number of times each outcome was generated as an estimate
of the actual distribution. For
example, to find the distribution of d6, imagine evaluating d6
ten times and
storing the results in the multiset. The result might be {1, 6, 4, 2, 5, 1,
3, 6, 3, 1}. You can see that this already approximates the true distribution. If instead of ten times, one sampled it 1000 times, then you would
get each number from 1 to 6 about 167 times.
Sampling is an approximate method. If a particular outcome is expected to occur n times on average after acquiring a given series of samples, the actual number of occurrences will usually be within about √n. For example, if you flip a coin 20000 times, you will rarely get exactly 10000 heads, but you will usually get between 9900 and 10100 heads. Therefore, your estimate of the probability of getting a head usually will be accurate to within 1% (in general, accuracy of roughly 1/√n). Polling is an example of using sampling to estimate a distribution. To get the usual desired accuracy of ±5%, pollsters call about 400 randomly chosen people because 1/√400 = 0.05. Thus, getting highly accurate information through sampling requires a lot of samples!
Hint: If you seem to be rewriting large chunks of code that you already wrote in Part 1 or Part 2, there may be a better and shorter way to do this. You are encouraged to make heavy use of basis library functions and the functions from the previous parts.
Your Task: Complete eval/Sample.sml. Attach additional
documentation in an ASCII file doc4.txt.
Specify and implement a pseudorandom number generator using the linear congruential multiplier technique described in this section.
Dice rolling requires randomness. If each possible die roll does not occur with equal probability, one player may gain an advantage in winning a game. To level the playing field, we need to simulate a die roll by generating a number with a uniform distribution, meaning each possible value occurs with equal probability. We will call the method used to generate such a number a random number generator.
One problem in using computers for dice rolling is that computers do not have randomness built into them. We can try to approximate such a number with some kind of algorithm, but generating truly random numbers with a deterministic algorithm is impossible. Sometimes programmers try to solve this by generating "random" numbers from the value of the system clock. This method breaks down when a program asks for random numbers rapidly in succession, or requests a random number periodically at regular intervals.
Although a deterministic computer can never truly generate such a random
number, it is possible to generate numbers that seem to be random to an observer
who does not know how they are generated. Several algorithms
are known to generate so-called pseudo-random numbers, numbers that
approximate a uniform distribution. One simple implementation is based
on linear congruential multipliers. Without
getting into the mathematics, the algorithm functions by
starting with some seed value. The algorithm then computes a
sequence of random numbers x1,
x2, x3, ...
deterministically based on that seed. Given a good seed, values tend
to occur with approximately equal probability. The algorithm computes the sequence as
follows:
seedHere a, c, and m are fixed parameters for the multiplier. Even though the new number xi+1 depends on the old number xi, the other operations reduce the dependence significantly.
It is clear that not all values of a,
c and m
generate good pseudo-random numbers. For example a=0, c=2 will make the generator
always return 2. If a=1, c=1 then
the generator is a counter that increments by 1 every time. Some choices of a
and c will cause the sequence of xi
to wrap back to the original seed quickly, which would be bad because the
random numbers will also repeat. Ideally all m
possible values of xi
will be visited before the sequence repeats. The choice of
a=31421, c=314159262 is supposed to
give a random distribution according to Knuth. You must specify the
signature for and implement the structure Random that uses the
values of a and c
above along with seed = 312
and m = 231-1. You are
not allowed to use the Random or Rand structures provided by the Basis
Library.
Given a pseudo-random number generator, you will need to use its output xi (a number between 0 and m-1) to construct random die rolls. When generating a die roll for an n-sided die, it is tempting to use xi mod n. This would be a bad idea because it effectively reduces the LCM modulus from m to n. A better approach is to start by computing (xi*n)/m.
Note: You may find the IntInf
structure provided by the basis library helpful for manipulating large numbers (same as LargeInt).
Your Task: Complete lcm/Random.sml. You will need to write
the specification and implementation for your random number generator from
scratch. Writing a good specification is very important for this part. Attach
any additional
documentation in an ASCII file doc5.txt.
In class we saw a data abstraction for polynomials. For this problem you will prove that the implementation of the addition operator on polynomials works correctly. The signature for polynomials looks as follows:
signature POLYNOMIAL = sig (* Overview: A poly is a polynomial with integer coefficients. * For example, 2 + 3*x - 5*x3. *) type poly (* plus(p, q) is p+q. *) val plus: poly*poly -> poly ... end
Here is an implementation showing just the representation and the code for plus:
structure Polynomial :> POLYNOMIAL = struct type poly = int list (* AF: [a0,...,an] represents a0 + a1*x + a2*x2 + ... + an*xn * [] represents 0 * RI: if the list is not empty, its last element is not zero *) fun plus(p: poly, q: poly): poly = case (p,q) of (p, nil) => p | (nil, q) => q | (a::p', b::q') => case (a+b)::plus(p',q') of [0] => [] | r => r end
Prove by induction that this implementation of plus is correct:
- State the condition to be proved.
- Express this condition as a proposition in terms of an integer n. Hint: let n be the length of the shorter of the two lists
pandq.- Show that
plusworks correctly in the base case (what is n for the base case?)- Prove the induction step. Remember to establish that the rep invariant holds on output!
Your Task: Turn in a file polynomial.txt in simple ASCII
format containing solutions to parts a–d. Note: this is a good
problem to do as a warm-up for the prelim.
The parameters a and c
that are used to generate pseudo-random numbers are generally chosen only if
they pass a number of tests of randomness. We have implemented one such test in Warm.sml.
We use your LCM to pick random numbers. Complete the rand function in lcm/Warm.sml to use your implementation. For
each pair of random numbers, we check if the numbers are coprime or not. A
pair of numbers (a, b) is called coprime if GCD(a,b) =
1, GCD being the
greatest common divisor. We keep track of the percentage of such pairs that
are coprime. Denote this percentage as P. We then compute M =
√6/P. What is the true value of this M?
Due to the pseudo-randomness of the LCM, you may need to run
Warm.apple() multiple times with different values of a and c for your LCM.
For good choices of (a, c) the returned values will all lie in the vicinity of the true M. If the returned
value for some a and c lies really far away from all the other values, you can conclude that the (a,
c) pair generated noticeably nonrandom numbers.
In the board game Risk™, an attacker's army consisting of n soldiers and a defender's army consisting of m soldiers go to war according to the following dice language. The attacker rolls 3 (6-sided) dice, of which the greatest two values are retained. Call these values A1 and A2 where A1 is the larger of the two. The defender rolls (at most) 2 dice. Call these values D1 and D2 where D1 is the larger of the two. Now, if Ai≤Di the attacker loses one soldier. Otherwise, the defender loses one soldier. This continues until one party has no soldiers left.
Assuming that the defender rolls exactly two dice and attacker rolls 3 dice; write a dice language program that returns the multiset {1, 1} if the attacker loses 2 soldiers, {1, 2} if the attacker and defender both lose one soldier each, and {2, 2} if the defender loses two soldiers. Compute the distribution for the program you wrote and determine whether the Risk dice roll is partial towards attackers or towards defenders.
Your Task: Enter your solution in karma/karma.txt