Logic Programming And Functional Nets
Logic Programming and Functional NetsPreliminary version1Alan Mycroft2Computer Laboratory, Cambridge UniversityNew Museums Site, Pembroke Street, Cambridge CB2 3QG, UKam@cl.cam.ac.ukAbstract. In general, programming languages and paradigms have eachbeen associated with their own underlying calculus. Thus functional programming has λ-calculus, logic programming has inference systems andconcurrent programming has various calculi: Petri nets, π-calculus, CCS,theoretical CSP and the like. Odersky recently showed how a development “Functional Nets” of the Join-calculus can express ideas fromFunctional, Concurrent and Object-Oriented languages within a singleframework in a manner which allows constructs from these disparate languages to interact. Here we examine how logic programming concepts fitinto this framework.1IntroductionIn general, programming languages and paradigms have each been associatedwith their own underlying calculus. Thus functional programming has λ-calculus,logic programming has inference systems and concurrent programming has various calculi: Petri nets, π-calculus, CCS, theoretical CSP and the like.Odersky recently showed how a development “Functional Nets” of the Joincalculus can express ideas from Functional, Concurrent and Object-Orientedlanguages within a single framework in a manner which allows constructs fromthese disparate languages to interact.One can also see this paper as an delayed continuation of Jones and Mycroft’s [2] work on semantics of Prolog. In that paper, denotational and smallstep operational semantics for Prolog were given; these are arguably a functionallanguage implementation and a hardware-implementable machine. Here we givea semantics (or implementation if one wishes to consider it that way!) of Prologvia Odersky’s Functional Nets [3].The use of Functional Nets somewhat generalises Odersky’s in that we willfeel free to use algebraic datatypes such a lists, whereas Odersky’s work on the12See http://www.cl.cam.ac.uk/users/am/research/funnel/ for a fuller version ofthis paper and sample programs.This work was partly done during sabbatical leave at AT&T Laboratories Cambridge.
basis of Functional Nets quite properly explains how they can be constructedwithin the language.2Theoretical BackgroundThe abstract syntax of logic programs for our purposes is as follows. Let Var bea set of variables (ranged over by x), Func be a set of function names (rangedover by f ) and Pred be a set of predicate names (ranged over by p). Predicateand function names each have a given arity ( 0), kp and kf . Terms (t), atoms(a), goals (g), clauses (c) and programs (p) have syntax:t :: x f (t1 , . . . , tkf )a :: p(t1 , . . . , tkp )g :: a1 , . . . , arc :: a0 :- a1 , . . . , amp :: c1 ; . . . ; cn ?- gThe final goal in a program (following ‘?-’ is called the query). The letter b alsoused to range over atoms in clauses. This language is a subset of Prolog, andwill be referred to as Prolog for convenience in the following.Given two atoms a and b, we have the notion of most-general unifier, that isa substitution θ such that θ(a) θ(b) which makes minimum identifications orreports failure when no unifier exists.A new variant of a clause is the clause renamed (bijective substitution) so asto have new variables, distinct from those under consideration.The semantics of Prolog is often defined in terms of SLD-trees. An SLD-treeis defined as follows. Given a program c1 ; . . . ; cn ?- g, an SLD-tree has a rootnode labelled with g. Suppose a node is labelled with goal a1 , . . . , ar . An SLDtree identifies a distinguished atom ai (the selected atom) from the goal andmoreover has one child for each new clause variant b0 :- b1 , . . . , bm of c1 ; . . . ; cnfrom the program whose head b0 unifies with ai . Such a child is labelled with(the resolvent) goalθ(a1 , . . . , ai 1 , b1 , . . . , bm , ai 1 , . . . , ar )where θ is the most-general unifier of ai and b0 . An SLD tree is determined byits choice strategy for the selected atom. Nodes labelled with the empty goalrepresent success, and the composition of substitutions (restricted to variablesoccurring in the root goal) encountered from root to such a node is the answer.The usual behaviour of Prolog is to consider a particular SLD-tree, the onein which the selected atom from a1 , . . . , ar is always a1 . Moreover this SLD-treeis searched in a depth-first left-right (i.e. textual order of clauses) manner.Depth-first SLD-tree searching defines an extremely sequential executionmechanism for Prolog. One alternative dimension is to search a given SLD-treein a more breadth-first fashion (this is generally called OR-parallelism). Another
evaluation choice is to arrange that, given a goal a1 , . . . , ar , the atom-selectionstrategy selects goals a1 , . . . , ar in some order (or even concurrently) before selecting goals bj which occur in the resolvent of atom ai and a given clause:θ(a1 , . . . , ai 1 , b1 , . . . , bm , ai 1 , . . . , ar ).This is generally called AND-parallelism. Note that in general this is more problematic than OR-parallelism due to contention during unification—we may findthat two concurrent resolutions are attempting to unify a variable with twoincompatible terms—and a way of dealing with this is required.In general it is often useful to consider Prolog execution as a search of anAND-OR tree.Petri Nets are another formalism whose elaboration also explores AND-ORgraphs. See Fig. 1 for an pictorial example. When playing the “token game”(defined below), the token on the leftmost s1 place can either fire transition t1or transition t2 (this is an OR-choice). If transition t1 fires then the originaltoken on s1 is replaced by two tokens, one each on s2 and s3 (this correspondsto an AND-choice).Formally1 a Petri net N is a quadruple (S, T, F, M0 ) where S is a set of places(drawn with circles, corresponding to states), T is a set of transitions (drawnwith boxes), F S T T S is the flow relation and M0 S is the initialmarking. The marking evolves by repeated occurrences of the firing rule. Lett T be a transition, we write ·t {s sF t} (the pre-set of t) and t· {s tF s}(the post-set of t); then the firing rule says that a marking M can evolve to amarking M \ ·t t· whenever ·t M . Moreover, if G T is a non-empty setof transitions then the members of G can fire concurrently providing their presets are disjoint, this is often called a step. Note that Petri nets capture finiteautomata as a special case, these are just finite nets with ( t T ) ·t t· 1.Note that there is no requirement for a Petri net to be finite. Indeed Nielsen,Plotkin and Winskel defined the notion of occurrence net2 which is a form ofunfolding of a given net which captures all its AND-OR behaviour. Such occurrence nets are acyclic (and moreover tree-like in that they allow path mergesonly to represent AND-joins and not OR-joins). Of course occurrence nets areinfinite for any net which admits unlimited firing sequences.There is a link between such unfoldings and SLD-trees, via the notion ofcoloured Petri nets. In these tokens carry additional state information ratherthan being indistinguishable, similarly transitions can choose whether or not tofire based on the values carried by their input tokens and moreover can writenew values into their output tokens. Using this model (with token values beinggoals) a non-deterministic Prolog interpreter can can be written as in Fig. 2where there is one transition ti for each clause in the program (transition ti isenabled when the goal is non-empty and its selected atom unifies with the clausei) plus one transition taccept which is enabled when the goal is empty. Unfoldings12Many presentations allow for multiple tokens to occur at a single place, but I haverather avoided this here.Beware: there is more than one definition of this term.
of this net are now isomorphic to SLD-trees (there is a family of both determinedby the strategy choosing the selected atom).BBsm2 -BBBBBBNs1 7 t1S7 SSw mr ms3SSSwt2SSSw m-- mSSSw- m - m-7 Fig. 1. A simple Petri NetIn general, mapping OR-choice into non-determinism is not very useful forprogramming—we would have to keep executing a program and hope that thehoped-for answer arises. Thus instead we map OR-choice to search, either sequential or concurrent. We now study this in more detail.3Implementing Prolog in Functional NetsThe standard implementation of substitution when implementing Prolog is toimplement variables as state-containing objects, as opposed to carrying a substitution as a value and (eagerly or lazily) applying it to a state-less term. Instantiating a variable to a term is implemented as assignment to a private field withinthe variable. In such implementations unify returns a boolean merely indicating whether the unification succeeded or not. Because of the need to undo thisassignment when backtracking to explore an (OR-) alternative, it is commonto record such instantiations in a data-structure called a trail. In the sequentialcase the trail can be implemented as a stack: a note of the stack depth is takenbefore performing resolution, unification pushes descriptors of variables as theyare instantiated and backtracking pops variable from the stack restoring theirstate to “uninstantiated”.Thus a traditional Prolog interpreter looks as follows (in Pseudo-C ):void solve(Goal *g, ClauseList *p, VarToNameMapping *map){
@@A@At1@ A7 @ A .@AU3R @ s - tnS SSwS - tacceptFig. 2. A Coloured Petri Net Prolog Interpreterif (g NULL) map- showanswer();else for (Clause *ci in p){Trail *t Trail::Note();Clause *c ci- copy();Trail::Undo(t);if (unify(g- car, c- head))solve(append(g- cdr, c- body), p, map);Trail::Undo(t);}}void start(Goal *g, ClauseList *p, VarToNameMapping *map){solve(g, p, map);printf("No more solutions\n");}I.e. if the Goal is empty then print the corresponding substitution and promptthe user as to whether alternatives are required; otherwise attempt to unify theleft-hand-side of a variant c ci- copy() with the first member of the goalg- car. If unification succeeds then append the right-hand-side of the variantto the remainder g- cdr of the goal. After unification and the recursive call tosolve it is necessary to restore instantiated variables by calling Trail::undo(t).It is convenient to allow unify to fail untidily (in an way which may leave somevariables instantiated) and to allow the call Trail::undo(t) also to restorethese also. Finally, it is sometimes convenient to allow copy() to temporarilyupdate variables present in clauses of the original program (e.g. to make copy()an O(n) process where n is the size of the clause being copied). The first call
to Trail::undo(t) can therefore serve to restore the original program too. Ofcourse various tricks are used, append is coded as O(1) and the recursive call isreplaced by an explicit stack, but the principle holds.3.1Finite FailureFinite failure (the search of the SLD-tree has been completed, with or withoutsuccess solutions) is important in that it indicates that the computation is finished as opposed to a possible additional answers being produced in the future.It is also important as a form of negation, but this is rather outwith the scopeof this paper.Sequentially, finite failure just reflects backtracking to the origin. With ORparallelism we have to keep track of which computations are extant, and we nowturn to a Functional Net solution.4Compiling Prolog to Functional NetsThe word ‘compile’ in this section represents forms of evaluation mechanismwhere the source program structure may be exploited, as opposed to an interpreter. The presentation does not aim at high efficiency, but it is clear thatefficiency-gaining adjustments (at the expense of clarity) would be possible. Consider the following, assuming that the program is cl1; . . . ; cln. (Here we represent substitutions s explicitly rather than by updating the state of the objectrepresenting a variable.)def solve(g: List[Atom], ans: List[String*Term],{if (g []) (print ans; ff());else{def f1() & . & fn() ff();(let (head:-body) copy(cl1)let s unify(hd(a), head)if (s fail) f1()else solve(s(tl(g)) @ s(body), s(ans),&.&(let (head:-body) copy(cln)let s unify(hd(a), head)if (s fail) fn()else solve(s(tl(g)) @ s(body), s(ans),}}def start(g: List[Atom], ans: List[String*Term]){ff: ()- ()) f1)fn)
def finitefail() print "No more solutions";solve(g, ans, finitefail);}This captures OR-parallel evaluation in a manner which lets us simultaneouslyunderstand the semantics and see possible implementation optimisations moreclearly. As an example of the latter, note that it would be simple to produce onevariant of solve for each predicate symbol p occurring in the program. Then theFunctional Net program would have one procedure for each predicate symbolcontaining actions determined solely by the clauses defining p. This reducesunnecessary tests in a manner characteristic of a compiler, but these actions areseen as semantically justified rather than based on low-level reasoning.5Conclusions and Further WorkThis paper confirms that Functional Nets are a promising formalism for describing Logic Programming in additional to their expressiveness at capturingfunctional and object-oriented concepts (and of course in expressing concurrencyfrom their basis in the Join calculus). The nearness of Functional Nets and Joincalculus means that the descriptions can easily be seen from both underlyingsemantic and implementation viewpoints.Clearly much remains to be done beyond these introductory notes.AcknowledgmentsI am indebted to Martin Odersky for discussions about Functional Nets.References1. Jensen, K. Coloured Petri Nets. Basic Concepts. EATCS Monographs of Theoretical Computer Science, Springer-Verlag, 1992.2. Jones, N.D. and Mycroft, A. Stepwise development of operational and denotationalsemantics for Prolog. Proc. IEEE intl. symp. on Logic Programming, Atlantic City,1984.3. Odersky, M. Functional Nets. Proc. ESOP’2000 Berlin, Springer-Verlag LNCSvol. 1782, 2000. See also http://lampwww.epfl.ch/funnel/4. Shen, K. Studies of AND/OR parallelism in Prolog. PhD thesis, Computer Laboratory, University of Cambridge, 1992.
Thus functional programming has -calculus, logic programming has inference systems and concurrent programming has var-ious calculi: Petri nets, ˇ-calculus, CCS, theoretical CSP and the like. Odersky recently showed how a development \Functional Nets" of the Join-calculus can express ideas from Functional, Concurrent and Object-Oriented
functional programming style. Adding functional programming facilities to Prolog results in a more powerful language, as they allow higher-order functional expres-sions to be evaluated conveniently within the logic programming environment. And, as will be shown in this thesis, the efficiency of functional programming in logic is
APPLICATIONS OF PETRI NETS A Thesis Submitted to . In this thesis we research into the analysis of Petri nets. Also we give the structure of Reachability graphs of Petri nets and . (Ye and Zhou 2003) about Petri nets and its’ properties. One can find further information about Pet
Make the 3D shapes 13 Use the nets you just made. 1. Put the nets flat on thin cardboard or thick paper. 2. Trace around the nets with a pencil to draw the nets on the thin cardboard. Or you can glue your paper net on the thin cardboard. 3. Cut out the cardboard nets. 4. Decorate the
The inductive learning and logic programming sides of ILP (cont') Inductive logic programming extends the theory and practice of logic programming by investigating induction rather than deduction as the basic mode of inference - Logic programming theory describes deductive inference from logic formulae provided by the user
BRIEF LADDER LOGIC OVERVIEW Page 2 18.05.2015 1.2 What is Ladder logic? Ladder logic, also known as a Ladder diagram, is a method for programming for Program-mable Logic Controls. Ladder Logic is a standardized type of graphic programming, which is similar to a circuit diagram. Programming with ladder logic is used, in particular, for creat-
Dynamic Logic Dynamic Circuits will be introduced and their performance in terms of power, area, delay, energy and AT2 will be reviewed. We will review the following logic families: Domino logic P-E logic NORA logic 2-phase logic Multiple O/P domino logic Cascode logic
functional and logic programming features are complex in detail so that the concrete design of an integrated functional logic language is a non-trivial task. This is demonstrated by a lot of research work on the semantics, operational principles, and implementation of functional logic languages since more than two decades.
care as a way to improve hospital quality and safety. As one indicator of this, the Centers for Medicare and Medicaid Services implemented new guidelines in 2012 that reduce payment to hospitals exceeding their expected readmission rates. To improve quality and reduce preventable readmissions, [insert hospital name] will use the Agency for Healthcare Research and Quality’s Care Transitions .
