Subject: Re: Please help!! From: Erik Naggum <erik@naggum.no> Date: 1999/02/11 Newsgroups: comp.lang.lisp Message-ID: <3127681433913250@naggum.no> * cbarry@2xtreme.net (Christopher R. Barry) | Freeing a programmer to not spend time and sacrifice maintainablity and | readability converting a double recursive prototype into production code | would be a nice win. I hope I have not contributed to this confusion by trying to force people to rethink this "recursive problem" thingie. see, I don't _believe_ in recursion in the moral sense of being _superior_ to iteration. I think I made the case that recursion is not as efficient as looping, but Barry is quite right that the argument in favor of recursion doesn't seem to be _total_ efficieny, just space efficiency. however, to the people who _believe_ in recursion, it should be valuable to understand that omitting the prologue and epilogue of a machine-language function, as it were, is not something you do lightly -- it adds significantly to the complexity of the compiler. some problems have not yet found solutions that can avoid space requirements linear or worse in the length of the input. I suspect those are the ones people call "recursive problems", but when it is possible to write algorithms that are sublinear in the length of the input, and smart people continue to astound with more efficient algorithms like that all the time, I'm not willing to buy the "intrinsically recursive" argument. take Fibonacci, which is _defined_ recursively, but which can _easily_ be implemented in constant memory and linear time. so even if Fibonacci is called a "recursive problem", the solution doesn't have to be. in any case, if an algorithm has a space requirement linear in the length of the input, you have a choice between real recursion and managing the space requirements elsewhere. sometimes, the stack space requirements of function calls make it unpalatable to use actual recursion, and it's easier to cons up the values on one or more lists. however, this would reduce the memory consumption with a constant number of bytes per call, and you should be pretty hard pressed for memory before this begins to be a serious impediment between "prototype" (another thing I don't _believe_ in) and production code. | I'd like to know more about the specific technical hurdles involved in | this type of thing, but this probably wasn't the right newsgroup to bring | it up in. And the answer is quite probably above my current level | anyways, but it would give me a start. discussions like these have raged in comp.compilers in the past, when I had time to follow that group. I learned a lot from following them, and, incidentally, much more fundamental stuff than the compiler course at the university, where the bondage with static typing was horribly stifling. (just because it makes sense in some cases to declare or compute types in the compiler doesn't mean it's smart to forget everything about types at run-time, but for some people it seems that the entire goal of static typing is to exclude type information at run-time, and I find that to be curiously irrational.) however, what has become clear is that a lot of people have no clue what to do _without_ type declarations, and become very insecure when they see Lisp programs without any explicit type information at all, so I recommend to learn all there is about compilers from the point of view that you _don't_ know the type of anything. this will improve your understanding greatly, as the explicit-typing crowd tends to gloss over type problems in the simple cases, and then tackle them inefficiently and clumsily in object systems and the like because they have never had an incentive to make it super efficient. sometimes, it helps to have been hurt by C, but I hope it's possible to learn this stuff without the pain and suffering. (a colleague was once watching me working out how to deal with unclosed sockets in Allegro CL under Linux, including comparing the symlinks in /proc/<pid>/fd/ to the table in /proc/net/tcp by hand and isolating the stream object that used it with a heap-walker -- this was before my auto-closing sockets -- and he went "wow, I didn't know you were such an expert!". I looked at him wearily and said "`oooh, I didn't know you had been hurt that much' is a lot more accurate.") #:Erik -- Y2K conversion simplified: Januark, Februark, March, April, Mak, June, Julk, August, September, October, November, December.