SI413 Scheme Lab 6: Breaking the functional paradigm

display and set!

Let's destroy the functional paradigm. Suppose I want to count the number of function calls in computing a fibanocci number the naive way:

(define (fib n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

A natural (though hackish) way to do it would be to have a global variable that you increment as the very first thing you do in each function call. Well guess what, the body of a function can contain more than one expression. If it does, the last one is the actual value of the function and the others would simply be called for side-effects. One side effect is I/O. The function call (display x) prints out whatever x is. In the following we have 4 expressions in the body. The first 3 are just there for side effects.

(define (fib n) 
  (display "fib called with n = ") 
  (display n) 
  (display "\n") 
  (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

> (fib 5)
fib called with n = 5
fib called with n = 4
fib called with n = 3
fib called with n = 2
fib called with n = 1
fib called with n = 0
fib called with n = 1
fib called with n = 2
fib called with n = 1
fib called with n = 0
fib called with n = 3
fib called with n = 2
fib called with n = 1
fib called with n = 0
fib called with n = 1
8

Obviously this scheme is not going to be usefull for (fib 30), since there'll just be too much input. We'd rather just have a number that tells us how many function calls. Here's a C++-esque way:

(define calls 0)

(define (fib n) 
  assign calls the value (+ calls 1)
  (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

(display calls)

This, of course, does not work! The infix assignment is a bit of C++ thrown in. It shows us what we need though, we need assignment in scheme. The set! function is scheme's assignement operator.

(define calls 0)

(define (fib n) 
  (set! calls (+ calls 1))
  (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2)))))

> (fib 30)
1346269
> calls
2692537

That's a lot of function calls!

By the way, let works the same way as functions, in that the body of the let may contain several expressions, they are evaluated in order, and the last expression is the value of the let statement. The other expressions are evaluated only for their side effects.

Problems:

1. Here's an old homework solution.

   ;#####################################################################
   ;## PROBLEM 2
   ;#####################################################################
   
   ;; compound-month B r: returns balance after 1 month of compounding
   (define (compound-month B r) (* B (+ 1 (/ r 1200.0))))
   
   ;; compound-months B r m: returns balance after m months of compounding
   (define (compound-months B r m) 
     (if (= m 0) 
         B 
         (compound-months (compound-month B r) r (- m 1))))
   
   ;; accrue B r y: returns balance after y years of monthly compounding
   
   (define (accrue B r y) (compound-months B r (* y 12)))
   	

   The accrue function returns the balance at the end of y years accrueing r% interest, comopunded monthly with a starting balance of B. Modify these functions so that the balance at the end of each month is printed out as you go.

   > (accrue 100 7 1)
   100.58333333333334
   101.17006944444445
   101.76022818287038
   102.35382951393713
   102.9508935194351
   103.55144039829847
   104.15549046728854
   104.76306416168106
   105.37418203595753
   105.98886476450062
   106.60713314229355
   107.22900808562359
   
   107.22900808562359
   > 

   Hint: Modify compound-month so that it calculates the value, prints it out then returns it.