functional programming & tail recursion?

[Tim Peters]

[Dennis E. Hamilton]
> I'm curious,
>
> I can't imagine any language providing a very good result for
>
> 	def fib(n):
>           assert n = int(n) and n = abs(n)
>           if n in [0, 1]:
>               return n
>           return fib(n-1) + fib(n-2)
>
> or any descriptive-language equivalent (Eiffel?).

Neither can I (certainly not Eiffel -- it's as imperative as Python or C++).

> Are you are thinking of descriptive languages that basically produce
> computations by inferences of some kind?  I would want to know the order,
> O(n), of the computation that actually occurs, I guess, in contrast to the
> ease of expression and the appearance of simplicity.

Dennis, I'm lost.  A Scheme programmer wouldn't write the above, if that's
what you think I was saying.  They would usually either write a "memoized"
function (saving a cache of prior results), or a tail-recursive helper
function that passes around a running accumulator, pragmatically equivalent
to the kind of "efficient loop" *you* would write.  See the book I
referenced (SICP) for details.

> I've seen functional-programming languages take the reverse approach:
> applicative operators that construct iterations (in terms of the result
> semantics), on the same principle as map-reduce sorts of operations.  The
> implementation worked well (assuming that closures are inexpensive,
> however).

A day or two ago I posted a msg on "lazy streams", which shows (a Python
spelling of) the  idiomatic Haskell approach to Fibonacci numbers:  define
an infinite stream "fib" consisting of 0, then 1, then "fib" itself
elementwise-added to its own tail.  That's basically a way to spell the
algorithm above.  Here's a complete Haskell defn, avoiding the std library &
"advanced" features so that it's all explicit:

fibs = 0 : 1 : sum fibs (tail fibs)
    where sum (x:xs) (y:ys) = (x+y) : sum xs ys

If you're used to this form of expression, that says very directly that
fib[i] = fib[i-1] + fib[i-2].  But Haskell is most often implemented via a
form of graph mutation, which magically "remembers" as much of the stream as
has ever been generated, and getting the n'th Fibonacci number is actually
linear-time there.

> Coming back to the claim that functional-programming is no good without
> automatic tail-recursion reduction, I am hard pressed to see that as
> *necessary*.  I can get it being recognition of a practice that has worked
> in the absence of explicit iterative or recurrence forms.
>
> Can you shed any light on that?

It's not deep:  consider a loop iterating a trillion times.  If your
language doesn't have loops, and you have to spell it via non-tail-optimized
recursion, you'll never find hardware that can execute it to completion (the
memory burden would be astronomical).  This is pragmatics, not theory:  the
Scheme std's requirement for "properly tail recursive" is a *practical*
necessity.

> PS: I understand that if I have a recurrence, it is easy to make a
> tail-recursive equivalent.  Or a Prolog clause scheme.  I was
> looking at the problem of having a recursive definition and doing the
> work to make it tail-recursive equivalent.

See SICP for details (there are several approaches, some special, some
general, but this is really getting way too specialized for c.l.py -- you
may want to ask on comp.lang.functional, though).

> I don't think one should begrudge an iterative implementation (which is
> pretty immediate) as non-functional!

"functional" implies (among other things) "no side effects".

    i = i+1

is not a functional program.  Saying that iteration is not functional is a
matter of defn, not of moral judgment.

albeit-on-real-hw-nothing-is-functional-under-the-covers-ly y'rs  - tim