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:

`... × ...`

`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 ﬂoating-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

- Each must return a value in the range −1.0 to 1.0 when its arguments are within this range
- 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`

. - Your code must be creative.
- Simply looking through the Real and Math structures and adding calls to other standard
functions (
`Real.abs`

,`Math.sqrt`

,`Math.atan2`

, ... ) is not creative. - Simple variants of existing operators (e.g.,
`(... + ... + ...)/3`

or`sin(2 × pi × ...)`

) are not creative. - Functions that can be built out of existing functions (e.g., (... × ... × ...)) are not creative.

- Simply looking through the Real and Math structures and adding calls to other standard
functions (

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:

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

.