# CS2500: Problem Set 11

## Due: Tuesday, April 6 at 11:59 PM

This assignment is to be completed with the same partner as PS10.

#### Purpose

Assignment goal:

• Understanding how Scheme works
• Generative recursion

#### Problems

1. Read HTDP §27.1: Fractals.

Your textbook describes a fractal, the Sierpinski triangle. Another fractal is the Sierpinski carpet:

To construct the Sierpinski carpet, start with a square:

Divide the square into a 3 by 3 grid, and fill the center square of the grid with a different color:

Then, repeat with the surrounding 8 squares, filling the middle square from each of them. Repeat until further changes would be too small to see.

Design a function sierpinski-carpet that takes a Natural and returns a Scene containing a square Sierpinski carpet of that size. The final iteration above is the result of (sierpinski-carpet 243). Your function must add detail until further squares would be too small to see.

2. Extend your evaluator from Problem Set 9, Part I to evaluate an expression in the context of function definitions, using your data definitions from Problem Set 10, Part III.

The function evaluate-expression must now consume two arguments, (the representation of) a Scheme expression, as before, a list of (representations of) function definitions. If e is the representation of an expression and defs is a list of representations of function definitions, then (evaluate-expressions e defs) produces the same number that DrScheme would if the definitions represented by defs were in the Definitions Window and the expression represented by e were entered in the Interactions Window.

Here’s how it works. The subtraction, multiplication, and square root expressions are evaluted as before, and as before. To evaluate the application of a function g, evaluate-expression

1. evaluates the argument;
2. looks up the definition of g in defs (indicating an error if g is not found);
3. substitutes the value of the argument for occurrences of the function parameter in the function’s body; and
4. evaluates the new expression via recursion.

As before, it is an error if evaluation encounters a variable, but note that a variable in a function body will not produce errors if it matches the function’s parameter. Why not?

#### Turn In

Please follow the electronic homework submissions instructions.

Last updated 30 March 2010.