[m-dev.] Stream2000

[Fergus Henderson]

On 31-Oct-2000, Peter Ross <peter.ross at miscrit.be> wrote:
> The only issue I have with this version is that it makes heavy use of
> existential types.  It seems once you start using them you just have to
> keep using them.

Why not use abstract types rather than existential types?

I noticed another important issue this time around:
you should document what can happen if two threads to
try perform operations on a single stream simultaneously. 
Is that supposed to be safe?  (e.g. can it seg fault?)
And are the results supposed to be consistent?
(e.g. is it guaranteed that if two threads read from a stream, each
character read from the stream will go to exactly one of the two
threads? Or might some characters be lost or sent to both threads?)

For safety, I think the answer to the first question should be "yes"
-- accessing a stream from two different threads shouldn't give
undefined behaviour.  But for efficiency, I think the answer to the
second question should perhaps be "no" -- the results are not
guaranteed to be consistent.

For cases where simultaneous access from multiple threads is desired,
we could define a `synchronized(S)' type (like the `putback(S)' type)
that adds a mutex to the stream type and that locks this mutax before
each operation and unlocks it afterwards.  The implementation would
probably need to use try_io to ensure that the stream gets unlocked if
an exception is thrown.  But this would probably be quite inefficient
compared to unsynchronized streams, so I don't think we want to make
it the default.

...
> :- typeclass stream(S) where [
> 	func stream__name(S) = string
> ].
> 
> :- typeclass stream__input(S) <= stream(S) where [
> 		% Read one character from the stream S.
> 	pred stream__read_char(S::in, stream__result(char)::out,
> 			io__state::di, io__state::uo) is det
> ].
> 
> :- typeclass stream__output(S) <= stream(S) where [
> 		% Write one character to the stream S.
> 	pred stream__write_char(S::in, char::in,
> 			io__state::di, io__state::uo) is det
> ].
> 
> :- typeclass stream__duplex(S)
> 		<= (stream__input(S), stream__output(S)) where [].
> 
> :- typeclass stream__putback(S) <= stream__input(S) where [
> 	pred stream__putback_char(S::in, char::in,
> 			io__state::di, io__state::uo) is det
> ].
> 
> :- typeclass stream__line(S) <= stream__input(S) where [
> 	func stream__line_number(S) = int
> ].

It would be a good idea to document in words what each type class is
supposed to be used for, what the putback_char and line_number methods do,
and what the behaviour of all of these methods is if something goes wrong.

> %-----------------------------------------------------------------------------%
> 
> 	%
> 	% Create a stream with infinite putback from an input stream.
> 	%
> :- some [T] (func putback_stream(S) = T
> 		=> stream__putback(T)) <= stream__input(S).
> 
> 	%
> 	% Create a stream which records which line of the input stream
> 	% we are up to.
> 	%
> :- some [T] (func linenumber_stream(S) = T
> 		=> stream__line(T)) <= stream__input(S).

Why not use abstract types rather than existential types?

Also it might be better to make those operations take a pair of io__states.
Otherwise you need to ensure that e.g. `putback_stream(X) = putback_stream(X)',
which is *not* true in your current implementation.

> :- type putback(S)
> 	--->	pb(
> 			S,
> 			mutvar(list(char))
> 		).
...
> :- pragma promise_pure(putback_stream/1).
> putback_stream(Stream) = pb(Stream, MPutbackChars) :-
> 	impure new_mutvar([], MPutbackChars).

I'm afraid that `promise_pure' is a lie, because
`putback_stream(X) = putback_stream(X)' may fail.

I suggest using a mutvar interface more like the one in
extras/concurrency/mutvar, except possibly without the
synchronization; that is, use a *pure* reference type
that uses the io__state as its store.

> :- pred putback_read_char(putback(S)::in, stream__result(char)::out,
> 		io__state::di, io__state::uo) is det <= stream__input(S).
> 
> :- pragma promise_pure(putback_read_char/4).
> putback_read_char(pb(Stream, MPutbackChars), Result) -->
> 	{ impure get_mutvar(MPutbackChars, PutbackChars) },
> 	(
> 		{ PutbackChars = [] },
> 		stream__read_char(Stream, Result)
> 	;
> 		{ PutbackChars = [Char | NewPutbackChars] },
> 		{ Result = ok(Char) },
> 		{ impure set_mutvar(MPutbackChars, NewPutbackChars) }
> 	).
> 
> :- pred putback_putback_char(putback(S)::in, char::in,
> 		io__state::di, io__state::uo) is det <= stream__input(S).
> 
> :- pragma promise_pure(putback_putback_char/4).
> putback_putback_char(pb(_Stream, MPutbackChars), Char) -->
> 	{ impure get_mutvar(MPutbackChars, PutbackChars) },
> 	{ impure set_mutvar(MPutbackChars, [Char | PutbackChars] ) }.

Both of these operations are non-atomic and so might result in inconsistent
behaviour if performed simultaneously from multiple threads.

> :- func linenumber(linenumber(S)) = int.
> 
> :- pragma promise_pure(linenumber/1).
> linenumber(line(_, MLine)) = Line :-
> 	impure get_mutvar(MLine, Line).

The `promise_pure' here is a lie too.
Consider

	foo(S) -->
		{ Line1 = linenumber(S) },
		read_char(C, S),
		{ Line2 = linenumber(S) },
		...

Here purity would require that Line1 = Line2, but that is not true for
your implementation.

Probably the best solution is to change this from a function to a pred
that takes an io__state pair.

> % File: impure.m.
> % Main author: petdr
> % Stability: exceptionally low.
> %
> % An impure interface for describing streams.
> %
> % This file provides a typeclass for people who want to map streams
> % to a foreign language binding while doing the minimum amount of work.  In
> % particular you need to write much less foreign language code, since
> % you only need to implement a few impure predicates with a well defined
> % interface.
> %
> % This file provides throwing exceptions, grabbing error messages,
> % results packaged into ok/error/eof, and turning C style handle based
> % IO into Mercury di/uo.  That's all it does, but it's something you'll
> % have to do and get right every time you implement a stream, so we have
> % done it for you.
> %
> % Note that current design isn't thread safe, it is up to the
> % implementor to ensure thread safety.

The comment at the end about thread safety isn't clear and needs to be
explained in more detail.  What do you mean "[the] current design isn't
thread safe"?  Does that mean that this library is unusable in the
presence of multiple threads?  It's important to spell out exactly
what kinds of things would be safe or unsafe.  And who is the
"implementor" that you refer to -- the implementor of the Mercury
standard library? The implementor of the impure stream instance?  If
the latter, please say so.

Also, I don't think it is enough to just leave thread safety to the
low-level stream interface implementors, since as noted above some of
the higher-level stream operations such as `putback_read_char' are
non-atomic.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------