ITEC380 tail-recursion, scope

tail-recursion, scope
and natnum template

Due Oct.16 (Sat) 23:59 on D2L.

Reading: Scott §§ 3.3.0–3.3.3 (scope), § 6.6 (tail-recursion).

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

sublist or take, since that's one of the problems below!

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-rest!. They aren't in intermediate-student, anyway.

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.

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

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 tail-recursive racket function(s). The goal of this problem is to have your racket code correspond nearly word-for-word to the above Java loop, computing the same result in exactly the same way. So each expression/step in one version should correspond directly to an expression/step in the other, with a racket helper-function corresponding to the java while, just as in the lecture examples. E.g. since the Java version has a variable a which is local to the loop, your racket code should do the same. Use corresponding names (e.g. “my-min”, “nums-remaining”, etc.). Include signature, purpose-statement, any pre-conditions, 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")
(check-expect (natnum->string/binary (+ 1024 8 4)) "10000001100")

(check-expect (natnum->string/binary #xA) "1010")  ; hex literal
(check-expect (natnum->string/binary #xFFFF) "1111111111111111")
(check-expect (natnum->string/binary #xfeedBee) "1111111011101101101111101110")

; 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 . Observe how the if could be fully evaluated before the recursive call!
Give a tail-recursive version of this function. (Be sure to include tests, purpose-statement, etc. for any helper function you write.)

processing a recursive datatype definition:

The Design Recipe

Who doesn't love binge-watching TV shows?³ After extensive research to determine what aspects of a TV series are important for binge-watching information, I have personally determined that most shows have plot threads which may span several episodes. It's not even important what the plot threads are; a true connoisseur cares only about how many plot threads there are.

Definition: A binge-task is one of:

A cliff-hanger, which contains three things: a number (how many existing plot threads are resolved), another number (how many new plot threads are introduced), and the remaining-show — a binge-task.
A moral, which: introduces either 0 or 1 plot threads (never more); never resolves any; contains a moral (like Be nice., or A fool sometimes shows wisdom, like Phoebe. (Or might not, like Joey.) ); and the remaining-show — a binge-task.
A finale, which has only one piece of interesting info: how many plot threads are resolved. (None are introduced.) It's the last episode of a binge-task; there is nothing more.
A shark-jump: No plot threads are introduced, and exactly two are resolved. But it's so contrived that everybody stops watching their binge-task, so there is nothing more after that.

List-like, but not lists: Although binge-tasks are not lists, they are certainly reminiscent of them: For example, finales and shark-jumps (like empty-lists) cannot possibly followed by any additional tasks. However, cliff-hangers and morals (like cons structs) do have information about an episode, “followed” by one more binge-task (which may be another cliff-hanger which itself contains yet another binge-task, etc.).
Compare this to how we represent a list of a thousand numbers really being a cons struct with only two fields: the first number, and the remainder of the list (which is another cons which itself contains yet another cons, etc.).

So: Do not use built-in lists; everything you need comes straight from the definition above.

Give a racket data-definition to represent a binge-task. (That is, to represent the above as code, what type(s) would you use in racket?)
Hint 1: As always, if you introduce compound data you need to provide both the names of the field (in a define-struct), and the type of the field (in a sample make-structname).

Hint 2: In cases where you don't have more than one piece of information to track, you don't need to introduce any compound-data.

warning: Make sure that you can distinguish between a shark-jump, and a finale that happens to resolve two threads (they are different). Also, do not try to represent all the above using a single struct -- one which contains a number-of-threads-introduced and a number-resolved and some sort of tag, plus further fields that are only meaningful depending on the tag. That would be sloppy data-modeling ⁴; a shark-jump struct/object houldn't contain fields that are meaningless or are a function of other fields ⁵.
Make five examples of binge-tasks (each different from each other in an interesting way). Give names to them (using define); four suggested names are provided; be sure to provide the close-paren.
(define finale0 (define shark0 (define moral1 (define cliffhanger1 (define
Note that to build examples from our definition, your first example(s) must necessarily be ones that don't contain a remainder-of-the-binge-task.

Write the function count-morals which is given a binge-task, and returns how many (possibly nested) morals it contains.

(check-expect (count-morals finale0)         )
(check-expect (count-morals shark0)         )
(check-expect (count-morals moral1)         )
(check-expect (count-morals cliffhanger1)         )
(check-expect (count-morals                         )         )

You do not need to write the template-for-binge-tasks, but certainly all its steps are required for writing the above function.

Write the function net-unresolved : binge-task -> number
which returns how many plot threads are introduced, minus how many are resolved.

Note: If somebody starts a binge-task halfway through, this might be a negative number, if they see a thread resolved that they never saw originally introduced ⁶ .

(check-expect (net-unresolved finale0)         )
(check-expect (net-unresolved shark0)         )
(check-expect (net-unresolved moral1)         )
(check-expect (net-unresolved cliffhanger1)         )
(check-expect (net-unresolved                         )         )

processing the natnum datatype definition: 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.
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.

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

³ Who'd love to have enough time to binge-watch a show? ↩

⁴ Using inheritance would make such an approach more amenable; you'd simply be sure that (say) the constructor for a shark-jump sets its private fields accordingly. But we'll do this without inheritance. ↩

⁵ A field which is a function of the other fields is a violation of 2nd Normal Form, in database-speak. ↩

⁶ Heck, if the writers resolve a thread that never was introduced, this could be negative?! Our data-definition doesn't preclude that. It would be reasonable to do so (if you want to rule out later writing prequels). However, that property is one that isn't a function of the binge-task itself; it relies on information about binge-tasks that refer to it. Thus the current datatype-definition and its template is not appropriate, or at least not self-contained. ↩

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

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

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

tail-recursion, scope and natnum template

The Design Recipe

tail-recursion, scope
and natnum template