ITEC 380 2014fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

hw04
Breakout I; grammars

Part A, Problems 1,2,9,10a: due Sep 30 (Tue) 23:59 and (section 01:) hardcopy the following class
Part B, the remainder: due Oct.05 (Sun)04 (Sat(!)) 23:59.

Your name and the assignment-number must be in a comment at the start of the file, and your hardcopy must be stapled. All functions/data must include the appropriate steps¹ of the-design-recipe—the design recipe: final version. In particular, test cases alone might be worth half the credit for a function. Unless otherwise indicated, two test cases will suffice for most problems, if they are testing different situations.

1. (5pts) In both racket and in Java: Write the function move-ball (Java: Ball#move²) that, for the given ball, returns a new ball object one tick later (ignoring any walls/bricks/paddles³).

   The Java and racket versions should both do the same thing: return a new object, rather than mutating any fields (Cf. derive-from in the lecture notes). The two versions should correspond as directly as possible (including all names being the same, up to idiomatic differences — racket prefers hyphens whereas Java uses camelCase).

   We won't use Java test-cases (since that entails overriding Object#equals, which is not really related to our problem, and is more involved⁴ than we'd prefer. Your Java method should compile and run and be correct, but then you can paste it into a racket block-comment (#| … |#) so that you only need submit&print one file. Make sure it is propertly formatted, of course.

2. Paddles.

   1. (2pts) Improved paddle representation.

      In the hw03-soln.rkt, it was noted that a paddle could be represented by just a single number (its x-coordinate). However, we will want to keep track of a little bit more: which direction the paddle is moving (right or left — or even, how fast right or left). This is so that if a player wants to move the paddle far to the left, they won't have to hit the right-arrow repeatedly.⁵

      So: now design a paddle struct (or object) that includes a horizontal direction (and, if you desire, speed). Make examples of your input. (You might have already had something like this in your hw03 submission.)

      1. Include at least two examples of the data.
      2. Write a template for a paddle-handling function.

   2. (4pts) Write move-paddle : paddle → paddle, which ignores walls/keypresses.
   3. (4pts) Write update-paddle : paddle → paddle, which accounts for stopping⁶ at the left or right edge of the world. (This will presumably call move-paddle; we have separated the movement code from the collision-code.)
   4. (4pts)

      Write paddle-handle-key : paddle keypress → paddle, which returns a brand-new paddle object which has accounted for any keypress your program cares about. See keypress data definition.

      Note:Handling a keypress should probably not move the paddle at all; the keypress as an instantaneous event — much shorter than one tick!

      Note: This function is intended to handle key-down events. If you want your program to also handle key-up events, then write a second function paddle-handle-key-up.

3. Worlds:

   1. (2pts) Define a “world” structure which contains one ball, one paddle, and (for now⁷) exactly one brick.

      As usual for our data-definitions, make examples of the data (at least two), and a template.

   2. (3pts) Write the function update-world : world → world which returns a new world one “tick” later.

      For now, you don't need test cases that involve the ball colliding with anything — you can just have the ball far away from any bricks, walls, paddles. (However, you might have a test where the paddle interacts with a wall/border.)

   3. (2pts) Write the function world-handle-key : world, keypress → world which returns a new world updated to handle the keypress. (Should be easy -- mostly defers to paddle-handle-key, and your test cases will largely crib from that.)
4. Drawing functions:
   1. (2pts) Write the function draw-brick : brick, image -> image, which takes a brick and a “background” image, and returns that background image with a brick drawn on top of it.

      hint:place-image is a handy function; it is similar to overlay/xy except that it crops the result to the background.

   2. (3pts) Write the similar function draw-paddle : paddle, image -> image.
   3. (0pts) Write the function draw-world : world -> image.

      hint: Call draw-brick with an empty-scene for the background; call draw-paddle passing it the result of draw-brick as the second argument.

   4. (2pts) Write the function draw-ball : ball, image -> image.
   5. (3pts) Change your draw-world so that it incorporates drawing the ball as well. (You don't need to include your previous part (c); you can update the code and test-cases directly. Part (c.) was just so that you'd understand how to combine the drawing of two things, before you try drawing three.)

5. (5pts) To do collision detection, write a a suitable helper function would be to detect when two rectangles overlap (e.g. the ball's bounding-box and the region occupied by a brick). Make at least four test-cases⁸ for this.

   There are several reasonable ways to represent rectangles, but it helps if your representation aligns with the arguments needed for 2htdp/image's rectangle. I recommend passing in four numbers for each rectangle, rather than the more heavyweight approach of defining a rectangle-struct.

   hint: I recommend using half-open intervals, to define a rectangular region: A rectangle from 10,20 that is 50x70 would be considered to have x-coordinates from in [10,60) — up to (but not including) the endpoint. It's not that big a deal, but it does mean it's easy to tile the entire plane while neither overlapping at all, nor leaving any 1-pixel-wide gaps.

   If doing so, a useful helper function to write might be (<=< a b c): is a ≤ b < c?

   cool hint, from robotics: We can reduce this problem involving two rectangles to a simpler one: checking if an expanded version of the first rectangle merely contains one particular point: the southeast corner of the second rectangle.
   For example: consider a 20×30 rectangle whose northwest corner is at (500,400) and a second rectangle which is 80×60. These two rectangles overlap exactly when the second rectangle's southeast corner is inside the (20+80)×(30+60) rectangle rooted at (500,400). Sketching this example on paper will help you understand why this works.

All the above should have their tests, as well as signatures and (brief) purpose statements. Only after all tests pass, the following should work (in racket):

(require 2htdp/universe)

(big-bang some-initial-world
          [on-key  world-handle-key]
          [on-tick moveupdate-world]
          [to-draw draw-world])

6. (2pts) Review Question 2.1 (p.50: syntax vs. semantics) — give a short (1-2 sentences) answer in your own words.
7. (2pts) Review Question 2.8 (p.51: define “ambiguous”) — give a short (~1 sentence) answer in your own words.
8. (4pts) Exercise 2.12, part b only (p.105: parse tree for “a b a a”). Note you can ignore the “$$”; the book uses this to indicate end-of-input. I recommend drawing your tree freehand¹⁰. Make sure that each non-leaf node of your tree corresponds directly to a rule in the grammar (the node is a rule's left-hand-side, and its children are exactly the right-hand-side) — no skipping steps.
9. (4pts) Exercise 2.13, part b only (p.105: leftmost derivation of “foo(a, b)”).

   I encourage you to actually put all the nonterminals in upper-case (or at least first-letter-upcased), just to make it easier to tell terminals from non-.

10. Deriving lists, with a grammar:
    Suppose we had the following grammar rule for a javascript function, “<JsFunc>”:

    <JsFunc> → function <JsIdent>( <JsIdents> ) { <JsBody> }

    1. (3pts) Define rule(s) for the nonterminal <JsBody>, which can be 0 or more statements.
       Presume that you already have rules for a nonterminal “<JsStmt>” (an individual statement; note that statements already include semicolons, so your rules shouldn't add any additional ones).

    2. (2pts) As we consider how to define <JsIdents>, a comma-separated list of identifiers, we note that the book as something similar: in the example of <id_list> (§2.3, pp.67–69), they present rules for a non-empty list of comma-separated identifiers (and, ending in a semicolon). Removing the semicolon will be trivial, but we do need to figure out how to adapt it to allow the possibility of zero identifiers.

       Working towards a solution, the programmer MC Carthy comes up with the following attempt for a nonterminal that generates comma-seperated lists of “x”s (also ending in a semicolon):

       <XS> → ; | x; | x, <XS>

       Prove that this grammar is not correct, by giving a derivation¹¹ of some string which is not a valid comma-separated list (ending in a semicolon).

    3. (3pts) Define rule(s) rules for the nonterminal <JsIdents> which correctly generates 0 or more comma-separated identifiers.
       Presume that you already have rules for a nonterminal “<JsIdent>” (an single identifier).
       You will need to include a second “helper” nonterminal.
    4. (3pts) Once you have your grammar, give a leftmost derivation of: function f( a, b ) { z = a*b; return a+z; }.

    Give your grammar rules as in class: in basic BNF using → (and ε), but not using Extended BNF constructs like ? and ^* (nor equivalently, written as _opt and …).

11. (6pts) Generating a grammar

    Give a grammar for Java's boolean expressions. (That is: a grammar describing exactly what you are allowed to put inside a the parentheses of a Java if (…) statement.)

    For this problem, assume that you already have grammar rules for a Java numeric expression (“NumExpr”, probably similar but, for Java, more-complete-than the book's Fig. 3.4Example 2.4, p.46), for a Java identifier (“Id”), and that the only operators you want to handle are &&,||,!,== and the numeric predicates >, >=, and ==. (You do not need to worry about making a grammar that enforces precedence, although you are welcome to.) For this problem, you may use extended BNF constructs ? or ^* (or equivalently, written as _opt and …).

    Using your grammar, give a parse tree (not a derivation) for: a+2 > 5 || (!false == x)
    In the tree, for children of NumExpr and Id, you can just use “⋮” to skip from the non-terminal directly to its children, since you didn't write the exact rules for those nonterminals. I recommend drawing your tree freehand¹².

  public boolean equals( /* Foo this, */ Object that ) {
    if (that==null) {
      return false;
      }
    else if (this==that) {
      return true; // short-circuit a common case
      }
    else if (that.getClass() != this.getClass()) {
      return false;  // CAUTION: unless we can be .equals to a subclass?
      }
    else {
      Foo thatt = (Foo)that;
      // NOW you can add your code that actually compares fields, say:
      return this.someField.equals( thatt.someField )
          && this.someOtherField.equals(thatt.someOtherField);
      }
    }
      

home—lectures—recipe—exams—hws—D2L—breeze (snow day)

©2014, Ian Barland, Radford University Last modified 2014.Oct.14 (Tue)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu