I would like to pose a (not so) simple question:
Suppose you have a function that yields 2 integers (fixnums). Some
possible mechanisms to return them to its caller would be:
- values. Both fixnums are ALWAYS necessary, so this doesn't seem an
adequate option in this case. (Moreover, some implementations seem to
have issues with applying values-list repeatedly. But that's another -
also intriguing- question).
- list with 2 elements.
- cons. A simple pair. This should perform at first glance slightly
better than a list.
- complex number. Separating later the real from the imaginary part.
- [simple] vector.
- some other form I have not thought of at this moment (please
suggest).
Which is the most efficient way to return two numbers? What would you
do?
<·······@eurogaran.com> wrote:
+---------------
| I would like to pose a (not so) simple question:
| Suppose you have a function that yields 2 integers (fixnums). Some
| possible mechanisms to return them to its caller would be:
| - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
| adequate option in this case.
+---------------
While true for Scheme, this is simply incorrect for Common Lisp.
In CL, excess return values are silently ignored:
> (+ 3 (values 4 13))
7
>
Just use VALUES.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Rob Warnock wrote:
> <·······@eurogaran.com> wrote:
> +---------------
> | I would like to pose a (not so) simple question:
> | Suppose you have a function that yields 2 integers (fixnums). Some
> | possible mechanisms to return them to its caller would be:
> | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> | adequate option in this case.
> +---------------
>
> While true for Scheme, this is simply incorrect for Common Lisp.
> In CL, excess return values are silently ignored:
That is how I parsed it at first, too, but on second parsing decided
they meant "always required by the application" the implied inadequacy
being that we do not use values for such beasts.
CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The Correct
Answer?
kt
On Aug 8, 8:49 am, Kenny <·········@gmail.com> wrote:
> Rob Warnock wrote:
> > <·······@eurogaran.com> wrote:
> > +---------------
> > | I would like to pose a (not so) simple question:
> > | Suppose you have a function that yields 2 integers (fixnums). Some
> > | possible mechanisms to return them to its caller would be:
> > | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> > | adequate option in this case.
> > +---------------
>
> > While true for Scheme, this is simply incorrect for Common Lisp.
> > In CL, excess return values are silently ignored:
>
> That is how I parsed it at first, too, but on second parsing decided
> they meant "always required by the application" the implied inadequacy
> being that we do not use values for such beasts.
>
> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The Correct
> Answer?
>
> kt
Yes. It says
"Use complex numbers to represent points in a plane"
but it also says:
"To improve the readability of your code ... If you have complex data
structures,
you are often better off describing them with a DEFSTRUCT, even if
the type is LIST"
A struct is another alternative, especially if the return value might
be extended
in the future.
--S
smallpond wrote:
> On Aug 8, 8:49 am, Kenny <·········@gmail.com> wrote:
>> Rob Warnock wrote:
>>> <·······@eurogaran.com> wrote:
>>> +---------------
>>> | I would like to pose a (not so) simple question:
>>> | Suppose you have a function that yields 2 integers (fixnums). Some
>>> | possible mechanisms to return them to its caller would be:
>>> | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
>>> | adequate option in this case.
>>> +---------------
>>> While true for Scheme, this is simply incorrect for Common Lisp.
>>> In CL, excess return values are silently ignored:
>> That is how I parsed it at first, too, but on second parsing decided
>> they meant "always required by the application" the implied inadequacy
>> being that we do not use values for such beasts.
>>
>> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The Correct
>> Answer?
>>
>> kt
>
>
> Yes. It says
>
> "Use complex numbers to represent points in a plane"
True, but for a different reason. Geometrical transformations such as
rotations become much easier if points are represented as complex numbers.
Alberto
Alberto Riva wrote:
> smallpond wrote:
>> On Aug 8, 8:49 am, Kenny <·········@gmail.com> wrote:
>>> Rob Warnock wrote:
>>>> <·······@eurogaran.com> wrote:
>>>> +---------------
>>>> | I would like to pose a (not so) simple question:
>>>> | Suppose you have a function that yields 2 integers (fixnums). Some
>>>> | possible mechanisms to return them to its caller would be:
>>>> | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
>>>> | adequate option in this case.
>>>> +---------------
>>>> While true for Scheme, this is simply incorrect for Common Lisp.
>>>> In CL, excess return values are silently ignored:
>>> That is how I parsed it at first, too, but on second parsing decided
>>> they meant "always required by the application" the implied inadequacy
>>> being that we do not use values for such beasts.
>>>
>>> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The Correct
>>> Answer?
>>>
>>> kt
>>
>>
>> Yes. It says
>>
>> "Use complex numbers to represent points in a plane"
>
> True, but for a different reason. Geometrical transformations such as
> rotations become much easier if points are represented as complex numbers.
>
But it was a Lisp FAQ, not a geometry FAQ, so I parsed "points in a
plane" as "two numbers". :) No?
kt
Kenny wrote:
> Alberto Riva wrote:
>> smallpond wrote:
>>> On Aug 8, 8:49 am, Kenny <·········@gmail.com> wrote:
>>>> Rob Warnock wrote:
>>>>> <·······@eurogaran.com> wrote:
>>>>> +---------------
>>>>> | I would like to pose a (not so) simple question:
>>>>> | Suppose you have a function that yields 2 integers (fixnums). Some
>>>>> | possible mechanisms to return them to its caller would be:
>>>>> | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
>>>>> | adequate option in this case.
>>>>> +---------------
>>>>> While true for Scheme, this is simply incorrect for Common Lisp.
>>>>> In CL, excess return values are silently ignored:
>>>> That is how I parsed it at first, too, but on second parsing decided
>>>> they meant "always required by the application" the implied inadequacy
>>>> being that we do not use values for such beasts.
>>>>
>>>> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The Correct
>>>> Answer?
>>>>
>>>> kt
>>>
>>>
>>> Yes. It says
>>>
>>> "Use complex numbers to represent points in a plane"
>>
>> True, but for a different reason. Geometrical transformations such as
>> rotations become much easier if points are represented as complex
>> numbers.
>>
>
> But it was a Lisp FAQ, not a geometry FAQ, so I parsed "points in a
> plane" as "two numbers". :) No?
Well, points in a plane can be represented as a pair of numbers, but
that doesn't necessarily mean that all pairs of numbers should be though
of as points in a plane (and therefore represented in a way that is
convenient for points in a plane, but not necessarily for other
purposes)... but I'm sure you knew that ;)
Alberto
Alberto Riva wrote:
> Kenny wrote:
>> Alberto Riva wrote:
>>> smallpond wrote:
>>>> On Aug 8, 8:49 am, Kenny <·········@gmail.com> wrote:
>>>>> Rob Warnock wrote:
>>>>>> <·······@eurogaran.com> wrote:
>>>>>> +---------------
>>>>>> | I would like to pose a (not so) simple question:
>>>>>> | Suppose you have a function that yields 2 integers (fixnums). Some
>>>>>> | possible mechanisms to return them to its caller would be:
>>>>>> | - values. Both fixnums are ALWAYS necessary, so this doesn't
>>>>>> seem an
>>>>>> | adequate option in this case.
>>>>>> +---------------
>>>>>> While true for Scheme, this is simply incorrect for Common Lisp.
>>>>>> In CL, excess return values are silently ignored:
>>>>> That is how I parsed it at first, too, but on second parsing decided
>>>>> they meant "always required by the application" the implied inadequacy
>>>>> being that we do not use values for such beasts.
>>>>>
>>>>> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The
>>>>> Correct
>>>>> Answer?
>>>>>
>>>>> kt
>>>>
>>>>
>>>> Yes. It says
>>>>
>>>> "Use complex numbers to represent points in a plane"
>>>
>>> True, but for a different reason. Geometrical transformations such as
>>> rotations become much easier if points are represented as complex
>>> numbers.
>>>
>>
>> But it was a Lisp FAQ, not a geometry FAQ, so I parsed "points in a
>> plane" as "two numbers". :) No?
>
> Well, points in a plane can be represented as a pair of numbers, but
> that doesn't necessarily mean that all pairs of numbers should be though
> of as points in a plane (and therefore represented in a way that is
> convenient for points in a plane, but not necessarily for other
> purposes)... but I'm sure you knew that ;)
>
Yes. I believe the key question is what is conveyed by the context of
this information's appearance in the Lisp FAQ.
Perhaps there is no conflict, perhaps the Lisp Gods who in days of old
were frequently set upon by geometers with this question, while today's
geometers being the thorough and studious type are finding their answer
in the Lisp FAQ this then being the first known success of an FAQ.
Happy thought!
kzo
Kenny <·········@gmail.com> writes:
> Rob Warnock wrote:
>> <·······@eurogaran.com> wrote:
>> +---------------
>> | I would like to pose a (not so) simple question:
>> | Suppose you have a function that yields 2 integers (fixnums). Some
>> | possible mechanisms to return them to its caller would be:
>> | - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
>> | adequate option in this case.
>> +---------------
>> While true for Scheme, this is simply incorrect for Common Lisp.
>> In CL, excess return values are silently ignored:
>
> That is how I parsed it at first, too, but on second parsing decided
> they meant "always required by the application" the implied inadequacy
> being that we do not use values for such beasts.
>
> CMIIAW, but doesn't the Lisp FAQ specify complex numbers as The
> Correct Answer?
Perhaps an old version of the FAQ. It's a trick that could be used on
an implementation where it would have some advantage.
But multiple values are clearly designed to let the compiler optimize
them a lot (using registers instead of L1-cache to store them). So
it's really the first choice. Only on a poor implementation or a poor
processor (register starved) could it be necessary to do it otherwise.
--
__Pascal Bourguignon__
On Fri, 08 Aug 2008 00:43:01 -0700, kodifik wrote:
> I would like to pose a (not so) simple question: Suppose you have a
> function that yields 2 integers (fixnums). Some possible mechanisms to
> return them to its caller would be: - values. Both fixnums are ALWAYS
> necessary, so this doesn't seem an adequate option in this case.
I don't understand this. Why would this fact prevent you from using
values?
> (Moreover, some implementations seem to have issues with applying
> values-list repeatedly. But that's another - also intriguing- question).
> - list with 2 elements.
> - cons. A simple pair. This should perform at first glance slightly
> better than a list.
> - complex number. Separating later the real from the imaginary part. -
> [simple] vector.
> - some other form I have not thought of at this moment (please suggest).
simple-array of 2 elements.
> Which is the most efficient way to return two numbers? What would you
> do?
I would not give a damn. Or just use values. Or if I find that this is
a bottleneck in my code (not very likely) after some profiling, I would
just time all options.
You did not specify what you mean by "efficient". Speed? Memory usage?
Compilation time? I am assuming it is speed, as most misguided
optimization attempts try to improve that.
You did not even say which CL implementation you are using. There are
some rules of thumb which tell you when something is more efficient than
something else, but I know of none that would apply here. Lisp compilers
are very efficient nowadays, and you can't easily guess what is the
fastest option.
Are you sure you are not engaging in premature optimization?
Tamas
> I would not give a damn. Or just use values. Or if I find that this is
> a bottleneck in my code (not very likely) after some profiling, I would
> just time all options.
>
I have timed some of the options inside Symbolics Genera
(interpreted), CLISP (interp.), OpenMCL (compiled) and SBCL
(compiled).
1- values are always big win.
2- cons is the second best option inside any implementation.
3- complex is always behind cons in speed
4- depending on the implementation, you find here the rest of the
candidates (2 element vector, list, etc.)
> You did not specify what you mean by "efficient". Speed? Memory usage?
> Compilation time? I am assuming it is speed, as most misguided
> optimization attempts try to improve that.
>
Yes. Need for Speed.
> You did not even say which CL implementation you are using. There are
> some rules of thumb which tell you when something is more efficient than
> something else, but I know of none that would apply here. Lisp compilers
> are very efficient nowadays, and you can't easily guess what is the
> fastest option.
>
I tend to go from one implementation to another. This conduct will be
the more frequent as open software extends.
By the way... Compilers could be more clever. I mean :
(time (dotimes (i 1000000) (progn (setq a (complex 3 4)) (setq b
(realpart a)) (setq c (imagpart a)))))
with an "intelligent" compiler should compile to :
(time (progn (setq a (complex 3 4)) (setq b (realpart a)) (setq c
(imagpart a))))
> Are you sure you are not engaging in premature optimization?
>
> Tamas
The question was a generic one, not specific to a program. But yes,
you really have a point here.
On Tue, 12 Aug 2008 01:43:36 -0700, kodifik wrote:
> By the way... Compilers could be more clever. I mean : (time (dotimes (i
> 1000000) (progn (setq a (complex 3 4)) (setq b (realpart a)) (setq c
> (imagpart a))))) with an "intelligent" compiler should compile to :
> (time (progn (setq a (complex 3 4)) (setq b (realpart a)) (setq c
> (imagpart a))))
Yes, you can optimize all sorts of things. But people who write
compilers have a finite amount of time and resources, and should not
concentrate on optimizing to counteract the idiocy of the programmer
(because anyone who writes that dotimes code should clearly look for a
career in other field; eg chartered accountancy).
Do you thing the compiler optimize (EXP (* #C(0 1) PI)) to -1? Where do
you stop?
Tamas
Tamas K Papp <······@gmail.com> writes:
> Do you thing the compiler optimize (EXP (* #C(0 1) PI)) to -1? Where do
> you stop?
Well, I would expect something close to that, but not exactly. Constant
folding is a standard compiler optimization:
CL-USER> (defun f () (EXP (* #C(0 1) PI)))
F
CL-USER> (compile 'f)
F
NIL
NIL
CL-USER> (disassemble 'f)
;; disassembly of #<Function F>
;; formals:
;; constant vector:
0: #C(-1.0d0 1.2246063538223773d-16)
;; code start: #x71b959cc:
0: e3 02 jcxz 4
2: cd 61 int $97 ; SYS::TRAP-ARGERR
4: 80 7f cb 00 cmpb [edi-53],$0 ; SYS::C_INTERRUPT-PENDING
8: 74 02 jz 12
10: cd 64 int $100 ; SYS::TRAP-SIGNAL-HIT
12: 8b 46 12 movl eax,[esi+18] ; #C(-1.0d0 1.2246063538223773d-16)
15: f8 clc
16: 8b 75 fc movl esi,[ebp-4]
19: c3 ret
--
Thomas A. Russ, USC/Information Sciences Institute
On Tue, 12 Aug 2008 15:10:14 -0700, Thomas A. Russ wrote:
> Tamas K Papp <······@gmail.com> writes:
>
>> Do you thing the compiler optimize (EXP (* #C(0 1) PI)) to -1? Where
>> do you stop?
>
> Well, I would expect something close to that, but not exactly. Constant
> folding is a standard compiler optimization:
>
>
>
> CL-USER> (defun f () (EXP (* #C(0 1) PI))) F
> CL-USER> (compile 'f)
> F
> NIL
> NIL
> CL-USER> (disassemble 'f)
> ;; disassembly of #<Function F>
> ;; formals:
> ;; constant vector:
> 0: #C(-1.0d0 1.2246063538223773d-16)
>
> ;; code start: #x71b959cc:
> 0: e3 02 jcxz 4
> 2: cd 61 int $97 ; SYS::TRAP-ARGERR 4: 80 7f cb 00 cmpb
> [edi-53],$0 ; SYS::C_INTERRUPT-PENDING 8: 74 02 jz 12
> 10: cd 64 int $100 ; SYS::TRAP-SIGNAL-HIT 12: 8b 46 12 movl
> eax,[esi+18] ; #C(-1.0d0 1.2246063538223773d-16) 15: f8 clc
> 16: 8b 75 fc movl esi,[ebp-4]
> 19: c3 ret
Yes, I realized my example was bad - I wanted an example for algebraic
manipulations done by the compiler. Replace it with
(+ (* a a) (* 2 a b) (* b b))
optimized to
(let ((sum (+ a b)))
(* sum sum))
Surely no one would expect this from a compiler. Likewise, nor would I
expect the loop in the OP to be optimized away.
Tamas
Tamas K Papp <······@gmail.com> writes:
> On Tue, 12 Aug 2008 15:10:14 -0700, Thomas A. Russ wrote:
>
>> Tamas K Papp <······@gmail.com> writes:
>>
>>> Do you thing the compiler optimize (EXP (* #C(0 1) PI)) to -1? Where
>>> do you stop?
>>
>> Well, I would expect something close to that, but not exactly. Constant
>> folding is a standard compiler optimization:
>>
>>
>>
>> CL-USER> (defun f () (EXP (* #C(0 1) PI))) F
>> CL-USER> (compile 'f)
>> F
>> NIL
>> NIL
>> CL-USER> (disassemble 'f)
>> ;; disassembly of #<Function F>
>> ;; formals:
>> ;; constant vector:
>> 0: #C(-1.0d0 1.2246063538223773d-16)
>>
>> ;; code start: #x71b959cc:
>> 0: e3 02 jcxz 4
>> 2: cd 61 int $97 ; SYS::TRAP-ARGERR 4: 80 7f cb 00 cmpb
>> [edi-53],$0 ; SYS::C_INTERRUPT-PENDING 8: 74 02 jz 12
>> 10: cd 64 int $100 ; SYS::TRAP-SIGNAL-HIT 12: 8b 46 12 movl
>> eax,[esi+18] ; #C(-1.0d0 1.2246063538223773d-16) 15: f8 clc
>> 16: 8b 75 fc movl esi,[ebp-4]
>> 19: c3 ret
>
> Yes, I realized my example was bad - I wanted an example for algebraic
> manipulations done by the compiler. Replace it with
>
> (+ (* a a) (* 2 a b) (* b b))
>
> optimized to
>
> (let ((sum (+ a b)))
> (* sum sum))
>
> Surely no one would expect this from a compiler. Likewise, nor would I
> expect the loop in the OP to be optimized away.
Actually, optmizing away the loop is easier than algebraic
manipulations. In the case of the loop, dataflow analysis routinely
done by compilers would show that the loop body doesn't depend on the
iteration variable and is side-effect free, so it can be considered
constant, and optimizing compilers to move constant calculations
outside of loops. There would remains an empty body which could easily
motivate removal of the loop as dead code prunning.
On the other hand, algebraic manipulations, or any other such
"simplification" would require a lot of rules, and possibly up to a
theorem prover to work in anything more than the most trivial cases.
This is not totally out of the order, but it isn't done usually in
compiler.
Notice that for most programming language, arithmetic is actually done
modulo a power of two, and therefore the _semantics_ of (+ (* a a) (*
2 a b) (* b b)) is not at all the same as that of (let ((sum (+ a b)))
(* sum sum)), with respect to overflows and error detection. If you
assumee integers or rationals, in lisp it would be ok to do it, but as
soon as you consider floating point, you might prefer one or the
other, for rounding and error propagation questions. So there are
very good reasons why normal compilers would not do such
transformations in the first place. Well, unless they consider
themselves symbolic calculus packages instead of compilers :-)
--
__Pascal Bourguignon__
In article
<····································@34g2000hsh.googlegroups.com>,
·······@eurogaran.com wrote:
> I would like to pose a (not so) simple question:
> Suppose you have a function that yields 2 integers (fixnums). Some
> possible mechanisms to return them to its caller would be:
> - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> adequate option in this case. (Moreover, some implementations seem to
> have issues with applying values-list repeatedly. But that's another -
> also intriguing- question).
> - list with 2 elements.
> - cons. A simple pair. This should perform at first glance slightly
> better than a list.
> - complex number. Separating later the real from the imaginary part.
> - [simple] vector.
> - some other form I have not thought of at this moment (please
> suggest).
> Which is the most efficient way to return two numbers? What would you
> do?
I would use 'values'.
I've seen also libraries where two small fixnums are coded into
one fixnum.
--
http://lispm.dyndns.org/
On Fri, 8 Aug 2008 ·······@eurogaran.com wrote:
> I would like to pose a (not so) simple question:
> Suppose you have a function that yields 2 integers (fixnums). Some
> possible mechanisms to return them to its caller would be:
> - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> adequate option in this case. (Moreover, some implementations seem to
> have issues with applying values-list repeatedly. But that's another -
> also intriguing- question).
> - list with 2 elements.
> - cons. A simple pair. This should perform at first glance slightly
> better than a list.
> - complex number. Separating later the real from the imaginary part.
> - [simple] vector.
> - some other form I have not thought of at this moment (please
> suggest).
> Which is the most efficient way to return two numbers? What would you
> do?
>
In scheme, I usually supply a continuation. In CL,
you have to be careful since CL doesn't fully
tail-optimize:
(defun add1and2 (a k)
(funcall k (1+ a) (1+ (1+ a))))
(add1and2 1 #'list)
=> (2 3)
(add1and2 1 #'(lambda (a b)
(list a b)))
=> (2 3)
On Aug 8, 7:58 am, "Kjetil S. Matheussen" <··············@notam02.no>
wrote:
> On Fri, 8 Aug 2008 ·······@eurogaran.com wrote:
>
>
>
> > I would like to pose a (not so) simple question:
> > Suppose you have a function that yields 2 integers (fixnums). Some
> > possible mechanisms to return them to its caller would be:
> > - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> > adequate option in this case. (Moreover, some implementations seem to
> > have issues with applying values-list repeatedly. But that's another -
> > also intriguing- question).
> > - list with 2 elements.
> > - cons. A simple pair. This should perform at first glance slightly
> > better than a list.
> > - complex number. Separating later the real from the imaginary part.
> > - [simple] vector.
> > - some other form I have not thought of at this moment (please
> > suggest).
> > Which is the most efficient way to return two numbers? What would you
> > do?
>
> In scheme, I usually supply a continuation. In CL,
> you have to be careful since CL doesn't fully
> tail-optimize:
>
> (defun add1and2 (a k)
> (funcall k (1+ a) (1+ (1+ a))))
>
> (add1and2 1 #'list)
>
> => (2 3)
>
> (add1and2 1 #'(lambda (a b)
> (list a b)))
>
> => (2 3)
Which CL implementation does not fully tail-optimize? (Yes: it is a
somewhat rethorical question). :)
Cheers
--
Marco
??>> In scheme, I usually supply a continuation. In CL,
??>> you have to be careful since CL doesn't fully
??>> tail-optimize:
MA> Which CL implementation does not fully tail-optimize? (Yes: it is a
MA> somewhat rethorical question). :)
····@debetch:~$ clisp
i i i i i i i ooooo o ooooooo ooooo ooooo
I I I I I I I 8 8 8 8 8 o 8 8
I \ `+' / I 8 8 8 8 8 8
\ `-+-' / 8 8 8 ooooo 8oooo
`-__|__-' 8 8 8 8 8
| 8 o 8 8 o 8 8
------+------ ooooo 8oooooo ooo8ooo ooooo 8
Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2006
[1]> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
TAILR
[2]> (tailr 1000 0)
1000
[3]> (tailr 10000 0)
*** - Program stack overflow. RESET
[4]>
i dunno why you consider this "rhetorical question" -- indeed, as Kjetil
says, you
need to be careful, as it depends on implementation, and whether function is
interpreted or compiled. it seems Armed Bear Common Lisp does not do tail
call optimization even in compiled mode, no matter what do you do -- and it
is considered a correct behaviour by standard, isn't it?
>>>>> "Alex" == Alex Mizrahi <········@users.sourceforge.net> writes:
Alex> ??>> In scheme, I usually supply a continuation. In CL,
Alex> ??>> you have to be careful since CL doesn't fully
Alex> ??>> tail-optimize:
MA> Which CL implementation does not fully tail-optimize? (Yes: it is a
MA> somewhat rethorical question). :)
Alex> ····@debetch:~$ clisp
Alex> i i i i i i i ooooo o ooooooo ooooo ooooo
Alex> I I I I I I I 8 8 8 8 8 o 8 8
Alex> I \ `+' / I 8 8 8 8 8 8
Alex> \ `-+-' / 8 8 8 ooooo 8oooo
Alex> `-__|__-' 8 8 8 8 8
Alex> | 8 o 8 8 o 8 8
Alex> ------+------ ooooo 8oooooo ooo8ooo ooooo 8
Alex> Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Alex> Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Alex> Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Alex> Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Alex> Copyright (c) Sam Steingold, Bruno Haible 2001-2006
Alex> [1]> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
Alex> TAILR
Alex> [2]> (tailr 1000 0)
Alex> 1000
Alex> [3]> (tailr 10000 0)
Alex> *** - Program stack overflow. RESET
Alex> [4]>
Perhaps it will work better if you compile tailr first.
Ray
"Alex Mizrahi" <········@users.sourceforge.net> writes:
> ??>> In scheme, I usually supply a continuation. In CL,
> ??>> you have to be careful since CL doesn't fully
> ??>> tail-optimize:
> MA> Which CL implementation does not fully tail-optimize? (Yes: it is a
> MA> somewhat rethorical question). :)
>
> ····@debetch:~$ clisp
> i i i i i i i ooooo o ooooooo ooooo ooooo
> I I I I I I I 8 8 8 8 8 o 8 8
> I \ `+' / I 8 8 8 8 8 8
> \ `-+-' / 8 8 8 ooooo 8oooo
> `-__|__-' 8 8 8 8 8
> | 8 o 8 8 o 8 8
> ------+------ ooooo 8oooooo ooo8ooo ooooo 8
>
> Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
> Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
> Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
> Copyright (c) Bruno Haible, Sam Steingold 1999-2000
> Copyright (c) Sam Steingold, Bruno Haible 2001-2006
>
> [1]> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
> TAILR
> [2]> (tailr 1000 0)
> 1000
> [3]> (tailr 10000 0)
>
> *** - Program stack overflow. RESET
> [4]>
Of course, you didn't ask for TCO!
C/USER[1]> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
TAILR
C/USER[2]> (compile 'tailr)
TAILR ;
NIL ;
NIL
C/USER[3]> (disassemble 'tailr)
Disassembly of function TAILR
2 required arguments
0 optional arguments
No rest parameter
No keyword parameters
9 byte-code instructions:
0 L0
0 (LOAD&PUSH 2)
1 (CALLS2&JMPIF 147 L7) ; PLUSP
4 (LOAD 1)
5 (SKIP&RET 3)
7 L7
7 (LOAD&DEC&PUSH 2)
9 (LOAD&INC&PUSH 2)
11 (JMPTAIL 2 5 L0) ;<---------------- there's even a JMPTAIL in the VM!
NIL
C/USER[4]>
> i dunno why you consider this "rhetorical question" -- indeed, as Kjetil
> says, you
> need to be careful, as it depends on implementation, and whether function is
> interpreted or compiled. it seems Armed Bear Common Lisp does not do tail
> call optimization even in compiled mode, no matter what do you do -- and it
> is considered a correct behaviour by standard, isn't it?
Yes it is.
So, there's one CL implementation that doesn't do it,
and one that let you debug your code in interpreted mode.
--
__Pascal Bourguignon__
PJB> Of course, you didn't ask for TCO!
that was the point -- it might not work automatically, you need to
ask for it.
PJB> So, there's one CL implementation that doesn't do it,
PJB> and one that let you debug your code in interpreted mode.
_at least_ one. i didn't say i tested them all. ECL also doesn't seem
to do tail call optimization neither in interpreted, nor in compiled mode:
ECL (Embeddable Common-Lisp) 0.9i
> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
TAILR
> (tailr 10000 0)
Frame stack overflow.
Broken at TAILR.
ECL (Embeddable Common-Lisp) 0.9i
> (defun tailr (a b) (if (plusp a) (tailr (1- a) (1+ b)) b))
TAILR
> (compile 'tailr)
;;; End of Pass 1.
;;; Note: Replacing variable G47 by its value
;;; Note: Emitting linking call for TAILR
;;; Calling the C compiler...
;;; Note: Invoking external command:
;;;
/usr/bin/gcc-4.1 -g -O2 -fPIC -D_THREAD_SAFE -fstrict-aliasing -Dlinux -O
"-I/usr/lib/ecl/" -w -c "/home/alex/ECL0017YAADj.c" -o
"/home/alex/ECL0017YAADj.o"
;;; Note: Invoking external command:
;;; /usr/bin/gcc-4.1 -o "/home/alex/ECL0017YAADj.fas" -L"/usr/lib/ecl/"
"/home/alex/ECL0017YAADj.o" -Wl,--rpath,/usr/lib/ecl/ -shared -lecl -lpthread
-ldl -lm -lgc -lgmp
;;; OPTIMIZE levels: Safety=2, Space=0, Speed=3
TAILR
NIL
NIL
> (tailr 1000 0)
1000
> (tailr 10000 0)
10000
> (tailr 100000 0)
Segmentation fault
On Aug 8, 3:43 am, ·······@eurogaran.com wrote:
> I would like to pose a (not so) simple question:
> Suppose you have a function that yields 2 integers (fixnums). Some
> possible mechanisms to return them to its caller would be:
> - values. Both fixnums are ALWAYS necessary, so this doesn't seem an
> adequate option in this case. (Moreover, some implementations seem to
> have issues with applying values-list repeatedly. But that's another -
> also intriguing- question).
> - list with 2 elements.
> - cons. A simple pair. This should perform at first glance slightly
> better than a list.
> - complex number. Separating later the real from the imaginary part.
> - [simple] vector.
> - some other form I have not thought of at this moment (please
> suggest).
> Which is the most efficient way to return two numbers? What would you
> do?
Use values. That is, return two values.
In the comments in front of the function, document that its contract
requires it to always return two values.
At ITA, we have a set of macros with names like define-strict-
function, in which we have an "enhanced" argument list that lists the
expected (runtime) types of all the arguments, and all the returned
values, as well as the conditions that this function is contractually
allowed to signal. We use it for major entrypoints between modules.
It generates check-type forms and so on, but also checks that the
number of returned values is as specified.
We've been thinking of open-sourcing these macros. It's just a few
pages of code. We've been refining and debugging them for a while
(e.g. making sure that the CCL and SBCL compilers don't complain about
"ignored variables" that aren't ignored, and a few little nits like
that). Maybe they're ready for prime time.