198:314 Fall 2005 Sec. 9 (Steinberg) Project 1 (scheme): shapes GENERAL RULES AND INFO: Some of the code is written for you in file shapes.scm. You must replace comments ;; your code here with appropriate code. You may not change other comments or code that are in the file but you may add additional functions. You may not use iteration or assignment. You must use recursion and variable binding by function call and let and let* instead. (The calls to set! which are already in the file are OK.) Turn in your program using handin.rutgers.edu. The program is officially due at noon on Sunday, October 2 but handin will accept it until 11:59 pm that day. Hand in the file shapes.scm. Some examples of the program running are in file shapes.trace. INTRODUCTION: This project will deal with patterns made out of the characters '.' and '#'. We assume we have a grid of charcters; all the characters in the grid will be '.'s except where we explicitly make them '#'s. The project involves implementing a language for specifying which characters should be '#'s and code for printing patterns specified in this language. A grid of characters might look like this: ...... .###.. .###.. ...... We will refer to a position in such a grid by its coordinates. (0, 0) is the upper left corner, so the #'s in the example above are at (1, 1), (1, 2), (2, 1), (2, 2), (3, 1), and (3, 2). The character grid above would be printed by the Schene expression (print-shape '(block 3 2) 6 4) In general, (print-shape maxx max) prints out the grid from (0, 0) to (maxx, maxy) with '#'s as specified by , which will be an expression in our shape language. Note the quote before (block ...) - this is an expression in our shape language, not in Scheme, and we need the quote to tell the Scheme interpreter not to try to evaluate it. The expression (block 3 2) means that the rectangle of characters from (1, 1) to (3, 2) should be #, as in the picture above. The upper left corner for a block will always be (1, 1) and the x and y coordinates of the lower right corner are given as arguments. Another expression in our language will be of the form (triangle ) where size is an integer and direction is one of the symbols nw, ne, sw, and se. E.g. (triangle 4 nw) will make the shape ....... .####.. .###... .##.... .#..... ....... Similarly, (triangle 3 ne) will procduce ..... .###. ..##. ...#. ..... The directions se and sw produce, respectively, lower-right and lower-left triangles. In the expression (pastey ) shape1 and shape2 are expressions in our language and yoffset is a number. For characters whose y coordinate is yoffset or less, pastey behaves like shape1. For characters whose y coordinate is greater than yoffset, pastey behaves as shape2 but moved down (to higher y values) by yoffset points. In other words, if y > yoffset, pastey makes the character at (x, y) be the character shape2 would have at (x, y - yoffset). For example (pastey (block 3 2)(block 6 4) 3) would produce ........... .###....... .###....... ........... .######.... .######.... .######.... .######.... ........... Note that the top row of the 4x4 block is moved down 3 rows by the yoffset of 3. The character at, for instance, (1, 4) is a # because (block 6 4) makes the character at (1, 4-3), that is, at (1, 1), be a #. A yoffset of 2 would produce ........... .###....... .###....... .######.... .######.... .######.... .######.... ........... Pastex is like pastey but puts the shapes next to each other instead of atop one another. Its third argument is xoffset. The expression (reflecty ) reflects shape across the line y = ycenter. That is, it treats (x, y) as if it were (x, (ycenter - (y - ycenter))) The expression (reflectx ) is simiilar. PART A Part A of the project is to write an interpreter for this language. That is, you are to write code which takes an expression and an x and a y coordinate and returns #t if the character at that location should be '#' and #f otherwise. E.g., (interpret 1 3 '(block 4 5)) returns #t. Note that a few key pieces are already written for you and these pieces should clarify what we want you to implement and how to do it. Interpret must be written in a data-driven manner. It determines what to do for a given shape by taking the car of the shape expression, e.g. the symbol block or pastey, and using it to look up a function which will handle this shape. The lookup is done using the global variable interpreter-defn-table, which is an assoc-list. Note that after your code defines a handler function it must use add-interpreter-defn to add the function to interpreter-defn-table. In addition to the interpreter you need to finish the functions that print out the result of interpretation. PART B Part B is a "compiler". That is, it doesn't directly determine what characters go where. Rather, it produces a function (more precisely, a closure) that later can be called with arguments x and y to determine what character goes there. That is, (let ((fn (compile shape))) (fn x y)) should return what (interpret x y shape) returns. Like the interpreter, the compiler is also data-driven. Part B also includes the printing functions for the compiler. Note that the handler functions for the compiler print output when they are called announcing they are running. If any of this output appears intermixed with the .'s and #'s you have a problem - your compiler is actually interpreting not compiling. Also note that your code should do as much as possible at "compile" time so that "run" time is faster.