Overnight I had the following thought, which I think could work
rather well. The most basic implementation of the idea is as
follows:
class MonadST s m | m -> s where
liftST :: ST s a -> m
a
instance MonadST s (ST s) where ...
instance MonadST s m
=> MonadST ...
newtype FooT m e = FooT (StateT Foo m
e)
instance (Monad m, MonadST s m) => Monad (FooT m) where
...
instance (Monad m, MonadST s m) => MonadBar (FooT m) where
<operations using an ST
state>
instance (Monad m, MonadST s m) => MonadST s
(FooT m) where ...
The point here is that a MonadST instance guarantees
that the bottom monad is an ST -- and therefore single-threaded of necessity
-- and grants any ST-based monad transformers on top of it access to its
single state thread.
The more fully general approach to guaranteeing an
underlying monad is single-threaded would be to create a dummy state parameter
version of each single-threaded monad -- State, Writer, and Reader -- and add
a typeclass called MonadThreaded or something.
The real question with
this approach would be how to go about unwrapping ST-based monad transformers
in this fashion: I'm thinking that you would essentially perform unwrapping of
the outer monad using an ST computation which gets lifted to the next-higher
monad. So, say, for example:
newtype MonadST s m => ArrayT e m
a = ArrayT {execArrayT :: StateT (STArray s Int e) m a}
runArrayT ::
(Monad m, MonadST s m) => Int -> ArrayT e m a -> m a
runArrayT n m
= liftST (newArray_ (0, n-1)) >>= evalStateT (execArrayT m)
Key
points:
- A MonadST s m instance should
always imply that the
bottom-level monad is of type ST s, preferably a bottom level provided when
defining a monad by stacking transformers. The fact that the bottom
monad is in ST should guarantee single-threaded, referentially transparent
behavior.
- A non-transformer implementation of an ST-bound monad
transformer would simply involve setting the bottom monad to ST, rather than
Identity as for most monad transformers.
- Unwrapping an ST-bound monad
transformer involves no universal quantification on the state type.
After all transformers have been unwrapped, it should be possible to invoke
runST on the final ST s a.
- Both normal transformers and ST-bound
transformers should propagate MonadST.
I'm going to go try implementing
this idea in stateful-mtl now...
Louis Wasserman
wasserman.louis@gmail.com
On Mon, Feb 16, 2009 at 3:07 AM, Sittampalam, Ganesh
<ganesh.sittampalam@credit-suisse.com> wrote:
Well, I
think a type system like Clean's that had linear/uniqueness types could
"fix" the issue by actually checking that the state is single-threaded (and
thus stop you from applying it to a "forking" monad). But there's a
fundamental operational problem that ST makes destructive updates, so to
support it as a monad transformer in general you'd need a type system that
actually introduced fork operations (which "linear implicit parameters" used
to do in GHC , but they were removed because they were quite complicated
semantically and noone really used them).
Okay, I tested it out and the arrow transformer has the same
problem. I realized this after I sent the last message -- the point is
that at any particular point, intuitively there should be exactly one copy
of a State# s for each state thread, and it should never get duplicated;
allowing other monads or arrows to hold a State# s in any form allows them
to hold more than one, violating that goal.
I'm not entirely
convinced yet that there
isn't some really gorgeous type system magic
to fix this issue, like the type-system magic that motivates the type of
runST in the first place, but that's not an argument that such magic
exists...it's certainly an interesting topic to mull.
Louis
Wasserman
wasserman.louis@gmail.com
On Sun, Feb 15, 2009 at 9:20 PM, Dan Doel
<dan.doel@gmail.com> wrote:
On Sunday 15 February 2009 9:44:42 pm Louis Wasserman wrote:
>
Hello all,
>
> I just uploaded stateful-mtl and pqueue-mtl
1.0.1. The ST monad
> transformer and array transformer have
been removed -- I've convinced
> myself that a heap transformer
backed by an ST array cannot be
> referentially transparent -- and
the heap monad is now available only as a
> basic monad and not a
transformer, though it still provides priority queue
> functionality
to any of the mtl wrappers around it. stateful-mtl retains a
>
MonadST typeclass which is implemented by ST and monad transformers
around
> it, allowing computations in the the ST-bound heap monad to
perform ST
> operations in its thread.
>
> Since this
discussion had largely led to the conclusion that ST can only be
>
used as a bottom-level monad, it would be pretty uncool if ST
computations
> couldn't be performed in a monad using ST internally
because the ST thread
> was hidden and there was no way to place ST
computations 'under' the outer
> monad. Anyway, it's
essentially just like the MonadIO typeclass, except
> with a
functional dependency on the state type.
>
> There was a
question I asked that never got answered, and I'm still
> curious:
would an ST *arrow* transformer be valid? Arrows impose
>
sequencing on their operations that monads don't... I'm going to
test out
> some ideas, I think.
Your proposed
type:
State (Kleisli []) x y = (s, x) -> [(s,
y)]
is (roughly) isomorphic to:
x -> StateT s [] y
= x -> s -> [(s, y)]
The problem with an ST transformer is
that the state parameter needs to be
used linearly, because that's the
only condition under which the optimization
of mutable update is safe.
ST ensures this by construction, as opposed to
other languages (Clean)
that have type systems that can express this kind of
constraint
directly. However, with STT, whether the state parameter is
used
linearly is a function of the wrapped monad. You'd have to give a
more fleshed
out version of your proposed state arrow transformer, but
off the top of my
head, I'm not sure it'd be any better.
-- Dan
==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer:
http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================
==============================================================================
Please access the attached hyperlink for an important electronic communications disclaimer:
http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html
==============================================================================