ITEC380 tail-recursion-and-trees -- tail-recursion, scope, trees

tail-recursion-and-trees
tail-recursion, scope, trees

Due Nov.06 (Mon) in class and part(b) Nov.13 (Mon), hardcopy and on D2L.

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

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)

list-ref, take, drop and similar (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-rest!.

(4pts) Write my-list-ref, which takes a list and an index, and returns the list item at the indicated index (0-based). (my-list-ref 2 (list 'a 'b 'c 'd 'e)) will return 'c. In Java, this function is called List#get(int). Your signature should include a type-variable such as α or T. The pre-condition ² is that the index is less than the length of the list. Of course, do not just call the built-in list-ref; you should follow the data-definition for natural numbers, instead of for lists. (So do not check for the empty-list ³.)

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.

(2pts) A tail-recursive function is one where after making a 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).

(5pts) 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 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 ~~variable-~~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.

(5pts) 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) "") 
(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.)

Recall: the scope of identifiers introduced with let is just the body of the let, while the scope of identifiers introduced with let* is the body of the let and all following right-hand-sides of the let*.

Recall: a variable-use's binding-occurrence is the place where that variable is defined.

(4pts) For each variable-use of a below, indicate where it gets its value from — its binding-occurence. For example, if a was used in some line F7, and that use’s binding occurrence was the global declaration in line 01, write “01 → F7”. Another use of a might cause you to write something like “G3 → G6”.
Hint: The binding-occurrence itself is not considered a use of the variable. There are a total of seven uses of a, amongst the four parts.
(2pts) Fill in the blank, with the result of evaluating the expression.

In all cases, presume we have:

line 01 (define a 5)
line 02 (define b 10)

line A1  (let {[z 50]
line A2        [a 51]
line A3        }
line A4    (+ a b z))

; evaluates to:

line B1     (let {[z 50]
line B2           [a 51]
line B3           [b (* a 3)]
line B4           }
line B5       (+ a b z))

; evaluates to:

line C1     (define (foo a)      
line C2      (let {[z 50]
line C3            [a 51]
line C4            [b (* a 3)]
line C5            }
line C6         (+ a b z)))
     
line C7     (foo 1001)

; evaluates to:

line D1     (let* {[z 50]
line D2            [a 51]
line D3            [b (* a 3)]
line D4            }
line D5        (+ a b z))

; evaluates to:

deferred:The following ~~two~~four problems will be due Nov.~~10 (Fri)~~13 (Mon) in class, as "hw0607b". We will go over passing functions and anc-trees in lecture on Monday and Wednesday.

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 #o222 (a transparency)) and a color. Two such examples are ellipse and rhombus.

(3pts) 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, #o222, and 'lightCoral, and putting all the images beside each other:

      (check-expect (shapes-in-a-row (list ellipse right-triangle rhombus))
                    (beside (ellipse 54 40 'solid 'orange#o222 'lightCoral)
                            (beside (right-triangle 54 40 'solid 'orange#o222 'lightCoral)
                                    (beside (rhombus 54 40 'solid 'orange#o222 'lightCoral)
                                            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 does not need to be tail-recursive — the goal of this exercise is to be comfortable with passing functions.

(2pts) Pass your function a list containing

a shape-drawing-function which (when passed v,w,mode,color) will create a 5-sided star with v ~~sides~~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,'solid#o222,'orange'lightCoral).
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.

(3pts) Scott, Exercise 11.7b (third ed: 10.7b), filter. Call your function my-filter; do not use the built-in function filter, of course. This function does not need to be tail-recursive — the goal of this exercise is to be comfortable with passing functions. Hint: Using the name “keep?” for one of your parameters is a good, descriptive name.

(2pts): using my-filter, re-write remove-off-screen-trucks ~~and count-bigs~~ as a one-liner.

(5pts) Write the function count-name, which takes in an anc-tree (as in lecture) and a string, and returns how many times that name occurs as a name in the anc-tree.

(5pts) Write a function that takes in an anc-tree, and returns a similar anc-tree where eye-colors might be changed: In particular, brown eyes have been changed to green, except that if you reach an ancestors with red eyes then don’t change the eye-colors of them or their ancestors. Call your function brown->green/stop-at-red⁸.

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

²Remember, your code doesn't need to check the pre-condition; if the caller violates it, your code can do whatever it likes — return a wrong answer, throw a (different) exception, run forever. For example, in Java "hello".substring(3,1) throws an exception with the slightly odd message “String index out of range: -2”. ↩

³ Since passing in an empty-list is a violation of the pre-condition, you don't need to check for it. Software design suggests your code can do anything it likes in this situation; signalling and error message yourself is a nice "extra", but I want to not do that here, to help reinforce how code follows from the data-definition. ↩

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

⁸ Well, more seriously: we’ll do an equivalent tree-traversal in the future, when working with parse-trees for a programming-language:
we’ll want to re-name all occurrences of a variable x, but if we come across a new variable-declaration named x, that’s making a new, different variable — so don’t change that x, nor any x in sub-trees of that declaration. We say that the newly-declared x is shadowing the original x being re-named. ↩

⁷ People sometimes wonder what possible use-case such a function could have. Well: Sometimes you want to doctor an ancestor-tree, to make yourself appear to be irish. But if you have an ancestor who cried so much that their eyes were red — probably on hearing how you seem to be ashamed of your heritage — we won’t modify their ancestors out of respect.⁸ ↩

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

tail-recursion-and-trees tail-recursion, scope, trees

tail-recursion-and-trees
tail-recursion, scope, trees