Re: [Chicken-users] Memoizing a procedure

[Peter Bex]

On Sun, Nov 28, 2010 at 12:53:53PM -0300, Hugo Arregui wrote:
> Hi guys,

Hi Hugo!

> I wrote a small code to add procedure memoization, most for learning
> purposes (attached).
> I'm glad to ear your suggestions.

It looks good to me.  It only works for simple procedures though,
not for procedures with optional arguments or keyword arguments.
Keyword args can be in any order, and an optional argument can be
identical to a missing argument when it has the value of the default.

A small optimization would be not to check the hash table first and
then perform another lookup.  You could perform one lookup and have
that immediately check whether the value is stored in the hash table:

(define (make-memoized proc)
  (let ((memo (make-hash-table))
        (missing (list 'missing)))
    (lambda args
      (let ((result (hash-table-ref/default memo args missing)))
        (when (eq? result missing)
          (set! result (apply proc args))
          (hash-table-set! memo args result))
        result))))

You could also use hash-table-ref and catch the exception it throws
when it can't find the key, but that's even uglier (and can result in
a problem when the procedure itself calls hash-table-ref or raises
a similar error).

You can also remove the reference to srfi-1 as you don't seem to be
using procedures from it.

> Also, I cheked advice egg, but I cannot find the way to reuse in this
> particular case.

I don't think the advice egg would add a lot.  You could use it like
this:

---------------------------------------------------------------------------
(use srfi-69 advice)
(define-syntax mdefine (syntax-rules ()
                         ((mdefine (proc v ...) body ...)
                          (begin (define (proc v ...) body ...)
                                 (memoize proc)))))

(define (memoize proc)
  (let  ((memo (make-hash-table))
         (missing (list 'missing)))
    (advise 'around proc
            (lambda (inner args)
              (let ((result (hash-table-ref/default memo args missing)))
                (when (eq? result missing)
                  (set! result (apply inner args))
                  (hash-table-set! memo args result))
                result))
            'memoized)))

(define (dememoize proc)
  (unadvise proc 'memoized))
---------------------------------------------------------------------------

The advantage of this is that this allows you to make any preexisting
procedure memoized without having to make a new procedure.  Anyone calling
the original procedure will then be calling the memoized version, which
would not happen with your code (because it produces a new, memoized
procedure and others still have a reference to the original non-memoized
version)

Advice also makes it easy to remove memoization from a procedure.

Cheers,
Peter
-- 
http://sjamaan.ath.cx
--
"The process of preparing programs for a digital computer
 is especially attractive, not only because it can be economically
 and scientifically rewarding, but also because it can be an aesthetic
 experience much like composing poetry or music."
                                                        -- Donald Knuth