On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
"Use complex numbers to represent points in a plane."
This sounds like something Dijkstra would not approve :) Any explanation why
this is prefered?
Paul Griffioen
Paul Griffioen wrote:
> On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
>
> "Use complex numbers to represent points in a plane."
>
> This sounds like something Dijkstra would not approve :) Any explanation why
> this is prefered?
I can only speculate. The complex numbers are isomorphic
the the points in a plane, so they are entirely adequate to the
task. Since complex numbers are built in to Common Lisp,
all implementations have an incentive to implement them
efficiently. Since points are not built in, but are often needed
in programs, representing them as anything other than complex
numbers would in time lead to a proliferation of representations
for points, and I suppose it is conceivable that, in some
implementations, programmer-defined data types might not
be as efficient as the built-in complex numbers.
As I said, the above paragraph is sheer speculation. It
has no real technical content. In particular, generalizing
this discussion to include points in 3-space is left as an
exercise for the reader.
Will
Paul Griffioen wrote:
> On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
>
> "Use complex numbers to represent points in a plane."
>
> This sounds like something Dijkstra would not approve :) Any explanation why
> this is prefered?
Well, for the underlying representation, anyway, it sounds like a good
idea. If you don't, you'll just end up replicating all the work for
addition, multiplication by a real and rotation. You might want to
create your own type and even a couple wrappers to hide this
implementation detail, but when you're prototyping, it pays to be lazy.
Paul Khuong
Paul Griffioen wrote:
> On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
>
> "Use complex numbers to represent points in a plane."
>
> This sounds like something Dijkstra would not approve :) Any explanation why
> this is prefered?
>
> Paul Griffioen
Historically, many tried to use imaginary numbers for many different
things. Some places do need imaginary numbers. Others have switched to
something else (like relativity). Well, some people like fancy stuff,
even when it is not exactly suitable.
Speaking of mathematics:
1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
will be a1*b1-a2*b2. Laurentz signature of the space instead of
Eucledian.
2) If your problem domain is purely real, you have to be careful with
getting answers right (read, real answers).
3) My personal opinion is to use complex numbers were they are
*really* needed. Else you get addition problems for no reason in terms
of math. If you do mistake in math, "style"-thing in programing will
not help you.
Speaking of programming:
1) If you screw the math with imaginary thingy, no programming style
will help.
2) Someone said not to waste effort of implementing things twice. I am
sure there should be an already existing package for eucledian vectors
that will do proper math and be a "nice style".
Mikalai wrote:
> Speaking of mathematics:
> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
> will be a1*b1-a2*b2. Laurentz signature of the space instead of
> Eucledian.
Maybe I'd better stick with Scheme.
Will
William D Clinger wrote:
> Mikalai wrote:
>
>> Speaking of mathematics:
>> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
>>will be a1*b1-a2*b2. Laurentz signature of the space instead of
>>Eucledian.
>
> Maybe I'd better stick with Scheme.
Damn - just when we thought we had another convert... ;)
Pascal
--
My website: http://p-cos.net
Closer to MOP & ContextL:
http://common-lisp.net/project/closer/
> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
> will be a1*b1-a2*b2. Laurentz signature of the space instead of
> Eucledian.
This may confuse people into thinking there is a mistake in CL, but
there isn't. The product of a and b is supposed to have the real part
you give, and imaginary part a1*b2+a2*b1.
To paraphrase what I think this quote is saying: if you want to
multiply a point times a scalar, don't accidentally multiply two points
instead.
CL-USER(3): (defvar a (complex 2 3))
CL-USER(5): (defvar b (complex 2 5))
CL-USER(7): (* a b)
#C(-11 16)
···············@yahoo.com writes:
>> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
>> will be a1*b1-a2*b2. Laurentz signature of the space instead of
>> Eucledian.
>
> This may confuse people into thinking there is a mistake in CL, but
> there isn't. The product of a and b is supposed to have the real part
> you give, and imaginary part a1*b2+a2*b1.
>
> To paraphrase what I think this quote is saying: if you want to
> multiply a point times a scalar, don't accidentally multiply two points
> instead.
No, I think he's saying: if you want the scalar (dot)
product of two 2-vectors, don't think you'll get it
as the real part of the product of the complex numbers.
I'm having difficulty imagining why anyone would think
you *would* get it that way, though.
--
Gareth McCaughan
.sig under construc
Mikalai wrote:
> Paul Griffioen wrote:
> > On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
> >
> > "Use complex numbers to represent points in a plane."
> >
> > This sounds like something Dijkstra would not approve :) Any explanation why
> > this is prefered?
> >
> > Paul Griffioen
>
> Historically, many tried to use imaginary numbers for many different
> things. Some places do need imaginary numbers. Others have switched to
> something else (like relativity). Well, some people like fancy stuff,
> even when it is not exactly suitable.
>
> Speaking of mathematics:
> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
> will be a1*b1-a2*b2. Laurentz signature of the space instead of
> Eucledian.
> 2) If your problem domain is purely real, you have to be careful with
> getting answers right (read, real answers).
> 3) My personal opinion is to use complex numbers were they are
> *really* needed. Else you get addition problems for no reason in terms
> of math. If you do mistake in math, "style"-thing in programing will
> not help you.
A lot of people mistrust complex numbers, or perhaps they mistrust
themselves when using complex numbers. I think that is too bad because
there is a lot of cool math that becomes really easy in the space of
complex numbers. It is non-mainstream, but I doubt that will deter
Lisp hackers. In fact, Henry Baker suggests using complex Gaussian
integers for graphics:
http://home.pipeline.com/~hbaker1/Gaussian.html
I was once working on an interesting problem of attempting to compute a
path for an `underactuated vehicle'. For instance, an automobile
cannot spin in place --- it has a minimum turning radius. It can be
hard to compute a path for such a vehicle when you have constraints of
position and orientation (if you want to park the car in a tight lot
and you are really close to the parking space, you may need a
self-intersecting curve). It turns out that a quintic (5th-order)
spline called a `Rational Pythagorean Hodograph Curve' has some handy
properties. It has enough degrees of freedom to get the car into the
parking spot in the right orientation, but not so many degrees of
freedom that it is a nightmare to solve.
The trick to solving the equation is pretty slick: you combine two
pairs of coefficients into a complex number and set the final
coefficient to a constant. Now, instead of a 5th-order equation, you
have a quadratic equation with a twist: the quadratic coefficients are
complex. But the standard quadratic formula still applies --- you
simply use complex numbers for `a, b, and c'. This is dead simple in a
language like Lisp where complex numbers are built in to the numeric
tower.
Here's another thing that should appeal to Lisp hackers: you can
construct higher-order complex numbers recursively (Cayley - Dickson
construction). If you allow the coefficients of your complex numbers
themselves to be complex, you'll have quaternions. This generalizes to
octonions and `sedenions' (but each step loses something: complex
numbers aren't real, quaternions aren't commutative, octonions aren't
associative (!), sedenions are not a `division algebra' --- a*b=0
doesn't imply that a=0 or b=0)
It seems to me that complex numbers are probably underutilized rather
than overutilized.
Interesting stuff.
My first reaction to the style preference was to dismiss it as a dirty trick
but your reply certainly made me rethink this. Thanks for the link, I'll
have to take a closer look at it but at the momement I guess you can say
that the representation depends on the plane that is represented and that
'points in a plane' is just too general for prefering complex numbers.
Anyway, maybe it's not such a dirty trick after all, just as it not
unreasonable to use negative numbers to represent a bank account.
Paul
"Joe Marshall" <··········@gmail.com> schreef in bericht
····························@g44g2000cwa.googlegroups.com...
>
> Mikalai wrote:
>> Paul Griffioen wrote:
>> > On Lisp Programming Style at http://www.lisp.org/table/style.htm I
>> > read:
>> >
>> > "Use complex numbers to represent points in a plane."
>> >
>> > This sounds like something Dijkstra would not approve :) Any
>> > explanation why
>> > this is prefered?
>> >
>> > Paul Griffioen
>>
>> Historically, many tried to use imaginary numbers for many different
>> things. Some places do need imaginary numbers. Others have switched to
>> something else (like relativity). Well, some people like fancy stuff,
>> even when it is not exactly suitable.
>>
>> Speaking of mathematics:
>> 1) With a=#c(a1,a2), b=#c(b1,b2), do not do by accident a*b, since it
>> will be a1*b1-a2*b2. Laurentz signature of the space instead of
>> Eucledian.
>> 2) If your problem domain is purely real, you have to be careful with
>> getting answers right (read, real answers).
>> 3) My personal opinion is to use complex numbers were they are
>> *really* needed. Else you get addition problems for no reason in terms
>> of math. If you do mistake in math, "style"-thing in programing will
>> not help you.
>
> A lot of people mistrust complex numbers, or perhaps they mistrust
> themselves when using complex numbers. I think that is too bad because
> there is a lot of cool math that becomes really easy in the space of
> complex numbers. It is non-mainstream, but I doubt that will deter
> Lisp hackers. In fact, Henry Baker suggests using complex Gaussian
> integers for graphics:
> http://home.pipeline.com/~hbaker1/Gaussian.html
>
> I was once working on an interesting problem of attempting to compute a
> path for an `underactuated vehicle'. For instance, an automobile
> cannot spin in place --- it has a minimum turning radius. It can be
> hard to compute a path for such a vehicle when you have constraints of
> position and orientation (if you want to park the car in a tight lot
> and you are really close to the parking space, you may need a
> self-intersecting curve). It turns out that a quintic (5th-order)
> spline called a `Rational Pythagorean Hodograph Curve' has some handy
> properties. It has enough degrees of freedom to get the car into the
> parking spot in the right orientation, but not so many degrees of
> freedom that it is a nightmare to solve.
>
> The trick to solving the equation is pretty slick: you combine two
> pairs of coefficients into a complex number and set the final
> coefficient to a constant. Now, instead of a 5th-order equation, you
> have a quadratic equation with a twist: the quadratic coefficients are
> complex. But the standard quadratic formula still applies --- you
> simply use complex numbers for `a, b, and c'. This is dead simple in a
> language like Lisp where complex numbers are built in to the numeric
> tower.
>
> Here's another thing that should appeal to Lisp hackers: you can
> construct higher-order complex numbers recursively (Cayley - Dickson
> construction). If you allow the coefficients of your complex numbers
> themselves to be complex, you'll have quaternions. This generalizes to
> octonions and `sedenions' (but each step loses something: complex
> numbers aren't real, quaternions aren't commutative, octonions aren't
> associative (!), sedenions are not a `division algebra' --- a*b=0
> doesn't imply that a=0 or b=0)
>
> It seems to me that complex numbers are probably underutilized rather
> than overutilized.
>
>
On Fri, 20 Jan 2006 20:01:28 +0100, Joe Marshall <··········@gmail.com>
wrote:
>
> Here's another thing that should appeal to Lisp hackers: you can
> construct higher-order complex numbers recursively (Cayley - Dickson
> construction). If you allow the coefficients of your complex numbers
> themselves to be complex, you'll have quaternions. This generalizes to
> octonions and `sedenions' (but each step loses something: complex
> numbers aren't real, quaternions aren't commutative, octonions aren't
> associative (!), sedenions are not a `division algebra' --- a*b=0
> doesn't imply that a=0 or b=0)
>
> It seems to me that complex numbers are probably underutilized rather
> than overutilized.
>
Quaterions are invaluable in 3D computer graphics.
Rotations have far less roundoff error and are more efficient
that with linear algebra.
http://en.wikipedia.org/wiki/Quaternions
http://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
On Thu, 19 Jan 2006 23:14:02 +0100, Paul Griffioen <·@dont.want.spam>
wrote:
> On Lisp Programming Style at http://www.lisp.org/table/style.htm I read:
>
> "Use complex numbers to represent points in a plane."
>
> This sounds like something Dijkstra would not approve :) Any explanation
> why
> this is prefered?
>
> Paul Griffioen
>
>
>
Good question.
Here's one for screen coordinates:
(don't try this on a 64-bit lisp)
how about:
(deftype scpoint () `(simple-array (unsigned-byte 32) 2))
(defmacro make-scpoint () (make-array 2 :initial-element 0))
(defmacro scref (point ind) `(the (unsigned-byte 32) (svref ,point (the
(integer 0 2) ,ind))))
(defun sc+ (scp1 scp2)
(declare (type scpoint scp1 scp2))
(let ((result (make-point)))
(declare (type scpoint result))
(setf (scref result 0) (+ (scref scp1 0) (scref scp2 0)) (scref
result 1) (+ (scref scp1 1) (scref scp2 1)))
result))
CL-USER 118 > (sc+ #(1 2) #(3 4))
#(4 6)
As you see it takes a bit of effort to make it efficient.
With complex numbers it is done for you and also you can forget
portabillity issues.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> Here's one for screen coordinates:
> (don't try this on a 64-bit lisp)
>
> how about:
> (deftype scpoint () `(simple-array (unsigned-byte 32) 2))
> (defmacro make-scpoint () (make-array 2 :initial-element 0))
Just to clarify, for others, exactly what (I think) Christophe Rhodes
is warning about, this make-scpoint (which has absolutely no need to be
a macro, because it is a simple function call), DOES NOT produce
something that is of type scpoint, because the element-type is not
specified.
> (defmacro scref (point ind) `(the (unsigned-byte 32) (svref ,point (the
> (integer 0 2) ,ind))))
(typep (make-scpoint) 'scpoint) will typically return NIL.
> (defun sc+ (scp1 scp2)
> (declare (type scpoint scp1 scp2))
> (let ((result (make-point)))
> (declare (type scpoint result))
This declaration is therefore a lie to the compiler.
> (setf (scref result 0) (+ (scref scp1 0) (scref scp2 0)) (scref
> result 1) (+ (scref scp1 1) (scref scp2 1)))
> result))
I think also that this setf is risky in the case of integer overflow.
··············@hotmail.com wrote:
> John Thingstad wrote:
>
> > Here's one for screen coordinates:
> > (don't try this on a 64-bit lisp)
> >
> > how about:
> > (deftype scpoint () `(simple-array (unsigned-byte 32) 2))
>
> > (defmacro make-scpoint () (make-array 2 :initial-element 0))
>
> Just to clarify, for others, exactly what (I think) Christophe Rhodes
> is warning about, this make-scpoint (which has absolutely no need to be
> a macro, because it is a simple function call), DOES NOT produce
> something that is of type scpoint, because the element-type is not
> specified.
>
> > (defmacro scref (point ind) `(the (unsigned-byte 32) (svref ,point (the
> > (integer 0 2) ,ind))))
Ah, yes, and one more thing, svref only works with simple-vectors which
can HOLD ANY LISP TYPE. Your type scpoint *cannot* be dereferenced with
svref. simple-vectors are subtypes of simple-arrays, but
one-dimensional simple-arrays with specialized element types are NOT
simple-vectors.
I admit this is confusing: "simple" in the "simple-array" means
something different than "simple" in "simple-vector." There's some
chance that I am also confused, and I would hope to be corrected, but
I've checked this twice in the Hyperspec.
On Fri, 20 Jan 2006 22:48:38 +0100, ··············@hotmail.com
<············@gmail.com> wrote:
>
> I admit this is confusing: "simple" in the "simple-array" means
> something different than "simple" in "simple-vector." There's some
> chance that I am also confused, and I would hope to be corrected, but
> I've checked this twice in the Hyperspec.
>
Yes. It confused me to. I plowed the Hyperspec for about a hour before
doing a grep deftype *.lisp and ending up with this solution..
For the record:
(defstruct scpoint
(x 0 :type (unsigned-byte 32))
(y 0 :type (unsigned-byte 32)))
is a much better solution.
I forgot that individual attributes in a struct could be given a type
and thought storeage would be inefficient.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> On Fri, 20 Jan 2006 22:48:38 +0100, ··············@hotmail.com
> <············@gmail.com> wrote:
>
> >
> > I admit this is confusing: "simple" in the "simple-array" means
> > something different than "simple" in "simple-vector." There's some
> > chance that I am also confused, and I would hope to be corrected, but
> > I've checked this twice in the Hyperspec.
> >
>
> Yes. It confused me to. I plowed the Hyperspec for about a hour before
> doing a grep deftype *.lisp and ending up with this solution..
> For the record:
>
> (defstruct scpoint
> (x 0 :type (unsigned-byte 32))
> (y 0 :type (unsigned-byte 32)))
>
> is a much better solution.
> I forgot that individual attributes in a struct could be given a type
> and thought storeage would be inefficient.
Just for information, the defstruct form itself takes a :type keyword
argument, which can suggest that the structure slots be contained in a
vector (including a specialized vector) or list. That allows slots to
be accessed through aref or car/cdr respectively.
Whether this is more or less efficient depends on how efficiently the
implementation stores vectors vs. structure-object objects.
··············@hotmail.com wrote:
> Just for information, the defstruct form itself takes a :type keyword
> argument, which can suggest that the structure slots be contained in a
To forestall corrections from others due to my imprecision here, the
"suggest" here only applies to the use of a specialized vector or
additional implementation-defined choices for structure representation.
As far as I can tell, the CL spec *requires* that 'list and 'vector
options result in the requested representation.
> vector (including a specialized vector) or list. That allows slots to
> be accessed through aref or car/cdr respectively.
>
> Whether this is more or less efficient depends on how efficiently the
> implementation stores vectors vs. structure-object objects.
"John Thingstad" <··············@chello.no> writes:
>> This sounds like something Dijkstra would not approve :) Any
>> explanation why
>> this is prefered?
>
> Good question.
> Here's one for screen coordinates:
> (don't try this on a 64-bit lisp)
Don't try it on any lisp; its behaviour is completely undefined.
(Furthermore, it is poor code in any case, using macros for
optimization when better mechanisms exist). It is likely to lead to
heap corruption in unsafe code, as raw 32-bit integers are interpreted
as pointers.
> (deftype scpoint () `(simple-array (unsigned-byte 32) 2))
> (defmacro make-scpoint () (make-array 2 :initial-element 0))
> (defmacro scref (point ind) `(the (unsigned-byte 32) (svref ,point
> (the (integer 0 2) ,ind))))
Using scref on an scpoint is now undefined behaviour. However, all of
this macroified optimization is unnecessary for efficiency in
implementations which perform even a small amount of type inference.
> As you see it takes a bit of effort to make it efficient.
Hmm.
> With complex numbers it is done for you and also you can forget
> portabillity issues.
That's not completely true, either. Common Lisp's complex numbers do
not allow you to represent a pure imaginary (or "pure y-axis", if you
will) floating point quantity.
Christophe
On Fri, 20 Jan 2006 16:35:57 +0100, Christophe Rhodes <·····@cam.ac.uk>
wrote:
> "John Thingstad" <··············@chello.no> writes:
>
>>> This sounds like something Dijkstra would not approve :) Any
>>> explanation why
>>> this is prefered?
>>
>> Good question.
>> Here's one for screen coordinates:
>> (don't try this on a 64-bit lisp)
>
> Don't try it on any lisp; its behaviour is completely undefined.
> (Furthermore, it is poor code in any case, using macros for
> optimization when better mechanisms exist). It is likely to lead to
> heap corruption in unsafe code, as raw 32-bit integers are interpreted
> as pointers.
>
The code is worked over from a real library on CLOCK as part
of a chess program. The file is bit-board.lisp.
By the way since most pointers are 32 bit it should work
on most implementations. Of course it's behaviour is not
defined by the spec... ;)
Normally I just use (make-array 2 :element-type 'fixnum :initial-element 0)
and hope the compiler knows what to do.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Fri, 20 Jan 2006 16:35:57 +0100, Christophe Rhodes
> <·····@cam.ac.uk> wrote:
>
>> Don't try it on any lisp; its behaviour is completely undefined.
>> (Furthermore, it is poor code in any case, using macros for
>> optimization when better mechanisms exist). It is likely to lead to
>> heap corruption in unsafe code, as raw 32-bit integers are interpreted
>> as pointers.
>
> The code is worked over from a real library on CLOCK as part
> of a chess program. The file is bit-board.lisp.
Unfortunately I couldn't find any references to this file on the big
bad internet, nor to "CLOCK". However, whether or not the original
code is broken, the code you chose to post publically is useless junk
and deserves to be held up as a didactic example of how not to do
things.
> By the way since most pointers are 32 bit it should work
> on most implementations.
If by "work" you mean "crash". If all you do is pass what are
actually simple-vectors to scref, then the worst you're likely to get,
indeed, is a type error informing you that your code is broken.
However, if you should have the temerity to actually pass an scpoint
(something that's TYPEP SCPOINT, rather than something that's returned
from MAKE-SCPOINT) to scref, you will likely corrupt your image.
> Of course it's behaviour is not defined by the spec... ;)
The way you say it you seem to think that that's a good thing, or
maybe a necessary thing to make it fast. Here is a free clue: it is
neither. The code you posted is rubbish, pure and simple, and I would
advise you to learn how to program before you post again, lest you
contaminate other people with your ignorance.
Christophe
(defstruct scpoint
(x 0 :type (unsigned-byte 32))
(y 0 :type (unsigned-byte 32)))
(defun sc+ (point1 point2)
(declare (type scpoint point1 point2)
;; in real code, this declaration wouldn't be here; instead,
;; would be an inline declaration or compiler macro calling to
;; an optimized out-of-line function
(optimize speed (safety 0)))
(let ((result (make-scpoint)))
(setf (scpoint-x result)
;; C-style wrapping semantics for overflow
(logand #xffffffff (+ (scpoint-x point1) (scpoint-x point2))))
(setf (scpoint-y result)
(logand #xffffffff (+ (scpoint-y point1) (scpoint-y point2))))
result))
Christophe Rhodes <·····@cam.ac.uk> writes:
> "John Thingstad" <··············@chello.no> writes:
>
>> On Fri, 20 Jan 2006 16:35:57 +0100, Christophe Rhodes
>> <·····@cam.ac.uk> wrote:
>>
>>> Don't try it on any lisp; its behaviour is completely undefined.
[...]
>> The code is worked over from a real library on CLOCK as part
>> of a chess program. The file is bit-board.lisp.
>
> Unfortunately I couldn't find any references to this file on the big
> bad internet, nor to "CLOCK". However, whether or not the original
The referred library might be the CLOCC subsystem `cil':
http://cvs.sourceforge.net/viewcvs.py/clocc/clocc/src/games/cil/
From the README file:
The CIL (Chess In Lisp) foundation is a Common Lisp implementaion of
all the core functions needed for development of chess applications.
Paolo
--
Why Lisp? http://wiki.alu.org/RtL%20Highlight%20Film
The Common Lisp Directory: http://www.cl-user.net
On Fri, 20 Jan 2006 18:12:22 +0100, Christophe Rhodes <·····@cam.ac.uk>
wrote:
> "John Thingstad" <··············@chello.no> writes:
>
>> On Fri, 20 Jan 2006 16:35:57 +0100, Christophe Rhodes
>> <·····@cam.ac.uk> wrote:
>>
>>> Don't try it on any lisp; its behaviour is completely undefined.
>>> (Furthermore, it is poor code in any case, using macros for
>>> optimization when better mechanisms exist). It is likely to lead to
>>> heap corruption in unsafe code, as raw 32-bit integers are interpreted
>>> as pointers.
>>
>> The code is worked over from a real library on CLOCK as part
>> of a chess program. The file is bit-board.lisp.
>
> Unfortunately I couldn't find any references to this file on the big
> bad internet, nor to "CLOCK". However, whether or not the original
> code is broken, the code you chose to post publically is useless junk
> and deserves to be held up as a didactic example of how not to do
> things.
>
http://cvs.sourceforge.net/viewcvs.py/clocc/clocc/src/games/cil/
>> By the way since most pointers are 32 bit it should work
>> on most implementations.
>
> If by "work" you mean "crash". If all you do is pass what are
> actually simple-vectors to scref, then the worst you're likely to get,
> indeed, is a type error informing you that your code is broken.
> However, if you should have the temerity to actually pass an scpoint
> (something that's TYPEP SCPOINT, rather than something that's returned
> from MAKE-SCPOINT) to scref, you will likely corrupt your image.
>
No I mean work.
(svref 1 #(1 #\a))
=> error #\a is not of type (unsigned-byte 32)
for example
For the record lisp is tagged and a integer is made to fit into
a pointer slot to save ram. It is hardly recomended to use it.
Nor is it likely to crash your system.
>> Of course it's behaviour is not defined by the spec... ;)
>
> The way you say it you seem to think that that's a good thing, or
> maybe a necessary thing to make it fast. Here is a free clue: it is
> neither. The code you posted is rubbish, pure and simple, and I would
> advise you to learn how to program before you post again, lest you
> contaminate other people with your ignorance.
I learn by doing.. Sometimes by doing bad.
I never claimed the code was brilliant.
In fact I claimed it was non portable which it is.
If that means contaminating delicate minds so be it.
But then as you see they contaminate mine too.
If you wish to prevent this I could really use a description of
the lisp type system. It is very difficult to find andy good
references to it. The Hyperspec sais very little on how to use it.
It's true I have little experience optimizing lisp, but I am a
fairly accomlpished programmer..
>
> Christophe
>
> (defstruct scpoint
> (x 0 :type (unsigned-byte 32))
> (y 0 :type (unsigned-byte 32)))
> (defun sc+ (point1 point2)
> (declare (type scpoint point1 point2)
> ;; in real code, this declaration wouldn't be here; instead,
> ;; would be an inline declaration or compiler macro calling to
> ;; an optimized out-of-line function
> (optimize speed (safety 0)))
> (let ((result (make-scpoint)))
> (setf (scpoint-x result)
> ;; C-style wrapping semantics for overflow
> (logand #xffffffff (+ (scpoint-x point1) (scpoint-x point2))))
> (setf (scpoint-y result)
> (logand #xffffffff (+ (scpoint-y point1) (scpoint-y point2))))
> result))
Too bad you manners arn't as good as your lisp.
John
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
"John Thingstad" <··············@chello.no> writes:
> On Fri, 20 Jan 2006 18:12:22 +0100, Christophe Rhodes
> <·····@cam.ac.uk> wrote:
>
>> "John Thingstad" <··············@chello.no> writes:
>>
>>> By the way since most pointers are 32 bit it should work
>>> on most implementations.
>>
>> If by "work" you mean "crash". If all you do is pass what are
>> actually simple-vectors to scref, then the worst you're likely to get,
>> indeed, is a type error informing you that your code is broken.
>> However, if you should have the temerity to actually pass an scpoint
>> (something that's TYPEP SCPOINT, rather than something that's returned
>> from MAKE-SCPOINT) to scref, you will likely corrupt your image.
>>
>
> No I mean work.
> (svref 1 #(1 #\a))
> => error #\a is not of type (unsigned-byte 32)
> for example
> For the record lisp is tagged and a integer is made to fit into
> a pointer slot to save ram. It is hardly recomended to use it.
> Nor is it likely to crash your system.
Yes, it is.
Let's consider the bit patterns, on a 32-bit lisp with a fairly common
implementation strategy, of
A = (make-array 2 :initial-element 3
:element-type '(unsigned-byte 32))
which is an SCPOINT in your language
and
B = (make-array 2 :initial-element 3)
which is something like what is returned from MAKE-SCPOINT
A will look something like
[ 000000xx | 00000008 | 00000003 | 00000003 ]
header length untagged3 untagged3
B will look like
[ 000000yy | 00000008 | 0000000c | 0000000c ]
header' length tagged3 tagged3
If you've lied to the compiler, as you have in your code, then
(scref a 0)
will return the untagged 3, but will not know that it was untagged; it
will instead treat it as a lispval. As you say, lisp objects are
normally tagged, with the low bits a type indicator and the rest an
address, in this case the address 0. There's nothing at that address,
so this dereference will segfault. This bogus lispval could well be
stored on the stack or in some variable (*, for example), which will
mean that the next GC will also segfault. (scref b 0) will not cause
such problems, as I said in my previous message.
Irrespective of this potential for heap corruption, it is also the
case that I would recommend against the use of macros for optimization
purposes.
Christophe
On Fri, 20 Jan 2006 20:34:08 +0100, Christophe Rhodes <·····@cam.ac.uk>
wrote:
Tried testing it in Corman LispWorks and Allegro.
Failed to reproduce any segfault even after a full gc clean-down.
Efficient though..
(deftype scpoint () `(simple-array (unsigned-byte 32) 2))
(defmacro make-scpoint () (make-array 2 :initial-element 0))
(defmacro scref (point ind) `(the (unsigned-byte 32) (svref ,point (the
(integer 0 2) ,ind))))
(defun sc+ (scp1 scp2)
(declare (type scpoint scp1 scp2))
(let ((result (make-scpoint)))
(declare (type scpoint result))
(setf (scref result 0) (+ (scref scp1 0) (scref scp2 0)) (scref result
1) (+ (scref scp1 1) (scref scp2 1)))
result))
(defun test ()
(declare (optimize (speed 3) (debug 0) (safety 0) (fixnum-safety 0)))
(let ((points
(loop repeat 1000
for A = (make-scpoint) then (make-scpoint) do
(setf (scref A 0) (random 1280) (scref A 1) (random 1024))
collect A)))
(reduce #'sc+ points)))
(loop repeat 10000 collect (test)
ran in approx 20 sec's on Pentiun Celleron D 320 with 256 MB ram.
(except in Corman which took twice as long)
Tried various error conditions which the comiler caught.
things like (sc+ #(1 #\a) #(1 2)), overflowing a fixnum etc.
also check-type'd the return.. fixnum
A fails as it is not a simple-vector.
If you want to crash a lisp compier it is easier just to
(declare (optimize (speed 3) (safety 0)) define a array
and the break the boundary.
Can you produce the code that breaks it?
>> No I mean work.
>> (svref 1 #(1 #\a))
>> => error #\a is not of type (unsigned-byte 32)
>> for example
>> For the record lisp is tagged and a integer is made to fit into
>> a pointer slot to save ram. It is hardly recomended to use it.
>> Nor is it likely to crash your system.
>
> Yes, it is.
>
> Let's consider the bit patterns, on a 32-bit lisp with a fairly common
> implementation strategy, of
>
> A = (make-array 2 :initial-element 3
> :element-type '(unsigned-byte 32))
> which is an SCPOINT in your language
>
> and
>
> B = (make-array 2 :initial-element 3)
> which is something like what is returned from MAKE-SCPOINT
>
> A will look something like
> [ 000000xx | 00000008 | 00000003 | 00000003 ]
> header length untagged3 untagged3
>
> B will look like
> [ 000000yy | 00000008 | 0000000c | 0000000c ]
> header' length tagged3 tagged3
>
> If you've lied to the compiler, as you have in your code, then
> (scref a 0)
> will return the untagged 3, but will not know that it was untagged; it
> will instead treat it as a lispval. As you say, lisp objects are
> normally tagged, with the low bits a type indicator and the rest an
> address, in this case the address 0. There's nothing at that address,
> so this dereference will segfault. This bogus lispval could well be
> stored on the stack or in some variable (*, for example), which will
> mean that the next GC will also segfault. (scref b 0) will not cause
> such problems, as I said in my previous message.
>
> Irrespective of this potential for heap corruption, it is also the
> case that I would recommend against the use of macros for optimization
> purposes.
>
> Christophe
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/
John Thingstad wrote:
> On Fri, 20 Jan 2006 20:34:08 +0100, Christophe Rhodes <·····@cam.ac.uk>
> wrote:
>
> Tried testing it in Corman LispWorks and Allegro.
> Failed to reproduce any segfault even after a full gc clean-down.
> Efficient though..
...
> (defun sc+ (scp1 scp2)
> (declare (type scpoint scp1 scp2))
> (let ((result (make-scpoint)))
> (declare (type scpoint result))
> (setf (scref result 0) (+ (scref scp1 0) (scref scp2 0)) (scref result
> 1) (+ (scref scp1 1) (scref scp2 1)))
> result))
>
> (defun test ()
> (declare (optimize (speed 3) (debug 0) (safety 0) (fixnum-safety 0)))
> (let ((points
> (loop repeat 1000
> for A = (make-scpoint) then (make-scpoint) do
> (setf (scref A 0) (random 1280) (scref A 1) (random 1024))
> collect A)))
> (reduce #'sc+ points)))
The declare in this function does NOT cause sc+ to be compiled with
high speed and low safety. That's the one with the lying declarations.