Types of Expressionist Art
 Checkpoint: Complete, commit, and push parts 03 (ontime 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 / cs251art
 add bpw as admin
 Parts 03 in
basics.sml
, Part 4 inart.sml
 Submission:
hg add
your favorite random art Estimate the time you spent on each section in
time.txt
.  Commit and push your completed work to your Bitbucket fork.
 Relevant reading:
 SML References
 An anecdote about ML type inference, by Andrew Koenig
 For CS 235 concurrent enrollees: Ocaml vs. SML:
 Tools:
 Collaboration:
 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 typechecking and type inference, datatypes and patternmatching, and working with abstract representations of simple programs. You will also produce art!
Contents
 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
squm
that takes a nonnegative integern
and sums the squares of all numbers from1
ton
inclusive. The snippet below shows a call tosqum
in 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 variableit
, 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
duplisty
that takes an elemente
of any type and a nonnegative integern
and returns a list containingn
copies ofe
. 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
sml
REPL. In addition to giving the type, you must also explain in detail why the type is correct and how you determined the type.Note:
2.0
has the typereal
(floating point) the multiplication operator works either on two
int
s or tworeal
s. div
is integer division./
is floating point division (onreal
s).

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 typechecker 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
=
and=>
incase
expressions,fun
bindings, andfn
definitions.  Precedence gotchas with nested
case
expressions. (Parenthesize!)  Missing parentheses around patterns: parenthesize all patterns in
fun
bindings. The structure ofcase
patterns and syntax allows looser parenthesization without issues, butfun f x::xs =
is parsed as something likefun (f x)::xs
, not what you meant! Parenthesize:fun f (x::xs) =
.

Write the function
zip : ('a list * 'b list) > ('a * 'b) list
to compute the product of two lists of arbitrary length. You should use pattern matching to define this function. If the lists have different lengths,zip
should 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_any
that takes a list of any number, n, of Llength lists and zips them into a single Llength list of ntuples? If so, write such a function:
zip_any [list1,list2,...,listn]
should return a list of ntuples 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 1
and 9
, and leaves (from left to right) 3
, 8
, 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 > int
that 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 bintree
that 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 list
that 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 = [251] : int list  inorder Empty; stdIn:4.14.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 bintree
or'a list
and 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 > bool
that returns true if the given function returns true on every value in the tree. Note that boolean and isx andalso y
and boolean or isx orelse y
in 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 Art^{1} (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
directly.
Complete the following tasks in art.sml
.

Printing Expressions: Write a function
exprToString : expr > string
to 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 > real
to evaluate the given expression at the given (x, y) location. Note thateval
is in curried form [covered in class soon if not yet]. You may want to use the functionsMath.cos
andMath.sin
, as well as the floatingpoint valueMath.pi
. (Note that an expression tree represented, e.g., asSine(VarX)
corresponds to the mathematical expression sin πx, and theeval
function 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.sml
file includes thedoRandomGray
anddoRandomColor
functions, 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. Inart.sml
, complete the definition of the functionfor : 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
for
should do nothing. Implement this function using tail recursion.The type
unit
describes 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, theprint
function has typestring > unit
. It prints a string as a side effect and returns()
. The()
value is necesary because ML has no “statements,” only expressions: every function must return some value.The SML expression
e1; e2
is the sequencing expression. Like()
, this expression appears only where side effects are desired. Its evaluation rule is: Evaluate
e1
to a value and discard it.  Then evaluate
e2
to 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
for
function 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 theemitGrayscale
function from the REPL. Look atdoRandomGray
to see how this function is used. Anuncaught exception OutOfRange
while producing a picture indicates that youreval
function is returning a number outside the range [1,1].  Evaluate

Viewing Pictures:
You can view
.pgm
files, as well as the.ppm
files described below, in the CS 251 computing environments with theeog
program. 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
.ppm
and.pgm
files. 
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
build
is 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 cutoff point (i.e.,depth
is 0), you can simply return an expression with no subexpressions, such asVarX
orVarY
. If not yet at the cutoff, randomly select one of the forms ofexpr
and recursively create its subexpressions.The second argument to
build
is a function of typerandgen
. As defined at the top ofart.sml
, the typerandgen
is simply a type abbreviation for a function that takes two integers and returns an integer:type randgen = int * int > int
Given a function
rand
of typerandgen
, callrand (l,h)
to get a number in the rangel
toh
, inclusive. Successive calls to that function will return a sequence of random values. Documentation in the code describes how to make arandgen
function withmakeRand
. You may wish to use this function while testing yourbuild
function.Once you have completed
build
, you can generate pictures by calling the functiondoRandomGray : 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
VarX
orVarY
, or something small likeTimes(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
expr
datatype with at least three more expression forms, and add the corresponding cases toexprToString
,eval
, andbuild
. 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
must carryexpr * 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 add
a 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. ↩