RU beehive logo promo banner for Computing & Info Sciences
ITEC 380
2024spring
ibarland

home—lectures—recipe—hws—exams—D2L—zoom (snow day)

scope; tail recursion

Due Mar.21 (Thu) at start of class. Submit via D2L and hardcopy.

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

  1. 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*.

    1. Fill in the blank, with the result of evaluating the expression.
    2. For each variable-use of a below, indicate where it gets its value from — its binding-occurence (that is, the line where that a is declared). 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”. A different use of a might cause you to write something like “G3 → G6”.
    DrRacket's Check-Syntax: Yes, you can answer this question by putting the code in DrRacket and clicking the Check Syntax button, and then mousing over a to see the arrows you'll write, as well as verify the result. But first attempt it “by hand”, since if it's on the exam you won't have DrRacket with you.
    In all cases, presume we have: 
    line 01 (define a 5)
line 02 (define b 10)

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

; evaluates to:         , with 1 use of a:       →      
       
    2. line B1     (let {[z 50]
line B2           [a 51]
line B3           [b (* a 3)]
line B4           }
line B5       (+ a b z))

; evaluates to:         , with 2 uses of a:       →       and       →      .
       
    3. 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:             , with 2 uses of a:       →       and       →      .
       
    4. line D1     (let* {[z 50]     ;note: let*, not let.
line D2            [a 51]
line D3            [b (* a 3)]
line D4            }
line D5        (+ a b z))

; evaluates to:         , with 2 uses of a:       →       and       →      .

    2. tail recursion

  2. 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).
  3. 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 220 = 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).
  4. 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 representation2: 
    (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”.
    1. 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!
    2. Give a tail-recursive version of this function. (Be sure to include tests, purpose-statement, etc. for any helper function you write.)

  5. 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-condition3 is that the index is less than the length of the list. Of course, do not just call the built-in list-ref. Follow the data-definition for natural numbers, instead of for lists. (So do not check for the empty-list4.)

    data def: A natural-number is:
    • 0, OR
    • (+ 1 [natural-number])
    The built-in 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.

1 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.      ↩
2 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.      ↩
3 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”.      ↩
4 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.      ↩

home—lectures—recipe—hws—exams—D2L—zoom (snow day)

logo for creative commons by-attribution license
This page licensed CC-BY 4.0 Ian Barland
Page last generated 		Please mail any suggestions
(incl. typos, broken links)
to ibarlandradford.edu		 Rendered by Racket.