Re: [math-fun] History of swap/exch computer instructions ?

Re: (rotatef a b c) <=> (progn (rotatef a b) (rotatef b c)) Not so fast! For example, (rotatef result freelist (cdr freelist)) has the effect of: (setq result (cons nil result)) or (push nil result) Try your suggestion: (setq freelist (list nil nil nil nil)) (NIL NIL NIL NIL)

(setq result 'end)

END

(rotatef result freelist (cdr freelist))

NIL

result

(NIL . END)

freelist

(NIL NIL NIL)

(setq freelist (list nil nil nil nil))

(NIL NIL NIL NIL)

(setq result 'end)

END

(rotatef result freelist)

NIL

(rotatef freelist (cdr freelist))

encountered a Lisp error: Error in CDR [or a callee]: END is not of type LIST. Automatically continuing. To reenable the Lisp debugger set *debugger-hook* to nil. Oops! At 09:05 AM 3/14/2018, Adam P. Goucher wrote:

Maybe the reason for lacking ROTATEF in modern instruction sets is that the n-ary rotation can be implemented using (n-1) SWAP instructions:

rotatef i_1 i_2 i_3 ... i_n

<==>

swap i_1 i_2 swap i_2 i_3 ... swap i_{n-1} i_n

Best wishes,

Adam P. Goucher

...

Sent: Wednesday, March 14, 2018 at 3:50 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] History of swap/exch computer instructions ?

Henry's understanding of the macro/function distinction in CL differs from mine. Even on the Lisp Machine, ROTATEF and SETF were both macros, though the compiler knew about them and had specific optimization along the lines Henry hints at. (I confirm that the rotation has leftward sense.) "Function" means specifically that arguments are evaluated in left-to-right order, and that only the values of the arguments were passed; the internals of a function have no access to the structure of the operand forms (as they need to for ROTATEF and SETF).

On Wed, Mar 14, 2018 at 10:27 AM, Henry Baker <hbaker1@pipeline.com> wrote:

...

One other point about EXCH/SWAP instructions:

Over the past decades I've played with these kinds of instructions via Common Lisp's "ROTATEF" function:

(rotatef (aref array i) (aref array j) (aref array k))

does a circular permutation (rotate left, I believe):

array[i]<-array[j]<-array[k]<-array[i]

Common Lisp places no requirement that these locations come from the same array; I merely did this to indicate that this was a "location" type of function akin to "SETF", rather than a "value" type of function. This made a lot more sense on the Lisp Machine, where rotatef could be an actual *function*, rather than just a very smart *macro*.

Of course, Common Lisp's rotatef can take any number of arguments; 0,1 are no-ops; 2 is SWAP/EXCH.

I have found the 3-argument version of rotatef perhaps the most useful for playing around with linked lists. I'm curious why this was never noticed by Knuth & others. Perhaps I'm the only one in the Lisp community that has ever used this rotatef feature?

At 11:15 PM 3/13/2018, Bill Gosper wrote:

...

Yes, JSP A,(A) . The PDP-6 had every imaginable subroutine instruction, jsp, jsr, jda, and, of course pushj, the latter as a sop to the Lisp community. Ironically, pushj turned out to be so fantastically useful that hardly anybody used the others. There was also UUO (unused opcode), which trapped to a uuo handler that could implement any kind of calling sequence you could dream up. It was sometimes possible to "outbum" pushj code using using jsp with an "implicit calling sequence". Instead of storing arguments after the jsp and then skipping over them upon return, you returned to the immediately subsequent instructions, which contrived to mention the arguments, which the subroutine fetched via (possibly multilevel) indirect addressing, with indexing at every level. Given the 16 triple purpose accumulators, it was usually possible to rearrange your steps to suit the expectations of the subroutine. And, of course, you could transmit multiple arguments in the accumulators. It was the greatest order code ever devised. --rwg

Also, I think HAKMEM mentions representing free storage as a linked list of exch instructions. (Talk about data execution.)

At the time, the machine was ridiculed for devoting an entire halfword (18 bits) to address memory, since nobody could need nor afford an entire megabyte. Instead of "Just you wait!", DEC mumbled meekly about symmetry.