Programming Assignment Help

Programming Task on Memoization in Scheme

#lang racket

#| Problem 1 |#
; Define the Fibonacci function fib as usual
(define (fib n)
(if (<= n 2) 1
(+ (fib (- n 1)) (fib (- n 2)))))

; Define the bind
(define (bind k v al)
(cons (list k v) al))

; Define the lookup
(define (lookup k al)
(if (null? al) #f
(if (equal? k (car (car al))) (car (cdr (car al)))
(lookup k (cdr al)))))

; Define a global variable al
(define al ‘())

; Define fib_mem
(define (fib_mem x)
(let ((res (lookup x al)))
(cond
((equal? res #f) (begin (set! al (bind x (fib x) al))) (fib x))
(else (begin (display “memoization hit: “)) res)
)))
#| Problem 2 |#

(define (build_mem f)
(let ((local_al ‘()))
(lambda (n)
(let ((res (lookup n local_al)))
(cond
((equal? res #f) (begin (set! local_al (bind n (f n) local_al))) (f n))
(else (begin (display “memoization hit: “)) res)))
)
))
;; Some test case
(if (= (fib 1) 1) ‘pass ‘fail)
(if (= (fib 2) 1) ‘pass ‘fail)
(if (= (fib 3) 2) ‘pass ‘fail)
(if (= (fib 4) 3) ‘pass ‘fail)
(if (= (fib 15) 610) ‘pass ‘fail)
(if (= (fib 20) 6765) ‘pass ‘fail)

(if (equal? (lookup 1 (bind 1 123 al)) 123) ‘pass ‘fail)
(if (equal? (lookup 1 (bind 2 123 al)) #f) ‘pass ‘fail)
(if (null? al) ‘pass ‘fail)