alan@nereid.jpl.nasa.gov (Alan Quan) (12/04/90)
I need to find out if it's possible to implement demons in Prolog in an efficient manner. These can be simple triggers which respond to pre-specified situations in the input data and then initiate a standard backward-chained Prolog inference (I'm also interested in efficient Prolog forward chaining in general, but this is not essential). I'd like to use such a technique for a real-time application so it has to be relatively fast--- any comments you can provide on suitability of Prolog for real-time environments (Prolog alone or Prolog in conjuction with C) will be of considerable interest. -- Alan Quan M/S T1704 4800 Oak Grove Dr. Pasadena, CA 91109-8099 alan@nereid.jpl.nasa.gov (818) 354-4221
ciancarini-paolo@cs.yale.edu (paolo ciancarini) (12/04/90)
In article <4716@mahendo.Jpl.Nasa.Gov> alan@nereid.jpl.nasa.gov (Alan Quan) writes: > > >I need to find out if it's possible to implement demons in Prolog in an >efficient manner. These can be simple triggers which respond to >pre-specified situations in the input data and then initiate a standard >backward-chained Prolog inference (I'm also interested in efficient >Prolog forward chaining in general, but this is not essential). > In the current implementation of Shared Prolog, a distributed logic language defined and implemented by myself and other people at University of Pisa, Italy, we use both backward and forward chaining as a technique to implement parallel logic agents and triggers. An SP program defines a set of logic agents that cooperate across a blackboard, i.e. a dynamic knowledge base that is actually a Tuple Space a la Linda. Communication operations are in fact in(Atom) and out(Atom), that have a semantic similar to assert and retract (I am afraid that this rule out real-time efficiency, but actually our performance experiences are quite encouraging; and for the moment we are not using Linda for the communication kernel). Agents are triggered by patterns that have the following structure: Read In | Goal Out where Read and In are logic goals that define an activation guard (a trigger) that when satisfied with respect the current contents of the blackboard starts a local Prolog goal (Shared Prolog is an extension of Prolog); when this terminates the Out is written back to the blackboard. So each agent uses locally backward chaining, while the blackboard as a whole can be seen as a working memory of a logic bases production system (that uses forward chaining). We could also define global distributed backtracking in a particular application, but of course it is very computationally expensive, so this is not an embedded linguistic mechanism (as opposed to DeltaProlog, that I believe in its last version included distributed backtracking as a linguistic feature). We implemented Shared Prolog on a network of non homogeneous workstations (Vaxes and Suns). Shared Prolog is a project in progress. It is used to design a complex programming environment. Some formal details are contained in a paper forthcoming on ACM TOPLAS (January 91). Some implementation details are contained in a paper published in Proc. ACM Symp on Principles and Practice of Parallel Programming, Seattle 1990, pp.40-49. Paolo Ciancarini Visiting Scientist Dept. of Computer Science Yale University
ludemann@mlpvm1.iinus1.ibm.com ("Peter Ludemann") (12/05/90)
alan@nereid.jpl.nasa.gov (Alan Quan) asks: > I need to find out if it's possible to implement demons in > Prolog in an efficient manner. The answer is "yes". IBM-Prolog has such a construct. I won't bore you with all the details (there are 16 pages in the Programmer's Guide plus a few in the Reference Manual). In essence, you can define three kinds of interrupts: 1. Wait on a variable to become instantiated. 2. Do not restore the initial state and allow choice points. 3. Restore the initial state and remove choice points after the interrupt finishes. The first kind is essentially the freeze/2 predicate. The other two are used to implement things such as the equivalent of control-C (stop execution). Each external interrupt has a predicate associated with it (by the "dec_it" declaration), an interrupt level (this can be used to mask out low priority interrupts), whether or not it can interrupt compiled code, and a "type" which indicates whether the failure in the interrupt predicate will cause failure in the currently executing goal (that is, whether or not the execution and backtrack stacks are restored after the interrupt predicate finishes). An interrupt can do any side-effects, including changing the internal database or raising error condition ("stop execution" simple causes a "stop execution" error which, like all other errors, can be trapped by the Prolog program). The debugger is also implemented with an interrupt mechanism. The efficiency of interrupt handling depends mainly on the operating system; with the right kinds of operating system features, the implementation inside Prolog is very simple and efficient (sorry, I can't provide details). - Peter Ludemann ludemann@mlpvm1.iinus1.ibm.com
mmh@cs.qmw.ac.uk (Matthew Huntbach) (12/05/90)
In article <4716@mahendo.Jpl.Nasa.Gov> alan@nereid.jpl.nasa.gov (Alan Quan) writes: > >I need to find out if it's possible to implement demons in Prolog in an >efficient manner. > >I'd like to use such a technique for a real-time application so it has >to be relatively fast--- any comments you can provide on suitability of >Prolog for real-time environments (Prolog alone or Prolog in conjuction >with C) will be of considerable interest. > I think the concurrent logic languages would be much more suitable for what you are doing than Prolog. I don't think Prolog's backtracking mechanism fits in well with real time programming. Demons are really an example of concurrent procedures, so a concurrent language is likely to give you a better implementation than a sequential one. Matthew Huntbach
finin@hamlet (Tim Finin) (12/06/90)
In article <4716@mahendo.Jpl.Nasa.Gov>, alan@nereid (Alan Quan) writes: > > >I need to find out if it's possible to implement demons in Prolog in an >efficient manner. These can be simple triggers which respond to >pre-specified situations in the input data and then initiate a standard >backward-chained Prolog inference (I'm also interested in efficient >Prolog forward chaining in general, but this is not essential). We've implemented a very flexible forward chaining system in Prolog called Pfc that also contains an integrated justification truth maintenance system. It not meet your needs for efficiency, however. The system alows one to write horn-clause rules which mix forward and backward chaining. This was described in: Finin, Tim, Rich Fritzson and Dave Matuzsek, ``Adding Forward Chaining and Truth Maintenance to Prolog'', IEEE Artificial Intelligence Applications Conference, (pp. 123 - 130), Miami, March 1989. >I'd like to use such a technique for a real-time application so it has >to be relatively fast--- any comments you can provide on suitability of >Prolog for real-time environments (Prolog alone or Prolog in conjuction >with C) will be of considerable interest. To achieve high efficiency, you might consider a hybrid system using a fast production system like CLIPS, if what you want to do is have data-driven rules which are triggered by input data which are streaming into Prolog. You could have the same data stream into a system implemented in CLIPS and have the CLIPS output piped into the Prolog as a stream of queries. Tim +----------------------------------------------------------------------+ | Tim Finin finin@prc.unisys.com | | Center for Advanced Information Technology 215-648-2840, -2288(fax) | | Unisys, PO Box 517, Paoli, PA 19301 USA 215-386-1749 (home) |
micha@ecrc.de (Micha Meier) (12/06/90)
In article <4716@mahendo.Jpl.Nasa.Gov> alan@nereid.jpl.nasa.gov (Alan Quan) writes: >I need to find out if it's possible to implement demons in Prolog in an >efficient manner. >... >--- any comments you can provide on suitability of >Prolog for real-time environments (Prolog alone or Prolog in conjuction >with C) will be of considerable interest. In the design of the SEPIA Prolog we tried to address exactly these problems, namely the suitability of Prolog for real-time applications and data-driven computation. First about the demons: If the condition for triggering a demon can be stated as a constraint on one or more variables, it is possible to use the coroutining facility, so that each time a variable occurring in the constraint is instantiated (or bound to another such variable), the suspended constraint is woken and the system checks if it can be evaluated or not. If not, it delays and waits for further instantiation. If yes, the body of the constraint predicate is executed in the normal manner. As far as real-time applications are concerned, SEPIA is able to process interrupts asynchronously, so that even if the interrupt comes while an external predicate written in C is executed, the execution is immediately interrupted and the user-defined interrupt handler, which can be any Prolog or external procedure, is invoked. It is also reasonably fast, so that fast response is guaranteed. On the other hand, currently it is running only under UNIX, which is not very good for such applications. We are actually looking for possible real-time applications for SEPIA and we are interested in cooperations in this field. --Micha -- E-MAIL micha@ecrc.de MAIL Micha Meier ECRC, Arabellastr. 17 8000 Munich 81 Germany
stolcke@ICSI.Berkeley.EDU (Andreas Stolcke) (12/07/90)
In article <4716@mahendo.Jpl.Nasa.Gov>, alan@nereid.jpl.nasa.gov (Alan Quan) writes: |> I'd like to use such a technique for a real-time application so it has |> to be relatively fast--- any comments you can provide on suitability of |> Prolog for real-time environments (Prolog alone or Prolog in conjuction |> with C) will be of considerable interest. There is a version of IF/Prolog called IF/PROmLOG that allows Prolog programs (along with the runtime system) to be put into ROM for real-time applications, robot control and similar environments. It's been used in several industrial applications, mostly under OS/9, if I remember correctly. For more information you should contact Annette Kolb InterFace Computer GmbH Garmischer Strasse 4 8000 Munich 2, Germany Phone 011-49-89 51086-55 Fax 011-49-89 51086-28 E-mail ifcom!annette@uunet.uu.net -- Andreas Stolcke International Computer Science Institute stolcke@icsi.Berkeley.EDU 1957 Center St., Suite 600, Berkeley, CA 94704 (415) 642-4274 ext. 126
fore057@csc.canterbury.ac.nz (12/08/90)
In article <4716@mahendo.Jpl.Nasa.Gov>, alan@nereid.jpl.nasa.gov (Alan Quan) writes: > I need to find out if it's possible to implement demons in Prolog in an > efficient manner. These can be simple triggers which respond to > pre-specified situations in the input data and then initiate a standard > backward-chained Prolog inference (I'm also interested in efficient > Prolog forward chaining in general, but this is not essential). > > I'd like to use such a technique for a real-time application so it has > to be relatively fast--- any comments you can provide on suitability of > Prolog for real-time environments (Prolog alone or Prolog in conjuction > with C) will be of considerable interest. Try PDC Prolog V3.2. It's set up to handle pipes for OS/2, and, although it violates some traditional Prolog conventions, it is fast, and would suit real-time applications. Regards, Euan "Reality is frequently innaccurate" - Douglas Adams