functional programming

[Neel Krishnaswami]

François Pinard <pinard at iro.umontreal.ca> wrote:
> 
> What would be the advantages of using a "functional" Python, as
> per your definition?  I mean, of course, in practice?

Threading becomes simpler to think about. This is not a theoretical
advantage! Whenever I have code that needs to be thread-safe, I find
it tons easier to write in a functional style than worry about locking
and race conditions and reentrancy and awful things like that. 

> P.S. - Yes, I know it has been theoretically proven that we could design
> computers needing no energy, if we could fully avoid side-effects, but I
> beg to do not consider this a practical advantage yet. :-)

Actually, this *isn't* so! 

Consider a computer with a memory space of N bits. After performing
some number of arbitrary computations, the memory space will be in a
random configuration of ones and zeros.[*] 

Since we don't know what any particular position in memory will be,
there is 1s a 50-50 chance it is a 1 or a 0. So in an information-
theoretic sense each position in memory has 1 bit of information, and
the whole memory space has around N bits of information.

Now, suppose that we call calloc() on this memory and zero out all the
bits. Now, note that the amount of information needed to encode a
series of N zeros is no more than O(log N). 

Here's the critical bit: this means that resetting those bits
decreased the information in the system! And since physical entropy
and the entropy of information theory have basically the same
definition, we can with a little handwaving[**] conclude that clearing
a bit costs on the order of kT*ln 2, where T is the temperature of the
computer and k is Boltzmann's constant.

How much is this thermodynamic limit? A typical computer is somewhere
around 300 K, k = 1.38 * 10**-23 J/K, and a computer might have 
128 megs of RAM, so clearing a PCs memory can never take less than
(drum roll please...)

   3 * 10**-12 J. 

Not much, but that little bit is the toll we absolutely must pay to
the 2nd law of thermodynamics. :)



Neel

[*] For pedants, I mean 'random' in the sense of the memory space
having a Kolmogorov complexity close to N, plus the appropriate
handwaving to define "abritrary computation" to make it come out this
way. ;)

[**] You don't really want to see me try to compute partition
functions in public. Really.