Comp 210 Lab 5: local; Generative Recursion

For today's lab, you'll have to bump up your language level up to "Advanced"!

Table of Contents

  • Understanding Error Messages
  • A Funny Function
  • local
  • Stone-Age Debugging
  • Root-Finding

    • Understanding the Doctor's Error Messages

    Just a quick reminder: when Dr. Scheme gives you an error message, the error message can give you a clue as to what went wrong. Read it!

    For instance, a common message you'll be getting is 

           #[procedure]: expects 1 argument, given 2: 234 'hi
    This means that some procedure which expects only one argument was actually given two (the integer 234 and the symbol 'hi). The offending function call will be highlighted. You have to figure out what went wrong: was the calling statement was incorrectly giving too many arguments, or was the called function was incorrectly defined as taking too few arguments.

    Moral: Read each word of cryptic error message closely, and sometimes they can give you a clue to the problem (even in cases when you don't understand the entire error message).

    A Funny Function

    Consider the function 
    f(n) =  { n/2    if n is even,
        { 3n+1   otherwise
    While it may look like a pretty mundane function, try iterating it (repeating it over and over, using the previous result), and seeing how long it takes to reach 1 (if ever). (This is known as Colatz's (?) function.)
    An example: if we start with (say) 5, we find that: f(5)=16, f(16)=8, f(8)=4, f(4)=2, f(2)=1. So starting with an initial value of 5, iterating f leads to 1 in five steps. "Sure," you say, "that starting point of 5 happens to lead to 1 after a few steps, just lucky!" What if we start iterating from 3? From 17?

    Write a program stops? which take a number n, and return #t if n, f(n), f(f(n)), ..., ever reaches the number 1. (What does your program do if this doesn't happen?) This function is an example of generative recursion: the answer to (stops? n) might depending generating a new instance--3n+1--and recursing on that. Notice that unlike structural recursion, there is no guarantee that our generative-recursion problem is going to finish.

    Why do we choose to stop at f(1)?

    Now, write a modified function time-til-stop (or tts if you hate typing), which instead of returning #t, it returns the number of steps until 1 is reached. That is, (time-til-stop 5) = 5.

    (This function can be written without using an accumulator. If you wanted, you could also use an accumulator for it. Really, you should have enough knowledge to write it either way.)

    Test time-til-stop on some large numbers, say 1001 and 2349872349247991. (Put these test in your program window, so you don't need to keep re-typing them as we modify time-til-stop.)

    local

    Suppose you used an accumulator to write time-til-stop. Then you used a helper function that did the real work, and time-til-stop just was a wrapper for that, setting up the accumulator correctly. Really, nobody else besides time-til-stop has the right to call that helper function. How can we enforce that?

    Perhaps you think that let is the answer: use a placeholder to stand for the entire helper function definition, and then in the body of the let just use this helper function. That way, nobody outside of the let can see the local placeholder.

    You'd be right and wrong.

    Yes, this is exactly the idea we want to use, but unfortunately if you try it you'll get an error. The problem is that define and define-struction aren't allowed inside a let statement. However, we can still local use of these statements with a new command, named local. It is just like let, but allows these define commands within a local part of your code. Remember that this means local can be used anywhere: For instance, 

    (define myFun
  (lambda (x)
     (local ((define omega '99)
             (define double
                (lambda (n)
                   (* 2 n)))
             (define ww (double omega)))
        (double (+ x ww)))))
    The full syntax of local is a follows; note the similarity to let: 
    (local (st1
        st2
        ...
        stn)
   bod)
    where st1,st2,...,stn are statements (which can be expressions or define or define-structure) which are evaluated in order. As before, the value of the entire local expression is the value of its body, bod, which may refer to placeholders defined above. Unlike let, any statement can see changes made by previous statements.

    Exercise: Now, re-write your function time-til-stop using an accumulator, and enclose its helper-function within a local statement.

    Stone-Age Debugging

    While fancy debugging tools exist for helping you understand what's going on in your code, sometimes the primitive, brute-force method is simplest: Just print statements as you execute your code.

    Dr. Scheme provides the function printf for to print "formatted", using a few special tilde-characters for formatting: 

    (define lyst (list 'one 'two 'three))
(printf "Length of ~s is ~s.~n" lyst (length lyst) )
    prints the following: 
    Length of (list 'one 'two 'three) is 3.
    What happened, exactly? The first ~s is replaces with the value of lyst, and the second ~s is replaced with the value of (length lyst). The ~n prints as a newline. That's it!

    You can stick printf statements into your functions, causing them to print out the value of their arugments. A note of caution follows. 

    (define contains-mary
  (lambda (names)
     (printf "contains-mary: checking through ~s~n" names)
     (cond ((null? names) #f)
           ((eq? 'mary (car names)) #t)
           (else (contains-mary (cdr names))))))
(contains-mary (list 'shelley 'contrary 'magdalene 'mead))
    Do not confuse what a function returns with what it happens to print! Things printed on the screen should be regarded as a side-effect of calling a function. In particular, printed quantities don't get passed to other functions! The return value of a function is passed to its enclosing function if there is one; if there isn't, then the value is printed (this is what you've been seeing all along).

    Warning: Always put a printf statement before the body of your functions. If you wonder why, consider the following UNUSEFUL thing to do: 

    (define x (print "uh-oh"))
    Exercise: Modify time-til-stop to print out the value of its argument each time it is called. (I suggest not using a newline character.) How large do the numbers get for (time-til-stop 1001) and (time-til-stop 2349872349247991)?

    Root-Finding

    As a different example of Generative Recursion, consider using Newton's Method to find the root of a function--that is, where the graph crosses the x-axis.

    Newton's method will be described by the TA on the board. Roughly, you start with an initial guess x0 as to where a function f crosses the x-axis. The guess is probably wrong, so generate a next guess by the following method:

  • calculate the slope of the function f at x0,
  • extend the tangent line from (x0,f(x0)) and see where that line crosses the x-axis;
  • Use that line-crossing as an estimate as to where the complicated function f crosses the line, making that new point your new guess.
    • A picture is worth a thousand words (but don't worry about all the words on that link unless you want to).

    Newton's method often converges very quickly to a root, but you can also think of cases where it is foiled: it might divide by 0, it might loop or diverge, and even if it gives you a root, it might not be the root you want.

    A hint (and test data) are available.

    Back to Comp 210 Home