Homework 6b
MUST BE DONE WITH YOUR (NEW) PARTNER
MUST USE CHECKED-SIGNATURES!
Due Date Thurs at 9:00pm (Week 6)
Purpose Complete first version of project & practice with list abstractions
Exercises
Exercise 1 Since you have repartnered since the last time you worked on the project, you now have two implementations to start from. You are welcome to take one, mix the two, or start over based on what you learned from both. However, in this problem you must explain your choices: what did you take from each implementation (in particular, representations for Cell & Grid), and why you took that rather than the alternative. Please write at least a few concise, clear, English sentences accounting for your decisions about each of the two data definition. Put your description within "block comments", which begin with #| and end with |#.
Exercise 2 Writing examples of Grid’s by hand is likely not very much fun, as the Cell constructors (and your Grid constructors) may be very verbose. An alternative to this is to provide a syntax for writing examples, and then convert (or parse) that into the actual data structure. This is a very common pattern in computation, and it is typical to have a semi-structured representation for data (the most pervasive, currently, is JSON). Here, we will use S-Expressions as our semi-structured data.
Your first task is to define an S-Expression representation of a Cell. To recall, S-Expressions are defined as:
(define SExp (signature (mixed Number String Boolean Symbol [ListOf SExp])))
Examples include:
(define S1 "hello") (define S2 '(hello "there" ((1 2) 3) #t)) (define S3 '(1 (2 (3)))) And we use, as shown above, quote to construct them (rather than using cons or list explicitly). If you don’t recall how Quote works, please review Lab 4.
Once you have figured out how you will represent Cells using S-Expressions (this is not a _data definition_, it’s a choice of how a subset of a data definition will be given meaning), design a function "parse-cell : SExp -> Cell" that takes an arbitrary S-Expression, and, provided it satisfies _your represention_, converts it to a Cell. Use "error" to report an error if the input cannot be converted to a Cell.
For example, I might represent Conductive plates as "'C". If that were the only type of Cell I could parse, then my implementation might look like (assuming I represented Conductive plates with the string "conductive" in my Cell definition):
(define (parse-cell s) (cond [(and (symbol? s) (symbol=? s 'C)) "conductive"] [else (error "Could not parse " s)])) Obviously, your implementation must have many more cases.
Exercise 3 Now that you can parse cells from S-Expressions, do the same for your Grid, designing a function "parse-grid : SExp -> Grid". Note that depending on how you represented coordinates in your grid, you may want to come up with a different representation for the S-Expression form of the Grid, as the goal should be to make writing examples as simple as possible.
From now on, you are welcome to (and encouraged) to use your parse functions when you write your test cases for other functions.
Exercise 4 Implement a "Grid -> Grid" function, "update-grid", that, given a grid, propogates positive/negative charge through the Grid, one time step. This means that a conductive plate, if adjacent (cardinal directions only, not diagonal) to another cell with charge, should gain that charge. If there are conflicting values, you should report an "error", as this is a short-circuit. Gates (and, or, not) should become charged (with the corresponding logical value) if their input directions have values.
Exercise 5 Combine your draw & update functions to create a main that simulates charge propagating through a circuit. This isn’t a game yet, as there is no goal, but it is an interesting animation!
Universality of foldr
You’ve started using a few different list abstractions: map, filter, ormap, andmap, and foldr. It turns out that "foldr" is in some sense "universal", in that the other abstractions can be implemented using foldr.
Exercise 6 Define "my-map", which behaves identically to "map" (with a single input list), but which is defined using "foldr". Note that you can use lambda, local, function application, variables, etc, but may not use recursion, "map", or other list abstractions!
Exercise 7 Define "my-filter", which behaves identically to "filter" (with a single input list), but which is defined using "foldr". Note that you can use lambda, local, function, application, variables, etc, but may not use recursion, "filter", or other list abstractions!
Exercise 8 Define "my-ormap", which behaves identically to "ormap" (with a single input list), but which is defined using "foldr". Note that you can use lambda, local, function, application, variables, etc, but may not use recursion, "ormap", or other list abstractions!
Exercise 9 Define "my-andmap", which behaves identically to "ormap" (with a single input list), but which is defined using "foldr". Note that you can use lambda, local, function, application, variables, etc, but may not use recursion, "andmap", or other list abstractions!