Assignment #4


For this assignment you have four possible options of what to do. Pick one and make sure that the comments at the top of your code not only identify you, but also tell me which option you have picked. These are challenging problems on a conceptual level though it is likely they will require less code than assignment #3. If you don't understand the concepts please ask me about them.

Binary Search Tree - If you pick this option, you will write a binary search tree in Scheme. The general idea of a binary search tree is that you have a set of nodes and each node can have two children, typically called left and right. The node stores a kley and a data element. All elements with keys "less" than the key in a node are off on the left side of the node. All elements with keys that are "greater" go to the right. In Scheme you can store a node as a list that looks like this (key value left right). Of course, left and right are subtrees that start with nodes. So a valid tree with integer keys might have 2 at the root, with 1 on the left and 3 on the right. This might look something like (2 data2 (1 data1 () ()) (3 data3 () ())). The empty lists show that the 1 and 3 nodes have no children. Leaving them out will cause problems since you can't signify only having a right child if you do that.

What I want you to submit for this assignment is code that can add to such a tree and search for elements in it. You don't have to do a remove since doing that well is harder. However, your tree should also be able to work with any type of data and any sortable keys. To make it "polymorphic", your add, search, and remove functions will take a function that is used for doing the comparisons. The comparator function should return 0 if the two values passed in are equal, a negative value if the first one is less, and a positive value if the first one is greater.

To help validate your tree you will also need to write functions to do the three standard traversals of your tree: pre-order, in-order, and post-order. These three traversals visit all the elements of the tree in specific ways. They all do a depth first traversal going left before right, but pre-order "visits" a node before going to the children, in-order visits between the children, and post-order visits after doing both children. These functions will be passed a visitor function that could do many things, but a printing function is one of the more standard things to do.

In all you need to write the following functions:

(add key data tree comp) - returns a new tree where the key data pair is added to the given tree using the provided comparator.

(search key tree comp) - returns the data from the first node that is found in the tree that matches the provided key.

(pre-order tree visitor) - applies the visitor to all elements in an pre-order way.

(in-order tree visitor) - applies the visitor to all elements in an in-order way.

(post-order tree visitor) - applies the visitor to all elements in an post-order way.

For extra credit you can also add a remove function that has the following form.

(remove key tree comp) - returns a tree where the first element found with a matching key has been removed.

LL-Parser for CF Grammar - Chompsky grammars are a fundamental part of computer science. There are four types of grammars with different levels of power: regular expressions, context free, context sensitive, and recursively emunerable. Context free, or CF grammars are the basis for the sytntax and parsing of all modern programming languages. We can describe a CF grammar as a set of productions where each production has a "non-terminal" on the left and a set of possible things it could become on the right. For example:

S -> PC
P -> aPb | ab
C -> cC | c

is a grammar that generates the set of strings we might describe as a^nb^nc^m. This is a string with an equal number of a's and b's followed by some number of c's. More specifically n and m must each be at least one. So the following strings are in the language generated by this grammar: abc, aabbc, abccc, aaabbbcccccccc, aaaabbbbc.

There is a subset of these grammars that are called LL-grammars. These grammars have to follow certain rules, but they make it easier to parse the language. In order to be LL a grammar can't be left-recursive. That is to say that the left most symbol in the product can't be the same non-terminal we are producing from (nor can you have longer cycles that get back to it as the left-most item). Also, the list of products off of a production must be distinguishable by the first element in it. So the grammar above fails this in both the P and C productions. A grammar that passes these requirements is the following:

S -> ABC
A -> aA | x
B -> bB | y
C -> AC | c

If you choose this assignment you will write functions to implement an LL parser. To see how this works, imagine we have the string aaxbyaxc as our input. The derivation starts proceeds as follows

S
ABC
aABC
aaABC
aaxBC
aaxbBC
aaxbyC
aaxbyAC
aaxbyaAC
aaxbyaxC
aaxbyaxc

This is a left-most derivation. So it replaces the first non-terminal going from left to right each time. Given the rules of an LL-grammar, You can always tell what the next step is just by looking at the grammar and the input string. The way your program will work the "strings" will actually be lists. The grammar will be stored as a list of productions where each production is a list that has the non-terminal followed by lists for each of tht things the non-terminal could become. So the grammar above would look something like this:

((S (A B C)) (A (a A) (x)) (B (b B) (y)) (C (A C) (c)))

Of course, this wouldn't quite work since Scheme isn't case sensitive so technically we'd have to put in parentheses which I didn't type here. You will create a curried function, parse-step, to do the parsing. This function takes three arguments, one at a time. The first argument is the grammar it is parsing with. The second argument is the list you want to end up with. The third argument is the list you have currently. This function will return the list that is the next step in the parse. So you could call it directly with

(((parse-step grammar) final-list) current-list)

to get the next step. Since it is curried though, you could call it with the first two arguments and bind it to those then use that repeatedly to go through the parse.

