Cost of Recursion
Robert Posey
My Professor made the statement that LISP is one of the few languages where
Recursion is a valid concept in nontrivial programs. She stated the cost
of each function call relatively much less than in C etc. I have now
read that this is true if a function is tail recursive. However, this
still seems odd to me since it requires compilers make some of those
smart decisions they so often fail to do in practice. Does anyone have
any benchmarks that compare recursion and Interation for large data
sets. Hopefully, the LISP benchmark writers will avoid the C vs C++
war benchmarks where highly optimized routines from the version the
author likes are compared against poorly written implementation in
the hated alternative. What I am looking for is reasonable attempts
at ultimate performance for both methods.
Muddy
Joe Marshall
Robert Posey <mu...@raytheon.com> wrote in message
news:38A0285E...@raytheon.com...
> Dear Gentle Persons,
> My Professor made the statement that LISP is one of the few languages
where
> Recursion is a valid concept in nontrivial programs.
Recursion is a valid concept independent of the language. Algorithms that
are not `primitive recursive' are extremely difficult to code in an
`iterative'
fashion (Ackermann's function, for example).
I assume that your professor meant something like `Where both are possible,
a recursive solution to a problem is likely to perform poorly compared to an
iterative one, except for some languages like Lisp.' But even this is too
vague
a statement to evaluate.
> She stated the cost
> of each function call relatively much less than in C etc.
It depends on what is involved in making a function call. In the C
implementations
I have seen, a function call usually means pushing some arguments on the
stack,
pushing a return address and jumping to the entry point, saving the
base-of-frame
pointer and adjusting the stack for locals. When returning, you discard the
locals,
pop the base-of-frame, return to the caller, and discard the arguments.
A standard Lisp function call happens the same way. There may be some extra
processing of keyword, optional and rest args, and maybe some dynamic
binding,
but the functional call sequence is likely to be similar.
I'd have to say that unless you have special `function calling hardware'
that the cost
of a function call to an 'unknown function' in C and Lisp are comparable.
Lisp compilers can be very smart about calls to `known functions'. If a
function is
lexically nested within another, via FLET or LABELS, the compiler can often
perform
extensive optimizations that will reduce or eliminate the function call
overhead.
However, C doesn't have nested functions, so you can't compare the costs of
these
functions.
(On the other hand, C++ *can* have nested classes with which you can emulate
nested functions. C++ compilers generally do no optimization whatsoever on
these kind of function calls.)
> I have now
> read that this is true if a function is tail recursive.
Tail recursive calls can be compiled into jump statements. Instead of
calling
the target function, you replace your stack frame with the callees arguments
a jump to the callees entry point. Tail recursive calls to
`unknown' functions (i.e., the compiler knows nothing about the callee), are
unlikely to be any faster (and may be slightly slower) than
non-tail-recursive calls.
The primary savings here is in space. A tail recursive call pushes no
stack, so
the process will evolve iteratively.
Tail recursive calls to known functions (like self calls and calls to
lexically visible
functions) can often be turned into simple jump statements. These calls are
no more expensive than the iterative version of the code (in fact, it
probably
compiles into the same object code).
Lisp compilers have been doing tail-recursion elimination for years, but
some C
compilers can do tail-recursion elimination. Certain constructs in the C
and C++
language limit the applicability of tail-recursion elimination (as do some
in Lisp),
but where both compilers can do tail-recursion elimination, they will emit
similar code.
> However, this
> still seems odd to me since it requires compilers make some of those
> smart decisions they so often fail to do in practice.
Tail recursion elimination doesn't require the mythical `sufficiently smart
compiler'.
Simply tracking the continuation through the code is often sufficient, but
if
there is stack-allocated data, you might have to analyze the lifetime of the
data.
> Does anyone have
> any benchmarks that compare recursion and Interation for large data
> sets.
When you can compare tail recursion and iteration in those problems that can
be structured both ways, the results are similar. There are a few edge
cases
where the tail recursive solution is slightly slower because in general you
have
to build a new stack frame and copy it over the current one. But there are
also
cases where the iteration is slightly slower.
> Hopefully, the LISP benchmark writers will avoid the C vs C++
> war benchmarks where highly optimized routines from the version the
> author likes are compared against poorly written implementation in
> the hated alternative.
The GNU C compiler can do tail recursion elimination for self calls, so
there
wouldn't be any glaring differences.
-----
Where tail recursion wins is not in performance, but in expressability. If
your compiler
does not do tail recursion elimination, there will be a `hidden' factor of
O(N) space
added to your algorithm if you code it in a recursive fashion. You will
have to keep that
in mind when coding a solution. However, if your compiler does tail
recursion
elimination, you don't need to worry about when and where this extra O(n)
factor appears.
For instance, some algorithms are more naturally expressed as a set of
mutually
tail recursive functions. You would have to rework the algorithm if your
compiler does
not do tail recursion elimination.
Some algorithms are `mostly iterative'. For instance algorithms that deal
with list structure
that is `mostly' linear, but with the occasionally sub-branch. If the
compiler does tail-recursive
elimination, the solution will be `mostly iterative' as well. If not, it is
rather difficult to
code this as an iterative process with an explicit stack for the branching
alternatives.
Some algorithms have unusual flow of control. If you have first-class
functions, you can
exercise explicit control over the flow by coding in `continuation-passing'
style. In this
style, you never return a value from a function, instead you call a
`continuation' function.
If your compiler does not do tail-recursion elimination,
`continuation-passing' style programming
will quickly exhaust the stack.
Barry Margolin
Joe Marshall <jmar...@alum.mit.edu> wrote:
>I'd have to say that unless you have special `function calling hardware'
>that the cost
>of a function call to an 'unknown function' in C and Lisp are comparable.
Traditionally, implementors of functional languages have worked harder on
optimizing function calls, since the style of programming in these
languages is so dependent on them. It has been more common to write
recursive programs in these languages. This is where old professors
probably got the impression that function calls and recursion were more
efficient in these languages.
--
Barry Margolin, bar...@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.
Marco Antoniotti
Robert Posey <mu...@raytheon.com> writes:
> Dear Gentle Persons,
> My Professor made the statement that LISP is one of the few languages where
> Recursion is a valid concept in nontrivial programs.
Recursion is a *necessary* concept in all inherently recursive
algorithms. E.g. Tree Traversal.
> She stated the cost
> of each function call relatively much less than in C etc. I have now
> read that this is true if a function is tail recursive. However, this
> still seems odd to me since it requires compilers make some of those
> smart decisions they so often fail to do in practice. Does anyone have
> any benchmarks that compare recursion and Interation for large data
> sets.
First get it right, then get it fast. If faster means nightmarishly
difficult to maintain, then keep the slower version. Usually
recursive solutions (especially for inherently recursive algorithms
and data-structures) are easier to get right and to maintain. Most of
the time they are also faster than the alternative , since a hand made
stack is most likely going to be slower than the one handled by the
compiler and runtime conventions of the host language. (If you do not
understand why I am talking about a stack, you need to do some more
reading :) )
Note that this comment is completely language independent.
> Hopefully, the LISP benchmark writers will avoid the C vs C++
> war benchmarks where highly optimized routines from the version the
> author likes are compared against poorly written implementation in
> the hated alternative. What I am looking for is reasonable attempts
> at ultimate performance for both methods.
Pardon my bluntness, but this is a bogus question. If your recursive
solution fits the bill (meets the specs, makes your customer happy,
whatever) why should you care? Meanwhile, as I said, *most likely*,
your recursive solution is going to be easier to maintain. This
should be enough.
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa
Gareth McCaughan
> My Professor made the statement that LISP is one of the few languages where
> Recursion is a valid concept in nontrivial programs. She stated the cost
> of each function call relatively much less than in C etc.
Function call is cheap in C too these days. Lisp compilers
tend to put more effort into making function calls efficient,
because typical Lisp programs use quite a lot of function
calls; but, against that, some Lisp function calls have to
be more expensive than C function calls have to be, because
you can redefine functions in Lisp.
That is, if I do
(defun foo (x) (* x x))
(defun bar (x) (+ (foo x) (foo x)))
(defun foo (x) 0)
then the call in BAR now needs to call the new version of FOO.
To arrange this you have to do one of two things: (1) make
the call to FOO do one more level of indirection than it would
have to in a language like C, to look up the current meaning
of FOO; or, (2) arrange that when the definition of FOO changes
the code for BAR gets patched to refer to the new definition.
So far as I know, no actual Lisp system takes option (2).
Some Lisp function calls are a lot more expensive than this
because of complications like multiple values, optional
arguments, and (much worse than either of these) keyword
arguments.
In any case, in most compiled languages these days, most
function calls are very cheap. Sufficiently cheap that it's
hardly ever correct to avoid function calls for the sake
of efficiency -- not, at least, until you've finished the
program and found it's too slow and established that the
function calls add significantly to the time it takes.
Which just about never happens.
> I have now
> read that this is true if a function is tail recursive.
The point here is that a tail call (note: what matters here
isn't whether the *function* is tail-recursive, but whether
the *call* you're considering is a tail call) can often be
compiled as some assignments and a jump.
Unless you're concerned about running out of stack space,
though, full calls aren't usually that much more expensive
than tali calls.
[SNIP: request for benchmarks]
I realise that that request was really the main point of
your request, but I have none to offer. Sorry.
It might, however, be worth mentioning that good Lisp compilers
(CMU CL, for instance) will sometimes turn recursions into
iterations, producing exactly the same code for each formulation.
Here's a toy example. If you give CMU CL the (stupid)
definition
(defun f (x)
(declare (type (integer 0 1000) x))
(if (> x 0)
(f (1- x))
x))
then (on my machine, at least!) it will compile it to machine code
with the following structure.
function entry:
check that exactly one arg was passed (if not, jump to ZOG1)
check that the argument is a fixnum in [0,1000] (if not, jump to ZOG2)
move argument into a temporary register
jump to FOO
ZOG2:
error-handling code for wrong-type case
FOO:
compare temporary register with 0
if >0, jump to BAR
return from function call
BAR:
subtract 1 from temporary register
jump to FOO
ZOG1:
error-handling code for wrong-number-of-args case
It would be possible to shave a couple of cycles off
this code, but there's certainly nothing there that
resembles a recursive function call any more.
--
Gareth McCaughan Gareth.M...@pobox.com
sig under construction
Robert Munyer
Robert Posey <mu...@raytheon.com> wrote:
> Dear Gentle Persons,
> My Professor made the statement that LISP is one of the few
> languages where Recursion is a valid concept in nontrivial
> programs.
Are you sure your professor didn't say "for TRIVIAL programs?"
In that case the statement would be true. If you are writing a
simple loop that needs to run fast, recursion is fine in Lisp but
should be avoided in most other languages.
But for NON-trivial programs, recursion is so valuable that you
will often want to use it even in languages that haven't been
optimized to handle it quickly.
For example, I heard some people have created an improved version
of Java, called Pizza. They wrote a translator (in Java) that
reads a Pizza program and translates it into an ordinary Java
program that any Java compiler can handle. I haven't read their
source code, but I'd be willing to bet that they used recursion,
even though Java is NOT optimized to handle recursion quickly.
Ask your professor if recursion is "valid" for implementing Quicksort,
in various languages. Personally I can't think of any language
except FORTRAN where I'd want to do Quicksort without recursion.
> She stated the cost of each function call relatively much less
> than in C etc. I have now read that this is true if a function
> is tail recursive. However, this still seems odd to me since it
> requires compilers make some of those smart decisions they so
> often fail to do in practice.
Dealing with tail recursion does not require an extremely smart
compiler. All the compiler has to do is notice that this function
does a function call and then immediately does a return, and doesn't
do any other useful work in between. Pretty simple.
> Does anyone have any benchmarks that compare recursion and
> Interation for large data sets. Hopefully, the LISP benchmark
> writers will avoid the C vs C++ war benchmarks where highly
> optimized routines from the version the author likes are compared
> against poorly written implementation in the hated alternative.
> What I am looking for is reasonable attempts at ultimate performance
> for both methods.
Benchmarks aren't necessary, because if you have a compiler that
achieves "ultimate performance for both methods," you can just
disassemble the compiled code and you'll see that both versions of
source code were compiled to the exact same machine language code.
-- Robert Munyer <mun...@mcs.com>
Robert Posey
Marco Antoniotti wrote:
>
> Robert Posey <mu...@raytheon.com> writes:
>
> > Dear Gentle Persons,
>
> > Hopefully, the LISP benchmark writers will avoid the C vs C++
> > war benchmarks where highly optimized routines from the version the
> > author likes are compared against poorly written implementation in
> > the hated alternative. What I am looking for is reasonable attempts
> > at ultimate performance for both methods.
>
> Pardon my bluntness, but this is a bogus question. If your recursive
> solution fits the bill (meets the specs, makes your customer happy,
> whatever) why should you care? Meanwhile, as I said, *most likely*,
> your recursive solution is going to be easier to maintain. This
> should be enough.
I am looking for the first evidence that a nontrivial recursive
solution is not much slower than the alternative. I am also
curious why you think a recursive solution would be easier to
maintain, its sure a lot harder to debug. Its a major pain to
handle in a multi-tasking system where you either add level of
recursion counters or become completely lost. It there is a easy
way to debug recursion, I would be very happy to read about it. I
work in an embedded environment I will admit, but I have never seen
recursive code released. If your compiler is smart enough to
properly handle tail recursive solutions, I am at a lost to how you
would debug optimized recursive code.
Muddy
Tim Bradshaw
> I
> work in an embedded environment I will admit, but I have never seen
> recursive code released.
Erm? Quicksort. Any of the multitude of n-ary tree algorithms.
--tim
Tim Bradshaw
> then the call in BAR now needs to call the new version of FOO.
> To arrange this you have to do one of two things: (1) make
> the call to FOO do one more level of indirection than it would
> have to in a language like C, to look up the current meaning
> of FOO; or, (2) arrange that when the definition of FOO changes
> the code for BAR gets patched to refer to the new definition.
> So far as I know, no actual Lisp system takes option (2).
Genera on Ivory gets very close with the `Direct calls' feature. You
can say that calls to a number (or all) functions are to be
direct-linked, which bypasses the function cell. If you redefine a
function which is called in this way you get an error, and one of the
proceed options is to unlink direct calls to it. You could almost
certainly wrap some error-handling code around this to unlink & then
relink. Redefining a function would take minutes though...
--tim
Robert Posey
At least in C, the performance of Quicksort can be improved quite a
bit(I hear) by Iteration. If I had easy access to a system that
I could do reasonable timing measurements on, I would attempt to prove it.
I will admit, that Quicksort is even harder to understand than usual
in Iterative form. I don't like it anyway, and would never use it
unless I had to. Its timing varies too much, on a small change, and
randomizing the input is a pain. Besides, in many cases Bucket sort
is faster and much easier. Classic example sorting incoming integers of
a know range is both much simpler and much faster using Bucket sort.
Quicksort is a good generic sort algorithm, but generic sort should
only be used when it not a performance driver, or the data types are
unknown in advance. In the Embedded world, both of these are unlikely.
Muddy
>
> --tim
Robert Posey
Of course on most DSO and some general processor the cost of performing a
loop N times is a low fixed setup cost with zero per iteration cost.
Muddy
>
> --tim
Joe Marshall
>
> I am looking for the first evidence that a nontrivial recursive
> solution is not much slower than the alternative.
I assume you agree that some problems are recursive by nature and
that an `iterative' solution isn't reasonable.
Given that, included is a program that will find the roots to an equation
using Newton's method. I tried to find a simple enough, but non-trivial
program that is in actual use. I copied the recursive version I found in
the scmutils package in use at MIT, I wrote the two iterative versions
myself.
All three versions run in just about the same time.
> I am also
> curious why you think a recursive solution would be easier to
> maintain, its sure a lot harder to debug.
Not that much harder.
> Its a major pain to
> handle in a multi-tasking system where you either add level of
> recursion counters or become completely lost.
I don't understand why you need `recursion counters'.
> It there is a easy
> way to debug recursion, I would be very happy to read about it. I
> work in an embedded environment I will admit, but I have never seen
> recursive code released.
I see it and write it all the time.
> If your compiler is smart enough to
> properly handle tail recursive solutions, I am at a lost to how you
> would debug optimized recursive code.
If your compiler is aggressively optimizing out tail calls, you are correct
in that you might find yourself in a function with no idea how you got
there.
A few calls to `trace' will generally solve that problem.
(in-package "USER")
(declaim (optimize (speed 3) (safety 1)))
(defun close-enuf? (a b eps)
(< (abs (- a b)) eps))
(defun average (a b)
(/ (+ a b) 2))
(defun newton-improve (f-and-df xn)
(multiple-value-bind (fn dfn)
(funcall f-and-df xn)
(- xn (/ fn dfn))))
(defun newton-search-rec (f-and-df this-guess eps)
(let ((next-guess (newton-improve f-and-df this-guess)))
(if (close-enuf? this-guess next-guess eps)
(average this-guess next-guess)
(newton-search-rec f-and-df next-guess eps))))
(defun newton-search-iter-1 (f-and-df start-guess eps)
(do ((next-guess (newton-improve f-and-df start-guess)
(newton-improve f-and-df next-guess))
(this-guess start-guess next-guess))
((close-enuf? this-guess next-guess eps) (average this-guess
next-guess))
))
(defun newton-search-iter-2 (f-and-df this-guess eps &aux next-guess)
(loop
(setq next-guess (newton-improve f-and-df this-guess))
(when (close-enuf? this-guess next-guess eps)
(return-from newton-search-iter-2 (average this-guess next-guess)))
(setq this-guess next-guess)))
(defun testit ()
(time (dotimes (i 100000)
(newton-search-rec
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
(time (dotimes (i 100000)
(newton-search-iter-1
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
(time (dotimes (i 100000)
(newton-search-iter-2
#'(lambda (x)
(values (cos x) (- (sin x))))
1.0d0
1d-15)))
)
;;; USER(24): (user::testit)
;;; cpu time (non-gc) 4,426 msec user, 0 msec system
;;; cpu time (gc) 321 msec user, 0 msec system
;;; cpu time (total) 4,747 msec user, 0 msec system
;;; real time 4,747 msec
;;; space allocation:
;;; 39 cons cells, 0 symbols, 84,000,160 other bytes, 0 static bytes
;;; cpu time (non-gc) 4,416 msec user, 0 msec system
;;; cpu time (gc) 290 msec user, 0 msec system
;;; cpu time (total) 4,706 msec user, 0 msec system
;;; real time 4,707 msec
;;; space allocation:
;;; 36 cons cells, 0 symbols, 84,000,160 other bytes, 0 static bytes
;;; cpu time (non-gc) 4,477 msec user, 0 msec system
;;; cpu time (gc) 260 msec user, 0 msec system
;;; cpu time (total) 4,737 msec user, 0 msec system
;;; real time 4,737 msec
;;; space allocation:
;;; 54 cons cells, 0 symbols, 84,000,256 other bytes, 0 static bytes
Fred Gilham
Robert Posey <mu...@raytheon.com> writes:
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
The c-library's quicksort under FreeBSD uses one recursive call and
one iterative call replacing the second recursive call. The reason
given is to save stack space:
Relevant part of code from qsort.c:
if ((r = pb - pa) > es)
qsort(a, r / es, es, cmp);
if ((r = pd - pc) > es) {
/* Iterate rather than recurse to save stack space */
a = pn - r;
n = r / es;
goto loop;
}
/* qsort(pn - r, r / es, es, cmp);*/
}
Clearly a function call is more expensive than a goto. But if the
compiler can transform a function call into a goto, they become
identical.
So for the instances where recursion in the general sense is required
by the algorithm, the issue becomes whether the programmer can write a
recursion simulation (i.e. stuffing values by hand on a home-brew
stack) that is faster than the procedure-call mechanism.
BTW I've always felt that recursion is far easier to understand than
iteration for the non-initiated. Using the infamous factorial
example, I've always found the following code
unsigned
factorial(unsigned n)
{
if(n == 0)
return 1;
return n * factorial(n - 1);
}
to be easy to understand because it reflects the mathematical
specification of factorial, while
unsigned
factorial(unsigned n)
{
unsigned x = 1;
unsigned i;
if(n > 0)
for(i = 1; i <= n; i++)
x *= i;
return x;
}
introduces a bunch of extraneous stuff that must be understood
independently of the specification. For example, where does this `x'
come from? What's the `i' for? What does that weird `for' construct
mean?
--
Fred Gilham gil...@csl.sri.com
Is, then, the loving cup so often filled
that we may toss a draught aside?....
-Jeff Iverson
Tim Bradshaw
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
I'd love to see an iterative version of quicksort.
--tim
Marc Battyani
Tim Bradshaw <t...@cley.com> wrote in message
news:ey3ya8u...@cley.com...
Here is a good one in C.
Marc Battyani
*Warning Old C code!*
The small runs are sorted by insertion sort which is more efficient.
/* QSort() -- Quicksort function
**
** Usage: qsort(base, nbr_elements, width_bytes, compare_function);
** char *base;
** unsigned int nbr_elements, width_bytes;
** int (*compare_function)();
**
** Sorts an array starting at base, of length nbr_elements, each
** element of size width_bytes, ordered via compare_function; which
** is called as (*compare_function)(ptr_to_element1, ptr_to_element2)
** and returns < 0 if element1 < element2, 0 if element1 = element2,
** > 0 if element1 > element2. Most of the refinements are due to
** R. Sedgewick. See "Implementing Quicksort Programs", Comm. ACM,
** Oct. 1978, and Corrigendum, Comm. ACM, June 1979.
*/
#define SWAP(a,b) {memcpy(Buf, a, Width); memcpy(a, b, Width); memcpy(b,
Buf, Width); }
#define COMP(a,b) (*Compare)(a, b)
void QSort (pChar Base, Short NbObjects, Short Width, Bool (*Compare)(pVoid
a, pVoid b))
{
char Buf[250];
char *stack[40], **sp; /* stack and stack pointer */
char *i, *j, *limit; /* scan and limit pointers */
unsigned thresh; /* size of MaxSpan elements in */
/* bytes */
thresh = MaxSpan * Width; /* init threshold */
sp = stack; /* init stack pointer */
limit = Base + NbObjects * Width; /* pointer past end of array */
while (1) /* repeat until done then return */
{
while (limit - Base > thresh) /* if more than MaxSpan elements
*/
{
/*swap middle, Base*/
SWAP (((unsigned)(limit - Base) >> 1) -
((((unsigned)(limit - Base) >> 1)) % Width) + Base, Base);
i = Base + Width; /* i scans from left to right */
j = limit - Width; /* j scans from right to left */
if ( COMP(i, j)) /* Sedgewick's */
SWAP(i, j); /* three-element sort */
if ( COMP(Base, j)) /* sets things up */
SWAP(Base, j); /* so that */
if ( COMP(i, Base)) /* *i <= *Base <= *j */
SWAP(i, Base); /* *Base is the pivot element */
while (1)
{
do /* move i right until *i >= pivot */
i += Width;
while (COMP (Base, i));
do /* move j left until *j <= pivot */
j -= Width;
while (COMP (j, Base));
if (i > j) /* break loop if pointers crossed */
break;
SWAP (i, j); /* else swap elements, keep scanning */
}
SWAP (Base, j); /* move pivot into correct place */
if (j - Base > limit - i) /* if left subfile is larger... */
{
sp[0] = Base; /* stack left subfile Base */
sp[1] = j; /* and limit */
Base = i; /* sort the right subfile */
}
else /* else right subfile is larger */
{
sp[0] = i; /* stack right subfile Base */
sp[1] = limit; /* and limit */
limit = j; /* sort the left subfile */
}
sp += 2; /* increment stack pointer */
}
/* Insertion sort on remaining subfile. */
i = Base + Width;
while (i < limit)
{
j = i;
while (j > Base && COMP (j - Width, j))
{
SWAP (j - Width, j);
j -= Width;
}
i += Width;
}
if (sp > stack) /* if any entries on stack... */
{
sp -= 2; /* pop the Base and limit */
Base = sp[0];
limit = sp[1];
}
else /* else stack empty, all done */
break; /* Return. */
}
}
Christopher R. Barry
> * Robert Posey wrote:
>
> > At least in C, the performance of Quicksort can be improved quite a
> > bit(I hear) by Iteration.
>
> I'd love to see an iterative version of quicksort.
#include <stdlib.h>
/* swap two ints */
int sw(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
return 0;
}
/* iterative quicksort (average execution time: O(NlogN)) */
int qs(int *h, int N)
{
int n=0,m=1,k=0,p=0,q=N,r,w,b,z;
int *x=malloc(sizeof(int)*N),*y=malloc(sizeof(int)*N);
if(!x||!y)return 1;
while(m<N)n++,m*=2;
while(k||q-p>1)
if(q-p<2)p=x[--k],q=y[k];
else
{
z=h[((w=r=p)+(b=q))/2];
while(w-b)h[w]<z?sw(h+r++,h+w++):h[w]-z?sw(h+--b,h+w):w++;
r-p<=q-w?x[k]=w,y[k++]=q,q=r:(x[k]=p,y[k++]=r,p=w);
}
return 0;
}
Christopher
Robert Monfera
What's this recent trend to post Intercal code on c.l.l. :-)
Joe Marshall
news:38A1DB58...@fisec.com...
What's wrong with you? This is obviously much more readable than the
equivalent prefix notation:
;(define (quick-sort! vector predicate)
; (define (outer-loop l r)
; (if (> r l)
; (if (= r (+ l 1))
; (if (predicate (vector-ref vector r)
; (vector-ref vector l))
; (exchange! l r))
; (let ((lth-element (vector-ref vector l)))
;
; (define (increase-i i)
; (if (or (> i r)
; (predicate lth-element (vector-ref vector i)))
; i
; (increase-i (+ i 1))))
;
; (define (decrease-j j)
; (if (or (<= j l)
; (not (predicate lth-element (vector-ref vector
j))))
; j
; (decrease-j (- j 1))))
;
; (define (inner-loop i j)
; (if (< i j) ;used to be <=
; (begin
; (exchange! i j)
; (inner-loop (increase-i (+ i 1))
; (decrease-j (- j 1))))
; (begin
; (if (> j l)
; (exchange! j l))
; (outer-loop (+ j 1) r)
; (outer-loop l (- j 1)))))
;
; (inner-loop (increase-i (+ l 1))
; (decrease-j r))))))
;
; (define-integrable (exchange! i j)
; (let ((ith-element (vector-ref vector i)))
; (vector-set! vector i (vector-ref vector j))
; (vector-set! vector j ith-element)))
;
; (if (not (vector? vector))
; (error:wrong-type-argument vector "vector" 'QUICK-SORT!))
; (outer-loop 0 (- (vector-length vector) 1))
; vector)
Barry Margolin
>> bit(I hear) by Iteration.
>
>one iterative call replacing the second recursive call. The reason
>given is to save stack space:
Basically, they performed the tail-recursion elimination in the source
code, rather than depending on the compiler to do it (reasonable, since
most C compilers don't).
Tim Bradshaw
> Here is a good one in C.
Erm.
> char *stack[40], **sp; /* stack and stack pointer */
That looks really like a stack to me! If you want to obscure the
recursion you'd be better doing what Christopher Barry did and posting
something that looks like line noise and hoping no one will notice the
stack.
Either it's recursive or it ain't quicksort.
--tim
Barry Margolin
Marc Battyani <Marc_B...@csi.com> wrote:
>
>Tim Bradshaw <t...@cley.com> wrote in message
>news:ey3ya8u...@cley.com...
>> * Robert Posey wrote:
>>
>> > bit(I hear) by Iteration.
>>
>
> char *stack[40], **sp; /* stack and stack pointer */
If you've got a stack, you're recursive. You're not using the underlying
language's recursion features, you're simply reinventing it. After all,
how do you think recursion in C is implemented on the underlying hardware?
It translates it into instructions that manipulate a stack pointer register
and then perform a transfer, precisely analogous to your stack[] array.
Barry Margolin
Gareth McCaughan <Gareth.M...@pobox.com> wrote:
>Robert Posey wrote:
>
>> My Professor made the statement that LISP is one of the few languages where
>> of each function call relatively much less than in C etc.
>
>tend to put more effort into making function calls efficient,
>because typical Lisp programs use quite a lot of function
>calls; but, against that, some Lisp function calls have to
>be more expensive than C function calls have to be, because
>you can redefine functions in Lisp.
>
>That is, if I do
>
>(defun foo (x) (* x x))
>(defun bar (x) (+ (foo x) (foo x)))
>(defun foo (x) 0)
>
>To arrange this you have to do one of two things: (1) make
>the call to FOO do one more level of indirection than it would
>have to in a language like C, to look up the current meaning
>of FOO; or, (2) arrange that when the definition of FOO changes
>the code for BAR gets patched to refer to the new definition.
>
>So far as I know, no actual Lisp system takes option (2).
Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
Thomas A. Russ
> Tim Bradshaw <t...@cley.com> wrote in message
> >
> > I'd love to see an iterative version of quicksort.
>
> Here is a good one in C.
...
> char *stack[40], **sp; /* stack and stack pointer */
Actually, it's still a recursive algorithm. Instead of having the
recursion explicit and using the built-in C function calling stack it is
handled internally in the function, which maintains its own stack.
It can handle at most 20 recursive calls to quicksort (each recursive
call requires to stack entries). Of course that does let you sort a
fair-sized input array. (Assuming perfect binary splits around pivots
this could be as big as 2^20 elements.
--
Thomas A. Russ, USC/Information Sciences Institute t...@isi.edu
Pierre R. Mai
> >Here is a good one in C.
> ...
> > char *stack[40], **sp; /* stack and stack pointer */
>
> If you've got a stack, you're recursive. You're not using the underlying
> language's recursion features, you're simply reinventing it. After all,
> how do you think recursion in C is implemented on the underlying hardware?
> It translates it into instructions that manipulate a stack pointer register
> and then perform a transfer, precisely analogous to your stack[] array.
And sadly, it's not even precisely analogous to the stack array,
because the stack array uses a small, hard-coded, undocumented limit,
which is a really nice source of bugs, whereas the implementations
stack will usually have much wider, better documented limits, and much
better/clearer error handling...
Now one might argue that the home grown stack could be implemented
much more robustly, but IMHO that is missing the point: With the
implementation stack, I get this for free, whereas with my home-grown
stuff, I have to invest the time and effort, and still risk
introducing bugs or maintenance hassles.
Basically IMHO this boils down to the reason why we have higher level
languages and COTS implementations thereof: We want to leverage the
work of very knowledgable implementors implementing things once (and
improving them constantly), so that not everyone has to reinvent the
wheel badly all the time. So if you fell you need to simulate
recursion in your language/implementation for performance reasons --
unless you are operating under very special circumstances, like e.g. a
DSP, etc. -- then file a performance bug report instead, so that the
implementation can be enhanced, which will make the world a better
place for all.
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> PGP and GPG keys at your nearest Keyserver
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Tim Bradshaw
> Now one might argue that the home grown stack could be implemented
> much more robustly, but IMHO that is missing the point: With the
> implementation stack, I get this for free, whereas with my home-grown
> stuff, I have to invest the time and effort, and still risk
> introducing bugs or maintenance hassles.
I think this `iterative' qsort is nearly a canonical example of the C
mindset. The C mindset being `wherever the language or hardware might
offer me some safety at some cost in performance, however minute, I
will either fail to provide or bypass those features'. About the only
place that you get any decent bounds checking in typical C programs is
stack overflow, and here we have someone carefully bypassing that last
remaining scrap of protection in the name of saving a few extra
cycles.
I believe that this is a compelling argument against the `modern
processors are C-machines' claim that was made here recently.
C-machines would not have memory protection or virtual memory, since
both those features get you safety at the cost of Quake frame-rate,
and Quake frame-rate is *all* that the C mindset cares about.
Of course, the C mindset has some problems here, because it's
stressing on about function call time when the time of a reasonably
sized qsort is likely to be massively dominated by memory access to
the object being sorted on any recent machine. But the C mindset
doesn't know about caching issues, because they never really got much
further than the PDP11, and their algorithms books all talk about
machines with uniform memory access times. You have to have the
FORTRAN-mindset (several stages up the evolutionary ladder) to know
about caching...
--tim
Christopher Browne
>I am looking for the first evidence that a nontrivial recursive
>handle in a multi-tasking system where you either add level of
>way to debug recursion, I would be very happy to read about it. I
>work in an embedded environment I will admit, but I have never seen
>would debug optimized recursive code.
- How would you use anything other than recursion for algorithms that
manipulate trees?
- Or do you not use binary trees? Or quicksort? Or mergesort?
- Every RDBMS out there uses recursive code to manage B-trees of one
variation or another. I assume from your comments that you never
use database systems, as they *all* use recursive algorithms.
- If you don't make use of any recursive parsers, then I don't think
you can be writing code in any language other than FORTH, which
doesn't do the "recursive parsing" thing.
If you think that you don't make use of recursive code, then I am at a
loss to imagine what kind of computer systems you're using, as they
*all* have significant amounts of recursive code around if they're
using a language newer than FORTRAN-77.
--
"... the most important thing in the programming language is the name. A
language will not succeed without a good name. I have recently invented a
very good name and now I am looking for a suitable language.
-- D. E. Knuth, 1967
cbbr...@ntlug.org- <http://www.ntlug.org/~cbbrowne/lsf.html>
Gareth McCaughan
> BTW I've always felt that recursion is far easier to understand than
> iteration for the non-initiated. Using the infamous factorial
> example, I've always found the following code
>
> unsigned
> factorial(unsigned n)
> {
> if(n == 0)
> return 1;
>
> return n * factorial(n - 1);
> }
>
>
> to be easy to understand because it reflects the mathematical
> specification of factorial, while
>
> unsigned
> factorial(unsigned n)
> {
> unsigned x = 1;
> unsigned i;
>
> if(n > 0)
> for(i = 1; i <= n; i++)
> x *= i;
>
> return x;
> }
>
> introduces a bunch of extraneous stuff that must be understood
> independently of the specification. For example, where does this `x'
> come from? What's the `i' for? What does that weird `for' construct
> mean?
I don't think this is quite fair; C's |for| statement
is particularly obscure until one gets used to it.
Consider the following possibilities (not in any real
language):
define factorial(n):
product = 1
for i from 1 to n: product = product * i
return product
define factorial(n):
if n==0 then 1
else n * factorial(n-1)
define factorial(n):
product of i for i in [1..n]
It seems to me that the first is much clearer than
your iterative code (because it isn't full of C-isms);
the second is clearer than the first; and the clearest
of all is the last one, which is presumably iterative.
That's for a function one of whose most familiar
definitions is recursive. What about a program to
print the squares of the first 10 positive integers?
for n from 1 to 10:
print n*n
define print_in_range(first,last):
if first >= last: return
print first*first
print_in_range(first+1,last)
No contest, right?
Christopher Browne
>"Marc Battyani" <Marc_B...@csi.com> writes:
>
>> Tim Bradshaw <t...@cley.com> wrote in message
>> >
>> > I'd love to see an iterative version of quicksort.
>>
> ...
>> char *stack[40], **sp; /* stack and stack pointer */
>
>recursion explicit and using the built-in C function calling stack it is
>handled internally in the function, which maintains its own stack.
>
>It can handle at most 20 recursive calls to quicksort (each recursive
>call requires to stack entries). Of course that does let you sort a
>fair-sized input array. (Assuming perfect binary splits around pivots
>this could be as big as 2^20 elements.
... Or as few as 20 elements, if the array is already sorted, and the
pivots are *not* intelligently chosen. (Personally, I like the idea
of picking the pivot *at random.*)
--
16-inch Rotary Debugger: A highly effective tool for locating problems
in computer software. Available for delivery in most major
metropolitan areas. Anchovies contribute to poor coding style.
cbbr...@ntlug.org - - <http://www.ntlug.org/~cbbrowne/lsf.html>
Marc Battyani
> * Marc Battyani wrote:
>
> > Here is a good one in C.
>
>
> > char *stack[40], **sp; /* stack and stack pointer
*/
>
OK sorry.
Next time I will read my message before posting it...
Marc Battyani
Marco Antoniotti
Robert Posey <mu...@raytheon.com> writes:
> Tim Bradshaw wrote:
> >
> > * Robert Posey wrote:
> >
> > > I
> > > work in an embedded environment I will admit, but I have never seen
> > > recursive code released.
> >
> > Erm? Quicksort. Any of the multitude of n-ary tree algorithms.
>
> At least in C, the performance of Quicksort can be improved quite a
> bit(I hear) by Iteration.
Quicksort is an inherently recursive algorithm. You cannot eliminate
recursion. The best that you can do is to introduce stacks to
*simulate* recursion, hence introducing the "recursion counters" you
talked about in a previous post.
> If I had easy access to a system that
> I could do reasonable timing measurements on, I would attempt to prove it.
> I will admit, that Quicksort is even harder to understand than usual
> in Iterative form. I don't like it anyway, and would never use it
> unless I had to. Its timing varies too much, on a small change, and
> randomizing the input is a pain. Besides, in many cases Bucket sort
> is faster and much easier. Classic example sorting incoming integers of
> a know range is both much simpler and much faster using Bucket sort.
It is not *easier* it is theoretically better since you are not using
a comparison based sort algorithm.
> Quicksort is a good generic sort algorithm, but generic sort should
> only be used when it not a performance driver, or the data types are
> unknown in advance. In the Embedded world, both of these are
> unlikely.
This is true. So, you know you have incoming integers (with
associated data, of course) in the 0-100 range and you have to sort
them. *Theory* tells you that you are better off using a
counting/radix/bucket sort (as per CLR terminology). This is
completely independent of the system being built and of the language
used.
#+with-personal-gripe
From experience, I'd say that the embedded world sometimes goes over
the board in making its life miserable :) by quibbling over
performance and loosing money on larger issues, such as
maintainability. :)
Marco Antoniotti
cba...@2xtreme.net (Christopher R. Barry) writes:
> Tim Bradshaw <t...@cley.com> writes:
>
> > * Robert Posey wrote:
> >
> > > At least in C, the performance of Quicksort can be improved quite a
> > > bit(I hear) by Iteration.
> >
> > I'd love to see an iterative version of quicksort.
>
>
> #include <stdlib.h>
>
> /* swap two ints */
> int sw(int *x, int *y)
> {
> int temp = *x;
> *x = *y;
> *y = temp;
> return 0;
> }
>
> /* iterative quicksort (average execution time: O(NlogN)) */
> int qs(int *h, int N)
> {
> int n=0,m=1,k=0,p=0,q=N,r,w,b,z;
> int *x=malloc(sizeof(int)*N),*y=malloc(sizeof(int)*N);
> if(!x||!y)return 1;
> while(m<N)n++,m*=2;
> while(k||q-p>1)
> if(q-p<2)p=x[--k],q=y[k];
> else
> {
> z=h[((w=r=p)+(b=q))/2];
> while(w-b)h[w]<z?sw(h+r++,h+w++):h[w]-z?sw(h+--b,h+w):w++;
> r-p<=q-w?x[k]=w,y[k++]=q,q=r:(x[k]=p,y[k++]=r,p=w);
> }
> return 0;
> }
>
Why all those newlines in the code? :)
Marco Antoniotti
Gareth McCaughan <Gareth.M...@pobox.com> writes:
(defun factorial (n)
(reduce #'* (iota n :start 1)))
Fernando D. Mato Mira
> and Quake frame-rate is *all* that the C mindset cares about.
And the worst is that most people think that if "Quake frame rate on
El-Cheapo 3D board"
is higher than "Quake frame rate on SGI" the offering from Mountain View
does not make any sense
from a strictly gfx perspective.
--
Fernando D. Mato Mira
Real-Time SW Eng & Networking
Advanced Systems Engineering Division
CSEM
Jaquet-Droz 1 email: matomira AT acm DOT org
CH-2007 Neuchatel tel: +41 (32) 720-5157
Switzerland FAX: +41 (32) 720-5720
www.csem.ch www.vrai.com ligwww.epfl.ch/matomira.html
Robert Posey
Christopher Browne wrote:
>
> If you think that you don't make use of recursive code, then I am at a
> loss to imagine what kind of computer systems you're using, as they
> *all* have significant amounts of recursive code around if they're
> using a language newer than FORTRAN-77.
Of course my windows, linux, unix machines use recursion, but I don't write
deliverable code for those machines. On the embedded systems, I have
never seen recursion.
Muddy
Joe Marshall
>
> I believe that this is a compelling argument against the `modern
> processors are C-machines' claim that was made here recently.
> C-machines would not have memory protection or virtual memory, since
> both those features get you safety at the cost of Quake frame-rate,
>
Hey, I think I made that claim.
In Jonathan Rees's paper:
Jonathan A. Rees.
A Security Kernel Based on the Lambda-Calculus.
Ph.D. dissertation, MIT, 1995.
Reprinted in part as MIT AI Memo 1564, March 1996.
http://mumble.net/jar/pubs/secureos/
Rees claims:
`There are several approaches to eliminating the risks associated
with machine programs:
[among which is] Limitation: switch into a limited hardware-provided
"user mode" when invoking the machine program.
Limitation may be the only option if one has little influence over the
compiler and program being compiled. For example, most C programs
use pointers in ways that are difficult to guarantee safe by
verification
or sandboxing, and few C compilers generate object code that checks
validity of pointers.'
Lisp Machines ran all their processes in a single address space. Since
it was unusual to make bogus tagged objects on a Lisp machine, and since
the underlying microcode enforced safety, there was no need for `memory
protection'
in the traditional sense.
But running multiple C programs in the same address space without memory
protection is not particularly robust (see Windows 95/98).
That's my story and I'm sticking to it.
Robert Munyer
Gareth McCaughan <Gareth.M...@pobox.com> wrote:
> What about a program to print the squares
> of the first 10 positive integers?
>
> for n from 1 to 10:
> print n*n
>
> define print_in_range(first,last):
> if first >= last: return
> print first*first
> print_in_range(first+1,last)
>
> No contest, right?
I think that by using "for" instead of a simpler looping construct,
you've applied to the iterative version a level of syntactic sugar
that you haven't applied to the recursive one. Also, the use of
an explicit "return" to break out of the function is not necessary
in structured languages. I'd rephrase your comparison like this:
define print_in_range(first,last):
n := first
while n < last:
print n * n
n := n + 1
define print_in_range(first,last):
if first < last:
print first*first
print_in_range(first+1,last)
-- Robert Munyer <mun...@mcs.com>
Gareth McCaughan
> I think this `iterative' qsort is nearly a canonical example of the C
> mindset. The C mindset being `wherever the language or hardware might
> offer me some safety at some cost in performance, however minute, I
> will either fail to provide or bypass those features'. About the only
> place that you get any decent bounds checking in typical C programs is
> stack overflow, and here we have someone carefully bypassing that last
> remaining scrap of protection in the name of saving a few extra
> cycles.
In the present instance, this isn't fair. Provided your
array can't be more than 2^40 elements in size (which is
probably a pretty safe guess) the posted quicksort routine
will never overflow its hard-coded stack, because it
always stacks the smaller subarray and iterates on the
larger.
This is not to disagree with the point you're making,
of course.
Gareth McCaughan
[I said:]
>> What about a program to print the squares
>> of the first 10 positive integers?
>>
>> for n from 1 to 10:
>> print n*n
>>
>> define print_in_range(first,last):
>> if first >= last: return
>> print first*first
>> print_in_range(first+1,last)
>>
>> No contest, right?
>
> I think that by using "for" instead of a simpler looping construct,
> you've applied to the iterative version a level of syntactic sugar
> that you haven't applied to the recursive one.
Quite true. I don't know of any comparable sugar that
can easily be applied to the recursive version. One of
the advantages of iteration is that we have good notations
for some particularly common looping constructs; and one
of the disadvantages of recursion is that it's a fairly
low-level construction: very powerful but sometimes hard
to follow. (Compare, though this isn't very fair, Scheme's
CALL-WITH-CURRENT-CONTINUATION versus the weaker but
more approachable THROW/CATCH.)
Of course, you can layer syntactic sugar on top of
recursion. You could, for instance, give a definition
of that "for i from 1 to 10" construct in terms of
recursion. But it seems to me that this amounts to
disguising recursion as iteration. There's nothing
wrong with that, but it's evidence that for some
purposes iteration is easier to understand than
recursion.
> Also, the use of
> an explicit "return" to break out of the function is not necessary
> in structured languages.
I know it's not necessary. I think it's often clearer,
though if you prefer the other version
> define print_in_range(first,last):
> if first < last:
> print first*first
> print_in_range(first+1,last)
then I have no quarrel with that. On reflection, I think
I too prefer it here.
Gareth McCaughan
[I said:]
>> To arrange this you have to do one of two things: (1) make
>> the call to FOO do one more level of indirection than it would
>> have to in a language like C, to look up the current meaning
>> of FOO; or, (2) arrange that when the definition of FOO changes
>> the code for BAR gets patched to refer to the new definition.
>>
>> So far as I know, no actual Lisp system takes option (2).
>
> Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
Excellent! I stand corrected.
Christopher Browne
say:
>recursion. You could, for instance, give a definition
>of that "for i from 1 to 10" construct in terms of
>recursion. But it seems to me that this amounts to
>disguising recursion as iteration. There's nothing
>wrong with that, but it's evidence that for some
>purposes iteration is easier to understand than
>recursion.
This seems to me to be the error that some introductory courses on
Lisp/Scheme make; they too often inflict on students the notion that
recursion is the *only* tool available for use.
*Can* you express everything using recursion? Surely.
- There are many things that recursion is useful to express.
- It can be *convenient* to transform iteration into recursion, when
there is some express purpose to this.
- But to force everything into a recursive mould can be as restrictive
as an attempt to force everything into an iterative mould.
For instance, the sum:
\[ S = \sum_{i=1}^{n}{ V_i } \]
would tend to be considered an iterative expression.
--> If you're trying to prove something about the properties of the
expression, it is common to use proof by induction, which is
inherently recursive.
--> If you're trying to *perform* the addition of the expression, it
may be natural to use a recursive recurrence, where
\[ S_{k+1} = S_k + V_i \]
--> If all you want to do is to baldly *describe* the expression, it
is more natural to merely indicate the iteration. Particularly if
you've got a macro expander that will turn this into recursion
behind the scenes.
--
As Will Rogers would have said, "There is no such thing as a free
variable." -- Alan Perlis
cbbr...@ntlug.org - - <http://www.hex.net/~cbbrowne/lisp.html>
Rainer Joswig
<Gareth.M...@pobox.com> wrote:
> Barry Margolin wrote:
>
> [I said:]
> >> To arrange this you have to do one of two things: (1) make
> >> the call to FOO do one more level of indirection than it would
> >> have to in a language like C, to look up the current meaning
> >> of FOO; or, (2) arrange that when the definition of FOO changes
> >> the code for BAR gets patched to refer to the new definition.
> >>
> >> So far as I know, no actual Lisp system takes option (2).
> >
> > Maclisp was doing option (2) 20 years ago, on both Multics and PDP-10's.
>
> Excellent! I stand corrected.
On the Lisp machine you can remove the indirection.
Rainer Joswig, ISION Internet AG, Harburger Schlossstraße 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: rainer...@ision.de , WWW: http://www.ision.de/
Gareth McCaughan
[I wrote:]
> In the present instance, this isn't fair. Provided your
> array can't be more than 2^40 elements in size (which is
> probably a pretty safe guess) the posted quicksort routine
> will never overflow its hard-coded stack, because it
> always stacks the smaller subarray and iterates on the
> larger.
Oops. I didn't read the code carefully enough. The limit
is actually 2^20. That's bad.
Frank A. Adrian
Ya know? After all of this discussion of how much recursion costs, I was
reflecting on Perlis' statement that "Lisp users know the value of
everyting, but the cost of nothing".
Yes, recursion can cost more than iteration. But it often has more value to
understanding and maintainability than its cost in memory or speed. As long
as the cost of using a recursive algorithm is less than the cost of using an
iterative one, it doesn't matter how much it costs from a baseline basis.
This is a common business fallacy, as well. People will say let's not do X
because it costs too much, but they often don't consider what it will cost
not to do X.
Finally, the cost one is willing to pay for something is usually tied up in
its percieved value. Until one states what their valuation function is
(i.e., are maintainability and extensibility out of the picture entirely, is
this in the inner loop of an FFT or just in the outer loop of some little
used event handling code, etc.), it is unlikely that any agreement can ever
be reached.
All-in-all, I think that this is more a warning against making blanket
statements like "recursion is more expensive than iteration" than anything
else.
faa
Tim Bradshaw
> --> If you're trying to prove something about the properties of the
> expression, it is common to use proof by induction, which is
> inherently recursive.
> --> If you're trying to *perform* the addition of the expression, it
> may be natural to use a recursive recurrence, where
> \[ S_{k+1} = S_k + V_i \]
Although I actually agree with your post, I think that one could
disagree with this pair of statements. If you want it to be
relatively easy to prove (formally or informally) that your program is
doing what you think, it may be better to implement the expression
about which you reasoned, rather than another expression which (you
think) is equivalent but is somehow `cheaper'. In particular you
might want to rely on a mechanical process (a compiler...) to convert
one to the other.
I think this argument doesn't only apply to the `we implement all our
programs in first-order-typed-fashionable-theory-of-the-week thus
ensuring complete formal-correctness and also that we never ship
anything' brigade, but also is relevant to the more human `we happily
use delta functions and assume everything is suitably differentiable'
people.
--tim
Joe Marshall
equivalent T`s `iterate' syntax.
While I happen to like that construct, and I happen to be very
`pro-tail-recursive', I don't see a compelling argument here that
would persuade an `iteration is not recursion' person to change
their mind.
Tim Bradshaw
> For me, a loop written with ITERATE is easier to read than the same
> loop written with DO. With ITERATE, the process of computation
> has a more linear "flow" through the text of the function. With
> DO, the step forms are interleaved with the initialization forms,
> which makes the flow of computation feel like it's been "scattered"
> all over the text of the function.
> But it's not just a matter of "look and feel;" there's also a
> difference in flexibility. ITERATE is more flexible than DO, and
> LABELS is more flexible than either. DO imposes a level of structure
> that doesn't always "fit" what you're trying to do. For example,
> sometimes the initialization form and the step form are the same
> piece of code. Earlier in this thread someone got around this by
> using a cute trick with #1#, but personally I'd rather get around
> it by just using ITERATE or LABELS; either one of them handles this
> situation beautifully, with no duplication of code.
The problem I have with ITERATE (and LABELS &co) used for looping is
that they are almost just using GOTO -- you can not only start the
next loop iteration at any point within it, but you can genuinely
recurse as well by using the same invocation as you would to simply
loop. I find it much easier to write entirely unreadable code using
ITERATE than I do even using LOOP. That's why I stopped using an
ITERATE macro when I really wanted to have a loop.
--tim
Erik Naggum
| For me, a loop written with ITERATE is easier to read than the same loop
| written with DO. With ITERATE, the process of computation has a more
| linear "flow" through the text of the function. With DO, the step forms
| are interleaved with the initialization forms, which makes the flow of
| computation feel like it's been "scattered" all over the text of the
| function.
what's keeping you from writing an ITERATE macro that expands into DO
(or, rather, TAGBODY and GO forms)? it should be eminently doable in the
majority of cases where it is indeed only (tail-recursive) iteration.
| In summary: the next time you're programming a loop, and the code doesn't
| seem to "fit," try using recursion. You might be surprised how well it
| works.
there is no semantic difference between (PSETQ FOO X BAR Z) (GO TAG) and
(ITERATOR :FOO X :BAR Z) as long as both "resolve" to tail recursion.
(I'm using keyword arguments only to be explicit.)
| In fact, I think the whole concept of "iteration vs. recursion" is a
| wrong way to think, a left-over distinction from the days before we
| understood tail recursion. I think it makes sense to think of a
| tail-recursive program as being both iterative AND recursive.
I agree with you on this.
| Now, on to the example I promised earlier. Below is a function I wrote a
| couple of years ago. As I recall, I tried several times to write it with
| DO, and every time the code came out UGLY. So I tried doing it with
| recursion, and it "just worked." It was easier to write, and easier to
| read, and just as efficient as the version I wrote with DO.
|
| ; Returns INV such that (= (MOD (* NUMBER INV) MODULUS) (GCD NUMBER MODULUS)).
| ; Note that if NUMBER and MODULUS are relatively prime, the GCD is 1, and INV
| ; is the multiplicative inverse of NUMBER over the Galois field of MODULUS.
|
| (defun mod-inverse (number modulus)
| (check-type number (integer 1))
| (check-type modulus (integer 1))
| (iterate iter ((a modulus) (b number) (c 0) (d 1))
| (multiple-value-bind (q r) (floor a b)
| (cond ((plusp r) (iter b r d (- c (* q d)))) ; thanks Euclid!
| ((minusp d) (+ d modulus))
| (t d)))))
(do ((a modulus) (b number) (c 0) (d 1))
((multiple-value-bind (q r) (floor a b)
(if (plusp r) (psetq a b b r c d d (- c (* q d))) t))
(if (minusp d) (+ d modulus) d)))
it _is_ unfortunate that DO et al were invented so long before multiple
values that we sometimes have to expand out the forms manually.
hope this helps.
#:Erik
Tim Bradshaw
> what's keeping you from writing an ITERATE macro that expands into DO
> (or, rather, TAGBODY and GO forms)? it should be eminently doable in the
> majority of cases where it is indeed only (tail-recursive)
> iteration.
I have such a macro. However it's dangerous because it also just
loops in the case where there is actual non-tail recursion going on so
things break in obscure ways. In order to avoid that you basically
have to do the tail-call analysis that a compiler does, which is kind
of a lot of work.
The whole problem is that ITERATE & macros like it confuse several things
-- general recursive call, looping and random GOTO, which is both why they
can lead to nightmarishly tangled code if abused and why they are hard
to implement.
--tim
Robert Munyer
> Both of the following two functions are recursive, but only one
> of them progressively consumes stack space:
Whoops! It's been so long since I used a Lisp without smart tail
recursion, I completely forgot that it's an optional feature.
Is there any CL in common use that can't run a function like the
one below without progressively consuming stack space?
(defun reverse-list (l)
(labels ((iter (in out)
(cond ((endp in) out)
(t (iter (rest in) (cons (first in) out))))))
(iter l nil)))
-- Robert Munyer <mun...@mcs.com>
F. Xavier Noria
wrote:
: ; Returns INV such that (= (MOD (* NUMBER INV) MODULUS) (GCD NUMBER MODULUS)).
: ; Note that if NUMBER and MODULUS are relatively prime, the GCD is 1, and INV
: ; is the multiplicative inverse of NUMBER over the Galois field of MODULUS.
:
: (defun mod-inverse (number modulus)
: (check-type number (integer 1))
: (check-type modulus (integer 1))
: (iterate iter ((a modulus) (b number) (c 0) (d 1))
: (multiple-value-bind (q r) (floor a b)
: (cond ((plusp r) (iter b r d (- c (* q d)))) ; thanks Euclid!
: ((minusp d) (+ d modulus))
: (t d)))))
:
: I'd be interested in hearing how other people would implement this
: function. Maybe there's an equally good way to do it without
: recursion, and I just couldn't think of it. I don't have much
: practice with non-recursive looping, because I always just switch
: to recursion whenever the logic doesn't seem to want to "fit" into
: the structure of a simple DO loop. Suggestions, anyone?
As far as I have read, the standard way to compute this is using
an algorithm to compute Bezout's identity. I have implemented a
no so short but fast one that comes in [1st] Henri Cohen's book on
Computational Algebraic Number Theory (please, excuse I have
not added comments practically.)
Since the book describes the algorithms `a la' TAGBODY I use it
when it is not worth avoiding it.
Regards,
-- Xavier
P.S.: I write this to practice Lisp. Since I am learning the
language by myself, the function may have newbie-code somewhere.
Any comments pointing it out would be very welcome.
;;;
;;; Algorithm 1.3.8 (Binary Extended). Given non-negative integers a
;;; and b, this algorithm determines (u, v, d) such that au + bv = d
;;; and d = (a, b). We use auxiliary variables v1, v3, t1, t3 and two
;;; Boolean flags f1 and f2.
;;;
(defun bezout (a b)
;; 1. Reduce size once
(let ((f1 nil))
(when (< a b)
(rotatef a b)
(setq f1 t))
(when (zerop b)
(if f1
(return-from bezout (values 0 1 a))
(return-from bezout (values 1 0 a))))
(multiple-value-bind (q r) (floor a b)
(setq a b b r)
;; 2. Compute power of 2
(when (zerop b)
(if f1
(return-from bezout (values 1 0 a))
(return-from bezout (values 0 1 a))))
(let ((k 0))
(loop while (and (evenp a) (evenp b)) do
(incf k)
(setq a (ash a -1) b (ash b -1)))
;; 3. Initialize
(let ((f2 nil))
(when (evenp b)
(rotatef a b)
(setq f2 t))
(let ((u 1) (d a) (v1 b) (v3 b) t1 t3 v)
(tagbody
(when (oddp a)
(setq t1 0 t3 (- b))
(go step-5))
(setq t1 (ash (+ 1 b) -1) t3 (ash a -1))
;; 4. Remove powers of 2
step-4
(loop while (evenp t3) do
(setq t3 (ash t3 -1))
(if (evenp t1)
(setq t1 (ash t1 -1))
(setq t1 (ash (+ t1 b) -1))))
;; 5. Loop
step-5
(if (plusp t3)
(setq u t1 d t3)
(setq v1 (- b t1) v3 (- t3)))
;; 6. Subtract
(setq t1 (- u v1) t3 (- d v3))
(when (minusp t1)
(incf t1 b))
(unless (zerop t3)
(go step-4)))
;; 7. Terminate
(setq v (/ (- d (* a u)) b) d (ash d k))
(when f2
(rotatef u v))
(decf u (* v q))
(if f1
(values u v d)
(values v u d))))))))
Steve Long
repeat operations. When I needed to write
serious applications in Lisp, ones that required tens- to
hundreds-of-thousands of steps,
I achieved improved performance economy (time and memory) and avoided
stack overflow by reimplementing
the iterative constructs as tail-recursive constructs. This is not to
say that this is always the
best answer, but did solve the problem in these situations.
sl
Christopher Browne
>* Christopher Browne wrote:
>
>> --> If you're trying to prove something about the properties of the
>> expression, it is common to use proof by induction, which is
>> inherently recursive.
>
>> --> If you're trying to *perform* the addition of the expression, it
>> may be natural to use a recursive recurrence, where
>> \[ S_{k+1} = S_k + V_i \]
>
>Although I actually agree with your post, I think that one could
>disagree with this pair of statements. If you want it to be
>relatively easy to prove (formally or informally) that your program is
>doing what you think, it may be better to implement the expression
>about which you reasoned, rather than another expression which (you
>think) is equivalent but is somehow `cheaper'. In particular you
>might want to rely on a mechanical process (a compiler...) to convert
>one to the other.
I think what we've got here is "violent agreement" masquerading as
disagreement :-).
The point of the first statement was to suggest a context other than
Lisp in which recursion is considered natural as a means of
expression. Proof by induction is inherently recursive, and quite
common.
The point of the second statement was to indicate that recursion may
represent a natural implementation scheme for dealing with iterative
processes. But a critical point here is that it is entirely sensible
for the recursion to take place as an off-stage actor.
For instance, the way that
(loop for i from 1 to 100
for y = (* i i)
sum y))
expands (e.g. - via macroexpand-1) into something that looks Rather
Different.
My reasoning on the second statement was exactly this notion of
expanding/rewriting the code (and I'll not show the macroexpand-1
results of the (loop) as that would be a fairly pointless exercise) so
that we start by *describing* the expression in some natural way that
may have nothing to do with recursion, and the computer does whatever
it will to transform this usefully.
>I think this argument doesn't only apply to the `we implement all our
>programs in first-order-typed-fashionable-theory-of-the-week thus
>ensuring complete formal-correctness and also that we never ship
>anything' brigade, but also is relevant to the more human `we happily
>use delta functions and assume everything is suitably differentiable'
>people.
Any time I start thinking that theory is pointless, someone who knows
*no* theory comes along and writes a program that performs *HORRIBLY*
due to their lack of understanding which nicely smacks this theory
upside the head...
--
PASCAL is not a language. It was an experiment combining the
flexibilty of C with that of a drug-crazed penguin. It is also the
'language' of choice of many CS professors who aren't up to handling
REAL programming. Hence, it is not a language.
cbbr...@ntlug.org- <http://www.hex.net/~cbbrowne/lisp.html>
Robert Munyer
F. Xavier Noria <f...@retemail.es> wrote:
> As far as I have read, the standard way to compute this is using
> an algorithm to compute Bezout's identity. I have implemented a
> no so short but fast one that comes in [1st] Henri Cohen's book
> on Computational Algebraic Number Theory
I haven't taken the time to understand your code; maybe I'll do it
later if I can find Cohen's book at the library. But I did test
the speed of your code (with random 300-digit numbers) and the
result may surprise you: my six-line recursive version ran almost
three times faster than the 58-line version you posted.
-- Robert Munyer <mun...@mcs.com>
Robert Munyer
Erik Naggum <er...@naggum.no> wrote:
> what's keeping you from writing an ITERATE macro that expands
> into DO (or, rather, TAGBODY and GO forms)?
Nothing. All of the iterative constructs we've been discussing
can be expanded into TAGBODY and GO. It's just a little more
difficult with ITERATE, because the step forms can be buried at
any level, anywhere inside the user-supplied body of the loop.
> it should be eminently doable in the majority of cases where it
> is indeed only (tail-recursive) iteration.
Right. In fact, I just wrote a macro that converts an ITERATE into
a TAGBODY, and I think it works correctly in every case that meets
the criterion you just mentioned. I would appreciate it if everyone
could take a look at my code, and let me know if you can think of
any case where it doesn't work -- or of any way to make it better
(i. e. more correct, or efficient, or elegant, etc.).
; the reference implementation, which I'm trying to emulate
(defmacro iterate (name bindings &body body)
`(labels ((,name ,(mapcar #'first bindings)
,@body))
(,name ,@(mapcar #'second bindings))))
; the implementation that expands into a tagbody
(defmacro iterate (name bindings &body body)
(let ((decl-count (position 'declare body :key #'first :test #'neq))
(tag-name (gensym))
(arg-names (mapcar #'first bindings))
(temp-names (mapcar #'(lambda (b)
(declare (ignore b))
(gensym))
bindings)))
`(block ,name
(let ,bindings
,@(subseq body 0 decl-count)
(tagbody ,tag-name
(return-from ,name
(flet ((,name ,temp-names
(setq ,@(mapcan #'list arg-names temp-names))
(go ,tag-name)))
(declare (inline ,name))
,@(nthcdr decl-count body))))))))
-- Robert Munyer <mun...@mcs.com>
Barry Margolin
Robert Munyer <mun...@mcs.com> wrote:
>Right. In fact, I just wrote a macro that converts an ITERATE into
>a TAGBODY, and I think it works correctly in every case that meets
>the criterion you just mentioned. I would appreciate it if everyone
>could take a look at my code, and let me know if you can think of
>any case where it doesn't work -- or of any way to make it better
>(i. e. more correct, or efficient, or elegant, etc.).
I'm not sure it's right. As another poster said, you need to do a code
walk to determine whether a recursive call is a tail call. Your macro
turns *all* recursive calls into GOs.
A simple test case would be a non-tail-recursive factorial:
(iterate fact (n)
(if (< n 2) 1
(* n (fact (1- n)))))
BTW, when posting code for review like this, I would leave out the part
that deals with declarations, to keep it simple and to the point of the
discussion.
--
Barry Margolin, bar...@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.
Robert Munyer
> > > it should be eminently doable in the majority of cases where
> > > it is indeed only (tail-recursive) iteration.
Robert Munyer <mun...@mcs.com> wrote:
> > Right. In fact, I just wrote a macro that converts an ITERATE
> > into a TAGBODY, and I think it works correctly in every case
> > that meets the criterion you just mentioned.
Barry Margolin <bar...@bbnplanet.com> wrote:
> I'm not sure it's right. As another poster said, you need to do
> a code walk to determine whether a recursive call is a tail call.
> Your macro turns *all* recursive calls into GOs.
Yes, that's what I meant when I said "every case that meets the
criterion [Erik] just mentioned." The idea is that this macro
should only be used when the code is tail-recursive. I think it
would be very bad programming style to use a macro named ITERATE
for a non-tail-recursive function, like your test case below.
> A simple test case would be a non-tail-recursive factorial:
>
> (iterate fact (n)
> (if (< n 2) 1
> (* n (fact (1- n)))))
>
> BTW, when posting code for review like this, I would leave out
> the part that deals with declarations, to keep it simple and to
> the point of the discussion.
Thanks, that's good advice. But in this case I included the
declaration handling because I was hoping for expert advice about
it. I'm not quite 100% sure that my code catches ALL declarations,
or that they ALL belong at the exact spot where I put them.
-- Robert Munyer <mun...@mcs.com>
Christopher Browne
>Tim Bradshaw wrote:
>> * Robert Posey wrote:
>> > I
>> > work in an embedded environment I will admit, but I have never seen
>> > recursive code released.
>>
>> Erm? Quicksort. Any of the multitude of n-ary tree algorithms.
>
>At least in C, the performance of Quicksort can be improved quite a
>bit(I hear) by Iteration. If I had easy access to a system that
>I could do reasonable timing measurements on, I would attempt to prove it.
>I will admit, that Quicksort is even harder to understand than usual
>in Iterative form. I don't like it anyway, and would never use it
>unless I had to. Its timing varies too much, on a small change, and
>randomizing the input is a pain. Besides, in many cases Bucket sort
>is faster and much easier. Classic example sorting incoming integers of
>a know range is both much simpler and much faster using Bucket sort.
>Quicksort is a good generic sort algorithm, but generic sort should
>only be used when it not a performance driver, or the data types are
>unknown in advance. In the Embedded world, both of these are unlikely.
The only way of doing Quicksort in a non-iterative way is to
*convince* yourself that by explicitly managing the stack, and
obfuscating the code, that you've made it non-iterative. And you'd be
fooling yourself, as recursion really just amounts to pushing a
location onto a stack, deferring some portion of processing 'til
later.
The "iterative" thing that *can* be done to Quicksort is to use
Quicksort only for lists of items of [size x] or greater. That way,
Quicksort gets things into *generally* the right order. You then use
something like insertion sort on the whole list, and that will provide
decent performance.
But you're still evading the issue that *any* tree-based data
structure will need to be processed using a recursive algorithm.
--
"Though the Chinese should adore APL, it's FORTRAN they put their
money on." -- Alan Perlis
cbbr...@hex.net- <http://www.ntlug.org/~cbbrowne/lsf.html>
Robert Munyer
Tim Bradshaw <t...@cley.com> wrote:
> * Robert Munyer wrote:
> > this macro should only be used when the code is tail-recursive.
> > I think it would be very bad programming style to use a macro
> > named ITERATE for a non-tail-recursive function, like your test
> > case below.
>
> And this is why a macro like that should never, ever be used.
> Some tiny and non-obvious editing change can change a TR call to
> a non-TR one, causing the whole thing to blow up in your face
> with basically no possibility of the compiler or macro warning
> you or anything. The only even slightly safe way to do ITERATE
> is the obvious macro in terms of LABELS.
I'm surprised to hear that you had that problem. I don't think I
have EVER made a "tiny and non-obvious editing change" that would
cause the TAGBODY code to fail, but wouldn't also cause the LABELS
code to fail.
Maybe that's just because I did a lot of T programming before Common
Lisp was invented. Once you get used to it, keeping track of tail
recursion becomes just as automatic and unconscious as keeping
track of parentheses.
As I see it, the real problem with the TAGBODY version is that its
behavior can be "surprising" when the user's code is defective.
I agree with you that this means it's not really a top-quality
development tool suitable for everyday use.
Nevertheless, I will keep it in my arsenal, in case I ever need to
deal with a CL implementation that's not smart enough to run the
LABELS version efficiently. Presumably I would not do serious
development on such a CL; I would simply port to it, and continue
using a more sophisticated CL as the main development platform.
Also, I think I'm going to start using the LABELS version of ITERATE,
instead of using LABELS directly, for functions like MOD-INVERSE
(in the article six levels above this one). ITERATE has the
advantage of directly expressing the programmer's intent that the
recursion is meant to be tail-recursive; with LABELS, you have to
actually walk the code (mentally or mechanically) to notice that
it's tail recursion.
-- Robert Munyer <mun...@mcs.com>
Robert Monfera
Robert Munyer wrote:
> TB: Of course I'm not trying to claim that *you* shouldn't use this
> TB: macro (or not seriously).
>
> What, you mean you're not going to help turn this thread into a
> religious war?
Let me help doing that by recalling what someone quoted a few days ago:
we mostly write programs for other (potentially not as
tail-recursion-conscious) programmers, not for the compiler. Maybe Tim
did want at least a battle, that's why he emphasized *you* :-o
Robert
Dorai Sitaram
Barry Margolin <bar...@bbnplanet.com> wrote:
>If a macro like ITERATE became popular, I would recommend that a naming
>convention be adopted for the tail-only functions that it defines. Just as
>we use * around special variable names so that we can tell that they'll act
>differently in LET, something special around these "function" names would
>warn you that calls to them act weirdly.
>
>Actually, perhaps a better way to do this is not with something that looks
>like a function. Instead of doing (<name> . <parameters>), how about
>(restart <name> . <parameters>). This way, RESTART is the only special
>name you have to remember. Basically, RESTART would be to ITERATE as GO is
>to TAGBODY.
Unless you can force RESTART to occur in tail
positions only -- ie, flag error reliably when
the programmer strays --, what does this solve?
I rather like your first suggestion of choosing loopy
names when we intend to iterate (if only because I've
already been using it as a heuristic in my
scm2cl translator for converting Scheme's named-LETs
into either LOOPs or LABELSes). At least, it is a
pure naming convention and doesn't overstate its
effect as an explicitly syntactic convention is liable
to.
--d
Barry Margolin
Dorai Sitaram <ds...@goldshoe.gte.com> wrote:
>In article <Mggr4.50$pO2.2954@burlma1-snr2>,
>Barry Margolin <bar...@bbnplanet.com> wrote:
>>If a macro like ITERATE became popular, I would recommend that a naming
>>convention be adopted for the tail-only functions that it defines. Just as
>>we use * around special variable names so that we can tell that they'll act
>>differently in LET, something special around these "function" names would
>>warn you that calls to them act weirdly.
>>
>>Actually, perhaps a better way to do this is not with something that looks
>>like a function. Instead of doing (<name> . <parameters>), how about
>>(restart <name> . <parameters>). This way, RESTART is the only special
>>name you have to remember. Basically, RESTART would be to ITERATE as GO is
>>to TAGBODY.
>
>Unless you can force RESTART to occur in tail
>positions only -- ie, flag error reliably when
>the programmer strays --, what does this solve?
It makes it more obvious that this is not a normal function, so you may be
less likely to use it inappropriately. It doesn't change the
implementation at all, it's just a flag to the programmer, much like the
naming scheme.
>I rather like your first suggestion of choosing loopy
>names when we intend to iterate (if only because I've
>already been using it as a heuristic in my
>scm2cl translator for converting Scheme's named-LETs
>into either LOOPs or LABELSes). At least, it is a
>pure naming convention and doesn't overstate its
>effect as an explicitly syntactic convention is liable
>to.
However, naming conventions can be violated easily, but this use of RESTART
would be required. So future maintainers of the program would not have to
know *your* naming convention.
--
BARRY MARGOLIN, bar...@bbnplanet.com
Robert Munyer
Barry Margolin <bar...@bbnplanet.com> wrote:
> Actually, perhaps a better way to do this is not with something
> that looks like a function. Instead of doing (<name> . <parameters>),
> how about (restart <name> . <parameters>). This way, RESTART is
> the only special name you have to remember. Basically, RESTART
> would be to ITERATE as GO is to TAGBODY.
This is an interesting idea! The word "restart" accurately describes
the behavior of the TAGBODY version of ITERATE, whether it's used
correctly or incorrectly [1].
But I can think of a few disadvantages:
(a) The user's understanding of how incorrect programs will behave
is improved only for the TAGBODY version of ITERATE, not for
the more straightforward LABELS version.
(b) The word "restart" sounds so much like a non-local transfer of
control, I'm afraid people might be tempted to use it that way
(i. e., deliberately make use of the deficiency that you and
Tim pointed out in the TAGBODY version of ITERATE). Then their
code wouldn't work right in the LABELS version of ITERATE.
(c) The word "restart" is already used in the condition system;
this could cause some confusion.
(d) On rare occasions, I find that I want to use the label created
by ITERATE as a funarg, to be passed as a continuation. But
I guess this isn't really a disadvantage, because I could just
create a funarg manually, by wrapping a RESTART inside a LAMBDA.
-- Robert Munyer <mun...@mcs.com>
[1] correctness as defined by my documentation for ITERATE, saying
that it should only be used for tail recursion.
Robert Munyer
Robert Monfera <mon...@fisec.com> wrote:
> Let me help doing that by recalling what someone quoted a few
> days ago: we mostly write programs for other (potentially not
> as tail-recursion-conscious) programmers, not for the compiler.
I agree that when we consider the use of any concept, we need to
think about whether we should avoid its use because someone else
might not understand it. In this case, however, the concept in
question (recursion) is so very fundamental that I think every CL
programmer needs to understand it anyway.
If you really understand how function calls work, then it is
trivially easy to understand stack recursion and tail recursion.
If you don't fully understand function calls, then you should try
to remedy that situation immediately.
("You" above is meant as the indefinite pronoun, not the second
person pronoun).
Personally, I suspect the average beginner would be able to understand
my version of MOD-INVERSE, more easily and more quickly than he or
she would be able to understand Erik's or Xavier's version. [1]
-- Robert Munyer <mun...@mcs.com>
[1] Erik's version is in the article 9 levels above this one. Go
up one more level to see mine, then down one level to see Xavier's.
Barry Margolin
Robert Munyer <mun...@mcs.com> wrote:
>In article <Mggr4.50$pO2.2954@burlma1-snr2>,
>Barry Margolin <bar...@bbnplanet.com> wrote:
>
>> Actually, perhaps a better way to do this is not with something
>> that looks like a function. Instead of doing (<name> . <parameters>),
>> how about (restart <name> . <parameters>). This way, RESTART is
>> the only special name you have to remember. Basically, RESTART
>> would be to ITERATE as GO is to TAGBODY.
>
>This is an interesting idea! The word "restart" accurately describes
>the behavior of the TAGBODY version of ITERATE, whether it's used
>correctly or incorrectly [1].
>
>But I can think of a few disadvantages:
>
>(a) The user's understanding of how incorrect programs will behave
> is improved only for the TAGBODY version of ITERATE, not for
> the more straightforward LABELS version.
>
>(b) The word "restart" sounds so much like a non-local transfer of
> control, I'm afraid people might be tempted to use it that way
> (i. e., deliberately make use of the deficiency that you and
> Tim pointed out in the TAGBODY version of ITERATE). Then their
> code wouldn't work right in the LABELS version of ITERATE.
How about this definition of RESTART when using the LABELS version of
ITERATE:
(defmacro restart (name &rest args)
`(return-from ,name (,name ,@args)))
This effectively turns all recursive calls into tail calls. Hopefully, the
compiler's tail-call optimization will recognize this and do the right
thing.
With this definition, an incorrect program (i.e. one that uses RESTART in a
non-tail-call position) will misbehave in both the TAGBODY and ITERATE
versions. I don't think the misbehaviors will be the same, but they'll
both be broken.
>(c) The word "restart" is already used in the condition system;
> this could cause some confusion.
Yeah, I was bothered by that as well. Other names that come to mind are
NEXT (as in Perl), GO-BACK-TO, AGAIN, and CONTINUE (not a great name, I
just included it because C/C++ uses it).
--
Barry Margolin, bar...@bbnplanet.com
Dorai Sitaram
Barry Margolin <bar...@bbnplanet.com> wrote:
>In article <88sn08$gh8$1...@eve.enteract.com>,
>Robert Munyer <mun...@mcs.com> wrote:
>>(c) The word "restart" is already used in the condition system;
>> this could cause some confusion.
>
>Yeah, I was bothered by that as well. Other names that come to mind are
>NEXT (as in Perl), GO-BACK-TO, AGAIN, and CONTINUE (not a great name, I
>just included it because C/C++ uses it).
REPEAT, as in TeX. RECUR also is good, and is a pun
of sorts (RECURsion), rather apt for what's going on
here.
--d