Newsgroups: comp.lang.lisp,comp.ai
Subject: Re: Automatic Memoization Facility Available
Distribution: world
References: <··········@aplcenmp.apl.jhu.edu>
····@aplcenmp.apl.jhu.edu (Marty Hall) writes:
>This message is to announce the availability of a facility for
>automatic memoization in Common LISP. Automatic memoization is a
>technique by which an existing function can be transformed into one
>that "remembers" previous arguments and their associated results,
>yielding large performance gains for certain types of applications.
Your message spurred me into activity, I thank you for sending it!
You might like to hear of the results of my activity. As follows:
MEMOISATION of APPLY
I have my own Lisp interpreter (not CL) which allows a symbol PNAME
to be an s-expression. So the following are valid symbol names:
(fib 1)
((lambda (x) x) 2)
After I saw your message on the net, I thought about adding
memoisation to the Lisp interpreter. I tried to memoise EVAL, but that
was a failure. I then memoised APPLY, by making it search the symbol
table to see if there is a symbol which looks like the form: (func arg
arg arg ....)
If so, it returns EVAL of that symbol and does not APPLY the func to the
args. (It returns the value of the symbol.)
This change seems to work without affecting existing programs, though
the interpreter is half the speed.
the result of this modification is that FIB can now be written as:
(defun fib (n)
(+ (fib (- n 1)) (fib (- n 2))) )
(assert `(,fib 1) 1) ; Make a symbol
(assert `(,fib 0) 1) ; Make a symbol
Notice the lack of CONDitional statements in FIB. It works because
the memoised (fib 1) => 1 and (fib 0) => 1 take precedence over the
application of FIB. ASSERT is a function that INTERNS a symbol with a
list for a name. APPLY picks up the symbol later.
This raises the possibility of extending DEFUN to allow things like:
(defun fib (1) 1)
(defun fib (0) 1)
CONCLUSION:
My conclusion is that a memoised APPLY is useful in its own
right, to get a more functional programming style. Explicit tabulations
can be used to remove CONDs.
QUESTION 1:
Are there any theorists out there who can tell me how memoisation
of APPLY fits in with the theory behind functional programming?
QUESTION 2:
Memoisation of EVAL appears to be possible but pointless. Is this
right?
QUESTION 3:
My prior experience in C programming is that considerable speedups
are possible without remembering _every_ result. For example, my
SIN function remembers only the previous call, because I know that
a lot of calls to it repeat the angle.
Can the MEMOISATION library use a queue of user specified length,
rather than a table? I think FIB only needs the previous two results.
Thanks in advance for your attention,
Bill
Bill Birch | ·······@uk03.bull.co.uk
Bull Info. Sys. Ltd. | Bull Tel: 773 4770
Maxted Road, | Bull Mail: HM14 UK03
Hemel Hempstead, | Tel: +44 442 884770
HERTS, HP2 7DZ, U.K. | Fax: +44 442 884570
Aviate, Navigate, Communicate...
;;;;----------------------------SOURCE CODE----------------------------
; handy function to create symbols which look like
; function applications
(defun assert (form result)
(set (addsym form) result)) ; add the new symbol with the form
; as a name, and set the result
; as its value.
; Fibonnacci Series
(defun fib (n)
; Note total lack of COND statements !!
(+ (fib (- n 1)) (fib (- n 2))) )
; Declare the terminating conditions of fibonacci series.
; These are found by APPLY in preference to an application.
(assert `(,fib 1) 1)
(assert `(,fib 0) 1)
;; Here is a memoised version of the fibonnacci series
;; which is very much faster than (fib)
(defun fib-fast (n)
; The assert statement saves the result for
; future executions of APPLY
(assert (list fib-fast n)
(+ (fib-fast (- n 1)) (fib-fast (- n 2))) ))
(assert `(,fib-fast 1) 1)
(assert `(,fib-fast 0) 1)
--
Bill Birch | ·······@uk03.bull.co.uk
Bull Info. Sys. Ltd. | Bull Tel: 773 4770
Maxted Road, | Bull Mail: HM14 UK03
Hemel Hempstead, | Tel: +44 442 884770
HERTS, HP2 7DZ, U.K. | Fax: +44 442 884570
Aviate, Navigate, Communicate...
In article <·····················@uk03.bull.co.uk> ······@hemel.bull.co.uk
(Bill Birch) writes:
[...]
>I have my own Lisp interpreter (not CL) which allows a symbol PNAME
>to be an s-expression. So the following are valid symbol names:
>
> (fib 1)
> ((lambda (x) x) 2)
>
>After I saw your message on the net, I thought about adding
>memoisation to the Lisp interpreter. I tried to memoise EVAL, but that
>was a failure. I then memoised APPLY, by making it search the symbol
>table to see if there is a symbol which looks like the form: (func arg
>arg arg ....)
>
>If so, it returns EVAL of that symbol and does not APPLY the func to the
>args. (It returns the value of the symbol.)
>
>This change seems to work without affecting existing programs [...]
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
I need to look more carefully at your LISP dialect. However, in Common
LISP there are a few gotchas. Ie the whole idea of automatic
memoization is that it makes functions faster without affecting their
semantics, and does this by having them cache previously calculated
results. However, this claim of not affecting existing programs does
not hold in every case. Most of these cases are obvious; automatic
memoization only works on true functions (not procedures), so any
"function" (in the LISP sense) that performs side effects, depends on
global values, etc, will not perform correctly after memoization. But
you also have to watch out more carefully for destructive operations.
Even if the memoized routine is a true function (in the sense of
output being totally determined by input), if destructive operations
are performed on the result, you have problems. Ie someone may know
that function Frobulate always conses up a new list, so they are free
to destructively hack the result. Someone else comes along later and
memoizes Frobulate, perhaps not even realizing what is being done with
the result. Voila: bugs that are hard to track down.
In Common LISP, there are a couple of other situations like this,
where users of memoization, if not warned ahead of time, can make
changes to the semantics of their programs without realizing it by
using automatic memoization. I am working on a draft of a paper that
outlines the empirical payoffs AND the unexpected pitfalls found in
using an automatic memoization facility over the last year on a DARPA
program.
>Can the MEMOISATION library use a queue of user specified length,
>rather than a table? I think FIB only needs the previous two results.
You lost me on why FIB only needs the previous two results. If I calculate
FIB of 100, and then come back later and ask for FIB 23, I would (in my view
of memoization) expect the answer immediately without calculation.
I've tried looking at all sorts of things to limit the size of the table.
One of my problems has been that a primary goal of memoization was to increase
efficiency, and I don't want to give up the behavior of near-constant-time
retrieval from the table (by using hash tables). I've had some trouble figuring
out a good scheme for limiting the table size that still maintains this. I can
do easy things like just stop adding entries to the table after a certain size,
but you would think frequency of access or time of last access should be a
factor in deciding what to keep or throw away from the table. But I've had
trouble doing this and still keeping my table-access time within a constant
factor of what it was before. There are a few heuristic schemes I'm still
looking at, but nothing that has yet grabbed me as being obviously good.
- Marty
PS I've gotten some mail from people asking for the IP address of the
host (archive.cs.umbc.edu) that the automatic memoization facility is on.
I wrote:
>PS I've gotten some mail from people asking for the IP address of the
>host (archive.cs.umbc.edu) that the automatic memoization facility is on.
Oops! Apparently our new mail reader chops the last line off of followups.
Anyhow, the IP address is 130.85.100.53.
- Marty
(proclaim '(inline skates))