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.