ITEC380 grammars

grammars
and tail-recursion, lambda

Due Oct.16 23:59, on D2L Submit two files: hw06.rkt, and then (from DrRacket) a print-to-pdf version hw06.pdf:

Do all your work in hw06.rkt. For non-code answers (e.g. drawing syntax trees), put your answer in a block comment #| … |#, and you can incorporate images (presumably hand-drawn) with DrRacket's Insert » Insert Image….
When your .rkt is complete, use DrRacket's File » Print Definitions

.pdf

Choose a reasonable font-size, like 10pt or so

Preferences » Font

.pdf

The derivations are best written in a text-editor where you can copy/paste one line and replace a single non-terminal to create the next line. But for parse-trees, I recommend drawing them freehand.

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

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

For this (and future) assignments, bump up your DrRacket language-level to Intermediate Student with lambda. Do not call any of the following functions:

list (except when making test-cases)

sublist, list-ref, take, drop and similar built-ins (unless you write them yourself, following the design-recipe)

append (unless you write it yourself, following the design-recipe)

remove (unless you write it yourself, following the design-recipe)

any functions with a “!” in their name, such as set! and set-first!, set-rest!.

Natural-number template

data def: A natural-number is:

0, OR

(+ 1 [natural-number])
The predicates zero? and positive? are often used to distinguish the two branches, though of course = and > could be used equally-well.
And/or, see the lecture notes on natnums as recursive data, about viewing sub1 as the getter to pull out the natural-number field, which a positive is built out of.

Write take : list-of-α, natnum → list-of-α, which returns the first `n` elements of `data`:

; take : list-of-α, natnum → list-of-α
; return the first `n` elements of `data`
; pre-condition: (<= n (length data))
;
(define (take n data n) (...))

(check-expect (take (list 'hi 'bye 'aloha 'ciao) 2)
(list 'hi 'bye))

Follow the data-definition for a natural-number.

tail-recursion

A tail-recursive function is one where after making its recursive call.

Note: Note that being tail-recursive is a property of a function’s source-code. The fact that a tail-recursive function can be optimized to not unnecessarily-allocate stack space is a compiler-implementation issue — albeit it’s what makes the concept of tail-recursion important.

Reading: Scott also discusses recursion and tail-recursion, in §6.6.1; (both 3rd and 4th eds).

Based on Exercise 11.6b from Scott (third ed., 10.6b), min:

First, complete the following Java while-loop, in spirit similar to stringAppendWhoa from lecture.

#|
/** Return the smallest number in a list.
* @pre <code>!nums.isEmpty()</code>
* @return the smallest number in `nums`.
*/
static Double myMin( List<Double> nums ) {
  // initialize our loop-variables:
  double minSoFar = nums.get(    );
  List<Double> numsRemaining = nums.subList(    ,nums.size());

  while (                                                                    ) {
    double a = numsRemaining.get(0);  // corresponding to Scott’s variable `a`
    minSoFar = (                                     ?                            :      );
    numsRemaining =                                                                                                                                     ;
    }
  return minSoFar;
  }
|#

