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:
... × ...
average(... , ...)
sin(pi × ...)
cos(pi × ...).
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.
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.sin, as well as the ﬂoating-point value
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
signature EXPR = sig 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
The code in
art.sml is the driver for the entire program; it includes the
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) -> unitThe 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))
12345 (without any spaces or newlines).
Test your code by producing a grayscale picture of the expression
look at the function
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).
Your next programming task is to fix the definition of
build : int * Random.rand -> Expr.exprin
art.sml. The first parameter to
buildis 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
Randomstructure to pull out new random numbers from this generator. The implementation of
Randomshouldn’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
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
Art.doGray : int * int * int -> unit Art.doColor : int * int * int -> unitEach takes a maximum depth, and two integers that together form the seed for the random-number generator.
Art.doGraygenerates an image of a random function and emits it as a grayscale image in a
Art.doColorcreates three random functions and uses them to emit a color image
.ppmfile. 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
.pngformat; see the submission information below.
signature RANDOM = sig 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;
Create a new file,
fexpr.sml. Like the file
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
function becomes much, much simpler than in dexpr.sml. Unfortunately, the
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
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
fexpr.sml, and recompile.
EXPR signature with three more expressions forms (be creative!); add the corresponding
implementations to both the
fexpr.sml files; and extend
use these new forms.
There are three requirements on the new expression forms that you create
buildfunctions should have type
expr*expr*expr -> expr.
Math.atan2, ... ) is not creative.
(... + ... + ...)/3or
sin(2 × pi × ...)) are not creative.
Make sure to comment your extensions in the
EXPR signature, and to test the implementations in both
The submission process has two parts:
.cmcode files, even those you haven't changed, so that the graders can easily compile and run your program.
convert <picture-filename> <picture-name>.png.