In addition to parse-step, I want you to write a full-parse method that isn't curried and takes the grammar, final results, and start list and runs the parse until it gets the final result, calling display at each iteration.

(full-parse grammar final-list start-list)

Obviously you will need to write a number of other helper functions to get this to work as well.

For extra credit you can write two different parse functions that don't have the limitation of requiring that the productions start with different terminal characters. The LL format is nice because it allows you to always parse in linear time, but it is a limitation. By making the recursion to a more complete search you can remove some of these restrictions.

OO Ray Tracing - This is a fun little exercise in geometry related to graphics. If you were to add just a bit of logic to it, you could create a full functional ray tracer. What we lack for that right now is actually just the ability to write the ray tracing out to either a graphics window or a file for something else to render it. This option is also somewhat object oriented. Basically, you will write functions to intersect rays in 3-D space with two different primitive objects and then return information about the intersection.

The two primitives that you will be using are a triangle and a sphere and you will make these act like polymorphic objects by making there first element the function that should be used to intersect them with a ray. So a sphere might look like (func (cx cy cz) radius) while a triangle might look like (func (x1 y1 z1) (x2 y2 z2) (x3 y3 z3)). You might find it is nice to put other information in the triangle as well, like a normal vector. The ray will be stored as two points, ((x1 y1 z1) (x2 y2 z2)).

A full description of the math needed to find where a ray hits a surface is given in this PDF file. This document was written for a PAD1 assignment that does a full rendering with ray tracing. I only want you to take a ray, and a list of geometry and figure out the first place the ray hits something in the geometry and what object it is. So you will write a function find-first-hit that is curried and is called something like this.

((find-first-hit geometry) ray)

The geometry is simply a list of triangles and spheres. This function returns a list of two elements. The first is the point of the intersection and the second is the object it hit.

To do this you might find it is nice to write some helper functions that work with points and vectors to find their difference, normalize them, do dot products and cross products.

You should also make constructors for your sphere and triangle so that a user doesn't really have to know their internal format. Those constructors should look like this:

(create-sphere center-point radius)
(create-triangle point1 point2 point3)

In both cases the points should be lists of three numbers.

For extra credit you can put in a function that the next layer out in doing a full ray tracer. This function takes the geometry and a set of light locations as well as the ray to trace and returns the brightness of the surface that would be seen. To do this you find what the ray hits and where, then send rays from that location to all the lights. If there is an object in between it is in shadow and you don't add any brightness for that light. If nothing is in the way, you add in a brightness given by (/ (dot-product surface-normal vector-to-light) (expt distance-to-light 2.0)).

Numeric Integration - For this option you will write Scheme functions that do numeric integration of functions. In particular, you will write three functions to do the numeric integration using different methods. You will then test the three method to see how they compare to one another.

As you all know, an integral measures the area under a curve. The fundamental theorem of calculus says that this happens to be the difference between the antiderivative at the boundaries of the region. We will be doing the calculation numerically though so it is truly only an approximation of the real answer. The three ways of doing this that we will look at are a rectangle method, that approximates the area under the curve with a large number of small rectangles, the trapazoid method which approximates the area as a number of trapazoids, and Simpson's method which fits a quadratic to the small regions and does the proper integral on that quadratic.

To further abstract the process, you will actually write one integration function that will affect the three methods by taking different functions as arguments. You will also curry the method so that a call might look something like this.

(((integrate method-function) func) min max interval-count)

The integrate method simply runs from min to max with the proper number of intervals in between and adds up all the small pieces. The area of each small piece is caluclated by the method-function which is passed the function, func, as well as the min and max of the small region and returns its approximation to the area.

The rectangle method function will evaluate the function between min and max and return that times the difference between min and max. The trapazoid method will evaluate the function that both min and max and return their average times the difference between min amd max. The Simpson's method is a bit more complex. It will evaluate the function at the min, middle, and max.then fit a quadratic to the three points and evaluate that quadratic. We'll go through the derivation of that here.

Assume the points at min, middle, and max are (x1,y1), (x2,y2), and (x3,y3). We want a quadratic a*x^2+b*x+c that passes through all three of them. If we set up the system of three equations and solve we get that

a=((y1-y2)*(x1-x3)-(y1-y3)*(x1-x2))/((x1^2-x2^2)*(x1-x3)-(x1^2-x3^2)*(x1-x2))
b=((y1-y2)-a*(x1^2-x2^2))/(x1-x2)
c=y1-a*x1^2-b*x1

The indefinite integral of this quadratic is (1/3)*a*x^3+(1/2)*b*x^2+c*x+D. So the integral over the range from min to max would be that formula with max plugged in for x minus it with min for x.

If you choose this option you will also need to compare how well the three methods work by integrating some functions that you know the integral of with each of the three methods using 5 intervals, 10 intervals, and 100 intervals and comparing the answer to the known value. You might try this with x^2 over 0 to 10 and cos(x) over the range 0 to 3.14159.