CS 131: Programming Languages

cos(pi*sin(pi*(sin(pi*(avg(avg(cos(pi*((((cos(pi*cos(pi*cos(pi*y)))) * (sin(pi*avg(sin(pi*x), y * x)))) * ((((avg(y,y)) * x) * (avg(cos(pi*y), avg(y,y)))) * (((avg(y,y)) * (cos(pi*y))) * (x * (sin(pi*y)))))) * (sin(pi*avg(sin(pi*(cos(pi*x)) * (avg(x,y))), cos(pi*cos(pi*sin(pi*y))))))) * (avg(avg(avg(cos(pi*sin(pi*sin(pi*y))), cos(pi*sin(pi*avg(x,y)))), cos(pi*(cos(pi*avg(x,y))) * (sin(pi*x * y)))), avg((cos(pi*y)) * (avg(cos(pi*x * y), cos(pi*avg(y,y)))), avg((sin(pi*cos(pi*y))) * y,cos(pi*sin(pi*y))))))), cos(pi*sin(pi*x))), sin(pi*sin(pi*cos(pi*cos(pi*avg(avg(cos(pi*avg(sin(pi*x), avg(x,y))), sin(pi*avg(x * x,cos(pi*x)))), (cos(pi*sin(pi*y * y))) * (avg(avg(sin(pi*x), x * x), cos(pi*avg(y,x))))))))))) * (sin(pi*sin(pi*(cos(pi*avg(avg((sin(pi*cos(pi*x * x))) * ((avg(sin(pi*y), cos(pi*y))) * (cos(pi*cos(pi*x)))), sin(pi*cos(pi*cos(pi*x * y)))), (((sin(pi*avg(y,x))) * ((sin(pi*x)) * (y * y))) * (sin(pi*(cos(pi*y)) * (x * x)))) * (avg(avg(sin(pi*x * x), sin(pi*x * x)), avg(avg(sin(pi*y), cos(pi*y)), cos(pi*sin(pi*x)))))))) * (sin(pi*sin(pi*cos(pi*(cos(pi*sin(pi*x * y))) * (avg(sin(pi*y * y), sin(pi*avg(x,y))))))))))))) * (cos(pi*sin(pi*cos(pi*((cos(pi*sin(pi*((sin(pi*cos(pi*sin(pi*x)))) * (avg(cos(pi*cos(pi*x)), (cos(pi*y)) * (avg(x,x))))) * (sin(pi*((avg(x,x)) * (sin(pi*x))) * (avg(y * y,cos(pi*x)))))))) * (sin(pi*sin(pi*avg(cos(pi*sin(pi*(x * y) * (y * x))), (sin(pi*sin(pi*avg(x,y)))) * (avg(sin(pi*y * x), (y * x) * (cos(pi*x))))))))) * (sin(pi*cos(pi*y)))))))))


Suppose we take an expression in x and y, built by nesting simple primitives:

If we compute the value at any point with −1 ≤ x, y ≤ 1, the result will also be between −1 and 1. By scaling the answer to a grayscale value 0 to 255, we can plot the function in this 2-by-2 square. (From three such expressions, we can get red, green, and blue values for each point.) Surprisingly, every sufficiently complicated expression has a decent chance of being interesting! We can generate deeply-nested expressions completely randomly, see how they look, and keep the good ones.

For this assignment, you will complete a program that randomly generates and plots these complicated expressions.

Expression Evaluation

The code in dexpr.sml is an almost-complete implementation satisfying the EXPR signature (SML structure interface), shown below. In this implementation, expressions are represented as values from a datatype. Finish this code by writing the function

 real * real -> real 

that evaluates the given expression at the given (x, y) location. You will want to use the functions Math.cos and Math.sin, as well as the floating-point value Math.pi. Because the function definitions are inside a structure, remember that to access these functions from outside (e.g., when testing at the command line) you have to say Expr.eval or Expr.build_avg).

signature EXPR =
    type expr  (* type of expressions *)

(* All expressions should return values in the range [-1,1] when x and y also range over [-1,1]. *) val build_x : expr (* returns the expression for "x" *) val build_y : expr (* returns the expression for "y" *) val build_sinpi : expr -> expr (* creates sine (PI * given expr) *) val build_cospi : expr -> expr (* creates cosine (PI * given expr) *) val build_avg : expr * expr -> expr (* average of the two exprs. *) val build_times : expr * expr -> expr (* product of the two exprs. *)
(* Expression evalation at the given (x,y) point *) val eval : expr -> real*real -> real
(* Pretty-printer for expressions *) val ppexpr : expr -> unit
(* A sample reasonably complicated expression *) val sampleExpr : expr end

Finishing the Driver Code

The code in art.sml is the driver for the entire program; it includes the doGray and doColor functions, which generate grayscale and color bitmaps respectively. These functions want to loop over all the pixels in a 301 by 301 square, which naturally would be implemented by nested for loops. The bad news is that SML does not include for loops. The good news is that we can use higher-order functions to implement them. In art.sml, fix the definition of the function

