-------- Original Message -------- Subject: Re: [cells-devel] Logic Programming in Cells Date: Tue, 24 May 2005 12:37:50 -0400 From: Kenny Tilton ktilton@nyc.rr.com To: Thomas F. Burdick tfb@OCF.Berkeley.EDU References: 17043.19525.48820.752685@conquest.OCF.Berkeley.EDU
Thomas F. Burdick wrote:
I was looking to build a Prolog-ish logic-programming layer on top of Cells, and looking at how to do this, it looks like basic support could be added to Cells itself pretty easily. Here's what I'm thinking. We add a new type of Cell, let's call it a Generator. Data propogation proceeds as usual, but when we get to a Generator, we mark this on a stack. If evaluation of some formula calls FAIL, we go back to the last Generator, evaluate it again, and resume data propogation from there. Any pending inputs from code that was backtracked over would of course be thrown out.
Any thoughts?
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).
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>.).
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. 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?
kt
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.
Thomas F. Burdick wrote:
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.
BTW, have you considered simply leaving Cells out of the logical computation? Just have a classic proplog-in-lisp work things out and produce an aggregation of values from which Cells simply look up the value decided for them? OTOH, I can see how, if you are using Cells, you would just as soon go on using them and then add a little logic, rather than end up with some of the system specified in Cells and some of it specified in some alternative scheme -- especially since the rules in the alternative scheme would tend to have dependencies on Cells. I am talking myself into your approach, but I just wanted to make sure there is not a better way than Cells.
kt
ps. I have to head out for some R&R, but will look at propagating on the stack instead of via the ufb-queue when I get back. k
Kenny Tilton writes:
BTW, have you considered simply leaving Cells out of the logical computation? Just have a classic proplog-in-lisp work things out and produce an aggregation of values from which Cells simply look up the value decided for them?
Well, I started with the idea of using Cells and Allegro Prolog. I tried a couple fake-ups but it felt awkward. Part of it is that you really need to interleave the two systems, because you don't want to generate lists of possibilities when you only need One That Works. So I was going to write a higher-level constraints system that would internally use Cells for data propagation, and Allegro Prolog for the LP part of constraints-solving. But ...
OTOH, I can see how, if you are using Cells, you would just as soon go on using them and then add a little logic, rather than end up with some of the system specified in Cells and some of it specified in some alternative scheme -- especially since the rules in the alternative scheme would tend to have dependencies on Cells.
... exactly, what I want to be able to have is a variable that magically takes on the right, constrained value. Having cells that depend on Prolog, whose predicates depend on cells ... this was looking ugly. My bet is that by adding Generators and backtracking, a lot of the Prolog work can be done in Lisp, and it will make interfacing between Lisp and Prolog nicer for those times when Prolog is a better solution.
I am talking myself into your approach, but I just wanted to make sure there is not a better way than Cells.
Actually, this could be seen as trying to build up what I need for a CL+Cells<->Prolog FFI :-)
Thomas F. Burdick wrote:
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.
I went ahead and implemented recursive propagation to users. No faster, btw, so I guess the queueing scheme... well, hang on, it was not a real-world test.
The bigger problem is that half-way thru I remembered that I kind of like the idea of setting a model in motion and then just having it run without further input because one change always leads to another. We'd have to have a hook somewhere to stop and check the event queue so the poor user can get in on the fun.
I cannot say for sure I will ever do that, but it Sounds Right. So I will look instead at maintaining a simulated propagation stack just to help debugging (a known need) with an eye towards someday possibly implementing "rule calculation backout". Am I right that the condition system would be too slow for logic programming? You mentioned the rule would "call FAIL". What would FAIL do?
Is this another role for the second value rules might return: :propagate, :no-propagate, nil, or :fail?
kt
Kenny Tilton writes:
The bigger problem is that half-way thru I remembered that I kind of like the idea of setting a model in motion and then just having it run without further input because one change always leads to another. We'd have to have a hook somewhere to stop and check the event queue so the poor user can get in on the fun.
I cannot say for sure I will ever do that, but it Sounds Right. So I will look instead at maintaining a simulated propagation stack just to help debugging (a known need) with an eye towards someday possibly implementing "rule calculation backout". Am I right that the condition system would be too slow for logic programming? You mentioned the rule would "call FAIL". What would FAIL do?
FAIL would do some sort of nonlocal exit :-)
Uhm, I'm not sure. Currently, the FAIL I have signals a NO-VALID-STATE condition, the code that runs the generators establishes a BACKTRACK restart, and wrapped around the very outside is a handler for NO-VALID-STATE that invokes the BACKTRACK restart if it can find it. I did this with the idea that Cells is probably not up to being a full-featured LP engine, so it's probably better to err on the side of letting the user hook in.
In the no-stack situation, FAIL could cause a RETURN-FROM back into the propagation machinery, which would certainly be faster. Whether that would make enough of a difference to enable a backtracking Cells to be used for more general LP stuff, I don't know. Only one way to find out, I guess.
-
Kenny Tilton -
Thomas F. Burdick