ITEC 380 2009fall ibarland

home—info—lectures—exams—hws—archive

hw05
functional loops; binary trees
tail recursion; lambda; map/filter/fold

Due Oct.22 (Wed). Turn in hardcopy and (on WebCT) a file with running code.

1. (1pt) A grammar is ambiguous if                 .

2. (10pts) Here is a grammar for a hypothetical language, N0:

   Expr ::= Number | Var | ParenExpr | BinExpr | IfZExpr ParenExpr ::= ( Expr ) BinExpr ::= ( Expr BinOp Expr ) IfZExpr ::= if Expr is0 then Expr else Expr ; BinOp ::= plus | minus | times

   where Number is any numeric literal (as written in either Java or Scheme, your choice), and Var is string with no whitespace or punctuation (parentheses, “;”) and is not otherwise a reserved word in N0 (i.e. a terminal in the above grammar -- “if”, “plus”, “is0”, etc.). Whitespace is required between all terminals/non-terminals, with the exception of punctuation.

   For each of the following, either give a parse tree, or give a brief motivation of why the string is not a valid N0 Expr:

   1. 23
   2. if z is0 then 22 else (z plus 3);
   3. if z is 9 then 22 else (z plus 3)
   4. if z is0 then 22 else (if y is0 then 4 else 5; plus 3);
   5. if z is0 then 22 else (if y is0 then 4 else 5 plus 3);
   6. If the grammar didn't require a semicolon at the end of an if expression, give a shortest-possible string which would be ambiguous. (Bad question; no answer. Two free points for all!)

3. (5pts) Write the function subst : (symbol? symbol? (listof symbol?) . -> . (listof symbol?)), which substitutes one symbol for another in a list. Use lambda along with one of map or filter. (See lect07a.ss)

   (check-expect (subst 'apple 'dell (list 'orange 'apple 'banana)) (list 'orange 'dell 'banana)) (check-expect (subst 'apple 'dell (list 'orange 'banana)) (list 'orange 'banana)) (check-expect (subst 'apple 'dell (list 'apple 'orange 'apple 'apple 'banana)) (list 'dell 'orange 'dell 'dell 'banana))

4. (5pts) Write draw-trucks-v2 which is just like draw-trucks from hw04, using foldr (and draw-truck). (Your code should run; you can call on your list-of-truck examples, to verify it returns the same image that draw-trucks does.)
5. (3pts) Write running Java code static String stringAppendAll( java.util.List<String> strs ) in the same style used by countHelloes in Looper.java That is, process the list using a while-loop and sublist(0,…). Your function should not modify the contents of the original list, nor have any other side effects¹.
6. (3pts) Now write a scheme version of the above Java function, where the Java loop is translated into a tail-recursive scheme function. Use the same variable names you did in your Java version². Every action your Java code performs, your scheme code should have an exact equivalent. (For example, since your Java code has an accumulator variable, your scheme code will as well; it will get initialized and updated in the exact same way.) The non-tail-recursive version is shown below, for your amusement. Only use the built-in string-append applied to exactly two strings. Do not assign to any scheme variables, of course.

   ; string-append* : (listof string?) -> string? ; Return a string with *all* the elements of `strs` appended, left-to-right. ; (define (string-append* strs) (cond [(empty? strs) ""] [(cons? strs) (string-append (first strs) (string-append* (rest strs)))))) ;>>>TODO: (define (string-append*-v2 data) ) (check-expect (string-append*-v2 empty) "") (check-expect (string-append*-v2 (list "hi") "hi") (check-expect (string-append*-v2 (list "hi" "there")) "hithere") (check-expect (string-append*-v2 (list "aye " "bee " "sea ")) "aye bee sea ")

7. (6pts)
   1. In functional programming, all data is                 .
   2. Give two ways in which a functional approach is worse than a non-functional approach. (It might help you to consider particular functions, like move-truck or move-trucks from hw04.)
   3. Give two ways in which a functional approach is better than a non-functional approach.
   4. Why is functional programming easier to adapt to parallel processors (e.g. multicores) than non-functional programming?

8. (5pts) Write a function which returns the number of 'blue-eyed people in an anc-tree.

   (check-expect (count-blues 'unknown) 0) (check-expect (count-blues lieselotte) 0) (check-expect (count-blues kristin) 1) (check-expect (count-blues ian) 3)

9. (5pts) Write a function which returns a list of the name of all baby boomers (people born between 1946 and 1964 inclusive).

   (check-expect (baby-boomers 'unknown) empty) (check-expect (baby-boomers lieselotte) empty) (define aa (make-child "aa" 1950 'gray 'unknown 'unknown)) (check-expect (baby-boomers aa) (list "aa")) (check-expect (baby-boomers (make-child "bb" 1970 'green aa ian)) (list "aa"))

10. (5pts) (Hypothetical situtation:) Imagine that a genetic test shows that somebody's eyes are not quite blue (a recessive gene), but actually (say) azure (a dominant gene).

    Write a function blue->azure which changes the eye-color of every 'blue-eyed person in the tree to 'azure.

    (check-expect (blue->azure 'unknown) 'unknown) (check-expect (blue->azure lieselotte) lieselotte) (check-expect (blue->azure kristin) (make-child "Kristin" 1943 'azure lieselotte 'unknown)) (check-expect (blue->azure ian) (make-child "Ian" 1966 'azure (make-child "Kristin" 1943 'azure lieselotte 'unknown) (make-child "Gordon" 1938 'brown (make-child "Lois" 1899 'brown 'unknown 'unknown) (make-child "George" 1894 'azure 'unknown 'unknown))))

11. (5pts) Imagine further, that anybody with green eyes can't have had an azure-eyed ancestor.

    Write a function blue->azure/stop-at-green which changes the eye-color of every 'blue-eyed person except that the ancestors of anybody with green eyes are not processed.

    (check-expect (blue->azure/stop-at-green 'unknown) 'unknown) (check-expect (blue->azure/stop-at-green lieselotte) lieselotte) (check-expect (blue->azure/stop-at-green kristin) (make-child "Kristin" 1943 'azure lieselotte 'unknown)) (check-expect (blue->azure/stop-at-green (make-child "cc" 2000 'orange kristin (make-child "bb" 1970 'green aa ian))) (make-child "cc" 2000 'orange (make-child "Kristin" 1943 'azure lieselotte 'unknown) (make-child "bb" 1970 'green aa ian)))

home—info—lectures—exams—hws—archive

©2009, Ian Barland, Radford University Last modified 2009.Dec.01 (Tue)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu