Attributes

[Sean 'Captain Napalm' Conner]

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

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

	char impure_read(int fh)
	{
          char c;
	  read(fh,&c,1);	/* assume no errors when reading */
	  return(c);
	}

  Subsequent calls to impure_read() will return different data. A more
"pure" form of this function may be:

	char pure_read(int fh)
	{
	  off_t cpos;
 	  char  c;

	  cpos = lseek(fh,0,SEEK_CUR);	/* return current position in file */
	  read(fh,&c,1);
	  lseek(fh,cpos,SEEK_SET);	/* restore position */
	  return(c);
	}

  Subsequent calls (assuming no one else does IO on the given file handle)
will always return the same data.  

  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?

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

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

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


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