Types of Expressionist Art

• 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 art.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:
    • SML/Ocaml syntax and feature comparison
    • SML vs. Ocaml syntax
• Tools:
  • Mercurial
  • Emacs
  • SML/NJ
• 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 type-checking and type inference, datatypes and pattern-matching, 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)

0. First Functions (10 points)

1. Define a function squm that takes a nonnegative integer n and sums the squares of all numbers from 1 to n inclusive. The snippet below shows a call to squm 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 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

2. Define a function duplisty that takes an element e of any type and a non-negative integer n and returns a list containing n copies of e.

    - 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)

1. 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 type real (floating point)
   • the multiplication operator works either on two ints or two reals.
   • div is integer division.
   • / is floating point division (on reals).

2. 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)

1. 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

2. 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

3. Is it possible to write a function zip_any that 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.

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)))

1. 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

2. 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

3. 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.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 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

4. 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 is x andalso y and boolean or is x 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¹ (30 points)

See Spring 2015 art here.

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.

1. 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.

2. Evaluating Expressions: Write the function eval : expr -> real*real -> real to evaluate the given expression at the given (x, y) location. Note that eval is in curried form [covered in class soon if not yet]. You may want to use the functions Math.cos and 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 eval 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

3. Driver Code: The art.sml file includes the doRandomGray and doRandomColor 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. 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 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, the print function has type string -> 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 the emitGrayscale function from the REPL. Look at doRandomGray to see how this function is used. An uncaught exception OutOfRange while producing a picture indicates that your eval function is returning a number outside the range [-1,1].

4. Viewing Pictures:

   You can view .pgm files, as well as the .ppm files described below, in the CS 251 computing environments with the eog 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.

5. 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 cut-off point (i.e., depth is 0), you can simply return an expression with no sub-expressions, such as VarX or VarY. If not yet at the cut-off, randomly select one of the forms of expr and recursively create its subexpressions.

   The second argument to build is a function of type randgen. As defined at the top of art.sml, the type randgen 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 type randgen, call rand (l,h) to get a number in the range l to h, inclusive. Successive calls to that function will return a sequence of random values. Documentation in the code describes how to make a randgen function with makeRand. You may wish to use this function while testing your build function.

   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 VarX or 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.

6. (Required) Extensions: Extend the expr datatype with at least three more expression forms, and add the corresponding cases to exprToString, eval, and build. The requirements for this part are that:

   1. these expression forms must return a value in the range [-1,1] if all subexpressions have values in this range;
   2. at least one of the extensions must be constructed out of 3 subexpressions, i.e., one of the new constructors for expr must carry expr * expr * expr; and
   3. 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.

7. Submitting: Submit your changes to the provided files and hg add a couple of your favorite random art pictures. We will make a gallery.