如何理解《Land of Lisp》329页闭包实现Memoization的示例代码？

Great question! Let's unpack this clever memoization snippet from Land of Lisp page 329—Conrad Barski does a nice job of using Common Lisp closures and hash tables to cut down on redundant function calls. Here's a step-by-step breakdown:

First, let's restate the full code for reference:

(let ((old-neighbors (symbol-function 'neighbors)) 
      (previous (make-hash-table)))
  (defun neighbors (pos)
    (or (gethash pos previous)
        (setf (gethash pos previous) (funcall old-neighbors pos)))))

Step 1: The let Block - Capturing Private State #

The outer let creates two local variables that the redefined neighbors function will "close over" (this is where the term closure comes from):

• old-neighbors: This grabs the original implementation of the neighbors function using (symbol-function 'neighbors). We need to save this because we're about to redefine neighbors—we don't want to lose the core logic that actually calculates neighbors!
• previous: This initializes an empty hash table (make-hash-table) that will act as our cache. It maps position values (pos) to their precomputed neighbor lists.

Step 2: Redefining neighbors with Caching Logic #

Inside the let, we overwrite the neighbors function to add memoization. The heart of the new function is this line:

(or (gethash pos previous)
    (setf (gethash pos previous) (funcall old-neighbors pos)))

This relies on Common Lisp's short-circuiting or behavior—here's what happens step by step:

1. First, it checks if pos exists in the previous hash table with (gethash pos previous). If the key exists, gethash returns the cached neighbor list right away, and the or stops here.
2. If pos isn't in the cache, gethash returns nil. The or then moves to the second clause:
   • It runs the original neighbors logic via (funcall old-neighbors pos) to compute the actual neighbor list for pos.
   • It stores this computed result in the hash table using setf (so future calls for the same pos will find it).
   • Finally, it returns the computed result (since setf returns the value it just stored).

Why the Closure Makes This Work #

The key trick here is that the redefined neighbors function keeps access to old-neighbors and previous even after the let block finishes running. These variables are private—no other code can mess with the cache or the original function logic accidentally. This means:

• The cache persists between calls to neighbors—it doesn't get reset every time you invoke the function.
• The original neighbors logic is safely tucked away and only used when absolutely necessary.

Full Workflow Example #

Let's walk through a real-world scenario to make this concrete:

1. First call: (neighbors '(1 2))
   • gethash looks for '(1 2) in previous—it's not there, so returns nil.
   • funcall old-neighbors '(1 2) runs the original logic, say returning '((0 2) (1 1) (1 3) (2 2)).
   • This result is stored in previous under the key '(1 2).
   • The result is returned to the caller.
2. Subsequent calls: (neighbors '(1 2))
   • gethash finds '(1 2) in previous and returns the cached list immediately.
   • No need to run the original (potentially slow) neighbors logic again—this is where the performance gain comes from!

内容的提问来源于stack exchange，提问作者Dominik Mokriš