Honors 295 - Fall 2003 Project 2: Fractal abstraction Parts 1 and 2 Part 1 by email to DD, noon Friday Oct 31 Part 2 by email to DD, noon Friday Nov 7

Solutions to part 1 (and switch example)

Solutions to part 2

Overview

This assignment is distributed over two weeks.

It takes advantage of a new scheme program, called snapl.scm. We talk in detail about this program in class Wednesday, Oct 29. For the first part of this assignment, you just have to know what this program does: when you look at the scheme file, just skip down to the example at the end of the file. (When you hit "execute", this example gets drawn on the screen.)

This program creates our own small new programming language - or SNAPL for short. SNAPL looks like scheme, but SNAPL programs give commands for a moving robot, like Karel the Robot or the turtle robot of Logo. Like the turtle robot, our robot carries a pen. By marking its path with the pen, our robot can create designs. Our robot can also follow over an old design, and revise it to replace it with a new design. However, our robot is a cellular automaton robot, like these built by Daniela Rus. (See the picture above, in which a simulated bunch of small robots have assembled themselves, for the moment, into the form of a dog.) It can split, by dividing itself in half at any point. In fact, the parts can split in turn, making smaller parts indefinitely. All the individual parts get their own pens, and move on their own.

SNAPL programs are made up of statements. Each statement takes the form of a scheme list with the command followed by its arguments. Here are the primitive SNAPL commands:

(turn RAD)

The robot moves clockwise by RAD radians. (Remember that pi radians is 180 degrees. pi is defined in snapl.scm.)

(flip)

The robot stands on its head (this exchanges the robot's left and right, and inverts all the turns), or, if the robot is already on its head, it turns back right-side-up.

(mark PEN DIST)

Use PEN to mark a segment by moving forward by a step DIST.

(skip DIST)

Move forward by step DIST, without marking with the pen.

(call PROGRAM)

PROGRAM is any Scheme expression that evaluates to a SNAPL program. This command executes this SNAPL program in its entirety before finishing.

(switch P1 ... Pk)

Pi are lists whose CAR is a SYMBOL specifying the name of one of the robot's pens; and whose CDR is a SNAPL program. A switch assumes that robot is editing a previous design. It looks at the PEN that the old design was drawn with, and finds the first Pi that has this pen as its CAR. It then executes just the program in the CDR of Pi. So it's like a COND.

Example

For example, here is a simple program to draw a triangle:

(define angle60 (/ pi 3))

(define triangle
    '((turn (- angle60))
      (mark edge 1)
      (turn (* 2 angle60))
      (mark edge 1)
      (turn (* 2 angle60))
      (mark edge 1)))

When a SNAPL program is executed, what results is a list of line segments. (Don't worry about how segments are represented.) The scheme function snapl-run executes a SNAPL program, and the scheme function snapl-show draws the output on the screen.

This is the scheme command that draws the triangle:

       (snapl-show (snapl-run triangle))

which looks like this:

This statement is also included in snapl.scm; when you hit "Execute", you'll see the triangle.

When the robot is revising a drawing, it uses another SNAPL program. This program is used to replace the segments (one at a time) that the original program produced. For instance, here is a SNAPL program that draws two lines:

(define breakup
    '((mark edge (/ 2 5))
      (skip (/ 1 5))
      (mark edge (/ 2 5))))

If you just execute the breakup program on its own, it will draw two lines separated by a small space. But if you revise using breakup, the robot will replace each line segment with two segments, leaving a small space between them. Essentially, the robot is applying the following replacement rule to every segment:

Here is how you apply and draw a revision using breakup:

    (snapl-show (snapl-edit breakup (snapl-run triangle)))

and using breakup twice:

    (snapl-show (snapl-edit breakup (snapl-edit breakup (snapl-run triangle))))

When the robot is revising a segment, all it knows is that it's standing at the place where the segment starts, and that if it moves forward by one unit of distance, it will be standing at the place where the segment ends.

Since the second line drawn in breakup ends one unit forward from where the robot started, the ending point of this segment will join up with the starting point of the next one. (So, if you're revising a drawing using a SNAPL program that just contains (mark edge 1), then nothing happens---the robot replaces every segment with another one just like it.)

Here is the triangle, along with the results of one and two applications of breakup:

Part 1

The first week's assignment is just designed to make sure that you understand the SNAPL language.

1. First, try to write the one-step rule for the Koch snowflake in SNAPL:

   

   which when applied to a triangle yields the following (after one, two and three steps):

   

   The initial path for the snowflake that the robot starts with is simply a triangle. When making the one-step rule, you'll need to do a little trigonometry; here is a hint:

             

   The scheme functions for sine and cosine are sin and cos; their argument is in radians. (And as you saw in class, you can also use sqrt for taking square roots, although the trig functions should be enough.)

2. Now, try to write the one-step rule for a fractal that evolves something like this:

   

   What is the initial path that the robot starts with?

;Your name here
(load "snapl.scm")
(define koch-program
   '(statement ... statement))
(define koch-start triangle)

(define other-program
   '(statement ... statement))
(define other-start
   '(statement ... statement))

Naturally, you wouldn't want to do this without using a few utilities that allow you to actually run SNAPL programs:

(snapl-run INITIAL-PROGRAM)

Run INITIAL-PROGRAM; return the design created.

(snapl-edit PROGRAM START)

Run PROGRAM repeatedly to transform the design START; return the design created.

(snapl-show DESIGN)

Display the pattern in the attached window.

So to put these commands together to show, for example, two layers of detail on your Koch snowflake, use code like this:

(define snowflake
   (snapl-edit koch-program
      (snapl-edit koch-program
         (snapl-run koch-start))))

(snapl-show snowflake)

When you're working on a program that is used to rewrite another design, keep the other design simple (perhaps use a single segment). That way, you can see what's happening. Or, if your SNAPL program doesn't use any complex commands, you can just use snapl-run directly instead of editing:

(snapl-show (snapl-run koch-program))

Part 2

The second part of the assignment is to extend the SNAPL language. You need to implement two new commands.

(choose P1 ... Pk)

Here we assume that each Pi is a SNAPL program. The choose program allows the robot to select any one of the Piprograms at random and to execute it.

(split P1 ... Pk)

Here again we assume that each Pi is a SNAPL program. A split program tells the robot to split into K identical parts which continue separately. Each part is assigned its own element of the Pi programs to execute. Then the robot parts return to the original position and reassemble the robot. This completes the command.

To create these SNAPL commands, your task is to write corresponding functions. Like all the SNAPL primitives, these functions take three arguments. The first is the CDR of the SNAPL command: this shows all the parameters to the action. The second is the ENVIRONMENT, which corresponds to the robot's position (and information about the segment of the higher level design that the robot is currently tracing over). The final argument is the REST, which holds the design that the robot has already constructed in carrying out the SNAPL program so far.

That means you'll be creating definitions like this:

(define choose
   (lambda (tail env rest)
    ...))

(define split
   (lambda (tail env rest)
    ...))

Each of these functions returns a list. The CAR of this list is the new environment that the robot ends the command in. The CDR of this list contains the design that the robot has constructed after carrying out all the SNAPL program so far, including the new command.

To run a SNAPL program, you can call the function snapl. Like everything else, you call snapl by

(snapl PROGRAM ENV REST)

To make sure you have choose and split working, use them to create an interesting "tree-like" fractal, along the lines of this one:

This one also used switch in a useful way.

For part two, hand in your two new functions, the rules for your tree-fractal. Include a scheme command that will draw the tree-fractal.