# RANDOM ART 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)))))))))

## Summary

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.

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

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

```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 =
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;
```

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

## Extensions

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

## Submission

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