start quoting Guybrush Treepwood :
> Is there a way in Common Lisp to represent Infinity, so that I can do:
>
> (> 0 Infinity) -> NIL
> (< 0 Infinity) -> T
Yes, by way of infinity being part of the IEEE floating-point specification.
Look up the *-float-(posi|nega)tive-infinity constants.
+ Svein Ove Aas <·········@aas.no>:
| start quoting Guybrush Treepwood :
|
| > Is there a way in Common Lisp to represent Infinity, so that I can do:
| >
| > (> 0 Infinity) -> NIL
| > (< 0 Infinity) -> T
|
| Yes, by way of infinity being part of the IEEE floating-point specification.
| Look up the *-float-(posi|nega)tive-infinity constants.
Not in the HyperSpec, hence probably not in ANSI Common Lisp, so there
is no portable way.
But I notice that CMUCL has them. Guess I was wrong in stating that
12.1.4.3 rules out the existence of these constants; it's just that
they cannot result from a computation with finite numbers in a
conforming implementation. Oh, wait a minute, CMUCL lets you ignore
floating point errors, in which case "the appropriate infinity" may
result.
Maybe I should listen more and post less.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow
Guybrush Treepwood <·······@hotmail.com> wrote:
> Is there a way in Common Lisp to represent Infinity, so that I can do:
>
> (> 0 Infinity) -> NIL
> (< 0 Infinity) -> T
some implementations defines constants, but it is not defined in the
standard:
http://groups.google.de/groups?threadm=utnDc.172%24nc.153%40fed1read03
Is it defined in LispWorks? I have found most-positive-single-float, only,
but not infinity, like described by the IEEE standard. The *features*
variable contains :IEEE-FLOATING-POINT, so I think infinity should be
defined.
--
Frank Bu�, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss wrote:
> Guybrush Treepwood <·······@hotmail.com> wrote:
>
>> Is there a way in Common Lisp to represent Infinity, so that I can do:
>>
>> (> 0 Infinity) -> NIL
>> (< 0 Infinity) -> T
>
> some implementations defines constants, but it is not defined in the
> standard:
I'm using Allegro CL. Is there then another way around that I could use to
represent infinity?
> I'm using Allegro CL. Is there then another way around that I could use to
> represent infinity?
Would something like (defconstant Infinity most-positive-long-float) be ok?
···············@yahoo.com wrote:
> It depends on your application. What would you like to use Infinity
> for?
In a heuristic function, when I calculate path costs, to rule out a path, I
would like to add Infinity to the other levelcosts.
On Wed, 05 Jan 2005 20:58:28 +0100, Guybrush Treepwood
<·······@hotmail.com> wrote:
> ···············@yahoo.com wrote:
>
>> It depends on your application. What would you like to use Infinity
>> for?
>
> In a heuristic function, when I calculate path costs, to rule out a
> path, I
> would like to add Infinity to the other levelcosts.
A sufficiently large value like most-positive-fixnum would do for this.
At least that is what I usually use.
As long at it is larger that any value you are likely to compute
it dosn't really make any difference.
Also It make the logic simpler since you would end up having
a if tree to handle combos of infinity and number otherwise.
--
Using M2, Opera's revolutionary e-mail client: http://www.opera.com/m2/
Guybrush Treepwood wrote:
> ···············@yahoo.com wrote:
>
>
>>It depends on your application. What would you like to use Infinity
>>for?
>
>
> In a heuristic function, when I calculate path costs, to rule out a path, I
> would like to add Infinity to the other levelcosts.
That is a kludge likely to cause more trouble than it would take to
explicity rule out paths. It already does not work in that there is no
portable way to specify infinity, and you are already on c.l.l. looking
for help. You'd be done by now with an explicit rule-out mechanism.
Mind you, programmers do this kind of cutesy hack all the time, but that
is part of why programming productivity remains at abysmal levels.
kenny
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Kenny Tilton wrote:
>
>
> Guybrush Treepwood wrote:
>
>> ···············@yahoo.com wrote:
>>
>>
>>> It depends on your application. What would you like to use Infinity
>>> for?
>>
>>
>>
>> In a heuristic function, when I calculate path costs, to rule out a
>> path, I
>> would like to add Infinity to the other levelcosts.
>
>
> That is a kludge likely to cause more trouble than it would take to
> explicity rule out paths. It already does not work in that there is no
> portable way to specify infinity, and you are already on c.l.l. looking
> for help. You'd be done by now with an explicit rule-out mechanism.
I will expand on this. Is the cost of these ruled-out paths infinite?
No, they have been ruled out, full stop. their costs have not been truly
calculated. had they been, some usable valuable would have resulted, and
no "In Search of Infinity" would have followed.
So. Does ruling things out complexify things? Not really. Don't forget,
things were already complexified by "The Quest For Infinity". So we
start a step ahead with explicit rule-outs. Now what we do is create
some explicit mechanism (flag, table, whatever) whose name screams
"these bad boys are not on the table". And, yes, instead of code simply
comparing costs, we see code which first checks if a path is still on
the table. And all i can say is, Yes! Let me see that test! Otherwise I
might be wondering, why the hell is every path being considered when I
know full well certain paths could have been eliminated by now? More
likely, some code whose actual cost is mad low and which should be
selected is not getting selected, and I go crazy trying to figure out why.
Eventually I find a line of code assigning infinitude to a cost when the
path is being ruled out, because of some rule-out scheme I happened not
to be considering because the only code I saw was (< cost-a cost-b)
instead of a loop tossing ruled-outs, so my candidate was not even
reaching the cost comparison, which would have tipped me off, and then I
load up my glock and go looking for the SOB who wrote the code. "Cute.
Now yer gonna die!" Often the victim is myself, mind you.
btw, note to Aaron Gross: here is a good example where someone asked
about a language mechanism, and once they disclosed why, at least one
cll denizen (moi) had much different advice to offer.
kenny
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Kenny Tilton wrote:
> Kenny Tilton wrote:
>
>> Guybrush Treepwood wrote:
>>
>>> In a heuristic function, when I calculate path costs, to rule out a
>>> path, I
>>> would like to add Infinity to the other levelcosts.
>>
>>
>> That is a kludge likely to cause more trouble than it would take to
>> explicity rule out paths. It already does not work in that there is no
>> portable way to specify infinity, and you are already on c.l.l.
>> looking for help. You'd be done by now with an explicit rule-out
>> mechanism.
Feh. Infinity is no kludge. Its semantics are so useful that they are
etched in silicon in the FPUs of all of our computers. My major exposure
to path cost calculations has been in the context of TCP/IP's associated
routing protocols, but the OP's approach is exactly how the literature
describes the algorithms.
> I will expand on this. Is the cost of these ruled-out paths infinite?
> No, they have been ruled out, full stop. their costs have not been truly
> calculated. had they been, some usable valuable would have resulted, and
> no "In Search of Infinity" would have followed.
>
> So. Does ruling things out complexify things? Not really. Don't forget,
> things were already complexified by "The Quest For Infinity". So we
> start a step ahead with explicit rule-outs. Now what we do is create
> some explicit mechanism (flag, table, whatever) whose name screams
> "these bad boys are not on the table". And, yes, instead of code simply
> comparing costs, we see code which first checks if a path is still on
> the table.
You and the OP are suggesting the same thing, except that the infinity
"flag" gets stored in the slot that would otherwise hold the finite path
cost, and the "code that checks" is at a lower level of abstraction
(possibly even in hardware), thus invisible. Which, I think, matches the
mental model used by the people who write this kind of code.
Cameron MacKinnon wrote:
> Kenny Tilton wrote:
>
>> Kenny Tilton wrote:
>>
>>> Guybrush Treepwood wrote:
>>>
>>>> In a heuristic function, when I calculate path costs, to rule out a
>>>> path, I
>>>> would like to add Infinity to the other levelcosts.
>>>
>>>
>>>
>>> That is a kludge likely to cause more trouble than it would take to
>>> explicity rule out paths. It already does not work in that there is
>>> no portable way to specify infinity, and you are already on c.l.l.
>>> looking for help. You'd be done by now with an explicit rule-out
>>> mechanism.
>
>
> Feh. Infinity is no kludge. Its semantics are so useful that they are
> etched in silicon in the FPUs of all of our computers. My major exposure
> to path cost calculations has been in the context of TCP/IP's associated
> routing protocols, but the OP's approach is exactly how the literature
> describes the algorithms.
>
>> I will expand on this. Is the cost of these ruled-out paths infinite?
>> No, they have been ruled out, full stop. their costs have not been
>> truly calculated. had they been, some usable valuable would have
>> resulted, and no "In Search of Infinity" would have followed.
>>
>> So. Does ruling things out complexify things? Not really. Don't
>> forget, things were already complexified by "The Quest For Infinity".
>> So we start a step ahead with explicit rule-outs. Now what we do is
>> create some explicit mechanism (flag, table, whatever) whose name
>> screams "these bad boys are not on the table". And, yes, instead of
>> code simply comparing costs, we see code which first checks if a path
>> is still on the table.
>
>
> You and the OP are suggesting the same thing, except that the infinity
> "flag" gets stored in the slot that would otherwise hold the finite path
> cost, and the "code that checks" is at a lower level of abstraction
> (possibly even in hardware), thus invisible. Which, I think, matches the
> mental model used by the people who write this kind of code.
I did not say the kludge could not be made to work. All kludges work.
Nor am I surprised to learn the kludge is popular. I have worked in tall
buildings with other programmers as much as I have done the solo
entrepreneur thing, and I see the code/algorithms discussed here on
c.l.l. There is a long tradition of clever tricks in computer
programming, which is why so very few are really very good at it.
The good news is that programming gets easier when one goes thru the
analysis I modeled above and simply mirrors in ones code the
functionality desired.
kenny
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
Ingvar <······@hexapodia.net> writes:
> For routing, specifically, not necessarily so. It introduces more
> special cases that need to bbe handled. Things like "this route is not
> considered" and "this route only leads to things not considered".
>
> Using a sufficiently-high cost makes those things fall out and be
> handled as part of the normal routing decision.
And you would change all your math to use floating point (something
which your fellow advocate does not understand at all) instead of the
far faster integer math just because of this single need... and in one
of the most speed-critical code paths in all of computing?
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Ingvar <······@hexapodia.net> writes:
> Rahul Jain <·····@nyct.net> writes:
>
>> And you would change all your math to use floating point (something
>> which your fellow advocate does not understand at all) instead of the
>> far faster integer math just because of this single need... and in one
>> of the most speed-critical code paths in all of computing?
>
> In general, no. I'd probably use something that was sufficiently
> outside normal expected values to represent "infinity" (if we're
> using unsigned 32-bit arithmetic and expect normal path costs to be in
> the range of 30-40, perhaps using 2^31 as an "infinity" is safe
> enough). Thus, should teh rest of the routing mesh be sufficiently
> brokwen that we reach a *real* path cost of multiple orders of
> magnitude larger than normal, we'd start considering our
> previously-uncosidered route due to the sheer cost of teh other paths.
Hmm... that would be a rather strange situation indeed, and I'm not sure
that you'd want to use a route that was explicitly asked to not be used
in that case. There may be security/trust issues involved.
> And, these days, I am not actually sure FP math is much slower than
> integer math.
If 7 times is "not much", ok.
> The expensive thing is doing route lookups and that
> doesn't involve running a routing protocol, it just involves looking
> at a ready-prepared FIB (it's usually a merge of the results from
> several routing protocols), so we're only doing routing calculations
> in the "slow path" anyway.
Hmm... but you'd need to compute routing costs via all routes for each
different destination, right? Wouldn't it be different for different
destinations and possibly for different ports for different
destinations? (Say, if you wanted to keep, latency-sensitive
communications to a specific network on a high-cost-per-byte link.)
> Using an "infinity" value isn't about
> speeding up the run-time, it's to simplify implementation.
Wouldn't something like (throw 'compute-cost nil) be more sensible?
(let ((best-cost t)
(best-route nil))
(dolist (route routes)
(let ((cost (catch 'compute-cost
(compute-cost dest route))))
(when (and cost
(or (not best-route) (< cost best-cost)))
(setq best-cost cost
best-route route)))))
Not sure how that's particularly complex to write.
> The unfortunate protocol I was alluding to, where this horizon is on
> the small side is (of course) RIP, where "infinity" is 15, making it
> hard using path cost to affect route selection, even in not-very-large
> networks.
Fun. Good thing we double RIP in civilized societies. ;)
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Rahul Jain wrote:
> Ingvar <······@hexapodia.net> writes:
>
>>And, these days, I am not actually sure FP math is much slower than
>>integer math.
>
>
> If 7 times is "not much", ok.
What CPU is this?
Cameron MacKinnon <··········@clearspot.net> writes:
> Rahul Jain wrote:
>> Ingvar <······@hexapodia.net> writes:
>>
>>>And, these days, I am not actually sure FP math is much slower than
>>>integer math.
>> If 7 times is "not much", ok.
>
> What CPU is this?
Pentium 4 is actually 10 times. (Integer adds take 1/2 cycle.)
The Athlon 64/Opteron is 3-4 times.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Guybrush Treepwood wrote:
>
>
>>I'm using Allegro CL. Is there then another way around that I could use to
>>represent infinity?
>
>
> Would something like (defconstant Infinity most-positive-long-float) be ok?
That depends.
There is a long-winded way of doing things which is of use in an
extended arithmetic setting. Of course, you must not be obsessed with
"efficiency" (quotes mandatory) in this case.
==================
(defpackage "MY-MATH" (:use "CL")
(:shadow "+" "<" #|etc etc|#)
(:export "+" "<" "+POSITIVE-INFINITY+" #|etc etc|#))
(defconstant +positive-infinity+ '+positive-infinity+)
;;; +negative-infinity+ etc. etc.
(defgeneric + (x y))
(defmethod + ((x number) (y number)) (cl:+ x y))
(defmethod + ((x number) (y (eql +positive-infinity+)))
+positive-infinity+)
(defmethod + ((x (eql +positive-infinity+))
(y (eql +positive-infinity+)))
+positive-infinity+)
(defmethod < ((x number) (y number)) (cl:< x y))
(defmethod < ((x number) (y (eql +positive-infinity+))) t)
(defmethod < ((y (eql +positive-infinity+)) (x number)) nil)
#|...|#
==================
You get the idea....
Cheers
Marco
I forgot a thing :)
Marco Antoniotti wrote:
>
>
> Guybrush Treepwood wrote:
>
>>
>>
>>> I'm using Allegro CL. Is there then another way around that I could
>>> use to
>>> represent infinity?
>>
>>
>>
>> Would something like (defconstant Infinity most-positive-long-float)
>> be ok?
>
>
>
> That depends.
>
> There is a long-winded way of doing things which is of use in an
> extended arithmetic setting. Of course, you must not be obsessed with
> "efficiency" (quotes mandatory) in this case.
>
> ==================
>
> (defpackage "MY-MATH" (:use "CL")
> (:shadow "+" "<" #|etc etc|#)
> (:export "+" "<" "+POSITIVE-INFINITY+" #|etc etc|#))
(in-package "MY-MATH") ; Sorry. This was missing.
>
> (defconstant +positive-infinity+ '+positive-infinity+)
> ;;; +negative-infinity+ etc. etc.
>
>
> (defgeneric + (x y))
>
> (defmethod + ((x number) (y number)) (cl:+ x y))
>
> (defmethod + ((x number) (y (eql +positive-infinity+)))
> +positive-infinity+)
>
> (defmethod + ((x (eql +positive-infinity+))
> (y (eql +positive-infinity+)))
> +positive-infinity+)
>
>
> (defmethod < ((x number) (y number)) (cl:< x y))
>
> (defmethod < ((x number) (y (eql +positive-infinity+))) t)
>
> (defmethod < ((y (eql +positive-infinity+)) (x number)) nil)
>
> #|...|#
>
> ==================
>
To use the above you can then do
cl-prompt> (in-package "MY-MATH")
#<Package MY-MATH>
cl-prompt> (+ 2 3)
5
cl-prompt> (+ 2 +positive-infinity+)
+POSITIVE-INFINITY+
cl-prompt> (< +positive-infinity+ most-positive-double-float)
NIL
Cheers
--
Marco
In article <·················@typhoon.nyu.edu>, Marco Antoniotti wrote:
> (defpackage "MY-MATH" (:use "CL")
> (:shadow "+" "<" #|etc etc|#)
> (:export "+" "<" "+POSITIVE-INFINITY+" #|etc etc|#))
>
[ (in-package "MY-MATH") ]
>
> (defconstant +positive-infinity+ '+positive-infinity+)
> ;;; +negative-infinity+ etc. etc.
>
>
> (defgeneric + (x y))
>
> (defmethod + ((x number) (y number)) (cl:+ x y))
>
> (defmethod + ((x number) (y (eql +positive-infinity+)))
> +positive-infinity+)
I've seen stuff like this before, and I'm curious what happens in the
case of
(+ +positive-infinity+ 0)
? That is, when you have
(defmethod operator ((x type1) (y type2))
...)
but you want it to work with the types of the operands swapped, too.
Certainly in this case you could
(defmethod + ((x (eql +positive-infinity+)) (y number))
(+ y x))
, but that only works for those two types. And so I wonder if you
could also do a more general declaration which says, in effect, "this
operator is commutative":
(defmethod operator ((x t) (y t))
(operator y x))
Would this work, in the general case? I think it would, but I'm not
positive. In particular, I'm not sure what would (or should) happen
in the case of arguments with no applicable methods (other than the (t
t) one). A quick test shows that you get infinite recursion (or just
an infinite loop, if your compiler optimizes away the actual function
call).
Perhaps something like
(defmacro def-commutative-method (name ((arg1 type1) (arg2 type2)) &body body)
`(progn (defmethod ,name ((,arg1 ,type1) (,arg2 ,type2)) ,@body)
(defmethod ,name ((,arg1 ,type2) (,arg2 ,type1)) (,name ,arg2 ,arg1))))
which only makes specific types commutative, and still allows for
recovery from no-applicable-method conditions.
-- Larry
From: Jim Newton
Subject: Re: Commutative method definition [Was: Re: Infinity]
Date:
Message-ID: <41E0309E.7010402@rdrop.com>
I've often thought of this problem of generic
functions with commutative parameters. In general it might
be that a function has several arguments, some of which
are commutative. It is a problem that comes up quite
often for me.
Arbitration functions are a good example.
Suppose you have a set of classes C1, C2, ... CN
and a function matches-p which determines whether
a given class is "applicable" for a situation indicated
by a control class S.
Suppose s is of class S and c1 is of class c1, then
(matches-p s c1) returning true means that C1 is applicable.
However, it might be the case that several of the C1...CN classes
are applicable and another generic function must arbitrate to the most
specific situation.
E.g., should it return c1 or c2? whichever is more specific (more specific
being defined in terms of whatever the application is, not necessarily
according to class precedence list).
But (arbitrate s c1 c2) returning c1 implies that (arbitrate s c2 c1)
must also return c1.
(defmethod arbitrate ((s s) (c1 C1) (c2 C2))
c1)
(defmethod arbitrate ((s s) (c2 C2) (c1 C1))
c1)
The find-most-significant function must call matches-p on
all the available classes, then it must call the arbitrate
function between enough pairs to narrow the selection down to
a single situation.
In article <················@rdrop.com>, Jim Newton wrote:
> I've often thought of this problem of generic functions with
> commutative parameters. In general it might be that a function has
> several arguments, some of which are commutative. It is a problem
> that comes up quite often for me.
>
> Arbitration functions are a good example.
[snip]
> The find-most-significant function must call matches-p on all the
> available classes, then it must call the arbitrate function between
> enough pairs to narrow the selection down to a single situation.
I think in a case like that, I'd take a different approach, and not
use generic dispatch directly. I think I'd just say
(defun arbitrate (s &rest args)
#| ... |# )
and have arbitrate do a more direct graph-search of the appropriate
methods.
Interesting approach, though.
-- Larry
From: Jim Newton
Subject: Re: Commutative method definition [Was: Re: Infinity]
Date:
Message-ID: <34d4b9F499m3eU1@individual.net>
hi Larry, the reason i do not like the defun approach
is that what if another user adds some new classes
to the system. What i'd like him to be able to do
is tell through a matches-p method when the new
classes are applicable, and through arbitrate methods
how to resolve ambiguous situations.
-jim
Larry Clapp wrote:
> In article <················@rdrop.com>, Jim Newton wrote:
>
>>I've often thought of this problem of generic functions with
>>commutative parameters. In general it might be that a function has
>>several arguments, some of which are commutative. It is a problem
>>that comes up quite often for me.
>>
>>Arbitration functions are a good example.
>
> [snip]
>
>>The find-most-significant function must call matches-p on all the
>>available classes, then it must call the arbitrate function between
>>enough pairs to narrow the selection down to a single situation.
>
>
> I think in a case like that, I'd take a different approach, and not
> use generic dispatch directly. I think I'd just say
>
> (defun arbitrate (s &rest args)
> #| ... |# )
>
> and have arbitrate do a more direct graph-search of the appropriate
> methods.
>
> Interesting approach, though.
>
> -- Larry
>
Guybrush Treepwood wrote:
> Frank Buss wrote:
>
>
>>Guybrush Treepwood <·······@hotmail.com> wrote:
>>
>>
>>>Is there a way in Common Lisp to represent Infinity, so that I can do:
>>>
>>>(> 0 Infinity) -> NIL
>>>(< 0 Infinity) -> T
>>
>>some implementations defines constants, but it is not defined in the
>>standard:
>
>
> I'm using Allegro CL. Is there then another way around that I could use to
> represent infinity?
>
These are from ACL:
ARCHOS(4): (apropos "INFINITY")
ACLWIN302:+INFINITY value: #.EXCL::*INFINITY-DOUBLE*
ACLWIN302:-INFINITY value: #.EXCL::*NEGATIVE-INFINITY-DOUBLE*
EXCL::INFINITY-DATA
EXCL::*INFINITY-DOUBLE* value: #.EXCL::*INFINITY-DOUBLE*
EXCL::*NEGATIVE-INFINITY-DOUBLE* value: #.EXCL::*NEGATIVE-INFINITY-DOUBLE*
EXCL::LOOP-MINIMAX-INFINITY-DATA [function] (STRUCT)
EXCL::*INFINITY-SINGLE* value: #.EXCL::*INFINITY-SINGLE*
EXCL::*NEGATIVE-INFINITY-SINGLE* value: #.EXCL::*NEGATIVE-INFINITY-SINGLE*
:INFINITY-DATA value: :INFINITY-DATA
Note that apropos is perfect for these kinds of questions. ACL also has
an apropos dialog on the Search menu, which is what I normally use.
kt
--
Cells? Cello? Celtik?: http://www.common-lisp.net/project/cells/
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film
+ Guybrush Treepwood <·······@hotmail.com>:
| Is there a way in Common Lisp to represent Infinity, so that I can do:
|
| (> 0 Infinity) -> NIL
| (< 0 Infinity) -> T
(defconstant Infinity 1)
8-)
Well, to attempt to be slightly more serious, it seems to me that
HyperSpec 12.1.4.3 rules that out.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- Debating gives most of us much more psychological satisfaction
than thinking does: but it deprives us of whatever chance there is
of getting closer to the truth. -- C.P. Snow