Subsets of monad state 
Author Message
 Subsets of monad state

If I understand correctly, Monads conceptually incorporate a
state-of-the-world in such a way that the state-of-the-world can't be
retrieved, it can only be serially changed.

My question is, can subsets of the world be extracted and used in
isolation?  (In theory, if not in a given language.)

EG, if a given function affects only the state of the random number
generator, is it conceptually possible to give it access only to that
subset of the world, the RNG state?

(* This is my understanding from Wadler's imperative.ps, the clearest
introduction to monads I have ever seen, at
http://www.*-*-*.com/ ;Thanks
to Ralf for originally posting that URL)

--
Tom Breton, http://www.*-*-*.com/ ~tob
Ugh-free Spelling (no "gh") http://www.*-*-*.com/ ~tob/ugh-free.html



Mon, 06 Aug 2001 03:00:00 GMT  
 Subsets of monad state

Quote:

> If I understand correctly, Monads conceptually incorporate a
> state-of-the-world in such a way that the state-of-the-world can't be
> retrieved, it can only be serially changed.

> My question is, can subsets of the world be extracted and used in
> isolation?  (In theory, if not in a given language.)

> EG, if a given function affects only the state of the random number
> generator, is it conceptually possible to give it access only to that
> subset of the world, the RNG state?

It is, in theory. You can execute a monad inside of the execution of
another monad which works on a projection of the state of the
enclosing monad.  After this monad has finished, it injects the result
back into the original monads state. There is a catchword for this
("lifting"?). I've forgotten, since I never played with this style in
practice.

The "IO" or "state-of-the-world" monad is problematic to this end,
however. The problem is that your are not the only one which effects
the world. There may be other activities in the environment which
modify it. For example, a file which is deleted by another process
meanwhile you are writing to it.

If such competive actions can be present, the "project-modify-inject"
scheme doesn't generally work. For example, if the random number
generator is a shared resource of other activities in the environment,
then there might happen a conflict when you want to "write it back".

This problem has a lot to do with concurrency.  IMHO, the FP scene had
not recognized the difference between "open" und "closed" world
assumptions to this end (it has been claimed that external choice can
be represented by pure state or "sequence" monads, as far as I
remember.).

An approach which tries to give a model for "state-of-the-world"
monads which reflects the open-world assumption has been tried out by
me and others in
http://uebb.cs.tu-berlin.de/papers/published/FUJI96.html.  But this is
a draft workshop publication, which had been never refined, since
research on monads is not the thing one can gain its living from in
Germany ;)

Regards
  Wolfgang

--



Tue, 07 Aug 2001 03:00:00 GMT  
 Subsets of monad state

Quote:

> My question is, can subsets of the world be extracted and used in
> isolation?  (In theory, if not in a given language.)

> EG, if a given function affects only the state of the random number
> generator, is it conceptually possible to give it access only to that
> subset of the world, the RNG state?

Sure.  Suppose the type of your state is (Int, Rest) where the Int is
the current
state of the random number generator and Rest is the type of the rest of
the state.
Let's say
        StateTrans s a
is a state transformer monad with state of type s and results of type a.
Then you
can write your random number generator subroutines as values of type
        setSeed :: Int -> StateTrans Int ()
        random :: StateTrans Int Int
Now write a function
        promote :: (StateTrans Int a) -> (StateTrans (Int, Rest) a)
and you now have functions
        promote setSeed :: StateTrans (Int, Rest) ()
        promote random :: StateTrans (Int, Rest) Int

For a more theoretical discussion see Combining Monads by Wadler and
King.

Cheers,
Theo Norvell



Tue, 07 Aug 2001 03:00:00 GMT  
 Subsets of monad state

Quote:

> It is, in theory. You can execute a monad inside of the execution of
> another monad which works on a projection of the state of the
> enclosing monad.  After this monad has finished, it injects the result
> back into the original monads state. There is a catchword for this
> ("lifting"?). I've forgotten, since I never played with this style in
> practice.

> The "IO" or "state-of-the-world" monad is problematic to this end,
> however. The problem is that your are not the only one which effects
> the world. There may be other activities in the environment which
> modify it. For example, a file which is deleted by another process
> meanwhile you are writing to it.

> If such competive actions can be present, the "project-modify-inject"
> scheme doesn't generally work. For example, if the random number
> generator is a shared resource of other activities in the environment,
> then there might happen a conflict when you want to "write it back".

> This problem has a lot to do with concurrency.  IMHO, the FP scene had
> not recognized the difference between "open" und "closed" world
> assumptions to this end (it has been claimed that external choice can
> be represented by pure state or "sequence" monads, as far as I
> remember.).

Thanks for the reply.  It sounds like that problem would be a general
problem with concurrency.

It's even possible that lifting(?) could help by trivializing some
cases of concurrency.  EG, if one thread goes off and plays with only
the RNG, and another does only file I/O, they're not really in
competition, but this can't be recognized if a state-of-the-world
monad is all you have.

--
Tom Breton, http://world.std.com/~tob
Ugh-free Spelling (no "gh") http://world.std.com/~tob/ugh-free.html



Wed, 08 Aug 2001 03:00:00 GMT  
 Subsets of monad state

Tom,

I've cancelled my original article you are replying to
since it contained some too inexact views on a complicated subject
I haven't worked on for some years now.

Quote:

> > This problem has a lot to do with concurrency.  IMHO, the FP scene had
> > not recognized the difference between "open" und "closed" world
> > assumptions to this end (it has been claimed that external choice can
> > be represented by pure state or "sequence" monads, as far as I
> > remember.).

In fact, the state-of-the-world monad can do concurrency (one can just
use the operational interpretation to see this: there is a
runtime-system which coordinates the concurrent actions of the
functional program with the concurrent environment). The point I
wanted to bit into is whether state-transformer functions on the
state-of-the-world provide an adequate _semantic_ model for
concurrency.  However, this topic is too far away from my current work
to seriously dicuss on it ;)

Regards
  Wolfgang

--



Wed, 08 Aug 2001 03:00:00 GMT  
 Subsets of monad state
f
--
Peter Lundell                   Ericsson Telecom AB

+46  8 719 9720                 126 25 Stockholm
+46 70 519 9720 (mobile)        +46 8 719 4344 (fax)


Tue, 14 Aug 2001 03:00:00 GMT  
 
 [ 6 post ] 

 Relevant Pages 

1. A class of State Monads in Haskell 1.3?

2. Monads, state

3. Memoize Function using State Monad

4. Help! : State monad using constructor classes

5. The FASTEST subsets function [Was: Subsets of a list]

6. Checking the state of a tri-state input signal in a Verilog testbench

7. Help with large state machine design (62 states)

8. State Machine - State Definition Question

9. Return to Known State From Unused States

10. finite state machines, state cad

11. State of Parrot -- was: Re: State of Python

12. Editing a subset of columns in a DataSet

 

 
Powered by phpBB® Forum Software