Attributes

[William Tanksley]

On Tue, 16 Sep 1997, Sean 'Captain Napalm' Conner wrote:

> On some network somewhere in cyberspace, William Tanksley transmitted:
> > On Tue, 16 Sep 1997, Alaric B. Williams wrote:

> > > > 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).

Your definition of 'context' sounds pretty precise -- a little too precise
-- but otherwise that agrees with my emendation (although not with my
original rule, as written above).

The first rule of 'pure functionality' is that the function must act like
a pure mathematical function by producing the same output for the same
input.  I think that we can safely subsume the second rule (producing no
global output) by clearly defining the function's output -- the only
problem with global variable changes is that the language wasn't expecting
them to change.  If it was informed it would have memo'r'ized that as
well.

>   By this definition, anything that acts on I/O isn't "pure".

By any definition I'm aware of, yes.

>   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?

Close.  A "pure function" is a computer procedure which behaves the same
way a mathematical function behaves.

> > > Ah, well - but a function that "leaves a record" would surely still 
> > > be pure,

> > 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'.

I've seen it too often.  I believe that it's a "verbing" of the word
"memo".  Verbing certainly does wierd language, doesn't it?

Memoizing is often done for functions which perform an inefficient search
or some such process, but often are given the same input.  It's kind of a
cache.

> > > just functions that reference that record would then be impure, right?

> > Clearly.

> > > There's a shade of purity. 

> > No.  Purity is absolute -- 99% pure is really 1% impure, not pure at all.
> > If a function is almost pure we can't memoize it at all.

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

Precisely.  It can be a runtime and a compile-time trick.

> > > A function that marks in a 
> > > log every application might be considered pure for reasons of 
> > > analysing the code produced by a compiler to see if it memoises 
> > > correctly and stuff like that... but if the function is being used 
> > > more as a setter - ie, the mutation is part of it's "exported" 
> > > semantics - then, indeed, it isn't quite pure any more. The 
> > > difference there is hard to define, no? :-)

> > 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",

WAIT!  If f() records its inputs and outputs then that record is one of
its outputs, right?  And thus those outputs must be recorded -- and so on.
That's a non-terminating recursion.  Don't do that.

In other words, NO.  The caller of f() is responsible for memoizing the
output of f(); think about it, f() couldn't possibly know its own output,
since it wouldn't be output until it was OUT of f().

> 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()).

This is one possible test.  Yes, it's been done.  It doesn't work, though,
since a single RARE global variable access can totally mess it up.

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

There are thesis to that effect.  One of the more impressive I have seen
is titled something like "Linear Computing: the Forth Shall be First".
Natually, being a Forth bigot, I remembered it.

I don't think that it's a good model, but I remembered it.

-Billy