[m-dev.] Stream2000

[Peter Ross]

On Wed, Nov 01, 2000 at 08:20:15AM +1100, Fergus Henderson wrote:
> 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?
> 
Abstract types are problematic when the stream has more then one extra
property.

For example putback and linenumbers would be encoded as the type
putback(linenumber(S)) or linenumber(putback(S)) both of which are
equally valid.

Now you have a pred which requires putback stream

:- pred p(putback(S), io__state, io__state) <= stream__input(S).

and a predicate which requires a linenumbered stream

:- pred q(linenumber(S), io__state, io__state) <= stream__input(S).

no matter which order the abstract type is declared you cannot easily
use both p and q with a stream which has both the putback and linenumber
properties.  So I don't think that you can get away from using
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.
> 
Not sure what will happen, I don't think it will seg fault, but I can
imagine that you will get problems with some of the operations not being
atomic.


> 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.
> 
Also you need to make sure that when constructing a synchronised stream,
that the synchronisation is the last property that is added to the
stream.

> ...
> > :- 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
> > ].
> > 
    Place the character back onto the input stream.  The implementation
    is required to guarantee at least one character of putback and throw
    a stream_error exception if the putback fails.

> > :- typeclass stream__line(S) <= stream__input(S) where [
> > 	func stream__line_number(S) = int
> > ].
> 
    What line number of the stream are we up to (the line numbering
    starts at one)

> 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.
> 
I will place some io_states into the operations.


> > :- 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.
> 
One solution would be to move the concurrency primitives into the std
library (assuming that the stream stuff ends up in the std library).
All I think that would need to happen is that the semaphore operations
become no-ops when in the non thread grades.

> > :- 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.
> 
Using the concurrency mutvar would avoid this problem.

> > :- 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.
> 
Yes it would be.

> > % 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.
> 
It should be reworded as follows:

This low level implementation isn't thread safe, as the operation of
reading/writing one character isn't atomic.  At some later date we
should add a new property (like linenumbers and putback) which ensures
that each stream operation is atomic.

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