This problem set has four parts. In Part 1, you will implement a plotter. The plotter will take user generated expressions and generate PostScript output that a printer or PostScript viewer understands. We are providing you with tools to parse input expressions into AST that you can interpret.
It is strongly encouraged that you work with one partner for this assignment. When you find a partner please form a group on CMS immediately. If you do not have a partner, you may post on the newsgroup to find one.
You will be implementing a plotter for general equations on variables x and y. Thus, the plotter will be able to handle equations where y is not a function of x, such as the equation x3 + y3 = 3xy, known as the Folium of Descartes. On this equation, the plotter will generate a plot that looks like this:
Your plotter will attempt to find the points in a region that satisfy a given equation. The trick is to interpret the equation as a function of x and y which has zeros at the places that the equation is true. For example, the equation above is true wherever the function f(x,y) = x3 + y3 - 3xy is equal to zero. Fortunately, you just implemented interval arithmetic in PS3, which is useful for efficiently finding function zeros. Of course, you'll want to be sure to fix any bugs that you had in PS3, because otherwise there will be bugs in PS4.
The strategy for finding zeros is as in PS3: evaluate the function on a region of its domain (the plane) using interval arithmetic. If the result interval contains zero, there may be a zero of the function within that region. We then recursively subdivide this region into smaller subregions, and search for a zero within them. There is more than one way to subdivide into subregions, but the rule of thumb is that the subregions should be similar in size. If the interval doesn't contain zero, the function cannot either, because interval arithmetic is conservative.
For example, consider the equation y = x - 1, plotted on the rectangle from (-8, -8) to (8, 8). We want to plot the zeros of the function y - x + 1. Evaluating this function on the intervals x = [-8,8] and y = [-8,8], we get:
[-8, 8] - [-8, 8] + [1, 1] = [-15, 17].
The resulting interval [-15, 17] contains zero. Thus, we subdivide the x and y regions and recurse.
Your program will continue to refine the subregions containing solutions to the function until it reaches a predefined maximum recursion depth. At maximum depth, the program still has a small box that presumably contains a zero. The program then draws a line to approximate the location of the zero. This is done by checking for zeros along the four sides of the box, with a similar recursive approach. Once zeros are located to within the required numerical precision, lines are drawn connecting the edge zeros.
We have provided you some framework for this project. It's up to you to
implement two modules: Lines and Plotter.
Lines will implement at least a signature with at least one operation:
signature LINES = sig type lines type interval = Interval.interval (* findLines(e, i1, i2, depth) generates lines representing the * a plot of the equation e over the x,y ranges defined by the * intervals i1 and i2. The maximum recursion depth is depth. *) val findLines: Eqn.expr * interval * interval * int -> lines end
Plotter will implement the signature:
signature PLOTTER = sig (* plot(lns, stream) writes a series of PostScript commands * to stream, where each command draws a line represented by lns. *) val plot: Lines.lines * TextIO.outstream -> unit end
You will use Lines.findLines to generate
a representation of all the lines to be plotted. How you choose to
represent lines is up to you. You may want to add more operations to the
LINES signature; think carefully before doing so.
The output of the plotter program is a program written in the PostScript programming language, written to the file out.ps. PostScript is a stack-based programming language that is understood by many printers and can be converted to other formats such as PDF. To help you generate PostScript, we have provided PostScript code that draws the axes for the plot and that can draw lines between two points on the plot. Your job is to generate PostScript code that can be inserted into the template code found in the skel.ps.
Three functions are defined in skel.ps that your code can use. (Note that as a stack-based language, PostScript applies functions in postfix order: the function name comes after its argument.)
x0 x1 y0 y1 setboundsSet up the plot to have the x range [x0,x1] and the y range [y0,y1], and draw the axes and labels for the plot.
x0 y0 x1 y1 drawlineDraw a line on the plot between (x0,y0) and (x1,y1) Requires that the plot is already set up.
x0 y0 x1 y1 filledboxDraw a solid black box in the plot, filling all points in [x0,x1]×[y0,y1]. Requires that the plot is already set up. This function may be useful in developing and debugging your code.
0 1 0 1 setbounds 0 0 1 1 drawline
At the end of the PostScript code, the command showpage tells the printer that the page is complete. The provided main program already generates this for you.
You will implement Plotter.plot, which generates the PostScript
code to be inserted into the template. If you want to explore or modify
skel.ps, you can, but this is not necessary. For more information
regarding PostScript check out http://en.wikipedia.org/wiki/PostScript.
You will call your plotting code from the main function
in relplot.sml
Compile your code using sml sources.cm. This will
generate a binary relplot.x86-<OS>, which
executes the main function in relplot.sml.
To run this program, type:
sml @SMLload=relplot.x86-<OS> <expr> <xMin> <yMin> <xMax> <yMax> [<depth>]
If you are running on a non-x86, you'll need to give a different extension for the file to load. You can write a script (.bat) file to do all this for you if you like.
Some helpful demonstrations:
 X^2 + Y^2 = 1 depth = 1 |
 X^2 + Y^2 = 1 depth = 2 |
 X^2 + Y^2 = 1 depth = 5 |
 X^2 + Y^2 = 1 depth = 7 |
 Y = |ln X| depth = 1 |
 Y = |ln X| depth = 2 |
 Y = |ln X| depth = 5 |
 Y = |ln X| depth = 8 |
Here are some more equations you may find interesting to plot and that you can test your code on:
A “flower”: (sqrt(x^2 + y^2) - 1/2)^5 = 4yx^3 - 4xy^3
A “Jellyfish”: ((xy(x-y)(x+y)(x^2+y^2-4))^2 - 1) = 1
CVS: We ask you to use CVS while developing code with your partner. CVS is a popular, convenient versioning system that allows you and your partner to share code in a common repository. It allows you to share common code, commit your code into the repository, or update your version with the changes of your partner.
To do: Submit a file log file cvslog showing your cvs activity during the assignment. For this, look into the "cvs log" command. Submitting photos of you and your partner exchanging a flash drive does not count.
Using CVS
Obtaining a CVS repository
Prove that the following code finds the
minimum value in a tree t, or NONE in the case of an empty tree.
Hint: Prove that the specification of least' is correct.
datatype tree = Node of (tree * int * tree) | Null
fun least(t:tree): int option =
let
(* least'(t, theLeast) is NONE if t is Null and theLeast is NONE.
* Otherwise, if theLeast is SOME(x), least'(t, theLeast) is SOME(y),
* where y is the minimum over all elements in t and x *)
fun least'(t: tree, theLeast: int option) =
case (t, theLeast) of
(Null, _) => theLeast
| (Node(l,v,r), NONE) => least'(l, least'(r,SOME(v)))
| (Node(l,v,r), SOME(lst)) =>
least'(l, SOME(Int.min(lst, valOf(least'(r,SOME(v))))))
in
least'(t, NONE)
end
To do: Submit part2.txt
| For n > 1, | T(n) = H(n) + T(n/2) |
| H(n) = H(n−1) + 1 | |
| T(1) = H(1) = 1 | |
fast:
fun fast(lst: int list): int =
case lst of
[] => 0
| [x] => x
| _ => let val (l1: int list, l2: int list, _) =
foldl
(fn (x:int, (l1:int list, l2:int list, toggle: bool)) =>
if toggle then (l1@[x], l2, not toggle)
else (l1, l2@[x], not toggle))
([], [], false)
lst
in
(fast l1) + (fast l2) + (fast l1) + (fast l2)
end
fast.
lst.
To do: Submit part4.txt