If I want an infinite loop of do-somethings, and I decided to do it via recursion, how would I go about it? is there some sort of "this" pointer, like in C++ classes. How does an unnamed function realize itself?
In article <d4b78695.0205162021.25844...@posting.google.com>, andr...@flop.co.uk (Andy Reiter) wrote:
> Say I have a little lambda function
> (lambda () > (do-something))
> If I want an infinite loop of do-somethings, and I decided to do it > via recursion, how would I go about it? is there some sort of "this" > pointer, like in C++ classes.
andr...@flop.co.uk (Andy Reiter) writes: > Say I have a little lambda function
> (lambda () > (do-something))
> If I want an infinite loop of do-somethings, and I decided to do it > via recursion, how would I go about it? is there some sort of > "this" pointer, like in C++ classes. How does an unnamed function > realize itself?
How does something with no name refer to itself? That's rather philosophical 8). You can always cheat and give it a name:
(lambda () ((lambda (this) (funcall this this)) (lambda (this) (sleep 1) (write-line "I'm doing something!") (funcall this this))))
Of course, using recursion to implement an infinite loop is a pretty bad idea in Common Lisp: you're likely to overflow the stack! A more preferable way to do something foerver in an anonmyous function would be to use LOOP, like so:
-- If that makes any sense to you, you have a big problem. -- C. Durance, Computer Science 234 (setq reply-to (concatenate 'string "Paul Foley " "<mycroft" '(#\@) "actrix.gen.nz>"))
> If I want an infinite loop of do-somethings, and I decided to do it via recursion, > how would I go about it?
This isn't Scheme; don't use recursion when iteration will do.
If you really need recursion in a lambda, use a LABELS form instead and return #'<function name>, or include an anaphoric lambda package (Graham?) and use the alambda macro, which would look something like this:
> This isn't Scheme; don't use recursion when iteration will do.
I wouldn't go *that* far. One should use the right tool for the job, be it recursion or iteration. One should first write the code in the most perspicuous manner possible (keeping in mind that Lisp has a far richer set of `iteration' constructs than Scheme) and *then* if a recursive construct is causing problems, change it to an iterative construct (keeping in mind that Lisp does not require tail-recursive calls to use constant space).
That being said, Paul's solution of wrapping your call to (do-something) in a LOOP is the clearest way to go about it.
> This isn't Scheme; don't use recursion when iteration will do.
Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack overflow can ocour, within a well known number of data. Please understand me right, but as everyone know, there are some old rules we just agrea, without even asking if the caurse we say so, is a tiny chance, that occoured in compleatly different situasions than the one in count. Reson I say so, is that this "rule" have been there since we all had 8k mem to work with, but today, ---- Eh , don't computers carry a bit more mem, than when this rule was documentet with Pi making stack overflow. _When_ do a recursive function cause this problem, --- and do this still justify that saying recursion, we emidiatly say "no-no, you just overflow the stack " ; I don't need to overflow any stack, if I know what I do, and if I know that this function working on this known set of data ,will _never_ overflow any stack. ------ or are we just stubbern old fanatics ,that just react from the rules, settled under compleatly different circumstances ,back then in the stoneage ? Do these old rules still rule, or is this also a matter about ideology ,that if anyone accept that you _can_ use recurtion, everyone have to give up their pony, and start riding another one. P.C. http://groups.yahoo.com/group/skuespilhus/
[SNIP] > " if I know what I do, and if I know that this > function working on this known set of data ,will _never_" <insert
anything>
Every time a programmer in the dungeons of M$ says these words to himself, yet another blue screen appears on my monitor...
> ------ or are we just stubbern old fanatics ,that just react from the > rules, settled under compleatly different circumstances ,back then in the > stoneage ?
I never programmed in the stone ages, but I still think it is a good rule though even more for readability and intuitiveness than safety.
> *When* does a recursive function cause this [stack overflow] problem?
The `problem' is that Common Lisp allows *any* recursive form to use as much stack as the implementors choose. So conforming code cannot make any assumptions about whether it will cause stack overflow.
However, all `industrial strength' implementations of Common Lisp can do tail-recursion under certain circumstances. These vary from vendor to vendor, but there are generally declarations and implementation switches that can be set to cause the compiler to recognize and optimize tail-recursive calls.
> Are we just stubbern old fanatics, just reacting from the > rules settled under completely different circumstances back in the > stone age?
Back in the 80's when Common Lisp was developed (wait a second. Is he implying that I am a fossil?!) there were several important Lisp implementations that did *not* support tail recursion at all. If you were attempting to write portable Lisp code, you simply could not rely on the compiler optimizing stack usage.
These days, I think you are justified in rejecting a Lisp implementation if there isn't some way to persuade it to optimize stack usage.
In general, I ignore the issue of tail recursion during development. If the obvious way to code is using tail recursion, then I use it. If it is with a DO or LOOP, I use them. Once it is written, if it is trivial to replace a tail-recursive call with a iteration, I'll do it, otherwise I'll just ensure that the compiler takes care of it.
> Do these old rules still apply, or is this a matter of ideology?
I'd say that the old rules are considerably relaxed, but not completely irrelevant. There are pragmatic reasons to distinguish between recursion and iteration; it isn't just ideology. For instance, it is often very hard to debug tail-recursive code because the path of execution immediately prior to the bug may have been discarded.
In a language that *requires* a tail recursive implementation, the onus is upon the implementor of the language to ensure that the compiler correctly optimizes stack usage in all cases. If you write code in Common Lisp that depends upon tail recursion, then the onus is upon *you* to make sure it works properly for the intended use. (I.e., you ought to know what options and settings are necessary for the implementions you intend to support.)
In article <kD_F8.8026$Bn5.3943...@typhoon.ne.ipsvc.net>, "Joe Marshall" <prunesqual...@attbi.com> wrote:
> I'd say that the old rules are considerably relaxed, but not completely > irrelevant. There are pragmatic reasons to distinguish between recursion > and iteration; it isn't just ideology. For instance, it is often very > hard to debug tail-recursive code because the path of execution immediately > prior to the bug may have been discarded.
That's *exactly* the same as iteration.
With a recursive formulation, if you turn off the tail call elimination then the whole history of the computation is right there, sitting on the stack for you to examine. There's no easy way to do the same for iteration.
* "P.C." <per.cor...@privat.dk> | Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack | overflow can ocour, within a well known number of data. | Please understand me right, but as everyone know, there are some old rules we | just agrea, without even asking if the caurse we say so, is a tiny chance, that | occoured in compleatly different situasions than the one in count. Reson I say | so, is that this "rule" have been there since we all had 8k mem to work with, | but today, ---- Eh , don't computers carry a bit more mem, than when this rule | was documentet with Pi making stack overflow. | _When_ do a recursive function cause this problem, --- and do this still justify | that saying recursion, we emidiatly say "no-no, you just overflow the stack " ; | I don't need to overflow any stack, if I know what I do, and if I know that this | function working on this known set of data ,will _never_ overflow any | stack. ------ or are we just stubbern old fanatics ,that just react from the | rules, settled under compleatly different circumstances ,back then in the | stoneage ? | Do these old rules still rule, or is this also a matter about ideology ,that if | anyone accept that you _can_ use recurtion, everyone have to give up their pony, | and start riding another one.
Per, please take an English course. This stuff is just too hard to read.
After considerable study of your garbled language and thinking, I believe you may be satisfied with replies to different questions than you appear to ask:
Is recursion always bad? No, it is not.
When is recursion bad and iteration good? When iteration requires no new storage per iteration, or less storage per iteration than recursion.
When is recursion good and iteration bad? When (1) you traverse the list forwards and backwards and maintain some state for each iteration that you unwind or something in the backward pass, and (2) your algorithm requires that you be able to backtrack if you make a mistake.
There is never enough memory for all tasks. You do in fact run out of memory every once in a while even without recursion. However, most systems are set up allow for a bigger heap than stack, and you can run out of stack faster than you run out of heap. Stack is not garbage- collected until you return from the allocating frame. However, there is no _fundamental_ difference between using heap or stack space, so what you think is a rule against recursion is a rule against recursion where iteration is clearly more efficient.
Since Scheme has a chosen a syntax and a culture using it that reinforce recursion at the cost of understanding iteration, many Scheme freaks fail to grasp that the iteration that results from their tail recursion has a number of internal language requirements. E.g., the named let, however, can easily be implemented in Common Lisp, since it is a local phenonmenon and a simple rewriting of the apparently recursive form to iteration is fairly trivial. However, mutually recursive functions are harder to rewrite, and that is where the Scheme solution requires language support. Failure to understand that this requires language support for making a tail call into a tail jump and reusing the caller's call frame causes massively wasteful programming styles.
So, over time, Scheme has come stand for the community of people who do not care about memory consumption and think it is somebody else's fault when they run out of memory, because they are religious about their recursion and are probably not sufficientl skilled to rewrite them to iterative form, to boot.
Ignorance of the real machine is never a good thing for a programmer. For that matter, ignorance of the real world is never a good thing. -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.
70 percent of American adults do not understand the scientific process.
> > I'd say that the old rules are considerably relaxed, but not completely > > irrelevant. There are pragmatic reasons to distinguish between recursion > > and iteration; it isn't just ideology. For instance, it is often very > > hard to debug tail-recursive code because the path of execution immediately > > prior to the bug may have been discarded.
> That's *exactly* the same as iteration.
Yes, but for one subtle difference: Forms specifically designed for iteration do not span function call boundaries.
(And languages that enforce tail-recursion optimization can keep a record of some fixed amount of stack frame info to aid debugging, too.)
> > > I'd say that the old rules are considerably relaxed, but not > > > completely irrelevant. There are pragmatic reasons to > > > distinguish between recursion and iteration; it isn't just > > > ideology. For instance, it is often very hard to debug > > > tail-recursive code because the path of execution immediately > > > prior to the bug may have been discarded.
> > That's *exactly* the same as iteration.
> Yes, but for one subtle difference: > Forms specifically designed for iteration do not span function call > boundaries.
Why would that make any difference?
In tail-recursion, each time you enter the function again you get new bindings to the formal arguments and lexical variables of the function disappear. You can still access and modify the previous values of variables in an enclosing lexical scope.
In iteration, each time you enter the loop you get new bindings of the loop control variable(s) and lexical variables within the body of the loop disappear. You can still access and modify the previous values of variables in an enclosing lexical scope.
The situations are totally identical with respect to maintaining state and debugging.
> > > > I'd say that the old rules are considerably relaxed, but not > > > > completely irrelevant. There are pragmatic reasons to > > > > distinguish between recursion and iteration; it isn't just > > > > ideology. For instance, it is often very hard to debug > > > > tail-recursive code because the path of execution immediately > > > > prior to the bug may have been discarded.
> > > That's *exactly* the same as iteration.
> > Yes, but for one subtle difference: > > Forms specifically designed for iteration do not span function call > > boundaries.
> Why would that make any difference?
Iteration forms are more restrictive than general tail recursion. There is usually a single entry point. A set of tail recursive functions, however, have many entry points. It can be difficult to find out which one was the one actually used.
> The situations are totally identical with respect to maintaining state > and debugging.
I agree that they are totally identical with respect to maintaining state, but I think debugging a program where the entire function call history is available is easier than debugging one where only some are available.
Concerning Scheme and tail recursion, Erik Naggum wrote:
> Failure to understand that this requires language support for making a > tail call into a tail jump and reusing the caller's call frame causes > massively wasteful programming styles.
I am not aware of anything in the Scheme language that would require reuse of the caller's call frame. It seems to me that a Scheme compiler is more likely to reuse frames for non-tail calls than for tail calls.
I have no idea what Erik might mean by "massively wasteful programming styles".
> Ignorance of the real machine is never a good thing for a programmer.
* William D Clinger | I have no idea what Erik might mean by "massively wasteful programming | styles".
Really? I thought you had hung around here for a while...
E.g., the classic Scheme mistake: Using recursion where absolutely no state information is retained between iterations, such as traversing down a list with recursive calls. -- In a fight against something, the fight has value, victory has none. In a fight for something, the fight is a loss, victory merely relief.
70 percent of American adults do not understand the scientific process.
On 16 May 2002 21:21:42 -0700, Andy Reiter <andr...@flop.co.uk> wrote:
>Say I have a little lambda function
>(lambda () > (do-something))
>If I want an infinite loop of do-somethings, and I decided to do it via recursion, >how would I go about it? >is there some sort of "this" pointer, like in C++ classes. How does an unnamed >function realize itself?
One way is to pass a reference to itself as an argument.
Note that in the programming language Lisp, recursion is not considered a substitute for iteration. Implementations of Lisp are not required to optimize tail recursion into iteration, so deep recursions might consume too much storage. Lisp has plenty of useful iteration constructs, from the simple to the complex.
Take a look at do, dolist, dotimes and the loop macro.
If you want a local function that supports recursion, look at the labels construct:
(labels ((function-1 (lambda-list-1) (do-something-1)) (function-2 (lambda-list-2) (do-something-2)) ... (function-N ...)) ;; call functions from here; they can mutually recurse (function-1 ...))
Lisp also supports unconditional control transfers, i.e. goto:
>> This isn't Scheme; don't use recursion when iteration will do.
>Now Im'e _very_ sorry, that every time somone say this, I wonder how a stack >overflow can ocour, within a well known number of data.
A stack overflow can easily occur if your recursion has a requirement for space that is linear, O(N), in the input size. Recursion can be used if you know N to be small, or if the consumption is better than linear, say O(log N). Many divide-and-conquer algorithms fall into this category.
If you *indiscriminately* use recursion as a substitute for iteration, as students of the language Scheme are taught to do, chances are that you will eventually write something which doesn't satisfy the rational conditions for the use of recursion.
Bruce Hoult <br...@hoult.org> wrote in message <news:bruce-FA8936.19343717052002@copper.ipg.tsnz.net>... > In article <m2it5nnte4....@mycroft.actrix.gen.nz>, > Paul Foley <mycroft+...@actrix.gen.nz> wrote: > > Spelled "labels" in CL. > Why doesn't that count as a name?
Because it's one of the tools provided by CL, used by you to build expressions, just like CDR and PROGN and LET, rather than some name you have to make up when you define a function. It's in the LISP package rather than in your own package, and implementors have already made sure it doesn't have the same name as any other tool in that package. The main problem with names is you run out of them or accidently step on something else by the same name that did something different or you have to use really long names to avoid those two problems. Consider this example: You need to make ten thousand different functions, each of which does something slightly different. With named functions, you have to make up ten thousand different names, and then try to remember which name did which task as you tried to call them by name as appropriate. But with unnamed functions you just make up ten thousand different task-expressions, each of which includes a LAMBDA at the top and LABELS somewhere inside. LAMBDA and LABELS are already defined in CL and are just two names instead of ten thousand names so they aren't a problem. The difference is especially important, and I assume here, when these ten thousand functions are designed by a program, i.e. you don't even know ahead of time how many of them there will be and what they will do so it's a pain to try to design a general purpose way to name them all before you even start running the program that makes them all. Think of a "smart system" or "neural net" implemented as a large number of cooperating functions, each of which is automatically adapted to the test data or real-life environmental data, and new functions (neurons) are created as needed, perhaps by some kind of replication and natural selection. Sure, you can GENSYM a new name as needed, but on a distributed system how can you synchronize GENSYM?? Imagine a gigantic array of computers linked across the InterNet, each containing enough space to store a hundred thousand of these evolving and competing functions, and you need to constantly move functions from one machine to another so that they can "breed" with non-siblings for better genetic diversity.
By comparison, if you're defining just a few functions, or you have careful control over the namespace in which you're developing one function at a time, named functions are just fine, and unnamed functions are mostly a fun class exercise. But actually a very common practical use of an unnamed function is to have a parameterized function used in a mapping function. For example, to add a given (not constant) number to each element of a list, do this:
(defun add-a-to-each-b (a blist) (mapcar (function (lambda (b) (+ a b))) ;lexical reference to local variable a blist))
In principle, each time that add-a-... function is called, it builds a brand-new unnamed function containing the current value of a frozen into it, calls that function a whole bunch of times, then discards it before returning the list of return values from that function. Of course an optimizing compiler might replace the unnamed function with some inline code, but at least in principle that's what we're doing.
In article <ef5aa6c5.0205221231.5b7fa...@posting.google.com>, r...@netmagic.net (Robert Maas) wrote:
> Bruce Hoult <br...@hoult.org> wrote in message > <news:bruce-FA8936.19343717052002@copper.ipg.tsnz.net>... > > In article <m2it5nnte4....@mycroft.actrix.gen.nz>, > > Paul Foley <mycroft+...@actrix.gen.nz> wrote: > > > Spelled "labels" in CL. > > Why doesn't that count as a name?
> Because it's one of the tools provided by CL, used by you to build > expressions, just like CDR and PROGN and LET, rather than some name you > have to make up when you define a function. It's in the LISP package > rather than in your own package, and implementors have already made sure > it doesn't have the same name as any other tool in that package.
You have mistaken my meaning. It is not that "labels" itself is a name, but that the recursive function(s) defined in it is given a name so it can call itself.
For the previous poster ... I'd thought that "labels" wasn't an equivilent to the Y combinator because it couldn't be used to create a first-class function. But it seems that it can:
(mapcar (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) #'fact) '(1 2 3 4 5))
> For the previous poster ... I'd thought that "labels" wasn't an > equivilent to the Y combinator because it couldn't be used to create a > first-class function. But it seems that it can:
> (mapcar > (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) > #'fact) > '(1 2 3 4 5))
> => (1 2 6 24 120)
> Would this be considered to be good style in CL?
I'd certainly consider it odd and wonder why you didn't write this:
(labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) (mapcar #'fact '(1 2 3 4 5)))
> > For the previous poster ... I'd thought that "labels" wasn't an > > equivilent to the Y combinator because it couldn't be used to create a > > first-class function. But it seems that it can:
> > (mapcar > > (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) > > #'fact) > > '(1 2 3 4 5))
> > => (1 2 6 24 120)
> > Would this be considered to be good style in CL?
> I'd certainly consider it odd and wonder why you didn't write > this:
> (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) > (mapcar #'fact '(1 2 3 4 5)))
Because that's not the same thing. The mapcar is just an example of one reason that you might want a first class anonymous recursive function. You might be returning it, or storing it in a data structure or doing any number of other things with it that might not be convenient to entirely contain within the body of the (labels ...).
It's a question of which thing is structurally nested within the other -- the same reason, for example, that it's useful to have available both a "collect" clause within the loop macro, and standalone collect macros.
> > > For the previous poster ... I'd thought that "labels" wasn't an > > > equivilent to the Y combinator because it couldn't be used to create a > > > first-class function. But it seems that it can:
> > > Would this be considered to be good style in CL?
> > I'd certainly consider it odd and wonder why you didn't write > > this:
> > (labels ((fact (n) (if (= n 0) 1 (* n (fact (- n 1)))))) > > (mapcar #'fact '(1 2 3 4 5)))
> Because that's not the same thing. The mapcar is just an example of one > reason that you might want a first class anonymous recursive function. > You might be returning it, or storing it in a data structure or doing > any number of other things with it that might not be convenient to > entirely contain within the body of the (labels ...).
Right. But when you *can* conveniently put it in the body of the labels, it seems less odd looking (and you did ask a style question).
> > In article <m2it5nnte4....@mycroft.actrix.gen.nz>, > > Paul Foley <mycroft+...@actrix.gen.nz> wrote: > > > Spelled "labels" in CL. > > Why doesn't that count as a name?
> Because it's one of the tools provided by CL, used by you to build > expressions, just like CDR and PROGN and LET, rather than some name you > have to make up when you define a function. It's in the LISP package > rather than in your own package, and implementors have already made sure > it doesn't have the same name as any other tool in that package. > The main problem with names is you run out of them or accidently step > on something else by the same name that did something different or you > have to use really long names to avoid those two problems. > Consider this example: You need to make ten thousand different functions, > each of which does something slightly different. With named functions, > you have to make up ten thousand different names, and then try to remember > which name did which task as you tried to call them by name as appropriate. > But with unnamed functions you just make up ten thousand different > task-expressions, each of which includes a LAMBDA at the top and LABELS > somewhere inside. LAMBDA and LABELS are already defined in CL and are just > two names instead of ten thousand names so they aren't a problem. > The difference is especially important, and I assume here, when these > ten thousand functions are designed by a program, i.e. you don't even > know ahead of time how many of them there will be and what they will do > so it's a pain to try to design a general purpose way to name them all > before you even start running the program that makes them all. Think of a > "smart system" or "neural net" implemented as a large number of cooperating > functions, each of which is automatically adapted to the test data or > real-life environmental data, and new functions (neurons) are created > as needed, perhaps by some kind of replication and natural selection. > Sure, you can GENSYM a new name as needed, but on a distributed system how > can you synchronize GENSYM?? Imagine a gigantic array of computers linked > across the InterNet, each containing enough space to store a hundred > thousand of these evolving and competing functions, and you need to > constantly move functions from one machine to another so that they can > "breed" with non-siblings for better genetic diversity.
> By comparison, if you're defining just a few functions, or you have > careful control over the namespace in which you're developing one > function at a time, named functions are just fine, and unnamed functions > are mostly a fun class exercise. But actually a very common practical > use of an unnamed function is to have a parameterized function used > in a mapping function. For example, to add a given (not constant) > number to each element of a list, do this:
> (defun add-a-to-each-b (a blist) > (mapcar > (function (lambda (b) (+ a b))) ;lexical reference to local variable a > blist))
> In principle, each time that add-a-... function is called, it builds > a brand-new unnamed function containing the current value of a frozen > into it, calls that function a whole bunch of times, then discards it > before returning the list of return values from that function. Of course an > optimizing compiler might replace the unnamed function with some inline > code, but at least in principle that's what we're doing.
Now this is maby just a comment from another amature, but my experience have been, that simply having a few functions defined like ; (defun a(b c d) (b c d)) (defun b (a b c) (c b a)) Aso. solve a lot of naming problems. Also you can use (a b c) in a number of fifferent situasions and for each task make a any function with two parameters . P.C. http://groups.yahoo.com/group/skuespilhus/ http://groups.yahoo.com/group/3D-Honeycomb-open/
