Attributes

[Alaric B. Williams]

> > > > I had thought that pure functions were a fairly well defined concept, so
> > > > that a function is pure if and only if every call of it with identical
> > > > (formal) parameters will produce identical results.

>   Hmmm, and I thought a function was "pure" if it didn't change the context
> in which it was called.  By context, I mean things like changing global
> variables, or changing state such that the next invocation will produce
> something different, or even modifying parameters given it (in Pascal, with
> the var attribute, in C, passing in a pointer to the data and modifying the
> data through the pointer).

That's another definition. See, it's not necessarily trivially well 
defined :-)

>   Am I on the right track as to what "pure" means?  A pure function will
> never change the context in which it is called?  Or that you can take a
> "pure" function from one "program" and use it in another program without
> violating the expectations of the programmer?

That pretty much says it, too!

> > I don't see that.  If the function leaves a record then that record must
> > have some use, and thus the function cannot be memoized.
> 
>   Now, what does it mean to memorize a function?  At least, I assume
> 'memoize' is a mistyping of 'memorize'.

No, it is memoize. It's an optimisation technique.

Say we have a function that returns a list of prime factors for a 
natural number. This function takes, say, ten thousand years to 
evaluate for a large integer N. If the runtime system is "memoizing" 
that function, then when the computation is complete, it remembers 
the result obtained for that N. So if the function is invoked on N 
again, the ten thousand years need not be performed again - the 
precomputed result is looked up in the table. The recursive 
definition of Fibonacci numbers benefits from this a lot:

fib(N) = 1 if N = 0 or 1
fib(N) = fib(N-1) + fib(N-2) otherwise

Work out fib(10) on paper with and without memoization :-)

>   By memorize do you mean recording the inputs and outputs and sort of
> "black boxing" the function?

Almost!

> > I can't understand what you're saying, aside from the fact that it has
> > something to do with output to a log by a putatively functional process.

>   Here's my take on this.  Given two functions, f() and g() whereby g() is
> the memorized f().  If f() records its inputs and outputs then by definition
> it is no longer "pure", as it changes the context (or state) of the program
> (even if it is a benign change).  But by having f() record its inputs and
> outputs, and having g() do the same, a comparrison can be made between the
> two records to see if g() is behaving the same as f() (assuming that's what
> this discussion on memorizing a function means - or at least giving the same
> output as f() given the same input as f()).

Well, the "purity" issue for memoization is that a memoized function 
is not made impure by the changes "within" it, since that hidden 
record is only ever viewed by the function, and used in such a way 
as to preserve an "illusion" of purity.

>   -spc (Or is this another ludicriously high theoretical computer
> 	construct that goes *splat* when it hits the real world?)

Ooooh :-)

ABW
--
Alaric B. Williams Internet : alaric@abwillms.demon.co.uk
http://www.abwillms.demon.co.uk/