Re: [Caml-list] environment idiom

[skaller <skaller@users.sourceforge.net>]

On Sun, 2004-12-12 at 05:13, Markus Mottl wrote:

> Another solution would be to use a state monad encapsulating
> the environment.  It has operators for getting and setting states.
> Instead of passing all arguments from function to function "manually",
> you then just need to use the monadic bind operator, which does all that
> implicitly - and even purely functionally + in a statically type safe way!

There's some illusion here. I had an argument with someone that
functional arrays were impossible: array implies O(1) which implies
mutable. Yet Haskell has them, via monads .. and it's all
'purely functional and referentially transparent'.

Took me a while to figure out why this is NOT the case.
Yet obviously, it cannot be. Consider a more extreme
example: using state transformer monads, you can emulate
the action of any C program in Haskell. So it is quite
clear there's no possibility of this being 'purely functional
and referentially transparent' because C programs are not.

The answer is evident in this example because it is so extreme.
Whether code is 'purely functional' etc or not, is a matter of
your viewpoint. Sure, the *Haskell* encoding is purely functional,
but the code *viewed at the monadic level* is not.

I.e. if you implement an interpreter for a non-transparent
non-functional language in a transparent and functional one,
then the interpreter is purely functional, but what it
interprets is not.

So monadic programming with state transformers is NOT
referentially transparent or purely functional at all.
Because you are NOT encoding in Haskell but using
the extension the monad provides.. and THAT code patently
isn't functional.

So actually all these claims about purely functional I/O
and state transformers are wrong: they miss the fundamental
point that when you use them you're no longer coding
in the base language -- the notion of 'code' is relative.

In the 'C interpreter' monad your code has all the
same properties C has -- in particular it isn't transparent
or purely functional. The fact that the interpreter implementation
retains these properties is only relevant to the correctness 
of the interpeter -- not the use of it.

I think there is a theorem here: when you abstract purely
functional code, there is no guarrantee the result is functional.
The bottom line is that given an environment E

	f: A -> B

is not functional if f fiddles with environment E.
It is absurd then to think that

	f: E * A -> E * B

is suddenly purely functional, just because the environment
is now made explicit. This is the inverse theorem:
you can lift any non-functional code to a purely functional
interpretation. Monads just 'drop' the explicit E,
leaving the orginal f which is not functional by specification.
Contradiction: monadic extensions of Haskell do not
magically allow purely functional arrays.

But it is all just fiddling with the 'level' of the code
you're talking about. Fundamentally the notions of purely
functional and referentially transparent are relative things.
Your Haskell is running on a CPU that clearly isn't functional.

A final example. Ocaml *is* purely functional. As long
as you consider references as values -- rather than what
they refer to. In reality, it's just a state transformer
monad like Haskell, only the encoding is built in to
the language.

-- 
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850, 
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net