ITEC380 tail-recursion, scope

tail-recursion, scope
and natnum template

Due ~~Mar.♣~~Mar.23 (Mon) on D2L. Problems 6,7 will be moved to the next homework.

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

Write the function sublist : list-of-α, natnum, natnum → list-of-α, which works similar to ² substring: (sublist lst i j) returns the elements of lst from index i up to (but not including) index j (using 0-based indices).

Follow the template for processing natural-numbers.
You can either:
1. follow the template for a single natnum (a cond with 2 branches), and then call a helper “take” which also follows the natnum template (and just returns the first k elements from a list); or
2. follow the template for a pair of natnums, where your cond considers all 2x2 combinations of your two natnums; or
3. as the preceding, but perhaps simplify or even omit some of the 2x2 cond branches based on your precondition.
Approach (a) is the most mindless, following straight from the design recipe (but needing a helper); approach (c) is the shortest code, but can introduce bugs if you're not careful. In any event, you should have conds with either 2, 2x2 or inbetween branches. You don't need more, since we'll rely on our precondition.
You can (should) assume the precondition (<= 0 i j (length lst)). (That is, it can give an exception if the precondition is violated.
Your function should take in “real” built-in natnums — -- not the natch structure from the lecture.
Your function does not need to be tail-recursive.

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

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:

We talked about functions-as-values (using lambda) at the end of lecture Thursday before break, but only briefly. We'll defer the next two problems to the following homework.

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.

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 #o222 'lightCoral)
                      (beside (right-triangle 54 40 #o222 'lightCoral)
                              (beside (rhombus 54 40 #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 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,#o222,'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.

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.

Using my-filter, re-write hw05's count-bigs and dotsaliens-remaining as one-liners. You don't need to submit all your Pac-man code/structs, nor your test-cases — however it should run just as before.

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

² But unlike substring, we won't have an overloaded, 2-argument version that stops at the end of the string. ↩

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

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

tail-recursion, scope
and natnum template