General memoization in Scheme

Question

i have been assigned homework to make a general memoization procedure in scheme, so far it works on procedures that take one argument, but fail on what it seems to be the last argument when provided with more than 1. It also fails to memoize procedures that take no arguments.

Any help would be greatly appreciated.

(define mem
  (lambda (mem-it func)
    (let ((table (make-table) )(func-store func))
      (cond
        ((equal? mem-it 'memoize)         
         (lambda args
           (if (null? args)
               func
               (let ((prev (lookup args table)))
                 (or prev
                     (let ((result (apply func args)))
                       (insert! args result table)
                       result))))))

        ((equal? mem-it 'unmemoize)
         (func-store))

        (else (display "No Such command"))))))

This is what i have so far

(define (test-proc . args)
  (display "computing test-proc of ")
  (display args)
  (newline)
  (if (null? args)
      0
      (+ (expt (- 42 (car args)) 2)
         (apply test-proc (cdr args)))))

And here is the test procedure provided

The error occurs when i try to run the following test

(set! test-proc (mem 'memoize  test-proc))
(test-proc 40 41 42 43 44)

Here are the other procedures used

  (define (make-table)
    (list '*table*))

  (define (lookup key table)
    (let ((record (assoc key (cdr table))))
      (and record (cdr record))))

 (define (insert! key value table)
   (let ((record (assoc key (cdr table))))
     (if record
        (set-cdr! record value)
         (set-cdr! table 
                   (cons (cons key value) (cdr table))))))

Your code is unreadable since the indentation is off. Why don't you use an editor that does this for you? — Sylwester
What ist your problem, exactly? Are you trying to memoize a function of more than one argument, or are you trying to apply a memoized function of one argument to a list of values? — Michael Vehrs
make-table, lookup and insert! is not a part of any scheme standard so this might be an uncompatible extension from a specific implementation. The standard is using SRFI-69 or R6RS (rnrs hashtables). You'll need to provide the definitions or tag/mention which implementation you are using. — Sylwester

Sylwester Sylwester · Accepted Answer · 2016-04-20T09:13:20

Your memoizarion procedure has a feature where it returns the implementation procedure when no arguments are passed:

((mem 'memoize test-proc)) ; ==> test-proc

The base case of your test procedure will never hit because of this feature thus for (test-proc 1) you can substitute it with the expression (+ 1681 test-proc) which will signal an error since test-proc is not a number.

It's better to use unique magic values:

(define +GET-PROC+ (list "get-proc"))
(test-proc +GET-PROC+) ; ==> original-test-proc

Since we are making a list it's is eq? that data only. In R6RS you can refrain from exporting so that code that uses memoization doesn't really have access to mess with it. All lists that look like it eg ("get-proc") won't be eq? so it can be used as an argument without getting the original procedure.

Since you are not using a standard hash procedure from (rnrs hashtables) or SRFI-69 it's not possible for me to check it but since you are using a list as key your hashtable must use equal? as test. This is often a source of frustration when using hash tables in most lisps.

General memoization in Scheme

1 Answers