28 Apr 2011 tampe   » (Journeyer)

A parallel brain is more expressive then an unparallel one

Assume that we have deduced a state S and there are two possible choices S1 and S2 to go from there how to zip them together?

One idea is to assume S1 outputs z1 and S2 outputs z2 and just combine these outputs e.g.


(zip-1 (z1 z2)
     (subshell S1 z1)
     (subshell S2 z2))
Here we create z1 and z2 on an outer stack, then run S1, it produces a value into z1 that are deduced on an inner stack. Then it will keep z1 and revert back to the initial state but store a continuation that are reinstated at back-tracking. This will be able to mimic generator behavior through back tracking. It is safe code because the interface is clear and has a potential performance bottleneck in that we need to reinstall the state of S1 and S2 at back tracking.

The other idea is to consider the stack as a DAG and use two branches of the stack describing the deduction S1 and then deduction S2. First S1 is done, then S2. and the state will be done on-top of each other but the action will be stored in branches e.g. a storage of a variable pointer and a value. But at backtracking, then we will just first backtrack S2 and by doing this not touch the other stack branch. Then we will backtrack S1 and not do the undos on the S2 stack branch. If there are a variable touched in both S1 and S2, with backtracking touching it only in S1 or only in S1 unpredictable things can happen. So this method is faster but can produce strange bugs.

Again parallel generation of sequences can be simulated using this trick.

In all, zip patterns call's for a more delicate stack engine then the common stack implementation one need to manage a forest of DAG's that should support continuation style of separation and storage. linked structures are attractive here due to it's simplicity in these situations, on the other hand the speed of allocations from a stack represented by an array is also attractive. Maybe a combination.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!