Greetings,
I've spent the best part of the last couple of days trying to figure
out how to make a macro that produces macros to iterate arrays of n
dimensions, with no success. I'm always one comma short. I would be
very grateful from any hint from backquote gurus.
The idea is that you should be able to say (nd-iterator 3), which would
create a macro do-3d-array that you can use to conveniently traverse an
array. In its most basic (useless) form it could look like this:
;;; A couple of helper macros:
;;; Paul Graham's on lisp
(defmacro with-gensyms (syms &body body)
`(let ,(mapcar #'(lambda (s)
`(,s (gensym)))
syms)
,@body))
;;; Peter Seibel's Practical Common Lisp
(defmacro once-only ((&rest names) &body body)
(let ((gensyms (loop for n in names collect (gensym))))
`(let (,@(loop for g in gensyms collect `(,g (gensym))))
`(let (,,@(loop for g in gensyms for n in names collect ``(,,g
,,n)))
,(let (,@(loop for n in names for g in gensyms collect `(,n
,g)))
,@body)))))
;;; This would actually build the code
(defun build-nd-iterator (ndims)
(with-gensyms (dim)
(labels ((dimf (nd)
(with-gensyms (dmax idx)
`(let* ((,dmax (nth (- ,ndims ,nd) ,dim)))
(do ((,idx 0 (+ ,idx 1)))
((= ,idx ,dmax))
,(if (= nd 1)
'(cons 'progn body) ; need a comma
here!
(dimf (decf nd))))))))
`(defmacro ,(intern (format nil "do-~Ad-array" ndims))
(mat &body body)
(once-only (mat)
`(let ((,',dim (array-dimensions ,mat)))
,',(dimf ndims)))))))
;;; And the macro
(defmacro nd-iterator (ndims)
(build-nd-iterator ndims))
If we try the code generation,
(pprint (build-nd-iterator 2))
we get
(DEFMACRO |do-2d-array| (MAT &BODY BODY)
(ONCE-ONLY (MAT)
`(LET ((#:G1698 (ARRAY-DIMENSIONS ,MAT)))
(LET* ((#:G1699 (NTH (- 2 2) #:G1698)))
(DO ((#:G1700 0 (+ #:G1700 1)))
((= #:G1700 #:G1699))
(LET* ((#:G1701 (NTH (- 2 1) #:G1698)))
(DO ((#:G1702 0 (+ #:G1702 1)))
((= #:G1702 #:G1701))
(CONS 'PROGN BODY))))))))
Which is very close to what we want: it just needs a comma in front of
the last line. But I can't see how to add it, despite having tried
many things that I wouldn't admit in public. Any suggestions? Maybe I
am following a wrong approach to the problem?
Thanks,
jm
······@gmail.com wrote:
> Greetings,
>
> I've spent the best part of the last couple of days trying to figure
> out how to make a macro that produces macros to iterate arrays of n
> dimensions, with no success. I'm always one comma short. I would be
> very grateful from any hint from backquote gurus.
Backquote is just an alternative syntax. If it's getting in your way,
don't use it or just use it as a building block in places where it does
what you want and don't use it for the whole structure.
Afterwards you'll probably see how to make it work with backquote.
······@gmail.com wrote:
> Greetings,
>> (pprint (build-nd-iterator 2))
>
> we get
... ah but that's where you are wrong.
> (DEFMACRO |do-2d-array| (MAT &BODY BODY)
> (ONCE-ONLY (MAT)
> `(LET ((#:G1698 (ARRAY-DIMENSIONS ,MAT)))
I ran your code under CLISP 2.38 and I get a regular quote here, not a
backquote.
Your assumption is that your macro-generating macro produces a DEFMACRO
containing a backquote. But in fact, the nested backquote can be
expanded all at once as one piece of syntax, and optimized. Inner
backquotes that don't interpolate anything can be compiled into forward
quotes.
So your very assumption is wrong. Even if you could assemble a
backquote out of pieces---a template of the outer backquote, and
separately created unquotes that are substituted into it---such a trick
wouldn't help you here, since you have no mating backquote for that
unquote.
As a rule of thumb, if the Lisp system, as a language extension, gives
you a target syntax for writing backquotes, you have to use that syntax
entirely, and not mix it with the backquote read syntax.
> (LET* ((#:G1699 (NTH (- 2 2) #:G1698)))
> (DO ((#:G1700 0 (+ #:G1700 1)))
> ((= #:G1700 #:G1699))
> (LET* ((#:G1701 (NTH (- 2 1) #:G1698)))
> (DO ((#:G1702 0 (+ #:G1702 1)))
> ((= #:G1702 #:G1701))
> (CONS 'PROGN BODY))))))))
Under CLISP, we can change this to (SYSTEM::UNQUOTE (CONS 'PROGN
BODY)). But it doesn't help us. We also have to construct the outer
backquote explicitly rather than relying on backquoted backquote sytax.
Here is a CLISP-specific hack, whose purpose is to illustrate how
tricky and non-portable this is to do your way:
(defun build-nd-iterator (ndims)
(with-gensyms (dim)
(labels ((dimf (nd)
(with-gensyms (dmax idx)
`(let* ((,dmax (nth (- ,ndims ,nd) ,dim)))
(do ((,idx 0 (+ ,idx 1)))
((= ,idx ,dmax))
,(if (= nd 1)
'(system::unquote (cons progn body))
(dimf (decf nd))))))))
`(defmacro ,(intern (format nil "do-~Ad-array" ndims))
(mat &body body)
(once-only (mat)
(,'system::backquote (let ((,dim (array-dimensions mat)))
,(dimf ndims))))))))
Note that you can't even write (system::backquote ...). We had to sneak
that in using (',system::backquote ...)
If you write (system::backquote (let ...)) the backquote expander will
think that the SYSTEM::BACKQUOTE was produced normally by the backquote
reader syntax. It will think that it's an ordinary nested backquote and
start processing it accordingly. And the problem with that will be that
the ,dim and ,(dimf ...) unquotes will then belong to that backquote
rather than the outer one.
So now when I run your code, I get this:
(DEFMACRO |do-2d-array| (MAT &BODY BODY)
(ONCE-ONLY (MAT)
`(LET ((#:G3158 (ARRAY-DIMENSIONS MAT)))
(LET* ((#:G3159 (NTH (- 2 2) #:G3158)))
(DO ((#:G3160 0 (+ #:G3160 1))) ((= #:G3160 #:G3159))
(LET* ((#:G3161 (NTH (- 2 1) #:G3158)))
(DO ((#:G3162 0 (+ #:G3162 1))) ((= #:G3162 #:G3161))
,(CONS PROGN BODY))))))))
which I think is what you want.
But, nonportable. Sorry.
To do it in portable CL, you will have to redesign your approach so
that it doesn't rely on the construction of backquote syntax out of
fragmented pieces.
"Kaz Kylheku" <········@gmail.com> writes:
> To do it in portable CL, you will have to redesign your approach so
> that it doesn't rely on the construction of backquote syntax out of
> fragmented pieces.
I think that this is one area where scheme gets it right, specifying
that `<form> expands to (backquote <form>) etc.
-russ
Kaz Kylheku wrote:
> Your assumption is that your macro-generating macro produces a DEFMACRO
> containing a backquote. But in fact, the nested backquote can be
> expanded all at once as one piece of syntax, and optimized. Inner
> backquotes that don't interpolate anything can be compiled into forward
> quotes.
That's a great point, I sure didn't expect it. I've installed clisp
2.38 and tried the version suggested by Pascal Constanza (posted
earlier) and it works ok. I hope that the different ways different
implementations failed are just symptoms of an originally flawed design
(and we can therefore expect predictable results for correct designs).
In any case, I've decided to take a completely different approach: a
do-array macro that iterates arrays of any rank, using row-major-aref
and some dirty tricks to build up the indices (if required). Here's
how it looks like (I believe this can be useful to somebody):
(defmacro do-array ((val mat &optional vidx) &body body)
(once-only (mat)
(with-gensyms (i dim idx n L v)
`(let* ((,dim (array-dimensions ,mat))
(,L (length ,dim))
(,idx (make-list ,L :initial-element 0))
,val)
(if ',vidx
(let (,@(loop for g in vidx collect `(,g 0)))
(dotimes (,i (array-total-size ,mat))
(setf ,val (row-major-aref ,mat ,i))
(multiple-value-setq ,vidx (values-list ,idx))
,@body
(dotimes (,n ,L)
(let ((,v (+ (nth (- ,L ,n 1) ,idx) 1)))
(if (< ,v (nth (- ,L ,n 1) ,dim))
(progn (setf (nth (- ,L ,n 1) ,idx) ,v)
(return))
(setf (nth (- ,L ,n 1) ,idx) 0))))))
(dotimes (,i (array-total-size ,mat))
(setf ,val (row-major-aref ,mat ,i))
,@body))))))
It's sort of ugly, but you don't pay any penalty if you don't care to
access the index variables. You'd use it like:
(do-array (v (make-array '(2 2 3) :initial-contents
'(((11 12 13)
(14 15 16))
((21 22 23)
(24 25 26))))
(p r c)) ; plane row col
(format t "~A ~A ~A -> ~A~%" p r c v))
or, faster,
(do-array (v (make-array '(2 2 3) :initial-contents
'(((11 12 13)
(14 15 16))
((21 22 23)
(24 25 26)))))
(format t "~A~%" v))
Thanks a lot for all the suggestions.
jm
······@gmail.com wrote:
> Kaz Kylheku wrote:
> > Your assumption is that your macro-generating macro produces a DEFMACRO
> > containing a backquote. But in fact, the nested backquote can be
> > expanded all at once as one piece of syntax, and optimized. Inner
> > backquotes that don't interpolate anything can be compiled into forward
> > quotes.
>
> That's a great point, I sure didn't expect it. I've installed clisp
> 2.38 and tried the version suggested by Pascal Constanza (posted
> earlier) and it works ok.
As you can see, your new version gets around the problem by computing
the backquote all in one piece. The DIMF function, and the unquote
within it where BODY is inserted, is now lexically enclosed by the
backquote.
So the whole problem of trying to construct backquote syntax from
pieces has gone away. The secondary backquote is constructed as a whole
inner backquote.
Nested backquote syntax only /looks/ like it constructs backquotes, but
that's not necessarily how it is implemented. So the inside piece that
/looks/ like a backquoted backquote may, in that very first expansion
of the outer backquote, be turned into the equivalent code, and not be
preserved as a backquote any longer.
In fact, backquotes can be expanded at read-time. So the whole thing
may become code in which there are no backquotes at all, before the
compiler or interpreter even gets a chance to see it.
Given something like:
`(let () `(inner ,backquoted ,',form ...))
the very first processing step may be to translate this whole thing
into code, perhaps resembling this:
(list 'let () (list 'list ''inner 'backquoted (list 'quote form)
...))
and so if the evaluation of any of these materials tries to construct
unquotes, they have no backquotes to match them.
All that matter is that the evaluation semantics are correct. Two
evaluations of the original form produce the form (inner
<value-of-BACKQUOTED> <value-of-FORM>)) where <value-of-BACKQUOTED> is
computed and substituted in the second evaluation round, and
<value-of-FORM> in the first, exactly as wanted.
Kaz Kylheku wrote:
> Given something like:
>
> `(let () `(inner ,backquoted ,',form ...))
>
> the very first processing step may be to translate this whole thing
> into code, perhaps resembling this:
>
> (list 'let () (list 'list ''inner 'backquoted (list 'quote form)
> ...))
>
> and so if the evaluation of any of these materials tries to construct
> unquotes, they have no backquotes to match them.
No wonder I couldn't find any example that did what I was trying to do.
I should be able to stay in safe waters now. Thanks again.
·······@gmail.com" <······@gmail.com> writes:
> In any case, I've decided to take a completely different approach: a
> do-array macro that iterates arrays of any rank, using row-major-aref
> and some dirty tricks to build up the indices (if required). Here's
> how it looks like (I believe this can be useful to somebody):
Fyi, regarding array reference, this is the reason that ROW-MAJOR-AREF
exists in the language.
These news postings are probably relevant if you want to read my comments
on that history...
<···············@shell01.TheWorld.com>
http://groups.google.com/group/comp.lang.lisp/msg/f361c5158f7c47db
<···············@shell01.TheWorld.com>
http://groups.google.com/group/comp.lang.lisp/msg/64a1715906a6e7b7
- - -
As far as backquote goes, I have comments to make there but no time to
make them today. I don't think the paradigm is fundamentally
deficient in any material way, though the notation is daunting. The
only short form suggestion I can make is that while it's possible to
get backquote to do most anything you need, there's often little value
in it. As people have observed, mixed-mode styles of backquote and
other construction operators usually avoid the common problems in a
more elegant way.
Kent M Pitman wrote:
> Fyi, regarding array reference, this is the reason that ROW-MAJOR-AREF
> exists in the language.
I'm very glad to see that I found a right answer.
> These news postings are probably relevant if you want to read my comments
> on that history...
It's great to be abe to peek into the origins of the language. I read
in one of your postings about displaced arrays; I might be able to use
for array slicing, which is what I am doing now. Maybe combine them
with a look-up table the size of the slice.
> As people have observed, mixed-mode styles of backquote and
> other construction operators usually avoid the common problems in a
> more elegant way.
I should have given up earlier, but it was painful to realize that I
didn't understand something I thought I understood. Good learning
though.
·······@gmail.com" <······@gmail.com> writes:
> In any case, I've decided to take a completely different approach: a
> do-array macro that iterates arrays of any rank, using row-major-aref
> and some dirty tricks to build up the indices (if required). Here's
> how it looks like (I believe this can be useful to somebody):
>
> (defmacro do-array ((val mat &optional vidx) &body body)
> (once-only (mat)
> (with-gensyms (i dim idx n L v)
> `(let* ((,dim (array-dimensions ,mat))
> (,L (length ,dim))
> (,idx (make-list ,L :initial-element 0))
> ,val)
> (if ',vidx
> (let (,@(loop for g in vidx collect `(,g 0)))
> (dotimes (,i (array-total-size ,mat))
> (setf ,val (row-major-aref ,mat ,i))
> (multiple-value-setq ,vidx (values-list ,idx))
> ,@body
> (dotimes (,n ,L)
> (let ((,v (+ (nth (- ,L ,n 1) ,idx) 1)))
> (if (< ,v (nth (- ,L ,n 1) ,dim))
> (progn (setf (nth (- ,L ,n 1) ,idx) ,v)
> (return))
> (setf (nth (- ,L ,n 1) ,idx) 0))))))
> (dotimes (,i (array-total-size ,mat))
> (setf ,val (row-major-aref ,mat ,i))
> ,@body))))))
>
> It's sort of ugly, but you don't pay any penalty if you don't care to
> access the index variables. You'd use it like:
>
> (do-array (v (make-array '(2 2 3) :initial-contents
> '(((11 12 13)
> (14 15 16))
> ((21 22 23)
> (24 25 26))))
> (p r c)) ; plane row col
> (format t "~A ~A ~A -> ~A~%" p r c v))
>
> or, faster,
>
> (do-array (v (make-array '(2 2 3) :initial-contents
> '(((11 12 13)
> (14 15 16))
> ((21 22 23)
> (24 25 26)))))
> (format t "~A~%" v))
>
> Thanks a lot for all the suggestions.
Oh, I see. I had this little macro:
(defmacro rloop (clauses &rest body)
(if (null clauses)
`(progn ,@body)
`(loop ,@(car clauses) do (rloop ,(cdr clauses) ,@body))))
(let ((a (make-array '(2 2 3) :initial-contents
'(((11 12 13)
(14 15 16))
((21 22 23)
(24 25 26))))))
(rloop ((for i from 0 below 2)
(for j from 0 below 2)
(for k from 0 below 3))
(format t "~A ~A ~A -> ~A~%" i j k (aref a i j k))))
Of course, if you want to scan all the dimensions of the array
automatically, it becomes more difficult. Here is another solution
that doesn't compute the indexes itself, but rely on the compiler at
run-time:
(defun gen-array-looper (dimensions indexes-p)
(let ((indexes (loop :repeat dimensions :collect (gensym)))
(maxes (loop :repeat dimensions :collect (gensym))))
(compile
nil
`(lambda (array bodyf)
(destructuring-bind ,maxes (array-dimensions array)
(rloop ,(loop
:for index :in indexes
:collect `(:for ,index :from 0 :below ,(pop maxes)))
(funcall bodyf (aref array ,@indexes)
,@(if indexes-p indexes '()))))))))
(defmacro do-array ((val mat &optional vidx) &body body)
(let ((vmat (gensym)))
`(let ((,vmat ,mat))
(funcall (gen-array-looper (length (array-dimensions ,vmat)) ',vidx)
,vmat (lambda (,val ,@vidx) ,@body)))))
If do-array is used often on arrays of the same dimensions, we could
profitably memoize the result of gen-array-looper.
Et hop! A macro with two reusable macro & functions :-)
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
Pascal Bourguignon wrote:
> Of course, if you want to scan all the dimensions of the array
> automatically, it becomes more difficult. Here is another solution
> that doesn't compute the indexes itself, but rely on the compiler at
> run-time:
Now that's a neat trick, compile at run time. I would have never
thought of it. Ever. And it works. I'll check out processing time
with a large array, and scrap my row-major-aref solution if this one is
faster. I am not especially proud of the way I figure out the indexes.
·······@gmail.com" <······@gmail.com> writes:
> Pascal Bourguignon wrote:
>> Of course, if you want to scan all the dimensions of the array
>> automatically, it becomes more difficult. Here is another solution
>> that doesn't compute the indexes itself, but rely on the compiler at
>> run-time:
>
> Now that's a neat trick, compile at run time. I would have never
> thought of it. Ever. And it works. I'll check out processing time
> with a large array, and scrap my row-major-aref solution if this one is
> faster. I am not especially proud of the way I figure out the indexes.
ROW-MAJOR-AREF can theorically lead faster times (in particular in the
case when you don't need to update indices), but it may depend on the
CL implementation.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we. -- Georges W. Bush
······@gmail.com wrote:
> Greetings,
>
> I've spent the best part of the last couple of days trying to figure
> out how to make a macro that produces macros to iterate arrays of n
> dimensions, with no success. I'm always one comma short. I would be
> very grateful from any hint from backquote gurus.
>
> The idea is that you should be able to say (nd-iterator 3), which would
> create a macro do-3d-array that you can use to conveniently traverse an
> array. In its most basic (useless) form it could look like this:
>
> ;;; A couple of helper macros:
>
> ;;; Paul Graham's on lisp
> (defmacro with-gensyms (syms &body body)
> `(let ,(mapcar #'(lambda (s)
> `(,s (gensym)))
> syms)
> ,@body))
>
> ;;; Peter Seibel's Practical Common Lisp
> (defmacro once-only ((&rest names) &body body)
> (let ((gensyms (loop for n in names collect (gensym))))
> `(let (,@(loop for g in gensyms collect `(,g (gensym))))
> `(let (,,@(loop for g in gensyms for n in names collect ``(,,g
> ,,n)))
> ,(let (,@(loop for n in names for g in gensyms collect `(,n
> ,g)))
> ,@body)))))
>
> ;;; This would actually build the code
> (defun build-nd-iterator (ndims)
> (with-gensyms (dim)
> (labels ((dimf (nd)
> (with-gensyms (dmax idx)
> `(let* ((,dmax (nth (- ,ndims ,nd) ,dim)))
> (do ((,idx 0 (+ ,idx 1)))
> ((= ,idx ,dmax))
> ,(if (= nd 1)
> '(cons 'progn body) ; need a comma
> here!
> (dimf (decf nd))))))))
> `(defmacro ,(intern (format nil "do-~Ad-array" ndims))
> (mat &body body)
> (once-only (mat)
> `(let ((,',dim (array-dimensions ,mat)))
> ,',(dimf ndims)))))))
>
> ;;; And the macro
> (defmacro nd-iterator (ndims)
> (build-nd-iterator ndims))
This is a problem of getting the phases right. The generated macro
accepts 'body as a parameter and must produce code that contains the
contents of 'body. What you are trying to do is generating that code as
part of the generating macro, not the generated macro. You're actually
trying to jump forward and then back again in time. It's the "jumping
back in time" part where you get bitten.
The solution is to defer code generation to be part of the generated
macro. So make dimf a local function of `(defmacro ,(intern ...) ...)
instead of 'build-nd-iterator. You have to shift the backquotes, quotes
and commas a little when you do that, but that should be relatively
straightforward to figure out.
I hope this helps.
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
Pascal Costanza wrote:
> ······@gmail.com wrote:
> The solution is to defer code generation to be part of the generated
> macro. So make dimf a local function of `(defmacro ,(intern ...) ...)
> instead of 'build-nd-iterator. You have to shift the backquotes, quotes
> and commas a little when you do that, but that should be relatively
> straightforward to figure out.
That did the trick, thank you very much! The working version:
(defun build-nd-iterator (ndims)
(with-gensyms (dim)
`(defmacro ,(intern (format nil "do-~Ad-array" ndims)) (mat &body
body)
(labels ((dimf (nd)
(with-gensyms (dmax i)
`(let ((,dmax (nth (- ,',ndims ,nd) ,',dim)))
(do ((,i 0 (+ ,i 1)))
((= ,i ,dmax))
,(if (= nd 1)
`(progn ,@body)
(dimf (decf nd))))))))
(once-only (mat)
`(let ((,',dim (array-dimensions ,mat)))
,(dimf ,ndims)))))))
Now I just have to make the indices available to the body. But I think
I've found a better way to solve the general problem: using
row-major-aref I should be able to write a do-nd-array that works for
arrays of any rank (for the record, I spent many hours trying to nail
down do-nd-array in a recursive version before deciding that it was
impossible, because the recursion parameter ---number of dimensions---
is not available at expansion time. Learning macros is expensive).
Thanks again,
jm