Functional languages

[LB]

I've seen a lot of examples and languages. They seem to be the easiest to parse, the most expressive to write, and the poorest to execute. At least those are my impressions.

Let's consider a "pure" functional environment, that means no procedural constructs such as for loops or multiple statements before a return statement or mutable variables. This is what many people tell me is the future of programming. I've heard that it solves all the problems with multithreading since there are no mutable variables. I've heard that you just have to learn how to loop with recursion and take user input in a different way. I've heard you don't have to worry about memory allocation or deallocation or garbage collection. I've heard lots of great things.

But let's also assume that we have reached a point where we just can't make things smaller and faster anymore - your current computer is as good as it gets.

Now, suppose you're making a game in this purely functional programming environment to target those good-as-it-gets consumer computers.

I see a problem here. If you loop with recursion, that means you will eventually run out of memory to contain the stack. How do you avoid that?

This is where I get excuses, like "well you would use a for loop instead of recursion" or "the host environment would call a draw function over and over and you wouldn't loop inside the code". No. No excuses.

Then there's the cheating, like "the recursive call uses the same call stack and objects as the calling function" but you just told me there were no mutable variables!

I want some answers here and I can't find them on Google. I'm probably not understanding an obvious concept :p

[MiiNiPaa]

Tail recursion is usually optimized into iteration.
http://en.wikipedia.org/wiki/Tail_call

in functional programming languages, tail call elimination is often guaranteed by the language standard, and this guarantee allows using recursion, in particular tail recursion, in place of loops. In such cases, it is not correct (though it may be customary) to refer to it as an optimization. The special case of tail recursive calls, when a function calls itself, may be more amenable to call elimination than general tail calls, when the function may be different.

[htirwin]

Here is a relevant link.

The contrast between the two processes can be seen in another way. In the iterative case, the program variables provide a complete description of the state of the process at any point. If we stopped the computation between steps, all we would need to do to resume the computation is to supply the interpreter with the values of the three program variables. Not so with the recursive process. In this case there is some additional ``hidden'' information, maintained by the interpreter and not contained in the program variables, which indicates ``where the process is'' in negotiating the chain of deferred operations. The longer the chain, the more information must be maintained.30

In contrasting iteration and recursion, we must be careful not to confuse the notion of a recursive process with the notion of a recursive procedure. When we describe a procedure as recursive, we are referring to the syntactic fact that the procedure definition refers (either directly or indirectly) to the procedure itself. But when we describe a process as following a pattern that is, say, linearly recursive, we are speaking about how the process evolves, not about the syntax of how a procedure is written. It may seem disturbing that we refer to a recursive procedure such as fact-iter as generating an iterative process. However, the process really is iterative: Its state is captured completely by its three state variables, and an interpreter need keep track of only three variables in order to execute the process.

One reason that the distinction between process and procedure may be confusing is that most implementations of common languages (including Ada, Pascal, and C) are designed in such a way that the interpretation of any recursive procedure consumes an amount of memory that grows with the number of procedure calls, even when the process described is, in principle, iterative. As a consequence, these languages can describe iterative processes only by resorting to special-purpose ``looping constructs'' such as do, repeat, until, for, and while. The implementation of Scheme we shall consider in chapter 5 does not share this defect. It will execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. An implementation with this property is called tail-recursive. With a tail-recursive implementation, iteration can be expressed using the ordinary procedure call mechanism, so that special iteration constructs are useful only as syntactic sugar.31

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2

an example,

/*recursive process*/
(define (factorial n) 
  (if (= n 1)
      1 
      (* n (factorial(- n 1))))) 

/*iterative process, recursive procedure*/
(define (factorial2 n) 
  (define (iter c p) 
    (define z (* p c)) 
    (if (= c 1) 
        p
        (iter (- c 1) z )))
  (iter n 1)  
)

In C or C++,

/*recursive process*/
int factorial(int n) {
    if (n == 1)
        return 1;

    return n * factorial(n - 1);
}

/* "iterative process", recursive procedure, in C or C++,
    memory will still build up even though the state 
    of the procedure is contained in the values of the procedure's
    variables at any point, not relying on previous values*/
int factorialIter(int c, int p) {
    if (c == 1)
        return p;
    return factorialIter( c - 1, c * p);
}
int factorial2(int n) {
    return factorialIter(n, 1);
}

Chapter 5 goes into how all of this works.

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-34.html#%_sec_5.4.2

[rapidcoder]

Then there's the cheating, like "the recursive call uses the same call stack and objects as the calling function" but you just told me there were no mutable variables!

And there are no. Once the stack frame is reused, the old variables are gone. The new stack frame is new variables. So the memory is physically reused, but there is no mutability.

[LB]

So then I can't keep track of past states for e.g. a game based on moving forward and backward in time? Tail calling is what I was referring to as 'cheating', because it defeats the purpose of recursion and basically means you just have a different syntax for procedural looping.

[Script Coder]

If used correctly recursion can solve many problems in a clearer way than iteration, and tail calling simply makes it more efficient.

[LB]

I know, but it's not what people advocate when they tell me about how great pure functional languages are.

[Script Coder]

Well what are the great qualities you have heard regarding recursion? Also, as far as I know the compiler does some optimisations so that object are not continuously reallocated and copied when "mutated".

[Oria]

A bit off-topic but:

LB wrote:

But let's also assume that we have reached a point where we just can't make things smaller and faster anymore - your current computer is as good as it gets.

Atomic transistors will keep us right on track in having smaller and faster computers :)

[Script Coder]

Atomic transistors will keep us right on track in having smaller and faster computers :)

True, but then again large scale quantum computing will speed life up even more.

[LB]

We can't keep making things smaller and faster forever - we will eventually hit a limit. I'm just saying imagine that right now we are at the limit (we're not, obviously).

[keskiverto]

"future of programming"

Didn't Amdahl say something about parallel computing already in the 1960s?

[Duthomhas]

There is a difference between how we humans view things and the way the computer actually does things.

A (considerable) advantage of pure functional languages is that the compiler can reason about your program in ways that compiler writers for other languages could only dream of.

In other words, the compiler can essentially do whatever it wants to make your code run, because it can guarantee that your code will produce the intended results.

In languages with side effects you could never make such a guarantee.

I see a problem here. If you loop with recursion, that means you will eventually run out of memory to contain the stack. How do you avoid that?

That is a problem for all languages. You are making an assertion that FP advocates do not make: "I cannot do something stupid to crash my program."

Of course you can. If you make a loop that is guaranteed to exhaust your resources, and the compiler cannot (1) recognize it and (2) find any way to prevent it, then you are just as screwed in functional languages as any other language.

It is still the programmer's responsibility to not do stupid things.

However, back to your intended point (I think), which has already been handled nicely by others responding to this thread: You claim that converting a tail-call into an iterative loop is cheating.

No it isn't. Remember, what FP advocates are advocating is not "all values are immutable" or anything like that. What they are saying is that treating all values as immutable gives the compiler a great deal of flexibility when it analyzes your program, and makes your job (as the programmer) a whole lot easier, because you too can reason about your program in ways you cannot in other languages.

Hope this helps.