Functional languages vs. hybrids (was Re: How does Ruby compare to Python?? How good is DESIGN ofRubycompared to Python?)

[Joe Mason]

Following Cameron's lead, I think it's time to retitle this thread...

In article <mailman.145.1077775035.8594.python-list at python.org>, Paul Prescod wrote:
>> I've always found the performance differences between functional and imperative
>> languages fascinating (well, ever since I found out about it) - on the
>> one hand, pure functional languages can prove facts about the code
>> mathematically, so in theory the compiler can optimize much more away.
>> But on the other hand, supporting all the extra function state they need
>> is very costly.
> 
> What do you mean by "extra function state?" Are you talking about LAZY 
> functional languages?

I was just being over-general.  Lemme see how much of this I can remember
without walking across the room to get a textbook...

Down in the depths of the compiler, the simplest way to implement
(C-style) functions is just to total up all the parameters and local
space it will need and lay out a stack frame.  Then the optimizer runs
through and tries to remove as much overhead as possible, inlines some
functions, etc.  The basic C++ object method is just a C function with
an extra parameter, just like Python's "self".

This works fine if functions are just named subroutines that can't be
passed around as values.  If you add the ability to pass functions
around - C can do this with function pointers - that's fine too.

If you add nested functions, but not function pointers, you still don't
need to change too much.  The only difference is that the amount of data
you need to make accessible goes up: as well as the function local
variables and parameters, and the global scope, you need to add all the
enclosing scopes.  You can either just append all these to the local
scope, and then optimize out any variables that aren't actually used, or
add a pointer to the enclosing stack frame.  This works because, since
you can't pass functions around, you're guaranteed that a nested
function can only be entered while its parent function has a frame on
the stack.

As soon as you add both function pointers and nested functions, this
isn't good enough.  Now you can call a function, creating a scope, and
then return a function that needs access to that scope.  If you destroy
the scope on return like usual, the function you just returned will
break.  So scope is no longer just a stack frame.  In functional
languages, all functions are full closures (meaning they carry with them
all the environment they need to run), which is more expensive.

The reason C is fast is that it's pretty close to the bare machine -
it's really just a thin shell over assembly language.  C++ isn't much
more, for all it's bells and whistles.  (Of course, the more the
machines mangle the code in complicated ways - branch prediction and
code morphing and whatnot - the less that's true.  But of course CPU's
are designed to run mainly C/C++ code, so of course none of these
optimizations will hurt.)  In pure functional languages, ironically,
functions hurt performance, but in theory they can be optimized much
more because the sections which can have side effects are clearly marked
off.  I haven't actually looked at any benchmarks to see what this
translates to in the real world, but I thought it was interesting.
(Maybe "fascinating" was too strong.)

Now somebody will surely chime in about Lisp machines...

>> Of course, hybrid languages like Python and Ruby have the worst of both
>> worlds - side effects everywhere AND extra function baggage to pass
>> around.
> 
> I don't know what you mean by "extra function baggage" and I don't see 
> how (e.g.) Python has some and Java or C# dn't. Maybe Haskell (but maybe 
> not). I don't know what you mean about Python.

...hybrid languages like Python and Ruby and Java and C#, then.  It's
the combination of first-order functions *and* side effects that kills
you.  (I don't know enough Java/C# to know if they have nested functions
and "function pointers" or equivalent - it actually wouldn't surprise me
if Java doesn't.)

Dynamic scripting languages aren't trying to go toe to toe with C on
performance, of course, so this isn't a criticism.

Joe