On Fri, 13 Feb 2009, Jon Lang wrote:
> In reading about functional programming, I ran across the concept of
> the "pure function" - i.e., a function that doesn't produce side
> effects.
[...]
> It occurred to me that this business of marking functions as pure could be
> done in perl by means of traits
Excellent plan.
But it's actually impurity that is infectious -- an impure function being
any function that might modify an object whose lifetime exceeds the
invocation of the function, either directly or by calling another impure
function. In the simple case that devolves to "you're impure if you call
another impure function, or modify anything in an outer scope".
But if you have objects and nested functions, the exact inference rule gets
a whole lot more complicated. With exceptions, threads and co-routines it's a
nightmare. In the general case, if your language has both pure and impure
functions, proving (at compile time) that something is not impure is an
NP-complete problem.
So you really want the programmer to mark them for you, and to have run-time
checking to make sure assumptions are not violated. And to encourage
efficiency generally, you want the Huffman coding for "pure" to be shorter
than the Huffman coding for "impure", or better still, "pure by default".
Perhaps anonymous code using the arrow notation should be implicitly
":pure"?
Another approach would be to treat purity like class finalization: start by
assuming you have pure functions, but go back and regenerate them if you
discover that a sub-function somewhere is actually impure. It won't be
trivial, given that you'll have to restart the regenerated code somewhere in
the middle.
Something else to be considered: we're close to reaching the limit on CPU
clock speed -- maybe only one more order of magnitude over the next couple
of decades. From here on the big gains will be from packing ever more cores
into a CPU, and development massively parallel software to take advantage of
them.
Applicative languages have a huge head-start on that; their no-overwrite
rule ("there are no variables, only values") means that data-flow
dependencies are *always* obvious, so very fine-grained parallel scheduling
can be used get a performance gain from every extra hyperthread (*1).
Although Perl6 will get quite a boost from various code migration
techniques, probably the biggest win will be from such implicit massive
micro-threading. If Perl6 can dispatch lots of threads all the time, not
just with "map" or "grep", then it will make the best possible use of the
available hardware.
However for this to be possible, just being "pure" won't be enough. It will
also need:
(A) cacheable functions whose return value depend only on the declared
parameters (this is orthogonal to not modifying the external environment);
and
(B) truly immutable objects, and declarative ways to guarantee them in all
contexts, such as:
* immutable function parameters (that can't be changed by the function)
* constant function parameters (that can't be changed by someone else
while the function is looking at them, even by other threads or coroutines)
* deep auto-cloning mutable "container" objects into immutable "value"
ones
* auto-boxing immutable "value" objects into "container" objects
-Martin
(*1: Google for the report by G Y Matthews (Sydney University, 1994) on
reformulating the "Magma" mathematical research language as an applicative
language.)
