itec380 tail-recursion, scope

tail-recursion, scope
and natnum template

Due Oct.28 (Fri) 23:59 on D2L; hardcopy at following class.

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 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. Put your signature in a comment (and use define instead of define/contract), since generic-types aren't supported by (run-time) contracts. 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 our function countdown (or other functions following the natural? template, about viewing sub1 as the getter to pull out the “natural-number field, which a positive is built out of”.

functions as values

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

Scott, Exercise 11.7b (third ed: 10.7b): Write filter.
Call your function my-filter; do not use the built-in function filter, of course.
Hint: A good, descriptive name for one of your parameters would be “keep?”.
This function does not need to be tail-recursive (and will naturally be not-necessarily-tail-recursive, since lists are recursively defined). The goal of this exercise is to be comfortable with passing functions.
Using my-filter, write count-bigs as a one-liner.
Note that you'll need to use lambda, because you need to define a function involving threshold, which is local to count-bigs.
Use define instead of define/contract, but put the signature in a comment. Recall that the for the first argument of my-filter is itself a function, so your contract will look like (-> (-> ) (listof ) (listof ))! You can use T or T? or α as a type-variable.

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 its input type “list-of-function”; give its full signature ⁵ (-> (listof (-> ) ).
This function does not need to be tail-recursive (though will naturally be not-necessarily-tail-recursive, since lists are recursively defined). The goal of this exercise is to be comfortable with passing functions.

Now, call shapes-in-a-row passing it a list containing the following two functions:
1. 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).
2. 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.
Do not use define to create these functions; your answer should be of the form (shapes-in-a-row (list (lambda …) (lambda …))).
This is actually an example of the adaptor pattern: shapes-in-a-row expects functions that meet a certain interface (4 inputs), but the functions we have (star, pulled-polygon) need to be adapted to satisfy that interface. This can be easy (a couple lines, as above) in languages with anonymous functions and dynamic-typing (or good type inference); otherwise it might require writing entire classes and interfaces.

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

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

⁵ For example, when sorting a list-of-songs, we might write sort-songs : (-> (listof song?) (-> song? song? boolean) (listof 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.) ↩

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

functions as values

tail-recursion, scope
and natnum template