Lab 3: Silly Sentences and Fancy Fractals

In this lab, you will be working with recursion. In the first part of the lab, you will write a program that generates random sentences based on a set of syntax rules. In the second, you will use recursion to create pictures of fractals.

The grammar of natural languages such as English exhibits a recursive structure.
This structure can be expressed in syntax rules written in the format known as
BNF (Bachus-Naur Form, named after the people who invented it). You have proably seen
BNF used to specify the syntax of programming languages. While BNF is ordinarily used
as a guide for *parsing* (that is, determining whether and how a given string follows
the syntax rules), it can also be used a a guide for *generating* strings that
follow the syntax rules. An example of this can be found in the sample
program SimpleRandomSentences. In this
example, each syntax rule -- except for the most basic ones --
is represented by a method that generates strings that
follow that rule. Where one syntax rule refers to another rule, the method that
represents the first rule *calls* the method that represents the second rule.

For the first exercise of the lab, you should write a similar program that implements the following rules:

<sentence> ::= <simple_sentence> [ <conjunction> <sentence> ] <simple_sentence> ::= <noun_phrase> <verb_phrase> <noun_phrase> ::= <proper_noun> | <determiner> [ <adjective> ]... <common_noun> [ who <verb_phrase> ] <verb_phrase> ::= <intransitive_verb> | <transitive_verb> <noun_phrase> | is <adjective> | believes that <simple_sentence> <conjunction> ::= and | or | but | because <proper_noun> ::= Fred | Jane | Richard Nixon | Miss America <common_noun> ::= man | woman | fish | elephant | unicorn <determiner> ::= a | the | every | some <adjective> ::= big | tiny | pretty | bald <intransitive_verb> ::= runs | jumps | talks | sleeps <transitive_verb> ::= loves | hates | sees | knows | looks for | finds

As in SimpleRandomSentences.java, you can use arrays to implement the last seven rules in this list. (You might improve on that program by writing a single method "void String randomItem(String[] listOfStrings)" for picking a random item from an array of strings.) You are welcome to add to or modify the items in the lists given here.

For each of the first three rules, you should write a subroutine to represent that rule.
Note that a choice of alternatives (represented in the rules by "|") can be implemented
using a *switch* or *if..else* statement; the various choices don't necessarily
have to have the same probability. An optional element
(represented by brackets, "[ xxx ]") can be implemented by a simple *if*.
And a repeated optional element (represented by brackets with dots, "[ xxx ]...")
can be represented by a *while* loop. You should implement the first four
rules exactly as stated here. The main routine should call the <sentence>
subroutine to generate random sentences.

You have to be careful in this program to avoid infinite recursion in this program. Since it will use random choices, there is no guarantee that the recursion will ever end. If your probabilities of doing recursion and continuing loops are too high, it is possible for the program to get lost in recursive calls forever -- or to produce some finite but ridiculously long sentences. You should adjust your probabilities to make sure that this doesn't happen, but that you still get some interesting sentences.

A "fractal" is a geometric figure that has some kind of "self-similarity." In one type of fractal, the self-similarity is an exact recursive structure: The figure is made up of several pieces that are scaled-down copies of itself. For a true fractal, the recursion is infinite; each scaled-down copy is itself made up of smaller copies, which are made up of even smaller copies, and so on forever. On the computer screen, we can get good approximations of fractals by limiting the recursion to a finite level.

One way to produce such fractals is to start with a piecewise linear path
from a point A to a point B, like the one shown on the left above. To form a fractal,
take the path and replace each line segment in the path with a scaled-down copy of
the original path. Then do the same thing to the new path -- replace each line
segment with a scaled copy of the *original* path. By repeating this process to
infinity, you get a true fractal. By repeating it for a finite number of steps, you
get an approximation to a fractal. In the above figure, the path shown on the right
is what you get when you apply just one step in the process to the path shown on the left.

If you follow the description I just gave, it can be hard to draw the path. It's easier if you use recursion (although there is still some rather complicated math). The idea is that we start with the original path, given as a sequence of points. This path is a "template" for the recursive paths that we will actually draw. The algorithm tells how to use the template to draw a path between any two points. The level of recursion that we want is also a parameter to the algorithm:

Algorithm "Recursive Walk", based on a path P = (s_{0},t_{0}), (s_{1},t_{1}), (s_{2},t_{2}), ..., (s_{k-1},t_{k-1}): To go from a point (a_{1},b_{1}) to a point (a_{2},b_{2}), with recursion level n: if n is 0: go directly from (a_{1},b_{1}) to (a_{2},b_{2}) in a straight line else: find a transformed copy of the path P that goes from (a_{1},b_{1}) to (a_{2},b_{2}), where the points on the copy are (x_{0},y_{0}), (x_{1},y_{1}), (x_{2},y_{2}), ... (x_{k-1},y_{k-1}) with (x_{0},y_{0}) = (a_{1},b_{1}) and (x_{k-1},y_{k-1}) = (a_{2},b_{2}) for (i = 1; i < k; i++): call the algorithm recursively to go from (x_{i-1}, y_{i-1}) to (x_{i}, y_{i}) with recursion level n-1

The hard part of this algorithm is transforming the path P. It's easiest if we assume that P goes
from the point (s_{0},t_{0}) = (0,0) to the point (s_{k-1},t_{k-1}) = (0,1).
In that case, the points of the transformed path can be computed using the formulas:

x_{i}= a_{1}+ s_{i}*(a_{2}-a_{1}) - t_{i}*(b_{2}-b_{1}) y_{i}= b_{1}+ t_{i}*(a_{2}-a_{1}) + s_{i}*(b_{2}-b_{1})

Unfortunately, the original path is not likely to be given as a path from (0,0) to (1,0), so the data that you get for the path has to be transformed to make this true. Here is the actual code from my program that takes the original path given as an array of points (with integer coordinates) and transforms that data to get arrays s and t of type double that represent the path from (0,0) to (1,0):

private double[] s; private double[] t; public void setPoints(Point[] points) { x1 = points[0].x; y1 = points[0].y; x2 = points[points.length-1].x; y2 = points[points.length-1].y; s = new double[points.length]; t = new double[points.length]; s[0] = t[0] = 0; double d = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1); for (int i = 1; i < points.length; i++) { s[i] = ( (x2-x1)*(points[i].x-x1) + (y2-y1)*(points[i].y-y1)) / d; t[i] = ( (x2-x1)*(points[i].y-y1) - (y2-y1)*(points[i].x-x1)) / d; } repaint(); }

The actual program that you will write is an interactive program where the user
can drag points on the screen to create the original path that is used as the basis
of the recursion. An executable jar file for the program can be found in the
file */classes/s09/cs225/FunnyFractals.jar*. The source code for the
main program
is in the file */classes/s09/cs225/FamousFractals.java*; you will want to
copy this file into your Eclipse project. You will have to create two classes,
*InputCanvas* and *DisplayCanvas*. The main program and the executable program
can serve as a guide for what needs to be in these classes. Each class can be written as a subclass
of *JPanel*. Both classes need paintComponent methods to draw the contents of the
panel. *InputCanvas* needs a mouse listener and mouse motion listener to allow
the user to drag the points. As the user drags a point, you need to call repaint, and you
need to call the *setPoints* method in the *DisplayCanvas* to get the new list of
points into that class as well.

This assigment is obviously about more than recursion. It's also a chance for you to review (or learn) some GUI programming. You will probably need help on this one, and the due date for the second part of the lab will almost certainly be later than next Tuesday.