- Checkpoint: Complete, commit, and push parts 0-3 (on-time submission counts for grade) by 11:00pm Thursday 8 October.
- Checkpoint: Start on part 4 by 11:00pm 8 Thursday October.
- Due: 11:00pm Wednesday 14 October.
- Starter files:
- fork wellesleycs251 / cs251-art
- add bpw as admin
- Parts 0-3 in
basics.sml, Part 4 in
hg addyour favorite random art
- Estimate the time you spent on each section in
- Commit and push your completed work to your Bitbucket fork.
- Relevant reading:
- All problems fall under the standard collaboration policy. You may discuss ideas with each other but your writing and code must be your own.
This assignment will familiarize you with Standard ML, basics of static type-checking and type inference, datatypes and pattern-matching, and working with abstract representations of simple programs. You will also produce art!
- 0. First Functions (10 points)
- 1. Types (25 points)
- 2. Zipping (15 points)
- 3. Trees (20 points)
- 4. Random Art (30 points)
Take some time to read through our introductions to Emacs and SML/NJ. Emacs and SML Mode provide great support for working with SML programs and the SML interpreter, including features like clicking on errors to jump to their source code line, plus clear syntax highlighting and indentation. Setting up the pieces is a little tricky, so we encourage you to use a provided CS251 computing environment to save the fuss.
0. First Functions (10 points)
Define a function
squmthat takes a nonnegative integer
nand sums the squares of all numbers from
ninclusive. The snippet below shows a call to
squmin the SML REPL. The first line is an expression from the user; the second is output from the REPL. The REPL always binds your expression to the variable
it, unless you write out a whole binding yourself. Don’t forget to type
;at the end of each line, otherwise the REPL thinks you are still entering your expression, continuing on the next line.
- squm (4); val it = 30 : int - squm (5); val it = 55 : int
Define a function
duplistythat takes an element
eof any type and a non-negative integer
nand returns a list containing
- duplisty ("moo", 4); val it = ["moo","moo","moo","moo"] : string list - duplisty (1, 2); val it = [1,1] : int list - duplisty (duplisty("cow", 2), 2); val it = [["cow","cow"],["cow","cow"]] : string list list
1. Types (25 points)
Explain the ML type for each of the following bindings:
fun f1 (x,y) = 4 * x + y - x div 4 fun f2 (x,y) = y * y / 2.0 fun f3 (f,x) = case x of NONE => NONE | SOME y => f y fun f4 (f,x) = f(f(x)) fun f5 (x,y,b) = if b(y) then x else y
Try to determine the type yourself, but feel free to check using the
smlREPL. In addition to giving the type, you must also explain in detail why the type is correct and how you determined the type.
2.0has the type
- the multiplication operator works either on two
ints or two
divis integer division.
/is floating point division (on
What is the type of the following ML function?
fun append (xs,ys) = case xs of  => ys | x::xs' => append (xs',ys)
Write one or two sentences to explain succinctly and informally why append has the type you give. This function is intended to append one list onto another. However, it has a bug. How might knowing the type of this function help the programmer to find the bug?
2. Zipping (15 points)
The toughest part of using ML is dealing with type-checker error messages. Often they are easy to decipher, but sometimes, the place the error is caught is very far away from the true source of the error. Get help from the course staff if messages make no sense!
Common sources of confusing errors:
- Mixing up
- Precedence gotchas with nested
- Missing parentheses around patterns: parenthesize all patterns in
funbindings. The structure of
casepatterns and syntax allows looser parenthesization without issues, but
fun f x::xs =is parsed as something like
fun (f x)::xs, not what you meant! Parenthesize:
fun f (x::xs) =.
Write the function
zip : ('a list * 'b list) -> ('a * 'b) listto compute the product of two lists of arbitrary length. You should use pattern matching to define this function. If the lists have different lengths,
zipshould raise an exception.
- zip ([1,3,5,7], ["a","b","c","de"]); val it = [(1,"a"),(3,"b"),(5,"c"),(7,"de")] : (int * string) list
Write the inverse function,
unzip : ('a * 'b) list -> ('a list * 'b list), which behaves as follows:
- unzip [(1,"a"),(3,"b"),(5,"c"),(7,"de")]; val it = ([1,3,5,7], ["a","b","c","de"]) : int list * string list
Is it possible to write a function
zip_anythat takes a list of any number, n, of L-length lists and zips them into a single L-length list of n-tuples?
- If so, write such a function:
zip_any [list1,list2,...,listn]should return a list of n-tuples no matter what n is.
- If not, explain why.
- If so, write such a function:
3. Trees (20 points)
Binary trees can be represented by the following datatype in ML:
datatype 'a bintree = Empty | Node of 'a * 'a bintree * 'a bintree
For example, this tree has root
7, internal nodes
9, and leaves (from left to right)
21. It also happens to be a binary search tree.
val bt = Node (7, Node (1, Empty, Node (3, Empty, Empty)), Node (9, Node (8, Empty, Empty), Node (21, Empty, Empty)))
Write a function
sumtree : int bintree -> intthat sums all node values in the given binary tree.
- sumtree bt; val it = 49 : int - sumtree Empty; val it = 0 : int
Write a function
maptree : ('a -> 'b) * 'a bintree -> 'b bintreethat takes a mapping function and a binary tree and returns a new binary tree of the same shape, where each element is the result of applying the mapping function to the corresponding element in the original tree.
- maptree (String.size, (Node ("like", Node ("I", Empty, Empty), Node ("programming languages", Empty, Empty)))); val it = Node (4, Node (1, Empty, Empty), Node (21, Empty, Empty)) : int bintree
Write a function
inorder : 'a bintree -> 'a listthat takes a binary tree and returns a list of its values according to an inorder (left to right) traversal. Do not use list append operations. Use only
::to construct lists.
- inorder bt; val it = [1,3,7,8,9,21] : int list - inorder (Node (3, Node (4, Empty, Empty), Empty)); val it = [4,3] : int list - inorder (Node (251, Empty, Empty)); val it =  : int list - inorder Empty; stdIn:4.1-4.14 Warning: type vars not generalized because of value restriction are instantiated to dummy types (X1,X2,...) val it =  : ?.X1 list
The strange type and accompanying warning in the last case show that the type checker cannot infer the concrete element type of the binary tree
Empty, since there is no carried data. As a result its return type is not concrete either. It might seem that the empty tree or list should should have type
'a listand be usable for any binary tree or list type, but there is an interesting reason this is not safe. We will study this reason (and the resulting value restriction) later. For now, we can avoid this with:
- inorder (Empty : int bintree); val it =  : int list
Write a function
forall : ('a -> bool) * 'a bintree -> boolthat returns true if the given function returns true on every value in the tree. Note that boolean and is
x andalso yand boolean or is
x orelse yin SML. (Peculiar, but it’s just syntax.)
- forall (fn x => x > 0, bt); val it = true : bool - forall (fn x => x > 0, Node (2, Node (~1, Empty, Empty), Empty)); val it = false : bool - forall (fn x => x > 0, Empty); val it = true : bool
4. Random Art1 (30 points)
Your job is to write an ML program to construct and plot randomly generated functions used to create random art. This program will apply ideas in grammars, parse trees, and their representation as ML datatypes. You will implement a very simple interpreter for a small language of plottable functions as well as generators of programs in this language.
The language for the functions can be described by a simple grammar:
e ::= x | y | sin πe | cos πe | (e+e)/2 | e*e
Any expression generated by this grammar is a function over the two variables x and y. Note that any function in this category produces a value between -1 and 1 whenever x and y are both in that range.
We can characterize expressions in this grammar with the following ML datatype:
datatype expr = VarX | VarY | Sine of expr | Cosine of expr | Average of expr * expr | Times of expr * expr
Note how this definition mirrors the formal grammar given above; for
instance, the constructor
Sine represents the application of the
sin function to an argument multiplied by π. Interpreting
abstract syntax trees is much easier than trying to interpret terms
Complete the following tasks in
Printing Expressions: Write a function
exprToString : expr -> stringto generate a printable version of an expression. For example:
- exprToString (Times(Sine(VarX),Cosine(Times(VarX,VarY)))) val it - "sin(pi*x)*cos(pi*x*y)" : string
The exact formatting is left to you. String concatenation is performed with the
^operator in SML. Test this function on a few sample inputs before moving to the next part.
Evaluating Expressions: Write the function
eval : expr -> real*real -> realto evaluate the given expression at the given (x, y) location. Note that
evalis in curried form [covered in class soon if not yet]. You may want to use the functions
Math.sin, as well as the floating-point value
Math.pi. (Note that an expression tree represented, e.g., as
Sine(VarX)corresponds to the mathematical expression sin πx, and the
evalfunction must be defined appropriately.
Test this function on several sample inputs before moving on to the next part. Here are a couple to start (try lots more):
- eval (Sine(Average(VarX,VarY))) (0.5,0.0); val it = 0.707106781187 : real - eval sampleExpr (0.1,0.1); val it = 0.569335014033 : real
Driver Code: The
art.smlfile includes the
doRandomColorfunctions, which generate grayscale and color bitmaps respectively. These functions need to iterate over all the pixels in a (by default) 301 by 301 square, which naturally would be implemented by nested for loops. In
art.sml, complete the definition of the function
for : int * int * (int -> unit) -> unit
The argument triple contains a lower bound, an upper bound, and a function; your code should apply the given function to all integers from the lower bound to the upper bound, inclusive. If the greater bound is strictly less than the lower bound, the call to
forshould do nothing. Implement this function using tail recursion.
unitdescribes a singleton value
(), which is pronounced unit and is used wherever no value is needed. Wherever unit occurs, side effects are most likely involved. For example, the
string -> unit. It prints a string as a side effect and returns
()value is necesary because ML has no “statements,” only expressions: every function must return some value.
The SML expression
e1; e2is the sequencing expression. Like
(), this expression appears only where side effects are desired. Its evaluation rule is:
e1to a value and discard it.
- Then evaluate
e2to a value and use its result as the result of the whole expression.
Test your code with a call like the following:
for (2, 5, (fn x => (print ((Int.toString(x)) ^ "\n"))));
It should print out the numbers 2,3,4, and 5.
Note: The type assigned to your
forfunction may be more general than the type described above. How could you force it to have the specified type, and why might it be useful to do that? (You don’t need to submit an answer to this, but it is worth understanding.)
Test your implementation by producing a grayscale picture of the expression
sampleExpr: call the
emitGrayscalefunction from the REPL. Look at
doRandomGrayto see how this function is used. An
uncaught exception OutOfRangewhile producing a picture indicates that your
evalfunction is returning a number outside the range [-1,1].
You can view
.pgmfiles, as well as the
.ppmfiles described below, in the CS 251 computing environments with the
eogprogram. To view the output elsewhere, convert the file to PNG format with the following command:
convert art.pgm art.png
The convert utility will work for both
Generating Random Expressions and Art: Your next programming task is to complete the definition of a function that builds random expressions recursively:
build : int * randgen -> expr
The first parameter to
buildis a maximum nesting depth for the resulting expression. A bound on the nesting depth keeps the expression to a manageable size. When you reach the cut-off point (i.e.,
depthis 0), you can simply return an expression with no sub-expressions, such as
VarY. If not yet at the cut-off, randomly select one of the forms of
exprand recursively create its subexpressions.
The second argument to
buildis a function of type
randgen. As defined at the top of
art.sml, the type
randgenis simply a type abbreviation for a function that takes two integers and returns an integer:
type randgen = int * int -> int
Given a function
rand (l,h)to get a number in the range
h, inclusive. Successive calls to that function will return a sequence of random values. Documentation in the code describes how to make a
makeRand. You may wish to use this function while testing your
Once you have completed
build, you can generate pictures by calling the function
doRandomGray : int * int * int -> unit
Given a maximum depth and two seeds for the random number generator, this function generates a grayscale image for a random image in the file
art.pgm. You may also run:
doRandomColor : int * int * int -> unit
Given a maximum expression depth and two seeds for the random number generator, this function creates three random functions (one each for red, green, and blue), and uses them to emit a color image
art.ppm. (Note the different filename extension).
A few notes:
A depth of 8 to 12 is reasonable to start, but experiment to see what you think is best.
If you find your art to be “boring,” consider this: If every sort of expression can occur with equal probability at any point, it is relatively likely that the random expression you get will be either
VarY, or something small like
Times(VarX,VarY). Since small expressions produce boring pictures, find some way to prevent or discourage expressions with no subexpressions from being chosen “too early”. There are many options for doing this — experiment and pick one that gives you good results.
The two seeds for the random number generators determine the eventual picture, but are otherwise completely arbitrary.
(Required) Extensions: Extend the
exprdatatype with at least three more expression forms, and add the corresponding cases to
build. The requirements for this part are that:
- these expression forms must return a value in the range [-1,1] if all subexpressions have values in this range;
- at least one of the extensions must be constructed out of 3
subexpressions, i.e., one of the new constructors for
expr * expr * expr; and
- they must not be possible to construct by combining existing expressions.
There are no other constraints; the new functions need not even be continuous. Be creative!
Make sure to comment your extensions.
Submitting: Submit your changes to the provided files and
hg adda couple of your favorite random art pictures. We will make a gallery.
The Random Art assignment is lightly adapted from a version by Steve Freund, based on versions by M. Dresner and Chris Stone. ↩