Here is my initial demo of pipes.
Schannels are extremely powerful, but a bit hard to use.
Here,. I'm building a simple pipeline using channels.
The design is part of the chips-and-wires paradigm
for re-usability. In this paradigm programmers can be
delegated the task of implementing reusable components
known as a "chips".
Chips can then be wired together to make circuit boards
(which are of course just new chips).
This technology is used in the electronics industry and provides
a very high level of reusability. It also provides a development
paradigm because chip implementation is context independent.
Chip libraries are similar to function libraries. Chips and functions
have inputs and outputs. There is an important difference though.
Functions are slaves. Composition in weak environments such as
C (and as it turns out LLVM) and probably JVM are severely compromised
by only having subroutine calling available.
Chips, on the other hand, use *exchange* of control, coroutines,
fibres, or whatever you want to call master/master relations.
Chips are active components.
In the pipeline circuit, we have a source, a sink, and a series
of transducers, wired together It is easy "in theory" to do this
without support. In practice it's quite tricky to get the inputs and
outputs right, even for a simple pipeline. The technology below
solves this by providing a familiar concrete representation
of the pipe line idiom.
First, we will make some sample chips.
We make a source which writes integers from 0 to 9 then suicides:
proc source (cho:oschannel[int]) {
for var i in 0 upto 9 do write (cho,i); done
}
And here is a sink, which reads integers and prints them.
It's an infinite loop.
proc sink (chi:ischannel[int]) {
while true do var x= read chi; println x; done
}
Finally a transducer which reads integers,
doubles them, and writes that on its output.
proc xduce (chi: ischannel[int], cho: oschannel[int]) {
while true do var x = read chi; write (cho, 2 * x); done
}
OK, so now we need two routines to connect these things:
First, we want to wire a source component to a sink.
We return coupled fibre ready to run: a chip with no inputs
or outputs.
fun pipe
(w: oschannel[int] -> 0,
r: ischannel[int] -> 0)
:
1 -> 0
=>
{
var chi,cho = mk_ioschannel_pair[int] ();
spawn_fthread { (w cho); };
spawn_fthread { (r chi); };
}
;
And here is a function that connects a source to transducer,
to produce a new source:
fun pipe
(w: oschannel[int] -> 0,
t: ischannel[int] * oschannel[int] -> 0)
:
oschannel[int] -> 0
=>
proc (out:oschannel[int])
{
var chi,cho = mk_ioschannel_pair[int] ();
spawn_fthread { (w cho); };
spawn_fthread { (t (chi, out)); };
}
;
Now that's it, for the library, but we need some syntax to make it
easy to use. Felix DSSL's come to the rescue again:
syntax chips {
// left associative
x[ssetunion_pri] := x[ssetunion_pri] "||" x[>ssetunion_pri] =># "(infix
'pipe)";
}
open syntax chips;
And now finally we will make a pipeline and execute it:
spawn_fthread$ source || xduce || xduce || sink;
To synchronise with the mainline you can also do this:
#(source || xduce || xduce || sink);
Pipelines constructed this way always work!
It is important not to underestimate how powerful this paradigm is.
Consider:
proc silly (chi: ischannel[int], cho: oschannel[int]) {
write (cho, 99);
while true do var x = read chi; write (cho, x); write (cho, 2 * x); done
}
The point? A transducer can read and write whenever it wants.
Its NOT a simple 1-1 relation like a callback function.
The transducer is a MASTER, not a slave.
HOW it works: only one "chip" is active at once. It yields control
by doing a read or write on a channel.
If there is another fthread which has done a write or read (resp)
one of the two threads gains control again (at present, the
reader so it can copy the data). If there is no matching transfer,
the thread is attached to the channel, and another thread from
the list of waiting threads is resumed.
Note carefully, the waiting fthread is NOT on a wait list
of the scheduler. It hangs off the channel. The channel is
the wait list.
If there are no active threads, the scheduler terminates the
program.
Now the IMPORTANT bit! When properly organised fibres don't
deadlock, they suicide instead. If a channel is unreachable,
the channel will be reaped by the garbage collector. This will
(usually) also kill any fthreads hanging on the channel
(because a channel is nothing more than a list of fibres waiting
on the channel). So an infinite loop is just fine, the fibre will
eventually find there's no data on the channel and no possibility
of any getting there, because no active fthreads own the channel.
So the fibre is deadlocked and subsequently reaped.
CARE must be taken to ensure that some fibre doesn't own
a channel and fail to write to it when required, because the
type system doesn't know whether that fibre is going to write
on the channel or not. If the channel is reachable, fibres
hanging on it remain deadlocked instead of being reaped.
This can hang your program.
CARE also has to be taken not to deadlock by out of order
channel operations.
The importance of the "pipeline" above is that it guarantees
none of these bad things happen. The channels are known
only to the fibres using them.
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Keep yourself connected to Go Parallel:
TUNE You got it built. Now make it sing. Tune shows you how.
http://goparallel.sourceforge.net
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
