Well it sounds very interesting, not sure I understand all of it.
However, a few thoughts did come to mind ...
- If you're going down the "parallel" route, keep in mind that all
elements of any collection could be processed in indeterminate order and
maybe in parallel ... so if one has an array this could also use
parallelism if available.
- Many trees actually are considered "ordered", like a red-black or AVL
tree, even though they aren't necessarily indexed numerically
- Probably order of operations should be selectable to some degree by
programmer: "serial pre-order, serial breadth-first, parallel, don't care"
On Mon, Sep 3, 2012 at 6:38 PM, john skaller
<skal...@users.sourceforge.net>wrote:
> 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
>
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Felix Language" group.
> To post to this group, send email to felix-langu...@googlegroups.com.
> To unsubscribe from this group, send email to
> felix-language+unsubscr...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/felix-language?hl=en.
>
>
------------------------------------------------------------------------------
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
