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.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 = 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 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) -> 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))
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).
Your next programming task is to fix the definition of
build : int * Random.rand -> Expr.exprin
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 -> unitEach 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 = 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 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
build
functions should have type expr*expr*expr -> expr
.
Real.abs
, Math.sqrt
, Math.atan2
, ... ) is not creative.
(... + ... + ...)/3
or sin(2 × pi × ...)
) are not creative.
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:
.sml
and .cm
code files,
even those you haven't changed, so that the graders can easily
compile and run your program. convert <picture-filename> <picture-name>.png
.