ITEC 380 2024spring ibarland

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

grammars

Reading: Scott §3.6.4 and §11.6 (lambda expressions); §2.1 (grammars). ; functional vs imperative trade-offs: 11.8 ; functional overall: all of 11, incl. 11.2(FP concepts)

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?”.

      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 write T or T? or α as a type-variable.
      Racket's contracts don't support generic types: as a run-time check, it'd require looking at a datum and deciding its type, which is problematic in the presence of not just inheritance, but also union-types.
   2. Using my-filter, re-write count-bigs from hw05 (lists) as a one-liner.
      Of course, don't change its signature.
      You can use the built-in function length.
      Note that you'll need to use the keyword function a.k.a. lambda because you need to create a function involving threshold, which is local to count-bigs.

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))))

      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 it is natural for it to be 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.
Write the function and/f, which takes in two predicates and returns a new function which is true exactly when both predicates would return true. Use define (instead of define/contract), but do include the signature in a comment, as we did (for example) for map in lecture. The following test-cases suffice; you don't need more.

(define positive-integer? (and/f integer? positive?)) (check-expect (positive-integer? 17) #t) (check-expect (positive-integer? -7) #f) (check-expect (positive-integer? 0) #f) (check-expect (positive-integer? "hello") #f) ; Note that `(integer? "hello")` is #f. (define non-empty-string? (and/f string? (λ(str) (not (string=? "" str)))) (check-expect (non-empty-string? "hello") #t) (check-expect (non-empty-string? "") #f) (check-expect (non-empty-string? 99) #f)

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. 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).

   Gloss over “missing rules”: Presume that <id> ⇒* x, and similarly that <number> ⇒* 2 and <number> ⇒* 3, even though we aren't shown the rules for <id> nor <number>. In your derivation you'll have a step using “⇒*” where (exactly) one of those non-terminals gets replaced (to show that there are technically multiple steps that are not being shown).

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

6. 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. The book includes a semicolon at the end, which we're ignoring. 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 indeed generate “x, x, x”.

      Prove that this grammar is actually not what we want, by giving a derivation of some string which is not a valid comma-separated list-of-“x”s. 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, show that function f( a, b ) { z = a*b; return a+z; } is a <JsFunc> by drawing a parse tree.

      Gloss over “missing rules”: Since we're presuming that <JsIdent> ⇒* a and <JsStmt> ⇒* z = a*b; (using rules we haven't been shown), in your tree just draw a dotted line “⋮” between them e.g. from <JsIdent> to its leaf/descendent a, and from <JsStmt> to its leaf/descendent z = a*b;.

7. Generating a grammar

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

      For this problem, assume that you already have grammar rules for a Java identifier (“<Id>”), for a Java numeric expression (“<NumExpr>” -- which is presumably similar to the book's Example 2.4, p.46), 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 “-”.

   2. Using your grammar, draw 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—hws—exams—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