ITEC 380 2022spring ibarland

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

grammars
and functions as values

Your name and the assignment-number must be in a comment at the start of the file, along with a link to this assignment page.

Reading: Scott §3.6.4 (Lambda expressions); §11, but skip 11.4 and 11.5 (OCaml and Evaluation Order, respectively).

For this (and future) assignments, be sure you have bumped up your DrRacket language-level to Intermediate Student with lambda.

functions as values

We discussed functions-as-values, with notes at passing-functions-before.rkt
1. 1. Scott, Exercise 11.7b (third ed: 10.7b): Write filter. Call your function my-filter; do not use the built-in function filter, of course.

      Hint: A good, descriptive name for one of your parameters would be “keep?”.

      This function does not need to be tail-recursive (though will naturally be not-necessarily-tail-recursive, since lists are recursively defined). The goal of this exercise is to be comfortable with passing functions.
   2. Using my-filter, write count-bigs as a one-liner.
      Note that you'll need to use lambda, because you need to define a function involving threshold, which is local to count-bigs. Use define instead of define/contract, but put the signature in a comment. Recall that the for the first argument of my-filter is itself a function, so your contract will look like (-> (->                            ) (listof       ) (listof       ))! You can use T or T? or α as a type-variable.

2. Notice that several of the image-creating functions imported via (require 2htdp/image) are similar, in that they happen to take four arguments: two non-negative numbers v and w, a drawing mode (e.g. 'solid or #o162 (a transparency)) and a color. Two such examples are ellipse and rhombus.

   1. Let’s write a function shapes-in-a-row which takes in a list containing such functions, and returns an image that is the result of calling each function with the arguments 54, 40, #o162, and 'lightGoldenrod, and putting all the images beside each other:

      (check-expect (shapes-in-a-row (list ellipse right-triangle rhombus)) (beside (ellipse 54 40 #o162 'lightGoldenrod) (beside (right-triangle 54 40 #o162 'lightGoldenrod) (beside (rhombus 54 40 #o162 'lightGoldenrod) empty-image))))

      Make sure you've increased your language-level to “Intermediate Student with lambda”, as mentioned above.
      When writing the signature for shapes-in-a-row, don’t just say its input type “list-of-function”; give its full signature¹ (-> (listof (->                                                                                               )                   ).
      This function does not need to be tail-recursive (though will naturally be not-necessarily-tail-recursive, since lists are recursively defined). The goal of this exercise is to be comfortable with passing functions.
   2. Now, call shapes-in-a-row passing it a list containing the following two functions:
      1. a shape-drawing-function which (when passed v,w,mode,color) will create a 5-sided star with v as its side-length, of the indicated mode & color (and w is unused).
         (shapes-in-a-row will of course pass your function the arguments 54,40,#o162,'lightGoldenrod).
      and
      2. a shape-drawing-function which (when passed v,w,mode,color) will create a pulled-regular-polygon with sides v long, having w sides, a pull of 0.9 and angle of 20 of the indicated mode and color.

      Do not use define to create these functions; your answer should be of the form (shapes-in-a-row (list (lambda …) (lambda …))).

      This is actually an example of the adaptor pattern: shapes-in-a-row expects functions that meet a certain interface (4 inputs), but the functions we have (star, pulled-polygon) need to be adapted to satisfy that interface. This can be easy (a couple lines, as above) in languages with anonymous functions and dynamic-typing (or good type inference); otherwise it might require writing entire classes and interfaces.

grammars

3. “Check Your Understanding” Question 2.1 (syntax vs. semantics: p.53 in 4ed, or p.50 in 3ed) — give a short (1-2 sentences) answer in your own words.
4. “Check Your Understanding” Question 2.8 (re “ambiguous”: p.53 in 4ed, or p.51 in 3ed) — give a short (~1 sentence) answer in your own words.
5. Exercise 2.12, part b only (a parse tree for “a b a a”; pp.107–8 in 4ed, or pp.104–5 in 5ed, and is exercise 2.9 in 2ed).
   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².
6. Using the grammar in the book's Example 2.4 (for expr, p.48–49 of Scott 4ed), give a leftmost derivation of the string 2+(3*-x). (Presume that id ⇒* x, even though we aren't shown the rules for id.)

   caution: Don't use the grammar of Example 2.8 by mistake.

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

   <JsFunc> → function <JsIdent>( <JsIdents> ) { <JsBody> } this is one long rule which contains two newlines

   For the grammar rules below, write them as in class: in basic BNF using “→” (and “ε”), but not using Extended BNF constructs like ? and ^* (nor equivalently, written as _opt and …).

   1. 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. As we consider how to define <JsIdents>, a comma-separated list of identifiers, we note that the book has something similar: in the example of <id_list> (Examples 2.20 and 2.21 in §2.3), 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 repetitions of the letter “x”, separated by commas and ending in a semicolon (which we won't end with in our part (c), next):

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

      This grammar can certainly generate “x, x, x;”.

      Prove that this grammar is not correct, by giving a derivation of some string which is not a valid comma-separated list-of-“x”s ending in a semicolon. As usual, for full credit give the shortest correct answer.³

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

8. Generating a grammar

   Give a grammar for Java's boolean expressions. (That is: a grammar describing exactly what you are allowed to put inside 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 Example 2.4, p.46), for a Java identifier (“Id”), and that the only boolean operators you want to handle are &&,||,!,== and the numeric predicates >, >=, and ==. (You do not need to worry about enforcing precedence, although you are welcome to.) For this problem, you may use the Extended BNF constructs ? and ^* (or equivalently, written as _opt and …).

   hints: Make sure you can derive expressions like !!!!!!false and ((((targetFound)))), in addition to the expression below. Make sure you cannot derive expressions like x false (two expressions not one), 2 > true (> can only occur between numeric-expressions, not boolean-expressions), or (the empty string). You might want to ask yourself:

   • What is allowed to follow a “!”?
   • What is allowed on each side of “||”?

   For comparison, see that book Example 2.4, and what is allowed on either side of binary operators like “+”, and also what it allowed to follow the unary-negation “-”.

   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 write “⋮” 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⁴.

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

This page licensed CC-BY 4.0 Ian Barland Page last generated

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