Last night i said to Shayne: "Felix needs more magic"
We have two features I consider magical:
x \in D // is x in the data structure D?
for i in D do .. done // stream processor
Functional programming is old magic. We need new magic.
Streams are a coinductive data type.
A stream is the control inverse of an infinite list which is the dual of a list.
By "control inverse" I mean, a stream isn't a spatial data structure,
its a temporal one.
Coinductive means that the data structure is imperatively understood
by destruction -- a stream is defined by the way it is taken apart
(by splitting into the head and tail repeatedly). As opposed to a list
which is understood inductively and functionally: take a tail and
cons a head onto it to get a new list:
Cons (head, tail) -> new list
Uncons (stream) -> new stream, head
The duality is clear that Cons^(-1) = Uncons.
Ok so back to magic. Lists and streams are sequential.
What about something else. Something more advanced.
How about a tree?
We know how to make a tree: Node (value, tree, tree) -> tree.
So an UnNode just undoes this, you get two trees as a result.
plus a value (I'm using trees with a value at each node).
What's the proper control for this?
Oh yes. For a list, sequential control. For a tree .. THREADS.
A coinductive tree must spawn a thread for each branch.
Roughly speaking:
for i in tree do
body (i)
done
This is the same as for a list, except the whole thing is spawned into two
copies
after grabbing a value i. Body is applied to i. Then we simultaneously
apply body to the two i's of the two branches (assume binary tree here).
Now, its vital to understand the role of laziness with stream iterators
so we can apply this knowledge to tree destructors. As you know we lift
a list into an infinite list by using the option type: we feed the elements
of the list as Some elt, then we feed an infinite stream of None.
That's the producer. You can see it must be lazy!
Our for/in iterator consumer then eager eats up Some elts,
until it hits None, then it returns.
In a more general setting, we can feed a stream of values down an s-channel.
The reader loop reads the values and does stuff with them.
This producer consumer relation can be terminated two ways.
(1) The producer just gives up and returns.
In this case the consumer will deadlock waiting for a value that never comes.
Provided the system is set up correctly, this will cause the consumer to
be orphaned (unreachable) and its objects will be reaped by the garbage
collector.
(2) The consumer gives up and returns.
Same thing happens. The producer just dies.
In these scenarios either the producer or consumer can be an
infinite loop. Laziness ensures the loop doesn't overrun.
Now the two scenarios above are a special case. In fact,
things can stop in a more general setting. Instead of the producer (or consumer)
actually giving up .. it could itself be reading or writing another s-channel.
And if that "locks up" it gets locked up too.
So we note again, even for a non-schannel based stream, the producer
must be an infinite loop (because a stream is infinite). The consumer
can just give up whenever it wants. The laziness of the producer --
only producing something when required by the consumer -- is vital.
I have made all this discussion to understand that when we destroy an
infinite tree, we can NOT just use say recursive descent. That will work
for a finite data structure optioned into an infinite one, where we
bottom out the recursion on None.
however whilst
for i in DataStructure
should always bottom out with None for an ordinary data structure,
for i in iterator
need not ever bottom out. We can still get an infinite stream of Some 1
from the iterator which generates a stream of 1s. More useful, a stream
0 1 2 3 4 ... is handy to zip with a list to produce a list of numbered
elements.
The zipping is terminate when the list expires, the index generator
just dies of old age waiting for a call for the next number it never gets.
So what happens with a tree? Each thread has to handle itself.
We cannot use a sequential emulation: the threads MUST run concurrently.
[This does not mean on different CPU's in parallel! It means the order
of evaluation MUST be indeterminate].
I need a motivating example and nothing seems better here than a GLR parser.
A GLR parser is a stream processor that takes a stream of tokens and produces
all possible parse trees. However the trees are not finite, because the input
isn't finite!
The branches of a GLR parser are always partially constructed.
Sometime they die out because that thread doesn't result in a viable
parse. Sometimes a production completes and returns a subtree,
but at the top level you must have an infinite recursion.
In Felix, the infinite recursion is to generate a list of statements.
It is terminated by ENDMARKER, but in effect we can say that's the None
of an option type. So we can return Some statement1, Some statement2, ...
and finally an infinite stream of None.
In fact, this is not what happens, because Dypgen doesn't just return a
statement.
It can return a list of statements: Felix barfs with "syntax error: ambiguous".
So the realiity is: for an non-terminal, we get data structures constructed by
EACH of productions that parses a fixed token sequence, which could
be more than one.
Even if there is just one, it is composed of a term which has as its
values what non-terminals in its production returned -- and THEY
can also be a list.
It's important to understand why GLR works: it does a "breadth first" search,
not a depth first one. It produces all partial results for a single input,
then reads the next token.
Alright .. I've waffled enough. A new project now, to investigate how to
properly handle at co-inductive trees (and more generally any data structure).
--
john skaller
skal...@users.sourceforge.net
http://felix-lang.org
------------------------------------------------------------------------------
Live Security Virtual Conference
Exclusive live event will cover all the ways today's security and
threat landscape has changed and how IT managers can respond. Discussions
will include endpoint security, mobile security and the latest in malware
threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/
_______________________________________________
Felix-language mailing list
Felix-language@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/felix-language
