In my self-study program, I'm currently working through "Common Lispcraft" by
J.Wilensky. One of the end-of-chapter exercises asks for code to transpose
matrices given a representation like:
((e00 e01 e02) (e10 e11 e12) (e20 e21 e22))
My solution was:
(defun transpose (matrix)
(cond ((null matrix) nil)
((null (car matrix)) nil)
(t (cons (mapcar 'car matrix)
(transpose (mapcar 'cdr matrix))))))
There is also a "hint" that suggests that the that most concise solution
involves #'apply of a mapping function. I can't for the life of me figure out
a solution that includes #'apply at all.
Obviously it's my inexperience that's holding me back, so I'm asking for some
on-the-spot mentoring. Anyone? Please?
+Mitchell
--
Mitchell Morris
A Woman's Rule of Thumb: If it has tires or testicles, you're going to have
trouble with it.
* Mitchell Morris wrote:
> There is also a "hint" that suggests that the that most concise solution
> involves #'apply of a mapping function. I can't for the life of me figure out
> a solution that includes #'apply at all.
(defun awful-transpose (matrix)
(apply #'mapcar #'list matrix))
You should now go and read Gabriel's `worse is better' paper to see
why this kind of thing is bad.
--tim
In article <···············@lostwithiel.tfeb.org>, Tim Bradshaw wrote:
>* Mitchell Morris wrote:
>
>> There is also a "hint" that suggests that the that most concise solution
>> involves #'apply of a mapping function. I can't for the life of me figure out
>> a solution that includes #'apply at all.
>
>(defun awful-transpose (matrix)
> (apply #'mapcar #'list matrix))
I now officially despair of ever learning to think in Lisp. I see that this
works, and I even can see how it works, but I don't know that I would ever
have figured it out otherwise.
>You should now go and read Gabriel's `worse is better' paper to see
>why this kind of thing is bad.
>
>--tim
Actually, I've read this paper several times. I'm not sure what lesson I
should be drawing in this particular context.
+Mitchell
P.S. Thanks for the solution.
--
Mitchell Morris
Is this really the future? Sort of. It would be the future if it did all of
these things without depending on any Microsoft software.
-- Philip Greenspun
···@unpkhswm04.bscc.bls.com (Mitchell Morris) writes:
> In article <···············@lostwithiel.tfeb.org>, Tim Bradshaw wrote:
> >* Mitchell Morris wrote:
> >
> >> There is also a "hint" that suggests that the that most concise solution
> >> involves #'apply of a mapping function. I can't for the life of me figure out
> >> a solution that includes #'apply at all.
> >
> >(defun awful-transpose (matrix)
> > (apply #'mapcar #'list matrix))
>
> I now officially despair of ever learning to think in Lisp. I see that this
> works, and I even can see how it works, but I don't know that I would ever
> have figured it out otherwise.
>
> >You should now go and read Gabriel's `worse is better' paper to see
> >why this kind of thing is bad.
> >
> >--tim
>
> Actually, I've read this paper several times. I'm not sure what lesson I
> should be drawing in this particular context.
The lesson is that it's a terrible idea to use lists to represent
matrices. Things like awful-transpose look pretty, but they run
slowly. Such examples mislead people into thinking that the Lisp
language is slow, when in fact the programmer has selected an
inappropriate representation. This is not an example of thinking
in Lisp.
At the risk of over-generalization, no competent CL programmer would
write matrix code in this fashion; he'd use arrays instead of lists.
-matt
Mitchell Morris wrote:
>
> In article <···············@lostwithiel.tfeb.org>, Tim Bradshaw wrote:
> >* Mitchell Morris wrote:
> >
> >> There is also a "hint" that suggests that the that most concise solution
> >> involves #'apply of a mapping function. I can't for the life of me figure out
> >> a solution that includes #'apply at all.
> >
> >(defun awful-transpose (matrix)
> > (apply #'mapcar #'list matrix))
>
> I now officially despair of ever learning to think in Lisp. I see that this
> works, and I even can see how it works, but I don't know that I would ever
> have figured it out otherwise.
Don't despair. It's important to be able to understand this code once written,
but you don't have to think in this manner and write code this way (IMHO of
course).
>
> >You should now go and read Gabriel's `worse is better' paper to see
> >why this kind of thing is bad.
> >
> >--tim
>
> Actually, I've read this paper several times. I'm not sure what lesson I
> should be drawing in this particular context.
At the risk of putting words in Tim's mouth, I think the reason this is bad is
that you are using the wrong data structure. I'm not sure why one would ever
want to implement a matrix as a list rather than as an array.
From: Christopher R. Barry
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <87ln9jyrfa.fsf@2xtreme.net>
···@unpkhswm04.bscc.bls.com (Mitchell Morris) writes:
> >You should now go and read Gabriel's `worse is better' paper to see
> >why this kind of thing is bad.
> >
> >--tim
>
> Actually, I've read this paper several times. I'm not sure what lesson I
> should be drawing in this particular context.
Reread the part about the matrix multiplication and how "you can't
write code this bad in C". Also, your original version used the
classic "recursively walk down a list, consing the result of applying
one function to the head and one function to the tail", which
unfortunately is often the only way students taking classes at schools
are tought to write Lisp. Production code would probably use LOOP.
Christopher
In article <··················@unpkhswm04.bscc.bls.com>,
Mitchell Morris <········@morrisland.com> wrote:
>In article <···············@lostwithiel.tfeb.org>, Tim Bradshaw wrote:
>>* Mitchell Morris wrote:
>>
>>> There is also a "hint" that suggests that the that most concise solution
>>> involves #'apply of a mapping function. I can't for the life of me figure out
>>> a solution that includes #'apply at all.
>>
>>(defun awful-transpose (matrix)
>> (apply #'mapcar #'list matrix))
>
>I now officially despair of ever learning to think in Lisp. I see that this
>works, and I even can see how it works, but I don't know that I would ever
>have figured it out otherwise.
Don't worry about it. This was essentially a puzzle, not a realistic
problem. Lots of excellent Lisp programmers might not have figured it out.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
* Mitchell Morris wrote:
>> (defun awful-transpose (matrix)
>> (apply #'mapcar #'list matrix))
> I now officially despair of ever learning to think in Lisp. I see that this
> works, and I even can see how it works, but I don't know that I would ever
> have figured it out otherwise.
I don't think this is really to do with `thinking in lisp' -- tricks
like this are the kind of thing that lisp people might delight in, but
that doesn't make them good style. It's like the way C people delight
in the duality between arrays and pointers, and the deeply obscure but
terribly neat code that lets you right.
I also must confess to a terrible delight when I actually got to write
something that needed to do:
(funcall #'funcall ...)
at some point.
> Actually, I've read this paper several times. I'm not sure what lesson I
> should be drawing in this particular context.
I think that, if you want arrays, you should use arrays rather than
punning on lists. This code also puns, in an inexact sort of way, on
the fact that Lisp source code is lists, so you can use APPLY to do
things that you really ought not to (because they blow up the moment
the list you pass in gets too long). And in general there is the
point that it would be hard to write something this awful if you
weren't using Lisp, which is a problem for Lisp, because truly awful
code can survive to give the language a bad reputation.
--tim
From: William Deakin
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37FA0C02.9CFC613E@pindar.com>
Tim Bradshaw wrote:
> ...tricks like this are the kind of thing that lisp people might delight in,
> but that doesn't make them good style. It's like the way C people delight in
> the duality between arrays and pointers, and the deeply obscure but terribly
> neat code that lets you right.
I'm sure I've said it before, and that I will say it again: eschew obsfucation.
:) will
> transpose matrices given a representation like:
> ((e00 e01 e02) (e10 e11 e12) (e20 e21 e22))
> [...]
> There is also a "hint" that suggests that the that most concise solution
> involves #'apply of a mapping function. I can't for the life of me figure out
> a solution that includes #'apply at all.
It's basically a shortcut using the match between the data structure
and the multiple-argument behaviour of the mapping function (take one
arg from each list):
(defun transpose (matrix)
(apply #'mapcar #'list matrix))
This kind of APL thinking is actually not very useful in CL, because
it won't work when the dimensions are larger than
CALL-ARGUMENTS-LIMIT. You can sometimes express such ideas using
REDUCE, but it usually ends up being considerably more involved.
--
Pekka P. Pirinen
Adaptive Memory Management Group, Harlequin Limited
Mail should be private, whether on paper or on disk. Public gatherings
should be a right, whether virtual or in person.
In article <··············@gaspode.cam.harlequin.co.uk>,
·····@harlequin.co.uk (Pekka P. Pirinen) wrote:
> (defun transpose (matrix)
> (apply #'mapcar #'list matrix))
>
> This kind of APL thinking is actually not very useful in CL
Not for industrial-strength implementation pehaps, but I think it's a
useful excercise for beginners to gain an understanding of the the
difference between apply and funcall. IMO.
Erann Gat
···@jpl.nasa.gov
In article <··················@unpkhswm04.bscc.bls.com>,
········@morrisland.com wrote:
> In my self-study program, I'm currently working through "Common Lispcraft" by
> J.Wilensky. One of the end-of-chapter exercises asks for code to transpose
> matrices given a representation like:
> ((e00 e01 e02) (e10 e11 e12) (e20 e21 e22))
>
> My solution was:
> (defun transpose (matrix)
> (cond ((null matrix) nil)
> ((null (car matrix)) nil)
> (t (cons (mapcar 'car matrix)
> (transpose (mapcar 'cdr matrix))))))
>
> There is also a "hint" that suggests that the that most concise solution
> involves #'apply of a mapping function. I can't for the life of me figure out
> a solution that includes #'apply at all.
>
> Obviously it's my inexperience that's holding me back, so I'm asking for some
> on-the-spot mentoring. Anyone? Please?
Think about what APPLY does. It takes a function and a list and
calls the function on the ELEMENTS of that list as arguments. In
other words:
(apply function '(a b c ...)) == (function 'a 'b 'c ...)
Actually, apply can take extra argument, so the whole truth is more like:
(apply function 'a 'b 'c ... '(d e f ...))
==
(function 'a 'b 'c ... 'd 'e 'f ...)
Consider your matrix representation. It's a list. If you applied something
to that list you'd be calling that something on the elements of the list, i.e.:
(apply 'mystery-function '((e00 e01 e02) (e10 e11 e12) (e20 e21 e22)))
==
(mystery-function '(e00 e01 e02) '(e10 e11 e12) '(e20 e21 e22))
Now think about what you'd want MYSTERY-FUNCTION to do in order to
transpose the matrix. First, you'd want it to pull off all the first
elements of the lists and assemble those into a list. Then you'd want
it to pull off all the second elements of the lists and assemble those
into a list, etc. Then you'd want it to take all those lists and
assemble them into one final list. That sounds like a mapping operation.
So MYSTERY-FUNCTION is something like:
(mapcar 'mystery-function2 '(e00 e01 e02) '(e10 e11 e12) '(e20 e21 e22))
==
(apply 'mapcar 'mystery-function2 '((e00 e01 e02) (e10 e11 e12) (e20 e21 e22)))
What is MYSTERY-FUNCTION2? Well, it's a function that takes a bunch
of arguments and assembles them into a list. You can probably figure it
out from here.
Erann Gat
···@jpl.nasa.gov
From: Donald Fisk
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37F8E951.F63A2162@inthan.be>
Mitchell Morris wrote:
>
> In my self-study program, I'm currently working through "Common Lispcraft" by
> J.Wilensky. One of the end-of-chapter exercises asks for code to transpose
> matrices given a representation like:
> ((e00 e01 e02) (e10 e11 e12) (e20 e21 e22))
>
> My solution was:
> (defun transpose (matrix)
> (cond ((null matrix) nil)
> ((null (car matrix)) nil)
> (t (cons (mapcar 'car matrix)
> (transpose (mapcar 'cdr matrix))))))
>
> There is also a "hint" that suggests that the that most concise solution
> involves #'apply of a mapping function. I can't for the life of me figure out
> a solution that includes #'apply at all.
>
> Obviously it's my inexperience that's holding me back, so I'm asking for some
> on-the-spot mentoring. Anyone? Please?
It's a well known parlour trick, like swapping the value of two
variables
without using a third, or a non-trivial Lisp expression which evaluates
to itself. What you're looking for is
: (defun transpose (x) (apply #'mapcar #'list x))
TRANSPOSE
: (transpose '((e00 e01 e02) (e10 e11 e12) (e20 e21 e22)))
((E00 E10 E20) (E01 E11 E21) (E02 E12 E22))
> +Mitchell
Le Hibou (ma propre opinion)
--
"People help themselves to things if they think they will get
away with it, even things they are unlikely to have much use
for and cannot resell, such as traffic cones. In the UK we
call these people 'students'." -- Joe Boswell
From: Christopher R. Barry
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <87btaez4ne.fsf@2xtreme.net>
Donald Fisk <···········@inthan.be> writes:
> It's a well known parlour trick, like swapping the value of two
> variables without using a third,
How is this a parlor trick?
(multiple-value-setq (x y)
(values y x))
If you know an actual parlor trick way to accomplish this feat, do
share it with us.
Christopher
Christopher R. Barry <······@2xtreme.net> wrote in message
···················@2xtreme.net...
> Donald Fisk <···········@inthan.be> writes:
>
> > It's a well known parlour trick, like swapping the value of two
> > variables without using a third,
>
> How is this a parlor trick?
>
> (multiple-value-setq (x y)
> (values y x))
>
> If you know an actual parlor trick way to accomplish this feat, do
> share it with us.
It could be done this way:
(setq x (prog1 y (setq y x)))
I believe this trick comes from MIT's HAKMEM.
--
Eugene.
On Tue, 5 Oct 1999 12:29:15 +0200, "Eugene Zaikonnikov"
<······@removeme.cit.org.by> wrote:
>
> Christopher R. Barry <······@2xtreme.net> wrote in message
> ···················@2xtreme.net...
> > Donald Fisk <···········@inthan.be> writes:
> >
> > > It's a well known parlour trick, like swapping the value of two
> > > variables without using a third,
> >
> > How is this a parlor trick?
> >
> > (multiple-value-setq (x y)
> > (values y x))
> >
> > If you know an actual parlor trick way to accomplish this feat, do
> > share it with us.
>
> It could be done this way:
> (setq x (prog1 y (setq y x)))
>
> I believe this trick comes from MIT's HAKMEM.
Or there's
(psetq x y y x)
or
(rotatef x y)
__Jason
In article <····························@4ax.com>,
Jason Trenouth <·····@harlequin.com> wrote:
>On Tue, 5 Oct 1999 12:29:15 +0200, "Eugene Zaikonnikov"
><······@removeme.cit.org.by> wrote:
>
>>
>> Christopher R. Barry <······@2xtreme.net> wrote in message
>> ···················@2xtreme.net...
>> > Donald Fisk <···········@inthan.be> writes:
>> >
>> > > It's a well known parlour trick, like swapping the value of two
>> > > variables without using a third,
>> >
>> > How is this a parlor trick?
>> >
>> > (multiple-value-setq (x y)
>> > (values y x))
>> >
>> > If you know an actual parlor trick way to accomplish this feat, do
>> > share it with us.
>>
>> It could be done this way:
>> (setq x (prog1 y (setq y x)))
>>
>> I believe this trick comes from MIT's HAKMEM.
>
>Or there's
>
> (psetq x y y x)
>
>or
> (rotatef x y)
It should be notes that all these solutions actually use additional
variables, they're just not explicitly named in the program. They're
temporaries that the compiler must necessarily generate.
The trick that works for integers using XOR really requires no additional
memory at all.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Eugene Zaikonnikov
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37FB65C0.938E596F@cit.org.by>
Barry Margolin wrote:
[snip]
> >> (setq x (prog1 y (setq y x)))
> >>
> >> I believe this trick comes from MIT's HAKMEM.
> >
> >Or there's
> >
> > (psetq x y y x)
> >
> >or
> > (rotatef x y)
>
> It should be notes that all these solutions actually use additional
> variables, they're just not explicitly named in the program. They're
> temporaries that the compiler must necessarily generate.
>
> The trick that works for integers using XOR really requires no additional
> memory at all.
I suppose Jason and I were mislead by the original problem about
transposing a matrix in Lisp. On the Lisp abstraction level none of the
solutions above uses additional variables.
OTOH, how can one swap two non-numeric values in Lisp using xor/addition
trick?
--
Eugene.
In article <·················@cit.org.by>,
Eugene Zaikonnikov <······@cit.org.by> wrote:
>OTOH, how can one swap two non-numeric values in Lisp using xor/addition
>trick?
You can't. It's a trick that takes advantage of integers properties.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Eugene Zaikonnikov
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37FCE45D.EA7FAA72@cit.org.by>
Barry Margolin wrote:
>
> Eugene Zaikonnikov <······@cit.org.by> wrote:
> >OTOH, how can one swap two non-numeric values in Lisp using xor/addition
> >trick?
>
> You can't. It's a trick that takes advantage of integers properties.
Certainly. Perhaps it's my problem in formulating asserting questions in
English. I tried to point out that the XOR trick is not the case for
Lisp.
--
Eugene.
In article <·················@cit.org.by>, Eugene Zaikonnikov
<······@cit.org.by> wrote:
> OTOH, how can one swap two non-numeric values in Lisp using xor/addition
> trick?
The same way you'd do it in any other language:
(setf x (logxor x y))
(setf y (logxor x y))
(setf x (logxor x y))
or
(setf x (+ x y))
(setf y (- x y))
(setf x (- x y))
Personally, I'd put this in the "parlor trick" category. Obfuscation
like this has no place in real code IMO.
Erann Gat
···@jpl.nasa.gov
···@jpl.nasa.gov (Erann Gat) writes:
> In article <·················@cit.org.by>, Eugene Zaikonnikov
> <······@cit.org.by> wrote:
>
> > OTOH, how can one swap two non-numeric values in Lisp using xor/addition
> > trick?
>
> The same way you'd do it in any other language:
>
> (setf x (logxor x y))
> (setf y (logxor x y))
> (setf x (logxor x y))
>
> or
>
> (setf x (+ x y))
> (setf y (- x y))
> (setf x (- x y))
>
> Personally, I'd put this in the "parlor trick" category. Obfuscation
> like this has no place in real code IMO.
In an undergraduate computer architecture/digital logic class I once
took, there was a question on the final exam:
How can you swap the contents of two registers by using basic ALU
operations without using any temporary storage?
Needless to say, the right answer was the xor trick. I didn't
know the trick at the time, so I missed that question.
The presence of that question on the exam (and my inability to figure
out the trick), still bugs me even years later.
--
R. Matthew Emerson
http://www.thoughtstuff.com/rme/
On Thu, 07 Oct 1999 20:42:55 GMT,
R. Matthew Emerson <···@nightfly.apk.net> wrote:
>
>In an undergraduate computer architecture/digital logic class I once
>took, there was a question on the final exam:
>
> How can you swap the contents of two registers by using basic ALU
> operations without using any temporary storage?
>
>Needless to say, the right answer was the xor trick. I didn't
>know the trick at the time, so I missed that question.
>
>The presence of that question on the exam (and my inability to figure
>out the trick), still bugs me even years later.
This is really an awful test question. It doesn't demonstrate anything
useful. Does this indicate the value of the rest of the course?
--
Kenneth P. Turvey <·······@SprocketShop.com>
--------------------------------------------
It would be an absurdity for jurors to be required to accept the judge's
view of the law, against their own opinion, judgment, and conscience.
-- John Adams
In article <······················@pug1.sprocketshop.com>,
Kenneth P. Turvey <·······@pug1.sprocketshop.com> wrote:
>On Thu, 07 Oct 1999 20:42:55 GMT,
>R. Matthew Emerson <···@nightfly.apk.net> wrote:
>>
>>In an undergraduate computer architecture/digital logic class I once
>>took, there was a question on the final exam:
>>
>> How can you swap the contents of two registers by using basic ALU
>> operations without using any temporary storage?
>>
>>Needless to say, the right answer was the xor trick. I didn't
>>know the trick at the time, so I missed that question.
>>
>>The presence of that question on the exam (and my inability to figure
>>out the trick), still bugs me even years later.
>
>This is really an awful test question. It doesn't demonstrate anything
>useful. Does this indicate the value of the rest of the course?
Notice that it was in a digital logic class, not a programming class. I've
never done much hardware design, but I imagine in designing complex digital
circuits it's useful to know how to optimize gates like this.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
In article <···················@burlma1-snr2>, Barry Margolin
<······@bbnplanet.com> wrote:
> In article <······················@pug1.sprocketshop.com>,
> Kenneth P. Turvey <·······@pug1.sprocketshop.com> wrote:
> >On Thu, 07 Oct 1999 20:42:55 GMT,
> >R. Matthew Emerson <···@nightfly.apk.net> wrote:
> >>
> >>In an undergraduate computer architecture/digital logic class I once
> >>took, there was a question on the final exam:
> >>
> >> How can you swap the contents of two registers by using basic ALU
> >> operations without using any temporary storage?
> >>
> >>Needless to say, the right answer was the xor trick. I didn't
> >>know the trick at the time, so I missed that question.
> >>
> >>The presence of that question on the exam (and my inability to figure
> >>out the trick), still bugs me even years later.
> >
> >This is really an awful test question. It doesn't demonstrate anything
> >useful. Does this indicate the value of the rest of the course?
>
> Notice that it was in a digital logic class, not a programming class. I've
> never done much hardware design, but I imagine in designing complex digital
> circuits it's useful to know how to optimize gates like this.
FWIW,
I learned of the XOR trick for linked lists in 1976 from a non-programmer!
Later, a friend showed me the short form in "C" for swapping two integers
without a temporary...
a^=b^=a^=b
Here is the form of a doubly linked list with one pointer...
Start->
A-link: ( &A xor &B )
B-link: ( &A xor &C )
C-link: ( &B xor &D )
D-link: ( &C xor &E )
E-link: ( &D xor &E )
Two pointers are used to traverse the list: Previous and Current.
Previous xor link(Current) => Next
If Previous xor link(Current) == Current then you are at the end.
Repeated iteration of
Previous xor link(Current) => Next, Previous = Current, Current = Next
will traverse the list repeatedly with 3 consecutive visits at each endpoint.
This form (with endpoints using XOR self) allows very simple
initialization of the list, simple add to head, add to tail. A list of
one element, A, has a link of (A xor A) or 0.
------
Siklossy (1972) showed a method for traversal of binary trees in Read ONLY
Memory, using constant space (In contrast to Schorr-Waite-Deutsch,
et.al.). It looks just like the example above except each element has two
link fields.
d
In article <····················@milo.jpl.nasa.gov>,
Erann Gat <···@jpl.nasa.gov> wrote:
>In article <·················@cit.org.by>, Eugene Zaikonnikov
><······@cit.org.by> wrote:
>
>> OTOH, how can one swap two non-numeric values in Lisp using xor/addition
>> trick?
>
>The same way you'd do it in any other language:
He said *non*-numeric. As he told me in private email, he was trying to
make the point that in Lisp we don't generally assume most variables are
numeric, and we go for general-purpose solutions.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
>>>>> "Barry" == Barry Margolin <······@bbnplanet.com> writes:
Barry> In article <····························@4ax.com>, Jason
Barry> Trenouth <·····@harlequin.com> wrote:
>>
>> (psetq x y y x)
>>
>> or (rotatef x y)
Barry> It should be notes that all these solutions actually use
Barry> additional variables, they're just not explicitly named in the
Barry> program. They're temporaries that the compiler must
Barry> necessarily generate.
Barry> The trick that works for integers using XOR really requires no
Barry> additional memory at all.
Presumably a compiler *could* perform this optimisation on the above
forms when it can deduce that the types of x and y are appropriate...
Sent via Deja.com http://www.deja.com/
Before you buy.
From: Christopher R. Barry
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <87905hzrfb.fsf@2xtreme.net>
"Eugene Zaikonnikov" <······@removeme.cit.org.by> writes:
> Christopher R. Barry <······@2xtreme.net> wrote in message
> ···················@2xtreme.net...
> > Donald Fisk <···········@inthan.be> writes:
> >
> > > It's a well known parlour trick, like swapping the value of two
> > > variables without using a third,
> >
> > How is this a parlor trick?
> >
> > (multiple-value-setq (x y)
> > (values y x))
> >
> > If you know an actual parlor trick way to accomplish this feat, do
> > share it with us.
>
> It could be done this way:
> (setq x (prog1 y (setq y x)))
>
> I believe this trick comes from MIT's HAKMEM.
Thanks for the reference. I did an Altavista search for that document
and found http://www.starfall.com/~andy/hakmem/programming-hacks.html.
It's item 163 (Sussman):
(SETQ X (PROG2 0 Y (SETQ Y X)))
[I wonder if this means PROG2 predates PROG1....]
Christopher
In article <··············@2xtreme.net>,
Christopher R. Barry <······@2xtreme.net> wrote:
>Thanks for the reference. I did an Altavista search for that document
>and found http://www.starfall.com/~andy/hakmem/programming-hacks.html.
>It's item 163 (Sussman):
>
> (SETQ X (PROG2 0 Y (SETQ Y X)))
>
>[I wonder if this means PROG2 predates PROG1....]
Yes. Maclisp only had PROG2, PROG1 was introduced in Zetalisp and
inherited by Common Lisp.
If you're wondering why it had PROG2 rather than PROG1, I think it may also
have predated PROGN, so it was the primitive sequence+return operator.
PROGN could be derived from it with:
(defmacro progn (&rest forms)
(if (null (cdr forms))
forms
`(prog2 (car forms)
(progn ,@(cdr forms)))))
(However, there was no DEFMACRO or BACKQUOTE at that time, either, so the
code would have looked much worse.)
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Eugene Zaikonnikov
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37FA3DFF.7B156496@cit.org.by>
"Christopher R. Barry" wrote:
>
> It's item 163 (Sussman):
>
> (SETQ X (PROG2 0 Y (SETQ Y X)))
>
> [I wonder if this means PROG2 predates PROG1....]
Hmm... really strange. I din't noticed that. Perhaps we should ask the
elders.
My first guess is that PROG2 was introduced for some specific purpose
(e.g. some hacker was too lazy to rearrange statments in his code,
adding new special form instead), and PROG1 was added later for
consistency.
Or Maclisp's PROG1 was buggy at the moment when Sussman wrote that item
:)
--
Eugene.
In article <·················@cit.org.by>,
Eugene Zaikonnikov <······@cit.org.by> wrote:
>"Christopher R. Barry" wrote:
>>
>> It's item 163 (Sussman):
>>
>> (SETQ X (PROG2 0 Y (SETQ Y X)))
>>
>> [I wonder if this means PROG2 predates PROG1....]
>
>Hmm... really strange. I din't noticed that. Perhaps we should ask the
>elders.
This crotchety old fart already answered.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
>>>>> "Eugene" == Eugene Zaikonnikov <······@removeme.cit.org.by> writes:
Eugene> Christopher R. Barry <······@2xtreme.net> wrote in message
Eugene> ···················@2xtreme.net...
>> Donald Fisk <···········@inthan.be> writes:
>>
>> > It's a well known parlour trick, like swapping the value of two
>> > variables without using a third,
>>
>> How is this a parlor trick?
>>
>> (multiple-value-setq (x y) (values y x))
>>
>> If you know an actual parlor trick way to accomplish this feat, do
>> share it with us.
Eugene> It could be done this way: (setq x (prog1 y (setq y x)))
(rotatef x y)
Sent via Deja.com http://www.deja.com/
Before you buy.
From: Donald Fisk
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <37F9CF31.CDE5002D@inthan.be>
"Christopher R. Barry" wrote:
> How is this a parlor trick?
>
> (multiple-value-setq (x y)
> (values y x))
>
> If you know an actual parlor trick way to accomplish this feat, do
> share it with us.
I assumed people were aware of it, so I didn't describe it. You
use exclusive or (or addition and subtraction). And you don't
use Lisp.
A := A # B;
B := A # B;
A := A # B;
Like the matrix transpose problem, cute but almost useless.
Now, if someone can put me out of my misery: what is the
non-atomic Lisp expression which evaluates to itself?
> Christopher
Le Hibou (ma propre opinion)
--
"People help themselves to things if they think they will get
away with it, even things they are unlikely to have much use
for and cannot resell, such as traffic cones. In the UK we
call these people 'students'." -- Joe Boswell
Donald Fisk <···········@inthan.be> wrote:
>...
>Now, if someone can put me out of my misery: what is the
>non-atomic Lisp expression which evaluates to itself?
Salut Donald ;-)
2 lignes seulement en Lisp:
((lambda (x) (list x (list 'quote x)))
'(lambda (x) (list x (list 'quote x))))
BTW I think Ken Thomson has written a C equivalent in 233 lines.
Francis
--
Francis Leboutte
··········@skynet.be http://users.skynet.be/algo
Francis Leboutte <··········@skynet.be> writes:
> Donald Fisk <···········@inthan.be> wrote:
> >Now, if someone can put me out of my misery: what is the
> >non-atomic Lisp expression which evaluates to itself?
> 2 lignes seulement en Lisp:
>
> ((lambda (x) (list x (list 'quote x)))
> '(lambda (x) (list x (list 'quote x))))
quine /kwi:n/ n.
[from the name of the logician Willard van Orman Quine, via Douglas
Hofstadter] A program that generates a copy of its own source text
as its complete output. Devising the shortest possible quine in
some given programming language is a common hackish amusement.
(The Jargon File: http://www.tuxedo.org/~esr/jargon/html/entry/quine.html)
There's an awfully large number of thse collected by Gary P. Thompson II
at http://www.nyx.net/~gthompso/quine.htm
-dan
Daniel Barlow <···@tninkpad.telent.net> wrote:
>
> quine /kwi:n/ n.
>
> [from the name of the logician Willard van Orman Quine, via Douglas
> Hofstadter] A program that generates a copy of its own source text
> as its complete output. Devising the shortest possible quine in
> some given programming language is a common hackish amusement.
>
>(The Jargon File: http://www.tuxedo.org/~esr/jargon/html/entry/quine.html)
>
>There's an awfully large number of thse collected by Gary P. Thompson II
>at http://www.nyx.net/~gthompso/quine.htm
fascinating!
--
Francis Leboutte
··········@skynet.be http://users.skynet.be/algo
From: Christopher R. Barry
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <87670lzr2r.fsf@2xtreme.net>
Donald Fisk <···········@inthan.be> writes:
> Now, if someone can put me out of my misery: what is the
> non-atomic Lisp expression which evaluates to itself?
I'm not sure I understand the question. If you are talking about a
quine, well there are infinitely many of them you can do with Lisp[1].
But you imply that there is only one "non-atomic Lisp expression which
evaluates to itself".
Christopher
1. The most balanced and beautiful one is (IMO)
((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))
From: Sam Steingold
Subject: Re: Please get me past this mental block!
Date:
Message-ID: <uso3oimxu.fsf@ksp.com>
>>>> In message <·················@inthan.be>
>>>> On the subject of "Re: Please get me past this mental block!"
>>>> Sent on Tue, 05 Oct 1999 12:13:05 +0200
>>>> Honorable Donald Fisk <···········@inthan.be> writes:
>>
>> Now, if someone can put me out of my misery: what is the
>> non-atomic Lisp expression which evaluates to itself?
(let((a'(list'let(list(list'a(list'quote a)))a)))`(let((a(quote ,a))),a))
((lambda (x) (list x (list 'quote x))) '(lambda (x) (list x (list 'quote x))))
((lambda (x) `(,x ',x)) '(lambda (x) `(,x ',x)))
(see http://www.podval.org/~sds/self-ref.html)
--
Sam Steingold (http://www.podval.org/~sds/)
Micros**t is not the answer. Micros**t is a question, and the answer is Linux,
(http://www.linux.org) the choice of the GNU (http://www.gnu.org) generation.
Profanity is the one language all programmers know best.
* Christopher R Barry wrote:
> How is this a parlor trick?
> (multiple-value-setq (x y)
> (values y x))
The standard C trick is to use xor isn't it? It's kind of interesting
I think because it's one of the things that can completely foul up any
conservative GC if the variables are pointers.
--tim
······@2xtreme.net (Christopher R. Barry) writes:
> Donald Fisk <···········@inthan.be> writes:
>
> > It's a well known parlour trick, like swapping the value of two
> > variables without using a third,
>
> How is this a parlor trick?
>
> (multiple-value-setq (x y)
> (values y x))
I like this:
(psetq x y
y x)
In article <··············@2xtreme.net>, ······@2xtreme.net (Christopher
R. Barry) wrote:
>How is this a parlor trick?
>
> (multiple-value-setq (x y)
> (values y x))
also,
(psetq x y
y x)
as in:
===
? (let ((x 1)
(y 2))
(format t "~%Before, X=~A and Y=~A." x y)
(psetq x y
y x)
(format t "~%After, X=~A and Y=~A." x y)
nil)
Before, X=1 and Y=2.
After, X=2 and Y=1.
NIL
?
===
sashank
In article <··············@2xtreme.net>,
Christopher R. Barry <······@2xtreme.net> wrote:
>Donald Fisk <···········@inthan.be> writes:
>
>> It's a well known parlour trick, like swapping the value of two
>> variables without using a third,
>
>How is this a parlor trick?
>
> (multiple-value-setq (x y)
> (values y x))
>
>If you know an actual parlor trick way to accomplish this feat, do
>share it with us.
>
Not exactly a trick, but more concise: (rotatef x y)
Bernhard
--
--------------------------------------------------------------------------
Bernhard Pfahringer
Austrian Research Institute for http://www.ai.univie.ac.at/~bernhard/
Artificial Intelligence ········@ai.univie.ac.at