Using DrRacket with Scheme Code Scheme Language

In this task, we define a function called fib mem, which is the memoized version of the Fibonacci function, which takes an integer n as input and returns the n-th number in the Fibonacci sequence.

a. Define the Fibonacci function fib as usual.

b. Define the bind and lookup functions for association lists, as we discussed in class. Recall that an association list in Scheme is just a list of pairs and each pair contains a key and a value.

(bind k v al) adds a new entry (k,v) to the beginning of association list al.

(lookup k al) returns the value for key k in al if there is an entry for k and returns #f otherwise.

c. Define a global variable al for the association list used in fib_mem.

(define al ())

d. Finally, define fib_mem. When given n, it checks whether there is an entry for n in al. If there is, it returns the value in the entry; if not, it invokes (fib n), adds the entry (n, (fib n)) in the association list, and returns (fib n).

Notes:

To distinguish the two cases in fib mem, add the following display command for the case when the input n is in the current association list. It displays the string on screen.

(display memoization hit )

To add an entry to al, you will have to use set! to modify the global variable al. This has the side effect of modifying al so that it is visible to the next invocation of fib_mem.

You will also need to use the sequencing construct in Scheme. In particular, (begin e1 e2) evaluates e1 (which usually has some side effect) and then evaluates e2; the value of e2 becomes the value of (begin e1 e2).

For example,

(begin

(display memoization hit )

(+ 1 2))

The example displays the message and returns 3.