I'm trying to write a macro that defines functions. Basically, my macro
is used to define "cacheable" functions; that is, functions whose
results for a given set of arguments will always evaluate to the same
result, and have no side-effects. The idea is that I can write a
function like this (my example is just the ubiquitous Fibonacci
function):
(defcacheingfun fib (num)
(if (< num 2)
1
(+ (fib (- num 1)) (fib (- num 2)))))
And automatically set up a hashtable of arguments to results that is
queried on future invocations. Here's the macro that i have so far:
(defmacro defcacheingfun (name arglist &body body)
(let ((cached-args-result (gensym "cached-args-result"))
(all-args (gensym "all-args"))
(hashtable-result (gensym "hashtable-result"))
(hashtable-member-p (gensym "hashtable-member-p")))
`(progn
(defparameter ,cached-args-result (make-hash-table :size 1024))
(defun ,name ,arglist
(let ((,all-args ',arglist) (,hashtable-result)
(,hashtable-member-p))
(multiple-value-bind (,hashtable-result ,hashtable-member-p)
(gethash ,all-args ,cached-args-result)
(if ,hashtable-member-p
,hashtable-result
(progn
(setf (gethash ,all-args ,cached-args-result)
(progn
,@body))))))))))
The problem that I'm having is that because of the way that I've
implemented it, for it to work with recursive functions it requires that
the very last thing evaluated as part of the function be the body of the
macro, which becomes part of the body of the function. This is because
subordinate instances of the function will redefine ,all-args (since
that (gensym) is defined globally).
While that looks like that's already the case, this part:
(setf (gethash ,all-args ,cached-args-result)
(progn
,@body)
Is actually evaluated ,@body first, *then* (gethash) (I'm using clisp,
if that matters, but sbcl seems to do the same). This means that the
body is *not* the last thing evaluated (because ,all-args has been
re-assigned), and means that this macro cannot work with recursive
functions. Is there an easy solution to this? All of the solutions that
I've come up with "dirty" up the macro. Here's one that i came up with:
(let ((the-place (get-place (gethash ,all-args ,cached-args-result))))
(setf the-place
(progn
,@body)))
(that forces the setf "place" to be evaluated first). The problems here
are that "the-place" may "shadow" variables used within functions
created using the macro (because if I use (gensym), then it's a global
variable and I'm back where I started with subordinate recursions called
by ,@body overwriting it), and there doesn't appear to be a function
resembling "get-place" or any way to store or set to a setf-able place
like that.
is there a way to create a symbol from within the function (like
(gentemp))? The problem with that is that I have to call it something,
and I don't want to "shadow" variables created by the functions
themselves
I'm in the midst of learning Lisp as a personal goal, so I'm happy to
hear solutions that look totally different, but I'm also interested in
the mechanics of things like setf, "setf-able places", and macros that
write entire functions, so I'd like a solution that allows me to do what
I'm trying to accomplish, too.
Thanks in advance
--David
On Jun 3, 4:59 am, David King <····@ketralnis.com> wrote:
> I'm trying to write a macro that defines functions. Basically, my macro
> is used to define "cacheable" functions; that is, functions whose
> results for a given set of arguments will always evaluate to the same
> result, and have no side-effects.
What you are doing is called memoization.
http://en.wikipedia.org/wiki/Memoization
Peter Norvig's PAIP (Principles of Artificial Intelligence
Programming) gives a very elegant solution to defining memoized
functions in Common Lisp in section 9.1.
(Apologies for any code formatting issues ahead of time. I'm using
Google Groups.)
(defun memo (fn)
(let ((table (make-hash-table)))
#'(lambda (x)
(multiple-value-bind (val found-p)
(gethash x table)
(if found-p
val
(setf (gethash x table) (funcall fn x)))))))
(defun memoize (fn-name)
(setf (symbol-function fn-name) (memo (symbol-function fn-name))))
(defmacro defun-memo (fn args &body body)
`(memoize (defun ,fn ,args ,@body)))
With a little effort, you can adjust this technique to work with
functions that take more than one required argument.
On Sun, 03 Jun 2007 07:54:42 -0700, Geoff Wozniak <·············@gmail.com> said:
| On Jun 3, 4:59 am, David King <····@ketralnis.com> wrote:
|| I'm trying to write a macro that defines functions. Basically, my macro
|| is used to define "cacheable" functions; that is, functions whose
|| results for a given set of arguments will always evaluate to the same
|| result, and have no side-effects.
| What you are doing is called memoization.
| http://en.wikipedia.org/wiki/Memoization
And another related term is tabulation.
Terminologically, caching usually applies when there is an upper
bound on the size of the cache and thus a discipline for discarding
existing entries to make room for new ones, and often there also is
a notion of expiration time. Typically, caching pertains to a
storage or data access hierarchy, where upper levels are cheaper in
time and costlier in space, rather than a "computation" hierarchy.
---Vassil.
--
The truly good code is the obviously correct code.
Correction:
On 03 Jun 2007 11:32:47 -0400, Vassil Nikolov <···············@pobox.com> said:
| On Sun, 03 Jun 2007 07:54:42 -0700, Geoff Wozniak <·············@gmail.com> said:
| | On Jun 3, 4:59 am, David King <····@ketralnis.com> wrote:
| || I'm trying to write a macro that defines functions. Basically, my macro
| || is used to define "cacheable" functions; that is, functions whose
| || results for a given set of arguments will always evaluate to the same
| || result, and have no side-effects.
| | What you are doing is called memoization.
| | http://en.wikipedia.org/wiki/Memoization
| And another related term is tabulation.
| Terminologically, caching usually applies when there is an upper
^ insert here:
there is the possibility of entry invalidation,
| bound on the size of the cache and thus a discipline for discarding
| existing entries to make room for new ones, and often there also is
| a notion of expiration time. Typically, caching pertains to a
| storage or data access hierarchy, where upper levels are cheaper in
| time and costlier in space, rather than a "computation" hierarchy.
---Vassil.
--
The truly good code is the obviously correct code.
Vassil Nikolov <···············@pobox.com> writes:
> On Sun, 03 Jun 2007 07:54:42 -0700, Geoff Wozniak <·············@gmail.com> said:
>
> | On Jun 3, 4:59 am, David King <····@ketralnis.com> wrote:
> || I'm trying to write a macro that defines functions. Basically, my macro
> || is used to define "cacheable" functions; that is, functions whose
> || results for a given set of arguments will always evaluate to the same
> || result, and have no side-effects.
>
> | What you are doing is called memoization.
>
> | http://en.wikipedia.org/wiki/Memoization
>
> And another related term is tabulation.
Yet another related topic is dynamic programming.
David King <·····@ketralnis.com> writes:
> (multiple-value-bind (,hashtable-result ,hashtable-member-p)
> (gethash ,all-args ,cached-args-result)
MULTIPLE-VALUE-BIND makes new bindings so you need not bind the
variables with LET first.
> The problem that I'm having is that because of the way that I've
> implemented it, for it to work with recursive functions it requires that
> the very last thing evaluated as part of the function be the body of the
> macro, which becomes part of the body of the function. This is because
> subordinate instances of the function will redefine ,all-args (since
> that (gensym) is defined globally).
I think you are mistaken. Although you construct the symbol at
macroexpand time, the expansion uses LET to bind it as a lexical
variable. Recursive calls are then no problem. Your bug is
elsewhere. Try putting in some (print ,all-args) calls.
> (setf (gethash ,all-args ,cached-args-result)
> (progn
> ,@body)
>
> Is actually evaluated ,@body first, *then* (gethash) (I'm using clisp,
> if that matters, but sbcl seems to do the same).
Lisp should evaluate first ,all-args then ,cached-args-result
then ,@body and finally write the value to the hash based on the
results of the evaluations. In SBCL, I get:
* (macroexpand-1 '(setf (gethash a b) (progn c d)))
(LET* ((#:G3929 A) (#:G3930 B))
(MULTIPLE-VALUE-BIND
(#:G3932)
(PROGN C D)
(SB-KERNEL:%PUTHASH #:G3929 #:G3930 #:G3932)))
T
Of course, the value must be computed before it can be saved.
> is there a way to create a symbol from within the function (like
> (gentemp))?
Well you can call GENSYM or GENTEMP from within a function,
and then use it in EVAL and SYMBOL-VALUE and PROGV and such,
but usually you shouldn't.
> I'm in the midst of learning Lisp as a personal goal, so I'm happy to
> hear solutions that look totally different, but I'm also interested in
> the mechanics of things like setf, "setf-able places", and macros that
> write entire functions, so I'd like a solution that allows me to do what
> I'm trying to accomplish, too.
The following seems to mostly work:
(defmacro defcacheingfun (name lambda-list &body body)
(let ((cache (gensym "CACHE"))
(parameters (gensym "PARAMETERS"))
(values (gensym "VALUES")))
`(let ((,cache (make-hash-table :test 'equal)))
(defun ,name (&rest ,parameters)
(values-list
(let ((,values (gethash ,parameters ,cache t)))
(if (listp ,values)
,values
(setf (gethash ,parameters ,cache)
(multiple-value-list
(block ,name
(apply #'(lambda ,lambda-list
,@body)
,parameters)))))))))))
It supports multiple values, declarations, and RETURN-FROM.
However, it would be better to use original lambda list and
docstring because interactive Lisp environments could then
display them to the user. Also, :TEST 'EQUAL (used here
because argument lists are generally not EQL even if the
arguments themselves are) may be wrong for some functions.
In article <··············@Astalo.kon.iki.fi>,
Kalle Olavi Niemitalo <···@iki.fi> wrote:
> The following seems to mostly work:
Thanks to all who responded and pointed out that memoization is already
a well-defined concept that I'd basically re-implemented (Geoff), how to
use it (Pascal), corrected my cacheing terminology :) (Vassil), and
showed me how to make what I was trying to do work (Kalle) while
pointing out my incorrect assumptions.
I have another question about (setf) that I hope isn't too general.
Basically, how does it work? What defines a "setfable place"? It seems
like there is some magic going on in the background that defines them,
and I never did like magic. In the case of basic (setf)s, like those
that are simple assignments, it's pretty apparent that they are just
binding the variable name to a new value, but what about in more
complicated cases, like:
(setf (gethash a b) c)
gethash returns two values (the value of the key in the hash, and
whether the key exists in the hash), so how does (setf) use these return
values to get what seems to be the equivalent of a pointer without
returning one?
In Kalle's post, he showed:
> * (macoexpand-1 '(setf (gethash a b) (progn c d)))
> (LET* ((#:G3929 A) (#:G3930 B))
> (MULTIPLE-VALUE-BIND
> (#:G3932)
> (PROGN C D)
> (SB-KERNEL:%PUTHASH #:G3929 #:G3930 #:G3932)))
> T
So then, is (setf) a macro that knows how to deal with arguments that
are lists that begin with certain symbols ((gethash), (slot-value), and
others), or do (gethash) and (slot-value) actually return a sort of
value (a place) that (setf) knows how to access?
Is there an introduction to the concept somewhere that I can read?
On Jun 4, 12:39 am, David King <····@ketralnis.com> wrote:
> Thanks to all who responded and pointed out that memoization is already
> a well-defined concept that I'd basically re-implemented (Geoff), how to
> use it (Pascal), corrected my cacheing terminology :) (Vassil), and
> showed me how to make what I was trying to do work (Kalle) while
> pointing out my incorrect assumptions.
>
Hey, that's why we're here. :-)
> I have another question about (setf) that I hope isn't too general.
> Basically, how does it work? What defines a "setfable place"? It seems
> like there is some magic going on in the background that defines them,
> and I never did like magic.
The apparent magic comes from the world of SETF expanders and
functions.
http://www.lispworks.com/documentation/HyperSpec/Body/05_a.htm
Common Lisp generalizes the notion of a place, which can be altered
using library functions or non-standard compiler primitives.
Functions of this variety know how to change internal
representations. And of course, you can define your own.
The precise workings of SETF is a bit involved, but browsing section
5.1.2 of the CLHS helps a lot. Here's an example of a custom SETF
function.
(defclass silly-map ()
((stuff :initform nil :accessor silly-map-stuff)))
(defmethod getmap ((map silly-map) key)
(rest (assoc key (silly-map-stuff map))))
(defmethod (setf getmap) (value (map silly-map) key)
(let ((curr (assoc key (silly-map-stuff map))))
(if curr
(setf (cdr curr) value)
(push (cons key value) (silly-map-stuff map)))
value))
(defparameter *my-map* (make-instance 'silly-map))
(getmap *my-map* 0) => nil
(setf (getmap *my-map* 0) 100) => 100
(getmap *my-map* 0) => 100
(macroexpand-1 '(setf (getmap *my-map* 0) 100))
=>
(LET* ((#:G710560 *MY-MAP*) (#:G710559 100))
(FUNCALL #'(SETF GETMAP) #:G710559 #:G710560 0))
T
The function/method (SETF GETMAP) is what will update the map inside
an instance of a SILLY-MAP. And not surprisingly, it uses SETF on its
internal representation.
Basically, SETF's job is to evaluate things in the proper order and
then evaluate the form that actually updates the place. How it does
this depends on what the form is that indicates the place to be
updated. The full details are on the CLHS as I cited above.
On Sun, 03 Jun 2007 22:45:28 -0700, Geoff Wozniak <·············@gmail.com> said:
| ...
| http://www.lispworks.com/documentation/HyperSpec/Body/05_a.htm
That is certainly required reading (well, it is not a textbook,
though). I think it is useful to understand the requirements that
necessitate the magic of the setf expander game:
1. Ensure that all subforms of the place are evaluated in the
correct (left-to-right order), and that such order can be
mechanically arranged, even when the place is arbitrarily complex
(with nested forms).
2. Ensure that the "being a place" property of a form can be
propagated upwards in the more complicated case when it
(recursively) depends on a subform having this property. By
definition, there are no trivial examples, and the canonical one
is with (LDB f1 f2) being a place iff f2 is a place, so that
(INCF (LDB b X)) is good but (INCF (LDB b 0)) isn't (it is
irrelevant here that (DPB (+ (LDB b 0) 1) b 0) _is_ good; compare
also to (INCF (AREF (VECTOR 0) 0)), which is good, even though
pointless).
3. Ensure that all subforms are evaluated only once, even when place
is both read and written, so that modify macros work properly.
For example, (INCF (GETHASH f1 f2 0)) is not simply shorthand for
(SETF (GETHASH f1 f2) (+ (GETHASH f1 f2 0) 1)) in the general
case. Without this requirement, SETF would be considerably more
boring, possibly to the point of losing its raison d'etre.
The setf expander protocol with the five return values logically
follows from the above. This is one of the (many) beautiful parts
of Common Lisp.
---Vassil.
--
The truly good code is the obviously correct code.
David King wrote:
> I have another question about (setf) that I hope isn't too general.
> Basically, how does it work? What defines a "setfable place"? It seems
> like there is some magic going on in the background that defines them,
> and I never did like magic. In the case of basic (setf)s, like those
> that are simple assignments, it's pretty apparent that they are just
> binding the variable name to a new value, but what about in more
> complicated cases
I think the only difference is that there are more layers of
indirection. If you read up on defsetf, you'll find that most (all?)
getter functions have corresponding setter functions, and setf knows
about all of them. All setf does is it expands itself into the
appropriate setter function, depending on the getter function passed
to it. So a setfable place is just any location that's accessible
one way or another through a variable binding in the current
environment.
> So then, is (setf) a macro that knows how to deal with arguments that
> are lists that begin with certain symbols ((gethash), (slot-value), and
> others), or do (gethash) and (slot-value) actually return a sort of
> value (a place) that (setf) knows how to access?
The first option. Getter functions don't return locations, they return
values. I think the only getter whose setter I've never seen named
is gethash.
--
Dan
www.prairienet.org/~dsb/
Dan Bensen <··········@cyberspace.net> writes:
> I think the only getter whose setter I've never seen named is
> gethash.
You can find at least ten more in CLHS figure 5-7.
Hi,
David King <·····@ketralnis.com> writes
in thread (setf) order of evaluation of arguments):
> I have another question about (setf) that I hope isn't too general.
> Basically, how does it work? What defines a "setfable place"? It seems
> like there is some magic going on in the background that defines them,
> and I never did like magic.
I encourage you and fellow Lispers to try out
(multiple-value-list
(let (a b)
(push (values 1 2) (values a b))))
and
(multiple-value-list
(let (a b)
(push (values 1 2) (values a b))
(list a b))
in various implementations.
Hopefully it will generate interesting discussion here.
- CLISP will "vectorize" the push:
a <- (1), b <- (2) -- much to my surprize
- sbcl errors out during macroexpansion.
Actually, I'm unsure whether CLISP's behaviour follows from logical
interpretation of CLHS, taking the text to its full consequences.
It makes somehow sense, but I wonder about other surprising consequences.
See http://www.lisp.org/HyperSpec/Issues/iss309-writeup.html
Back in 1998, Sam Steingold changed CLISP to generate the above results.
However, even CLISP errors out on
(get-setf-expansion '(values a (ldb (byte 5 6) (values b c))))
(which is implicit for (setf (values a #) (values 1 2)) )
Isn't that as well (or not) defined as the previous example by ANSI CL?
Regards,
Jorg Hohle
Telekom/T-Systems Technology Center
Joerg Hoehle <······@users.sourceforge.net> wrote:
> (multiple-value-list
> (let (a b)
> (push (values 1 2) (values a b))
> (list a b))
> in various implementations.
>
> Hopefully it will generate interesting discussion here.
>
> - CLISP will "vectorize" the push:
> a <- (1), b <- (2) -- much to my surprize
> - sbcl errors out during macroexpansion.
>
> Actually, I'm unsure whether CLISP's behaviour follows from logical
> interpretation of CLHS, taking the text to its full consequences.
> It makes somehow sense, but I wonder about other surprising consequences.
>
> See http://www.lisp.org/HyperSpec/Issues/iss309-writeup.html
> Back in 1998, Sam Steingold changed CLISP to generate the above results.
I don't really see why PUSH would be required to support a place that
provides multiple values. There's no mention of that being required,
either in the issue writeup or on the description of PUSH. The
opposite is implied by all the mentions of "the list" in the
description being singular, not plural. On the other hand, there's an
explicit note about how multiple values should be dealt with in the
descriptions for ROTATEF and SHIFTF (the operators mentioned in the
writeup).
It also seems strange to just use the CLISP interpreration of this
issue with PUSH, but not to e.g. INCF. But maybe I'm just missing
something. Could you expand the reasoning for the CLISP behaviour a
bit?
--
Juho Snellman
On 11 Jun 2007 20:00:56 +0200, Joerg Hoehle <······@users.sourceforge.net> said:
| ...
| (let (a b)
| (push (values 1 2) (values a b)))
| ...
| See http://www.lisp.org/HyperSpec/Issues/iss309-writeup.html
Well, the issues are not part of the specification in any case.
And then is there any place in the specification that says that
(PUSH (VALUES 1 2) ...) should be any different than (PUSH 1 ...)?
(I am not aware of any such place.)
---Vassil.
--
The truly good code is the obviously correct code.
David King <·····@ketralnis.com> writes:
> I'm trying to write a macro that defines functions. Basically, my macro
> is used to define "cacheable" functions; that is, functions whose
> results for a given set of arguments will always evaluate to the same
> result, and have no side-effects. The idea is that I can write a
> function like this (my example is just the ubiquitous Fibonacci
> function):
>
> (defcacheingfun fib (num)
> (if (< num 2)
> 1
> (+ (fib (- num 1)) (fib (- num 2)))))
>
> And automatically set up a hashtable of arguments to results that is
> queried on future invocations. Here's the macro that i have so far:
Note that to do that you don't nede to do anything special. Just:
(defun fib (num)
(if (< num 2)
1
(+ (fib (- num 1)) (fib (- num 2)))))
(asdf-install:install :memoize) ; if not already done.
(asdf:oos 'asdf:load-op :memoize)
(memoize:memoize-function 'fib)
(fib 100)
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.