for : int * int * (int->unit) -> unit 

The argument triple contains a lower bound, and 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. For example,
Art.for (1, 5, fn x => print (Int.toString x))

should print 12345 (without any spaces or newlines).

Test your code by producing a grayscale picture of the expression Expr.sampleExpr. (Hint: look at the function Art.emitGray.)

Note: There are two natural ways in SML to do something, throw away its result, and then do something else. You can either say let val _ = e1 in e2 end or you can use the expression form (e1 ; e2). The latter works because inside an expression, a semicolon acts exactly like the comma operator in C or C++. (It evaluates the first expression, throws away the result, and then returns the result of the next expression).

Generating the Random Expressions

Your next programming task is to fix the definition of

build : int * Random.rand -> Expr.expr
in art.sml. The first parameter to build is a maximum nesting depth that the resulting expression should have, and the second parameter is a random-number generator. (A bound on the nesting depth keeps the expression to a manageable size.) The second argument, a value of type Random.rand, is a random-number generator (which might be thought of as an infinite source of random numbers). You can use the functions in the Random structure to pull out new random numbers from this generator. The implementation of Random shouldn’t matter to you at all, but you will want to look at its interface: shown below.

If every sort of expression can occur with equal probability at any point, it is likely that the random expression you get will be either x or y, or something similarly small. Because small expressions produce boring pictures, you must find some way to prevent or discourage small expressions.

Once you have successfully recompiled with CM.make, you can test your code by running the functions

  Art.doGray : int * int * int -> unit 
  Art.doColor : int * int * int -> unit
Each takes a maximum depth, and two integers that together form the seed for the random-number generator. Art.doGray generates an image of a random function and emits it as a grayscale image in a .pgm file, while Art.doColor creates three random functions and uses them to emit a color image .ppm file. Depth 9 is a reasonable place to start, but experiment to see what you think works best. The two seeds for the random number generators determine the eventual picture, but are otherwise completely arbitrary. To view the output, you will probably need to convert this file to a .png format; see the submission information below.

signature RANDOM = 
   type rand   (* the internal state of a random number generator *) 
   (* create rand from initial seed *)
val rand : (int * int) -> rand (* convert state to and from string * fromString raises Fail if its argument * does not have the proper form. *) val toString : rand -> string val fromString : string -> rand
(* generate ints uniformly in [minInt,maxInt] *) val randInt : rand -> int
(* generate ints uniformly in [0,maxInt] *) val randNat : rand -> int
(* generate reals uniformly in [0.0,1.0) *) val randReal : rand -> real
(* randRange (lo,hi) generates integers uniformly [lo,hi]. * Raises Fail if hi < lo. *) val randRange : (int * int) -> rand -> int end;

An Alternate Representation

Create a new file, fexpr.sml. Like the file dexpr.sml that you were given, this file should contain a structure Expr satisfying the EXPR signature. In this version, the definition of the type expr should be not a datatype, but

   type expr = real * real -> real

That is, instead of the symbolic representation used by dexpr.sml, this implementation will represent each function in x and y directly as an SML function of two real arguments that gives you the expression's value (in the interval -1 to 1 inclusive) given the (x,y) coordinate. You should define all the functions required by the EXPR interface. In particular, the eval function becomes much, much simpler than in dexpr.sml. Unfortunately, the ppexpr function cannot be written successfully, since there’s no way to convert an SML function to a string. Thus, your implementation of this function can return something like the the string "<function>" or "unknown".

The build_XXX functions must then combine functions for the subexpressions into functions computing the whole expression. For example, build_times should return the “pointwise product” of two given functions (i.e., given two functions f and g, return a new function that, at each point, returns the product of f's and g's values.) Similarly build_x returns the function that produces the x coordinate for each point.

[Note: in some cases, you may have to write fn (x:real,y:real) => ... instead of just fn (x,y) => ... . Simple arithmetic expressions are among the rare exceptions where SML type inference has problems.]

To test your code, remove the name dexpr.sml from the file sources.cm and replace it with the name fexpr.sml, and recompile.


Extend the EXPR signature with three more expressions forms (be creative!); add the corresponding implementations to both the dexpr.sml and fexpr.sml files; and extend Art.build to use these new forms. There are three requirements on the new expression forms that you create

  1. Each must return a value in the range −1.0 to 1.0 when its arguments are within this range
  2. At least one of the three must be constructed out of three subexpressions, i.e., one of the new build functions should have type expr*expr*expr -> expr.
  3. Your code must be creative. For example, you can (but are certainly not required to) add a non-continuous operator.

Make sure to comment your extensions in the EXPR signature, and to test the implementations in both dexpr.sml and fexpr.sml .


The submission process has two parts:

  1. You must submit all of the .sml and .cm code files, even those you haven't changed, so that the graders can easily compile and run your program.
  2. Additionally, to receive credit for this assignment you must provide your favorite output file. To save space and improve portability, first convert your picture to PNG format, using the ImageMagick command convert <picture-filename> <picture-name>.png .