itec380 tail-recursion; higher-order functions

tail-recursion; higher-order functions

Due Oct.31 (Thu) at start of class on D2L, and hardcopy.

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.

functions as values

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

Write the function and/f, which takes in two predicates and returns a new function which is true exactly when both predicates would return true. Use define (instead of define/contract), but do include the signature in a comment, as we did (for example) for map in lecture. The following test-cases suffice; you don't need more.

(define positive-integer? (and/f integer? positive?))
(check-expect (positive-integer? 17) #t)
(check-expect (positive-integer? -7) #f)
(check-expect (positive-integer?  0) #f)
(check-expect (positive-integer? "hello") #f) ; Note that `(integer? "hello")` is #f.


(define non-empty-string? (and/f string? (λ(str) (not (string=? "" str))))
(check-expect (non-empty-string? "hello") #t)
(check-expect (non-empty-string? "") #f)
(check-expect (non-empty-string? 99) #f)

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?”.
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 write T or T? or α as a type-variable.
Racket's contracts don't support generic types: as a run-time check, it'd require looking at a datum and deciding its type, which is problematic in the presence of not just inheritance, but also union-types.
Using my-filter, re-write count-bigs from hw05 (lists) as a one-liner.
Of course, don't change its signature.
You can use the built-in function length.
Note that you'll need to use the keyword function a.k.a. lambda because you need to create a function involving threshold, which is local to count-bigs.

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

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 it is natural for it to be 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.

tail recursion

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(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 have the same. The biggest difference will be that the loop will become its owned named function, as we saw in lecture. 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.
If we call my-min, passing in a reference to a list with 2²⁰ = 1M ~ 1million items, how much stack space (memory) is used if we implement it as:
1. a for-loop
2. the tail-recursive version, where tail-call optimization is not implemented by the compiler
3. the above tail-recursive version, where tail-call optimization is implemented by the compiler
Give your answer in MiB, with 1 or 2 significant figures, to within 20% of the exact answer (or, to within 50B). Presume that:
- It requires 1 word (= 8B) of memory to store a value (whether int, char, object-reference, etc. — both in racket and Java)
- A stack-frame requires, in addition to space to hold the parameters, two additional words of memory (for the stack-pointer and return-instruction-pointer, perhaps).

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

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

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

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

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

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