Lambda the Ultimate

I don't believe this to be true - although there are no user-accessible operations to store into memory in a true functional language the implementation certainly stores into memory - otherwise would we need memory at all? The only way to get efficiency in a functional language is to detect previously computed results and share them - this is the "update" problem - so there are stores due to that as well as due to result construction. In fact, memory bandwidth usage of functional languages is somewhat higher to extremely higher (in current implementations) than in imperative languages due to the high rate of structure (closure) construction, which puts great pressure on the garbage collector.

An interesting note about APL (and, by extension, J): They lend themselves to algorithms that are O(n) and O(n**2) - since they are array based. That is, the notation encourages one to think in terms that lead to algorithms like that. You have to go out of your way to program an algorithm that runs in O(log n) or O(n log n).

I really like APL but never quite got the hang of J - the Iverson vocabulary for programming language syntax which is stolen from natural language grammar (noun, gerund, adverb, etc.) is so different than the way anyone else describes programming languages that it is difficult for me to get used to, plus J relies on the ASCII character set rather than a special character set like APL so the resulting programs look more like line noise than TECO ever did. (Not that anyone sees line noise anymore since error-correcting modems have been ubiquitous for a decade, much less anyone still knows the joys of TECO.)

With those out of the way, does the lack of "real variables" (as opposed to identifiers for local intermediate values - what is the correct terminology here?) imply that within a function data are more likely to be kept in registers and that the return value, rather than being stored in memory, is likely to be required immediately by the "next function" (the caller).

(I'm assuming a non-lazy language, with static typing or a nice compiler or whatever to avoid worrying about type information.)

Of course I'm clutching at straws - I'm just curious whether the above makes any sense at all (it seems believable to me, but that doesn't mean much). Is it a slight effect that is insignificant compared to the cost of closures and updating (or not) large data structures, or do you get equivalent gains from a good optimizing compiler for a procedural language, or am I just completely wrong?

Cheers, Andrew

PS. I'm pretty sure there are problems for which functional languages are provably less efficient than procedural languages - there was a discussion about this not long ago on comp.lang.functional - and (a bit less sure) I think this is because of the update problem. But my original comment was about efficient use of memory access rather than efficient algorithms, although I'm not sure that's either a useful distinction, or even correct....

PPS. Sorry, this could probably be more concise and better argued - I've just come back in from a large meal!

Following on from this, the "labelled values" probably have a much better chance of being allocated on the stack which helps the cpu cache. No proof this can be done but I think it's plausible.

A good procedural compiler should have a better chance of inlining function calls though which would give it the advantage (though you did say non-lazy so perhaps not unless you're curried).

Well the quicksort which can't sort arrays in place, is going to cause less efficient use of memory, so algorithms and memory usage are somewhat related. The exact implementation of Lists, for example, make a lot of difference to efficiency of memory and algorithms.

If you changed the nice compiler to an intelligent, exhaustive optimising one. I am sure lots of run-time details could be inferred and hence optimised, such as the need of a stacked function call.

PPS. Er, I'll blame this on a large drink!