CS2500: Problem Set 11

Due: Tuesday, April 6 at 11:59 PM

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


Assignment goal:


  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:

    sierpinski carpet, iteration 0

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

    sierpinski carpet, iteration 1

    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.

    sierpinski carpet, iteration 2 sierpinski carpet, iteration 3 sierpinski carpet, iteration 4

    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.

CS2500 Home

Last updated 30 March 2010.

Valid XHTML 1.1 Valid CSS!