Please do the following program in Scheme using Dr.Racket

(5 points) In this task, we define a function called

fac

mem

, which is

the memoized version of the factorial function; it takes an integer

n

as

input and returns the factorial of

n

.

Define the factorial function

fac

as usual.

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)

returns a new association list, which is the

result of adding a new entry

(k,v)

to the beginning of asso-

ciation list

al

.

(lookup k al)

returns the value for key

k

in

al

if there is

an entry for

k

and returns

#f

otherwise.

Define a global variable

al

for the association list used in

fac

mem

.

(define al ())

Finally, define

fac

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

(fac n)

, adds the entry

(n, (fac n))

in the

association list, and returns

(fac n)

.

Notes:

To distinguish the two cases in

fac

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

fac

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.