Continuing this series, in Common Lisp…
Memoizer
As before, we’ll be walking through a memoizing function — for review, it’s a function that will transforms an existing function into one that remembers previous results instead of recomputing them.
;;; memoizer
(defun memoizer (f)
(let ((store (make-hash-table)))
(labels
((replace-f (self n)
(let ((found (gethash n store)))
(if found
found
(setf (gethash n store) (funcall f self n))))))
#'replace-f)))
The first part of memoizer uses the Common Lisp function ‘make-hash-table‘ to create a new hash table, and assign it to a new local variable ‘store‘. You might also see this refered to as a ‘lexical variable‘, which simply means that you can only refer to the variable in that block of the program — a variable with the same name in a different block is a different variable.
(let ((store (make-hash-table))) ... )
Next, we’ll create a new replacement function nested in memoizer, named ‘replace-f‘. As in the Lua and Python examples, nested functions can refer to the outer lexical scope as well, so it can make use of ‘store‘ from within this replacement.
(labels
((replace-f (self n)
...))
...)
Replace-f works like f — it’s a function that takes two arguments, the first being a function to use for recursion, and the second is the value ‘n‘ for which we’re memoizing. This version will check for a cached value corresponding to ‘n‘, and if not found, recurse on the original function ‘f‘.
Lastly, we recursively call through the variable ‘f‘, the original function. In Common Lisp, variables and functions are separate namespaces, so to call through a variable, we use the funcall operator (similar to the .call syntax in Ruby):
(funcall f self n) ; call f with (self n) as arguments
Abstracting recursion
You may have noticed something up with how recursion is being done — instead of calling ‘(f n)‘ i’m calling ‘(f something n)‘. In the Python example recall, ‘fib’ was first defined to call ‘fib’ recursively, but since the name ‘fib’ is resolved dynamically in Python, by the time it gets called ‘fib’ now points to a different function — it’s no longer auto-recurive.
Alternately, ‘fib’ could be specified to take the replacement as an argument — and I’m doing that here. Rewriting fib to take itself as an argument:
;;; fixed-point version of fibonacci function
(defun fib-fixed (self n)
(if (< n 2)
1
(+ (funcall self self (- n 1))
(funcall self self (- n 2)))))
In this case, you can invoke "(fib #’fib 30)" to calculate the 30th fibonacci number, but it will take a while. We can now memoize this function though, without replacing the original function, by modifying the recursive ‘self’ parameter.
(defun fib (n)
(let ((memo-fib (memoizer #'fib-fixed)))
(funcall memo-fib memo-fib n)))
This function will create a new memo of fib, and then invoke with that memo.
If this seems inside out, you can always use Common Lisp’s dynamic capabilitied to redefine fib like was done in the earlier examples. Proof by example:
;;; simpler memoizer, doesn't require
;;; function to provide recursion parameter
(defun simple-memoizer (f)
(let ((store (make-hash-table)))
(labels
((replacement (n)
(let ((found (gethash n store)))
(if found
found
(setf (gethash n store) (funcall f n))))))
#'replacement)))
;;; define a global named *fib2* that is a function
(defparameter
*fib2*
(lambda (n)
(if (< n 2)
1
(+ (funcall *fib2* (- n 1))
(funcall *fib2* (- n 2))))))
;;; replate *fib2* with a memoized copy of the current
;;; value of *fib2*
(defparameter
*fib2* (simple-memoizer *fib2*))
;;; wrapper function
(defun fib2 (n) (funcall *fib2* n))
Try it out!
Copy all the complete code snippets seen here into a file named ‘memo.lisp’, and then you can load it at the REPL prompt, represented here by star (*).
* (load "memo.lisp") T * (loop for x upto 50 collecting (fib x)) (1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733 1134903170 1836311903 2971215073 4807526976 7778742049 12586269025 20365011074) *
And there ya go!