CS 5010: Problem Set 7
Out: Monday, October 24, 2016.
Due: Monday, October 31, 2016 at 600pm local time.
Update 1: Numbered rules and added rule 3.3 (Mon Oct 24 18:47:58 2016)
Update 2: Added make-turn-left, etc. to deliverables. (Wed Oct 26 16:56:46 2016)
Update 3: Fixed bug in example for f2. (Wed Oct 26 23:04:38 2016)
Update 4: Clarified rule for spaces between arguments in Rule 3.1 (Thu Oct 27 14:44:36 2016)
The goal of this problem set is to give you practice using context arguments and invariants.
Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.
You must use DrScheme’s HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are “obviously” applicable.
Note: not everything on this problem set requires the use of invariants; some may only require generalization. Part of your task is to figure out when you need an invariant and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.
The quality of your purpose statements, invariants, and halting measures will be an important part of the evaluation of your submission.
Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS07.
As usual, the rubric for grading is here.
- You have taken a job with NextPython, Inc., the makers of GarterSnake. They want to add a better user interface for their development environment, so they want to add a pretty-printer which will convert the GarterSnake syntax-tree representation, from Lesson 7.4, into a nicely indented format.Recall that the syntax-tree representation of GarterSnake is defined as follows:
;; A Program is a ListOfDefinition. (define-struct def (name args body)) ;; A Definition is a (make-def Variable ListOfVariable Exp) ;; INTERPRETATION: ;; name is the name of the function being defined ;; args is the list of arguments of the function ;; body is the body of the function. (define-struct varexp (name)) (define-struct appexp (fn args)) ;; An Exp is one of ;; -- (make-varexp Variable) ;; -- (make-appexp Variable ListOfExp) ;; INTERPRETATION; ;; (make-varexp v) represents a use of the variable v ;; (make-appexp f (list e1 ... en)) represents a call to the function ;; named f, with arguments e1,..,en ;; A Variable is a Symbol.
Your task is to write
;; program-to-strings : Program PosInt -> ListOfString ;; GIVEN: GarterSnake program and a width ;; RETURNS: a representation of the program as a sequence of lines, ;; following the formatting rules described below.
The detailed formatting rules will be given below, but here’s an example of the function:
(define sample-program (list (make-def 'a-very-long-function-name (list 'x) (make-appexp 'f1 (list (make-varexp 'x)))) (make-def 'f2 (list 'x 'a-very-long-variable-name 'y) (make-appexp 'f1 (list (make-varexp 'y)))) (make-def 'f3 (list 'x 'z 't 'u) (make-appexp 'f1 (list (make-appexp 'f2 (list (make-varexp 'z) (make-varexp 'y))) (make-varexp 'z) (make-appexp 'f1 (list (make-appexp 'f2 (list (make-varexp 'z) (make-varexp 'y))) (make-varexp 'z)))))))) (program-to-strings sample-program 20) => (list "def a-very-long-function-name (x) :" " f1(x)" "def f2 (x," " a-very-long-variable-name," " y) :" " f1(y)" "def f3 (x,z,t,u) :" " f1(f2(z, y)," " z," " f1(f2(z, y)," " z))")The formatting rules are as follows:
1. Layout of Programs: The program is formatted by formatting each of definitions in sequence. 2. Layout of Definitions: 2.1 Definitions are formatted by formatting the header, consisting of the function name and arguments, followed by the function body, starting on a new line with 4 additional spaces of indentation. 2.2 The function is header is formatted as def fnname (arg1,arg2,arg3) : if it will fit on a line no longer than the given width. 2.3 If the function header as shown in 2.2 will not fit into the given width, then the function header should be laid out as def fnname (arg1, arg2, .. argn) : with each subsequent argument indented to line up under the first argument. 3. Layout of Expressions: 3.1 For a function application, if the string fnname(e1, e2, e3) will fit on a single line, including its indentation and closing parentheses (and comma if needed), then it is formatted that way. 3.2 If a function application, including its indentation, closing parentheses and comma (if present), will not fit on a single line, but the fnname(e1, will fit, then that much of the call is placed on a single line and each of the remaining argument expressions begins on a separate line, indented to line up under e1, and the closing parenthesis is placed on the same line as the last argument expression. e.g. foo(e1, e2, e3) The closing paren is always on the last line. Here "e2,", etc. stand for a set of lines with a comma at the end of the last line, and "e2)" stand for a set of lines with a right parenthesis at the end of the last line. 3.3 If fnname(e1, including its indentation, closing parentheses and comma, will not fit on a single line, then the function name is placed on a line by itself, and e1 is formatted beginning on the next line, indented with 1 additional space and a left parenthesis. Subsequent arguments are indented to line up under e1, e.g. fnname (e1, e2, .. en) Here "e2,", etc., stands for a set of lines with a comma at the end of the last line, and "e2)", etc., stands for a set of lines with a right parenthesis at the end of the last line. 3.4 If the expression is a variable, then it is placed on a line by itself with its associated indentation, right parentheses and possible comma even if that does not fit on one line. 4. General Properties These properties all follow from the rules above, but are stated here for reference. 4.1 There are no blank lines. 4.2 No line ever ends with a space. 4.3 No left parenthesis is ever followed by a space, and no left parenthesis ever appears at the end of a line. 4.4 No right parenthesis is ever preceded by a space or a comma, and no right parenthesis ever appears at the start of a line. 4.4 For any given program and width, these rules determine one and only one layout. 4.5 Following these rules may result in some lines that are longer than the given width. For example, the name binary-search-helper-2 (besides being a poor function name!) will never fit within a line of length 10.To help you debug your program, we have provided in extras.rkt the function:
;; display-strings! : ListOfString -> Void ;; GIVEN: a list of strings ;; EFFECT: displays the strings on separate lines ;; RETURNS: no value
Here is a sample interaction:
> (display-strings! (cons "12345678901234567890" (program-to-strings sample-program 20))) 12345678901234567890 def a-very-long-function-name (x) : f1(x) def f2 (x, a-very-long-variable-name, y) : f1(y) def f3 (x,z,t,u) : f1(f2(z, y), z, f1(f2(z, y), z)) >Turn in your solution is a file named q1.rkt. You also must turn in a call graph for your solution, as in the last few problem sets. Call this file call-graph-1 with an appropriate suffix. Be sure your code includes a halting measure for every function that appears in a cycle in your call graph.
This problem requires careful analysis of the context. For example, when your program generates the string
" f1(f2(z, y),"
what information does it need to know about the context? If there is more than one thing that it needs to know, you can introduce multiple context variables to keep track of them.
- The new model of the Pluto probe from ps02 is has just come out. The new probe is just like the one from Problem Set 02, except for the following:
- It is programmable. The programming language for the robot is defined as follows:
A Program is a ListOfInstruction Interp: A sequence of instructions, to be executed from left to right. An Instruction is one of -- (make-turn-left) Interp: a turn-left instruction -- (make-turn-right) Interp: a turn-right instruction -- (make-move-forward PosInt) Interp: an instruction to move forward the given number of steps. - Alas, the new model of the Pluto probe is less reliable than the old one. If you send it forward by some number of steps, it may take up to TWO steps more than you told it to, or TWO steps less than you told it to. As before, the probe never moves backward, nor will it ever turn by mistake.Thus, if the robot is facing east at x=20, then after a (make-move-forward 10) instruction, it will end still facing east, with its x-coordinate in the interval [28,32] (that is, 30 plus or minus 2), and its y-coordinate unchanged. If the instruction were instead (make-move-forward 1), then afterwards the x coordinate would be in the interval [20,23] (not [19,23]).You are to write file named q2.rkt that provides the following function:
;; probe-possible-outcome? : Int Int Program Int Int -> Bool ;; GIVEN: starting coordinates x0, y0, a robot program p, and ending ;; coordinates x1, y1. ;; RETURNS: true iff the robot, starting at (x0, y0) and facing north, ;; and executing program p according to the tolerances given above, ;; could end at (x1, y1). ;; EXAMPLES: ;; Let p1 = (list (make-turn-right) ;; (make-move-forward 10) ;; (make-turn-right) ;; (make-move-forward 5)) ;; then (probe-possible-outcome 20 100 p1 x1 y1) = true iff ;; x1 is in the interval [28, 32] and y1 is in the interval ;; [103,107]. ;; make-turn-right : -> Instruction ;; make-turn-left : -> Instruction ;; make-move-forward : PosInt -> Instruction ;; As usual, if these are defined by define-struct, you need not ;; write any of the other deliverables (purpose statement, tests, etc.)
For this problem, your program needs to provide acceptable performance. “Acceptable” means that it can provide answers for programs of length 20 in a few seconds– the time it takes to take a sip of coffee. If you are tempted to go get a fresh cup of coffee, your program is too slow. HINT: Small changes in your code will probably not help. You will need to devise a good representation for the possible states of the robot in the middle of the program execution.
Last modified: Thu Oct 27 14:44:38 Eastern Daylight Time 2016
- It is programmable. The programming language for the robot is defined as follows: