Permuting array rows

[Jason Sewall]

I posted this to /r/common_lisp, but nobody seemed interested, so I thought I'd try this turf.

I have some array rows I'd like to permute; I'd like a function/macro

> (setf A (make-array '(3 6) :initial-contents '((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))))
#2A((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))
> (rotatef-rows A (list 0 2 1))
#2A((12 13 14 15 16 17) (0 1 2 3 4 5) (6 7 8 9 10 11))

Clearly there are some ways this can be done with a few loops and a spare buffer, but I was wondering if there was some more elegant way of doing it. I wanted something that would expand to

(dotimes (i (array-dimension A 1))
(rotatef (aref A 0 i) (aref A 2 i) (aref A 1 i)))

but as far I as can tell, the macroness of rotatef means that I can't do this unless my permutation list is known at expansion time.

Is the "pretty" solution one involving define-modify-macro, which I never learned?

[Tamas Papp]

My CL-SLICE library can do something similar, although not
destructively, and the syntax is a bit different from rotation:

--8<---------------cut here---------------start------------->8---
(asdf:load-systems :cl-slice)
(use-package :cl-slice)

(let ((a #2A((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))))
(slice a #(2 0 1) t))
;; => #2A((12 13 14 15 16 17) (0 1 2 3 4 5) (6 7 8 9 10 11))
--8<---------------cut here---------------end--------------->8---

I don't think you can define a macro for the general case, but maybe
someone will come up with a clever solution. Writing a function for
in-place rotation would not be that complicated either.

Best,

Tamas

[Jeff Barnett]

Jason Sewall wrote, On 5/17/2013 1:15 AM:

> Original message deleted - lines too long for me to post, sorry.

A problem using rotatef or any of the ...f functions is that an array
row isn't a place. The expansions depend on a way to access a place as a
unit. On the other hand, if you had an array (1D) of lists, each array
element, now a row, would be a place. Of course, rotatef expects an
explicit list of places as arguments. So in my opinion, what you are
trying to do does not fit the ...f function model at all.

Jeff Barnett

[Jason Sewall]

On Friday, May 17, 2013 8:20:19 AM UTC-7, Jeff Barnett wrote:
> Jason Sewall wrote, On 5/17/2013 1:15 AM:
>
> > Original message deleted - lines too long for me to post, sorry.

Sorry about that; I was using the Google web interface and I assumed
it could wrap lines for me. Actually, can't your reader wrap it?

> A problem using rotatef or any of the ...f functions is that an array
> row isn't a place. The expansions depend on a way to access a place as a
> unit. On the other hand, if you had an array (1D) of lists, each array
> element, now a row, would be a place. Of course, rotatef expects an
> explicit list of places as arguments. So in my opinion, what you are
> trying to do does not fit the ...f function model at all.

I thought my 'sketch' of the way I'd like the code to look like was
clear, and that I wasn't trying anything like (rotatef (row A 0) (row
A 1)); even if that were possible, the underlying problem is that I
can't build a 'call' to rotatef without knowing the number of rows
I'll be permuting.

I agree that it doesn't fit the *f model (which is actually 'macro
model'), but it is because there is no 'apply' for macros. The best
solution I know of is to write your own rotatef in the code for the
job (using cl-iterate, and without any pesky error-checking):

(defun rotate-rows (A rows)
(dotimes (v (array-dimension A 1))
(iter (with w = (aref A (car rows) v))
(for r on rows)
(while (cdr r))
(setf (aref A (car r) v) (aref A (cadr r) v))
(finally (setf (aref A (car r) v) w)))))

I guess my point for posting this question here was see if the
resident paren-ninjas knew a macro-wizardry trick that allows
something like this to be written in terms of rotatef.

Cheers,
Jason

[Pascal J. Bourguignon]

Jason Sewall <jason...@gmail.com> writes:

> On Friday, May 17, 2013 8:20:19 AM UTC-7, Jeff Barnett wrote:
>> Jason Sewall wrote, On 5/17/2013 1:15 AM:
>>
>> > Original message deleted - lines too long for me to post, sorry.
>
> Sorry about that; I was using the Google web interface and I assumed
> it could wrap lines for me. Actually, can't your reader wrap it?
>
>> A problem using rotatef or any of the ...f functions is that an array
>> row isn't a place. The expansions depend on a way to access a place as a
>> unit. On the other hand, if you had an array (1D) of lists, each array
>> element, now a row, would be a place. Of course, rotatef expects an
>> explicit list of places as arguments. So in my opinion, what you are
>> trying to do does not fit the ...f function model at all.
>
> I thought my 'sketch' of the way I'd like the code to look like was
> clear, and that I wasn't trying anything like (rotatef (row A 0) (row
> A 1)); even if that were possible, the underlying problem is that I
> can't build a 'call' to rotatef without knowing the number of rows
> I'll be permuting.

Yes, it was clear, and you correctly analysed the problem. The solution
would be indeed to generate the function with the hard-coded row indexes
at run-time, and to compile it before calling it (or have it
interpreted). In both cases, it would be slow.

> I agree that it doesn't fit the *f model (which is actually 'macro
> model'), but it is because there is no 'apply' for macros.

No, it is because macros are designed to work at compilation time. You
could write an apply for macro, but it would still means compilation or
interpretation of a run-time generated function.

> The best solution I know of is to write your own rotatef in the code
> for the job

Definitely, just write your own function.

> (using cl-iterate, and without any pesky error-checking):
>
> (defun rotate-rows (A rows)
> (dotimes (v (array-dimension A 1))
> (iter (with w = (aref A (car rows) v))
> (for r on rows)
> (while (cdr r))
> (setf (aref A (car r) v) (aref A (cadr r) v))
> (finally (setf (aref A (car r) v) w)))))
>
> I guess my point for posting this question here was see if the
> resident paren-ninjas knew a macro-wizardry trick that allows
> something like this to be written in terms of rotatef.

If you have to do permutations of rows a lot, you could instead
permutate the rows, using vectors of vectors.


(defun a->vv (a)
(loop
:with width = (array-dimension a 1)
:with height = (array-dimension a 0)
:with v = (make-array height)
:for i :below height
:do (setf (aref v i) (make-array width
:displaced-to a
:displaced-index-offset (* i width)))
:finally (return v)))

(a->vv #2A((1 2 3) (4 5 6) (7 8 9)))
;; --> #(#(1 2 3) #(4 5 6) #(7 8 9))

(aref #2A((1 2 3) (4 5 6) (7 8 9)) 1 2)
;; --> 6

(aref (aref (a->vv #2A((1 2 3) (4 5 6) (7 8 9))) 1) 2)
;; --> 6

(let ((v (a->vv #2A((1 2 3) (4 5 6) (7 8 9)))))
(rotatef (aref v 2) (aref v 0) (aref v 1))
v)
;; --> #(#(4 5 6) #(7 8 9) #(1 2 3))


Of course, if you also need to use aref a lot on those vectors of
vectors, you can also define:

(defun vvref (vv i j) (aref (aref vv i) j))
(defun (setf vvref) (nv vv i j) (setf (aref (aref vv i) j) nv))

(vvref (a->vv #2A((1 2 3) (4 5 6) (7 8 9))) 1 2)
;; --> 6



--
__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
You can take the lisper out of the lisp job, but you can't take the lisp out
of the lisper (; -- antifuchs

[RG]

In article <1eb85577-7c49-4725...@googlegroups.com>,

No, the "pretty" solution is something like this:

(defstruct permuted-array array indirection-vector)

(defun p-aref (permuted-array row col)
(aref array (aref indirection-vector row) col))

Iniitalize the indirection vector to be the integers from 0 to
number-of-rows. Then permute the indirection vector, not the array.

rg

[Jason Sewall]

On Saturday, May 18, 2013 9:58:52 AM UTC-7, RG wrote:
> In article <1eb85577-7c49-4725...@googlegroups.com>,

> Jason Sewall wrote:

> > Is the "pretty" solution one involving define-modify-macro, which I never
> > learned?
>
> No, the "pretty" solution is something like this:
>
> (defstruct permuted-array array indirection-vector)
>
> (defun p-aref (permuted-array row col)
> (aref array (aref indirection-vector row) col))
>
> Iniitalize the indirection vector to be the integers from 0 to
> number-of-rows. Then permute the indirection vector, not the array.

Clearly, this does not solve the problem that I specified. I'm
not saying it's a bad approach, my question was one of how to
implement an algorithm, not what algorithm to use for a high-level
problem.

Cheers,
Jason

[Pascal Costanza]

On 17/05/2013 22:39, Pascal J. Bourguignon wrote:
> Jason Sewall <jason...@gmail.com> writes:
>
>> On Friday, May 17, 2013 8:20:19 AM UTC-7, Jeff Barnett wrote:
>>> Jason Sewall wrote, On 5/17/2013 1:15 AM:
>>>
>>> > Original message deleted - lines too long for me to post, sorry.
>>
>> Sorry about that; I was using the Google web interface and I assumed
>> it could wrap lines for me. Actually, can't your reader wrap it?
>>
>>> A problem using rotatef or any of the ...f functions is that an array
>>> row isn't a place. The expansions depend on a way to access a place as a
>>> unit. On the other hand, if you had an array (1D) of lists, each array
>>> element, now a row, would be a place. Of course, rotatef expects an
>>> explicit list of places as arguments. So in my opinion, what you are
>>> trying to do does not fit the ...f function model at all.
>>
>> I thought my 'sketch' of the way I'd like the code to look like was
>> clear, and that I wasn't trying anything like (rotatef (row A 0) (row
>> A 1)); even if that were possible, the underlying problem is that I
>> can't build a 'call' to rotatef without knowing the number of rows
>> I'll be permuting.
>
> Yes, it was clear, and you correctly analysed the problem. The solution
> would be indeed to generate the function with the hard-coded row indexes
> at run-time, and to compile it before calling it (or have it
> interpreted). In both cases, it would be slow.

Not sure I recommend the following solution, but it's fun. ;)


(defmethod rotate-function (n a is j)
(let ((m `(lambda ()
(defmethod rotate-function ((n (eql ,n)) a is j)
(rotatef ,@(loop repeat n
collect '(aref a (pop is) j)))))))
(funcall (compile nil m)))
(rotate-function n a is j))

(defun rotate-rows (a &rest is)
(loop with n = (array-dimension a 0)
for j below (array-dimension a 1)
do (rotate-function n a is j)
finally (return a)))


Pascal

--
My website: http://p-cos.net
Common Lisp Document Repository: http://cdr.eurolisp.org
Closer to MOP & ContextL: http://common-lisp.net/project/closer/
The views expressed are my own, and not those of my employer.

[Madhu]

* Jeff Barnett <kn5hre$tf3$2...@speranza.aioe.org> :
Wrote on Fri, 17 May 2013 09:20:19 -0600:

| A problem using rotatef or any of the ...f functions is that an array
| row isn't a place. The expansions depend on a way to access a place as
| a unit. On the other hand, if you had an array (1D) of lists, each
| array element, now a row, would be a place. Of course, rotatef expects
| an explicit list of places as arguments. So in my opinion, what you
| are trying to do does not fit the ...f function model at all.

You could define a ROW as a CL PLACE

(defun row (array i)
(make-array (array-dimension array 1)
:displaced-index-offset (array-row-major-index array i 0)
:displaced-to array))

;; then the OP could write the macro he wanted:

(defmacro rotatef-rows (array row-indices)
(let ((array-var (gensym "ARR-")))
`(let ((,array-var ,array))
(rotatef ,@(loop for i in row-indices
collect `(row ,array-var ,i))))))

;; this of course requires an appropriate SETF function or SETF-EXPANDER
;; (see spec section 5.1.1.2)

(define-setf-expander row (array i)
(let ((array-var (gensym "ARRAY"))
(row-index (gensym "I"))
(new-value-var (gensym "NEWROW")))
(values
`(,array-var ,row-index)
`(,array ,i)
`(,new-value-var)
`(progn
(dotimes (.j. (array-dimension ,array-var 1)
,new-value-var)
(setf (aref ,array-var ,row-index .j.)
(aref ,new-value-var .j.))))
`(COPY-SEQ (row ,array ,row-index)))))

#+nil
(progn
(defparameter $a

(make-array '(3 6)
:initial-contents
'((0 1 2 3 4 5)
(6 7 8 9 10 11)
(12 13 14 15 16 17))))

(rotatef-rows $A (list 0 2 1))
$a)


For outstanding issues: 1. the COPY-SEQ defeats the whole point of doing
modifications in-place, without excessive copying. 2. This assumes 2-D
arrays, but this could be generalized to full insanity: ROW could return
a displaced array of any [sub] dimensions. ---Madhu

[WJ]

Tamas Papp wrote:

> On Fri, May 17 2013, Jason Sewall wrote:
>
> > I posted this to /r/common_lisp, but nobody seemed interested, so I thought I'd try this turf.
> >
> > I have some array rows I'd like to permute; I'd like a function/macro
> >
> >> (setf A (make-array '(3 6) :initial-contents '((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))))
> > #2A((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))
> >> (rotatef-rows A (list 0 2 1))
> > #2A((12 13 14 15 16 17) (0 1 2 3 4 5) (6 7 8 9 10 11))
> >
> > Clearly there are some ways this can be done with a few loops and a
> > spare buffer, but I was wondering if there was some more elegant way
> > of doing it. I wanted something that would expand to
> >
> > (dotimes (i (array-dimension A 1))
> > (rotatef (aref A 0 i) (aref A 2 i) (aref A 1 i)))
> >
> > but as far I as can tell, the macroness of rotatef means that I can't do this unless my permutation list is known at expansion time.
> >
> > Is the "pretty" solution one involving define-modify-macro, which I never learned?
>
> My CL-SLICE library can do something similar, although not
> destructively, and the syntax is a bit different from rotation:
>
> --8<---------------cut here---------------start------------->8---
> (asdf:load-systems :cl-slice)
> (use-package :cl-slice)
>
> (let ((a #2A((0 1 2 3 4 5) (6 7 8 9 10 11) (12 13 14 15 16 17))))
> (slice a #(2 0 1) t))
> ;; => #2A((12 13 14 15 16 17) (0 1 2 3 4 5) (6 7 8 9 10 11))

Clojure:

user=> (replace [[0 1] [2 3] [4 5]] [2 0 1])
[[4 5] [0 1] [2 3]]

[Jason Sewall]

On Sunday, May 19, 2013 8:34:02 AM UTC-7, Madhu wrote:

<snip>

> ;; then the OP could write the macro he wanted:
>
> (defmacro rotatef-rows (array row-indices)
> (let ((array-var (gensym "ARR-")))
> `(let ((,array-var ,array))
> (rotatef ,@(loop for i in row-indices
> collect `(row ,array-var ,i))))))
>

<snip>

> (rotatef-rows $A (list 0 2 1))
> $a)
>
> For outstanding issues: 1. the COPY-SEQ defeats the whole point of doing
> modifications in-place, without excessive copying. 2. This assumes 2-D
> arrays, but this could be generalized to full insanity: ROW could return
> a displaced array of any [sub] dimensions. ---Madhu

Did you run this code? Both sbcl and ecl choke on 'list' in the second
argument to rotatef-rows, because it is never evaluated. It will only
work for literal, unquoted lists e.g. "(rotatef-rows $A (0 2 1))".

The row-setting stuff is neat (I have never seriously studied places
and setf-expanders, so it was neat to see one created, but it is
orthogonal to the problem. Your 'rotatef-rows' looks almost exactly
like the original one I wrote before I got on here.

I am fairly convinced now that my original problem of clever
macro-writing isn't a great exercise, because the problem is
fundamental: to build a call to rotatef, you have to do it at
macroexpansion time, which means you have to know the length of
row-indices during expansion.

My original note probably needed more of the classical "Do you really
need a macro for this" scrutiny, although I suppose I was really
asking to see if it was possible as a macro, not if it was advisable
:)

Cheers,
Jason

[Jason Sewall]

On Sunday, May 19, 2013 2:51:31 AM UTC-7, Pascal Costanza wrote:
> Not sure I recommend the following solution, but it's fun. ;)
>
> (defmethod rotate-function (n a is j)
> (let ((m `(lambda ()
> (defmethod rotate-function ((n (eql ,n)) a is j)
> (rotatef ,@(loop repeat n
> collect '(aref a (pop is) j)))))))
> (funcall (compile nil m)))
> (rotate-function n a is j))
>
> (defun rotate-rows (a &rest is)
> (loop with n = (array-dimension a 0)
> for j below (array-dimension a 1)
> do (rotate-function n a is j)
> finally (return a)))

This is a little gross, but it does solve the problem of essentially
needing a collection of rotatef wrappers with a differing number of
arguments. Neat!

[RG]

In article <4ef59fe7-a2ba-4a55...@googlegroups.com>,

You said you wanted "some more elegant way of doing it" without being
specific about what "it" was. But OK...

> the macroness of rotatef means that I can't do this unless my permutation
> list is known at expansion time.

Actually all you need to know is the length of your list/number of rows.

But on what metric are you judging elegance here? What's so great about
ROTATEF? Is this elegant?

(defun permute-array (a l)
(dotimes (i (second (array-dimensions a)))
(let ((tmp (aref a (car l) i)))
(dolist (j (cdr l))
(rotatef tmp (aref a j i)))
(rotatef tmp (aref a (car l) i)))))

or something like that? (It's not entirely clear to me what the
semantics of your permutation list are supposed to be.)

rg

[Pascal Costanza]

It's probably better to put the loop over (array-dimension a 1) in the
method body as well, because Common Lisp implementations are usually not
good at inlining generic function calls, so you want to avoid them in
tight loops...