[Fwd: Re: [cells-devel] Logic Programming in Cells]

[Thomas F. Burdick]

Kenny Tilton writes:

 > So the generator sits there trying different values, with nested 
 > generators each working thru their values? The generator needs to be 
 > able to keep track of where it is between evaluations, including knowing 
 > when it is starting a fresh search (if you will).

Yep.  I'm envisioning a generator doing things like producing
permutations or counting or working its way through a database cursor.
Knuth will be useful here.  I'm thinking a generator has an internal
state which is initialized by a rule, but can be set by the
generator's formula.  In the case where the generator is reevaluated
because something under it FAILed, the state is not reinitialized.

 > Are you up to speed on the new propagation scheme, as featured most 
 > prominently in "unfinished-business"? I guess teh good news is that 
 > propagation to dependent cells completes before any output is done, so 
 > you do not have to back out outputs (and rules are not supposed to have 
 > side effects, tho I did just that in the Dwo Jones use case <gasp>.).

Yeah, the new propagation scheme is really the reason I thought of
doing this in Cells itself; it should make it easier to handle at the
Cells level.

 > But what about the dependency propagation itself? A retry by the 
 > Generator may not propagate to the same population, so some positive 
 > mechanism must un-calculate dependencies reached during any failed 
 > propagation.

Yeah, I'm hoping this isn't too hard.

 > Too bad I am not using the stack any more....Just had an 
 > idea. I need to look at the logic again, but what if we let dependency 
 > propagation take place on the stack. One nice thing here is that I was 
 > just about to /fake/ a stack just for debugging purposes, so I could 
 > figure out where problematic data pulses were originating. So either we 
 > do not need to do that, or that supports the backtracking you will need.
 > 
 > Again, have you been thinking about these issues? Either way, am I in 
 > the right ballpark approach-wise?

You're pretty much right-on.  I was going to look hard at the
propagation code to figure out whether to use the control stack, or
hand-manage a stack of my own.  If it uses tail-calls in the case
where there are no backtracking points and *debug* is nil, it should
be possible to avoid excessive stack use in the normal case, at least
for high-quality CLs.