(Your code must be legal, running Java, but you don't need to submit an extra .java file — you can just paste the method into a #| racket block comment |#.)

Now, convert the above code to a tail-recursive racket function. Use corresponding names (e.g. “my-min”, “nums-remaining”, etc.). Include signature, purpose-statement, and test-cases for both your main function and your helper.
Btw: The book’s starting-code calls (empty? (rest l)) — something not in the template. It’s a bit of a hack to stray from the template: Scott wants to avoid making a helper-function, but still return a sentinel-value answer for empty-lists.
However, when converting to tail-recursion, this difference ends up being moot: as you make a helper/wrapper function for the tail-recursion, that extra check disappears.

scheme vs racket: The book’s scheme code uses: car, cdr, null?, and #t. In racket, these names are (respectively): first, rest, empty?, and #true.

Inspired by Scott's exercise about log2 (11.6a; third ed. 10.6a): Here is a function to convert a number to its base-2 representation ²:

(check-expect (natnum->string/binary 0) "")    ; Note that we remove (all) leading zeroes (!)
(check-expect (natnum->string/binary 1) "1")
(check-expect (natnum->string/binary 2) "10")
(check-expect (natnum->string/binary 3) "11")
(check-expect (natnum->string/binary 4) "100")
(check-expect (natnum->string/binary 5) "101")
(check-expect (natnum->string/binary 15) "1111")
(check-expect (natnum->string/binary 16) "10000")

; natnum->string/binary : natnum -> string
; Return the binary-numeral representing n (without any leading zeroes).
; Note that the numeral for zero, without leading zeros, is the empty-string!
;
(define (natnum->string/binary n)
    (cond [(zero? n) ""]
          [(positive? n) (string-append (natnum->string/binary (quotient n 2))
                                        (if (even? n) "0" "1"))]))

Btw: This code doesn’t quite follow the design-recipe for natural-numbers, because it recurs on (quotient n 2) rather than (sub1 n). But it still works fine because it “reduces” the natnum to a smaller one. To reason about this code, you wouldn’t use straight-up mathematical induction; instead you'd call it “strong induction”.

The above code is not tail-recursive, because after the recursive call, it must still call .
Give a tail-recursive version of this function. (Be sure to include tests, purpose-statement, etc. for any helper function you write.)

functions as values

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.

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 one input is of type “function”; give its full signature ³. This function and the next do not need to be tail-recursive — the goal of this exercise is to be comfortable with passing functions.

Using lambda, write a single expression (no defines) which calls your function and passes it a list containing the following two functions:

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

Don’t name these functions ⁴; use lambda. Do not, of course, modify your previous code for shapes-in-a-row.

We discussed functions-as-values, with notes at passing-functions-before.rkt

grammars

(2pts) “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.

(2pts) “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.

(4pts) 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 ⁵.

Using the grammar in the book's Example 2.4 (for expr), give a leftmost derivation of the string 2+(3*-x). (Presume that id ⇒* x, even though we aren't shown the rules for id.)

modification: This problem replaces book-exercise 2.13b, that was originally posted briefly. If you already completed that (more-confusing) problem, you don't need to do this one; just let me know.

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

(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).
(2pts) 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).
(3pts) 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.
(3pts) Once you have your grammar, give a leftmost derivation of: function f( a, b ) { z = a*b; return a+z; }.

(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 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 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 ⁷.

¹ Your final program doesn’t need to include any "transitional" results from the template: For example, you don’t need the stubbed-out version of a function from step 5. However, you should still have passed through this phase. ↩

² Realize that numbers, numerals, and digits are three distinct concepts. In programming, the distinction becomes clear: numbers/numerals/digits correspond to double/string/char, respectively. ↩

³ For example, when sorting a list-of-songs, we might write sort : list-of-song, (song, song → boolean) → list-of-song.
(Though in the case of sort, “song” could be replaced by any type, so we used a type-variable like α or (in Java) <T>. That’s not needed here; we already know the exact the signature of the functions that shapes-in-a-row receives.) ↩

⁴ In many languages, we'd call this the "adaptor pattern", and might write entire classes and interfaces, instead of just using an anonymous function. ↩

⁵ I encourage you to notate, to the right of each step, the exact rule-number used for that step (numbering the grammar rules 1,2,3a,3b, etc.). ↩

⁶ The best answer is the shortest: if you have a simple example that uncovers the grammar's flaw, that is better than a long example doing so. ↩

⁷ You can turn in your printout + your drawing, or if you really want just one file to turn in, you can take a photo and then insert it into DrRacket. ↩

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

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

grammars and tail-recursion, lambda

Natural-number template

tail-recursion

functions as values

grammars

grammars
and tail-recursion, lambda