We design a Fluent class hierarchy which includes first-class stateful objects representing the meta-level Horn Clause Interpreters, file, URL, socket Readers and Writers, as well as composable data structures, with high-level operations mapped to efficent iterative constructs in the underlying implementation language.
Fluents melt naturally in the fabric of Logic Programming languages and can be implemented to recover resources on backtracking or to persist. Their expressiveness is shown by redesigning key components of Prolog's system of built-in predicates and through examples of interoperation with the underlying Java system used as an implementation language.
The Web site of our Kernel Prolog prototype, http://www.binnetcorp.com/kprolog/Main.html allows the reader to try out online the examples discussed in this paper and shows the extressivenes of Kernel Prolog and its extensibility through new Java based built-ins for building a GUI toolkit.
Keywords: Logic Programming Language Design and Implementation, Interoperation of Declarative and Stateful Languages, Meta-Programming and Reflection
Despite significant syntactic, semantic and implementational variations, Logic Programming languages share a common kernel: Horn Clause Resolution1, a semantically and operationally well understood calculus. As it is the case with pure functional programming languages, this calculus allows reasoning with referentially transparent, stateless entities. The code itself can be seen as a set of declarations (equations in Functional Programming and implications in Horn Clause Resolution) from which answers to a query are derived through a uniform, step by step proof process.
However, the resolution process as such, is obviously not stateless, as it proceeds in time, step by step. If we want to preserve the ability to reflect in the object language the resolution process provided by the underlying ''glass-box'' interpreter, in its full generality, we suddenly face the need of stateful primitives. Evolving algebras [8] and abstract recursive state machines [9] have shown that programming languages can be seen as a combination of a basic, terminating step and some form of iterative closure operation. Linear logic [7,1,13] has provided a more accurate description of the state of the proof process, with emphasis on seeing formulas as resources, with special notation indicating if they are unique or reusable. Independently, the same needs arise for interoperation of declarative languages with conventional software and operating system services which often relay on stateful entities.
Through constructs ranging from plain file or socket streams in C, to lazy list streams in languages like Scheme, iterators in Java or C++, monadic constructs [15,28,29,3] in Haskell or in l-Prolog, declarative I/O in Mercury [20], the need for abstracting away the nature of the stepping process in a (finite or infinite, actual or generated as needed) sequence. Moreover, in the case of a declarative language implmented in a procedural or object oriented language, a uniform reflection mechanism is needed, for consistent modeling of stateful external objects providing native services.
This paper will introduce a concept of first class fluents on top of Horn Clauses with LD-Resolution to provide reflection of the underlying glass-box interpreter and interoperation with external stateful components, in a uniform way.
We describe a set of Fluent constructors which create Fluents from conventional data structures like lists, strings, files, terms and clauses and then provide Fluent Composers - allowing to elegantly combine them as building blocs for software components. When seen from inside an Interpreter, other Interpreters will appear as instances of Fluents (Sources) producing a stream of answers. Through a set of suitable abstractions, they will be put to work as reusable components cooperating through independent resolution processes.
While the semantics of a fluent-enabled, multi-interpreter programs cannot be expressed in a trivial way in terms of one-interpreter Horn Clause LD-resolution, their operational semantics reuses common programming knowledge as basic as reading a sequence from a file or using an iterator. Our design ensures that the usual declarative semantics covers each LD-resolution interpreter while the more powerful Fluent manipulation language is kept as an orthogonal meta-level component.
As a practical outcome, we provide a complete redesign of Prolog's built-ins which can be of use in the next iteration of the ISO Prolog standardization process.
A compact Java based reference implementation, (downloadable and testable online at http://www.binnetcorp.com/kprolog) illustrates in more detail the ideas described in this paper and provides a first draft of an Open Source executable specification of Kernel Prolog.
We will build Kernel Prolog as a collection of Horn Clause Interpreters running LD-resolution on a default clause database and calling built-in operations. Each of them has a constructor which initializes them with an goal and an answer pattern. They are in fact possibly infinite sources of answers which can be explored one by one. The object encapsulating the state of the interpreter is very similar to a file descriptor encapsulating the state of a file reader. We will call such stateful entities evolving in time Fluents.
Kernel Prolog Interpreters will possess, through built-in calls, the ability to create and query other Interpreters, as part of a general mechanism to a manipulate Fluents, external stateful objects with independent life-cycles.
This general mechanism will also allow Kernel Prolog interpreters to interoperate with the underlying object oriented implementation language.
We will start with an overview of the Fluent class, some simple Fluent examples and operations on Fluents.
Fluents are created with specific constructors, usually by converting from other Fluents or conventional Prolog data structures like Terms, Lists or Databases. 2. All Fluents are enabled with a stop/1 operation which releases their resources (most Fluents also call stop/1 on backtracking, through their internal undo operation).
In our Java based reference implementation, the Fluent class looks as follows:
class Fluent extends SystemObject {
Fluent(Prog p) {
trailMe(p);
}
// add the fluent to the parent Interpreter's Trail
protected void trailMe(Prog p) {
if(null!=p) p.getTrail().push(this);
}
// usable (through overriding) to release resources
// and/or stop ongoing computations
public void stop() {
}
// release resources on backtracking, if needed
protected void undo() {
stop();
}
}
Sources are Fluents enabled with an extra get/2 operation. Typical Sources are Horn Clause Interpreters, File, URL or String Readers, Fluents built form Prolog lists, Fluents iterating over data structures like Vectors or Hashtables or Queues in the underlying implementation language.
Note that the constructor Fluent(Prog p) does a trailing operation on the caller program p's Trail, and provides and undo operation to be called by p on backtracking, to release resources through the Fluent's stop method.
In our Java based reference implementation the Source abstract class looks as follows:
abstract class Source extends Fluent {
Source(Prog p) {
super(p);
}
abstract public Term get();
}
Sinks are fluents enabled with an extra put/2 and collect/2 operation. Typical Sinks are ClauseWriters or CharWriters targeted to TermCollectors (implemented as a Java Vectors collecting Prolog terms), StringSinks (implemented as a Java StringBuffers collecting String representations of Prolog terms), Files.
In our Java based reference implementation the Sink abstract class looks as follows:
abstract class Sink extends Fluent {
Sink(Prog p) {
super(p);
}
// sends T to the Sink for tasks as
// accumulation or printing
abstract public int put(Term T);
// return data previously sent to the Sink
// (if collection ability is present)
public Term collect() {
return null;
}
}
Not surprisingly, even Prolog databases are first class citizens implemented as extensions of Sources which provide add/2, remove/2, collect/2 operations.
Fluents can be seen as resources which go through state transitions as a result of put/2, get/2 and stop/1 operations. They end their life cycle in a stopped state when all the data structures and/or threads they hold are freed.
Fluent composers provide abstract operations on Fluents. They are usually implemented with lazy semantics.
For instance, append_sources/3 creates a new Source with a get/2 operation such that when the first Source is stopped, iteration continues over the elements of the second Source.
Compose_sources/3 provides a cartesian product style composition, the new get/2 operation returning pairs of elements of the first and second Source.
Reverse_source/2 builds a new Source such that its get/2 method returns its elements in reverse order.
Split_source/3 creates two Source objects identical to the Source given as first argument. It allows writing programs which iterate over a given Source multiple times.
Sources and Sinks are related through a discharge(Source,Sink) operation which sends all the elements of the Source to the given Sink.
Fluent modifiers allow dynamically changing some attributes of a give Fluent. For instance set_persistent(Fluent,YesNo) is used to make a Fluent survive failure, by disabling its undo method, which, by default, applies the Fluent's stop method on backtracking.
Let us put to work in a more specific way the view of Interpreters as Fluents in a redesign of Prolog on top of Horn Clauses with LD-resolution. All we have to provide is a Fluent constructor, creating an Answer Source from an Answer Pattern and a Goal given to an Interpreter. As a result, we will cover negation, limited pruning through once/1, if-then-else/3, findall/3, var/1, and, beyond standard Prolog, forms of lazy, on-demand generation of sets of solutions, as well as a uniform set of built-ins for manipulation of first class Prolog databases and external objects like Files or URLs.
Answer Sources can be seen as generalized iterators, allowing a given program to control answer production in another. Each Answer Source works as a separate Horn Clause LD-resolution interpreter (a very compact Java implementation of such an interpreter is given in the APPENDIX).
The Answer Source constructor initializes a new interpreter.
answer_source(AnswerPattern,Goal,AnswerSource)
creates a new Horn Clause solver, uniquely identified by AnswerSource (a Source Fluent), which shares code with the currently running program and is initialized with resolvent Goal. AnswerPattern is a term, usually a list of variables occurring in Goal.
The get/2 operation (provided by all Sources) is used to retrieve successive answers generated by an Answer Source, on demand.
get(AnswerSource,AnswerInstance)
tries to harvest the answer computed starting from Goal, as a instance of AnswerPattern. If an answer is found it is returned as the(AnswerInstance), otherwise no is returned. Note that once no has been returned, all subsequent get/2 on the same AnswerSource will return no. Bindings are not propagated to the original Goal or AnswerPattern when get retrieves an answer, i.e. AnswerInstance is obtained by first standardizing apart (renaming) the variables in Goal and AnswerPattern, and then backtracking over its alternative answers in a separate Prolog interpreter. Therefore, backtracking in the caller interpreter does not interfere with the new Answer Source's iteration over answers. Note however that backtracking over the Answer Source's creation point as such makes it unreachable and therefore subject to garbage collection.
Finally, an Answer Source is stopped with the stop/1 operation implemented by
all Sources.
stop(AnswerSource)
The stop/1 operation is called automatically when no more answers can be produced as well as through the Fluent's undo operation on backtracking.
To give a glimpse to the expressiveness of the resulting language, we will know introduce, through definitions in Kernel Prolog, a number of predicates known as `impossible to emulate' in Horn Clause Prolog (except by significantly lowering the level of abstraction and implementing something close to a Turing machine).
These constructs are implemented simply by discarding all but the first solution produced by a Solver.
% returns the(X) or no as first solution of G
first_solution(X,G,Answer):-
answer_source(X,G,Solver),
get(Solver,R),
stop(Solver),
eq(Answer,R).
% succeeds by binding G to its first solution or fails
once(G):-first_solution(G,G,the(G)).
% succeeds without binding G, if G fails
not(G):-first_solution(_,G,no).
The simplest meta-interpreter metacall/1 just reflects backtracking through element_of/2 over deterministic Answer Source operations.
metacall(Goal):-
answer_source(Goal,Goal,E),
element_of(E,Goal).
element_of(I,X):-get(I,the(A)),select_from(I,A,X).
select_from(_,A,A).
select_from(I,_,X):-element_of(I,X).
We can see metacall/1 as an operation which fuses two orthogonal language features provided by Answer Sources: computing an answer of a Goal, and advancing to the next answer, through the source level operations element_of/2 and select_from/3 which 'borrow' the ability to backtrack from the underlying interpreter.
Note that element_of/2 works generically on Sources and is therefore reusable, for instance, to backtrack over the character codes of a file or a URL.
After showing that we can emulate metacalls, we will use, for convenience, variables directly in predicate call position.
Note that an Answer Source enumerates over the transitive closure of a clause unfolding relation [24,25]. If our interpreter can access a single unfolding step through a similar Fluent, a finer grained meta-interpreter can be built. First let's introduce a new Fluent,
unfolder_source(Clause,Source)
which, given a Clause produces a stream of clauses obtained by unfolding the first atom on the right side against a matching clause in the database. Each step is described through an (associative) clause composition operation Å as follows:
Let A0:-A1,A2,...,An and B0:-B1,...,Bm be two clauses (suppose n > 0, m ³ 0). We define (A0:-A1,A2,...,An) Å (B0:-B1,...,Bm) = (A0:-B1,...,Bm,A2,...,An)q
with q = mgu(A1,B0). If the atoms A1 and B0 do not unify, the result of the composition is denoted as ^ (failure). Furthermore, we consider A0:-true,A2,...,An to be equivalent to A0:-A2,...,An, and for any clause C, ^ Å C = C Å ^ = ^. As usual, we assume that at least one operand has been renamed to a variant with variables standardized apart.
We can now build a meta-interpreter which implements the transitive closure of the unfolding operation Å (provided as the get/2 operation of an Unfolder Source in the underlying implementation language), combined with backtracking trough element_of/2.
unfold_solve(Goal):-
unfold(':-'(Goal,Goal),':-'(Goal,true)).
unfold(Clause,Clause).
unfold(Clause,Answer):-
unfolder_source(Clause,Unfolder),
element_of(Unfolder,NewClause),
unfold(NewClause,Answer).
Once we have first solution and metacall operations, emulating if-then-else is easy.
% if Cond succeeds executes Then otherwise Else
if(Cond,Then,Else):-
first_solution(successful(Cond,Then),Cond,R),
select_then_else(R,Cond,Then,Else).
select_then_else(the(successful(Cond,Then)),Cond,Then,_):-Then.
select_then_else(no,_,_,Else):-Else.
All-solution predicates like findall/3 can be obtained by collecting answers through recursion.
% if G has a finite number of solutions
% returns a list Xs of copies of X each
% instantiated correspondingly
findall(X,G,Xs):-
answer_source(X,G,E),
get(E,Answer),
collect_all_answers(Answer,E,Xs).
% collects all answers of a Solver
collect_all_answers(no,_,[]).
collect_all_answers(the(X),E,[X|Xs]):-
get(E,Answer),
collect_all_answers(Answer,E,Xs).
Note that, again, the collect_all_answers operation is generic, and works on any Source. This suggest providing a built-in Source-to-List converter source_list/2 which can be made more efficient in the underlying implementation language. The alternative definition of findall/3 becomes simply:
findall(X,G,Xs):-
answer_source(X,G,Solver),
source_list(Solver,Xs).
% creates a copy of G with variables uniformly
% substituted with new variables not occurring
% in the current resolvent)
copy_term(X,CX):-first_solution(X,true,the(CX)).
% true if X is currently a free variable
var(X):-copy_term(X,a),copy_term(X,b).
The previous definitions have shown that the resulting language subsumes (through user provided definitions) constructs like negation as failure, if-then-else, once, copy_term findall - this justifies its name Kernel Prolog. As Kernel Prolog contains negation as failure, following [6] we can, in principle, use it for an executable specification of full Prolog.
With these additions, it turns out that Kernel Prolog is a fairly expressive language. Unlike pure Horn Clause Prolog and unlike weaker languages based on Prolog + negation, which have been extensively studied in the past, Kernel Prolog has enough power to be used as a basis for building compact Prolog implementations as well as for modular library components.
While providing a formal semantics of Kernel Prolog needs more research and it might need methods beyond the techniques used for less expressive logic languages, let us give a sketch of the issues involved.
Note that Kernel Prolog is a superset of Horn Clauses with a form of metacall facility. Related semantic issues have been studied [30,11] and are now fairly well understood.
Like in the case of findall/3, solutions returned by Answer Source contain new variables. As such, their formal description cannot be covered through a straightforward adaptation of work like [14,2]. The issues are in fact similar with those involved in describing formally AND-parallel execution of Prolog programs [19,16], with resolution theory needing to be adapted to deal with separate computations of answers within the same AND-branch.
Clearly, the three new builtins answer_source/2, get/2, stop/1 added to Horn Clause Prolog lack an obvious declarative semantics. On the other hand, the dialog between a master Horn Clause interpreter creating a new interpreter for execution of one of its subgoals and the slave Answer Source Fluent which returns new answers on demand, is well known to any Prolog user as it is essentially the same as querying a Prolog interpreter through a toplevel command interpreter.
However, in a more declarative framework, it can be the case that a suitable semantics for our Fluent operations is given in terms similar to that of streams in functional languages.
Modular extension of Kernel Prolog through new built-ins is based on an Object Oriented hierarchy of Fluents. In our reference implementation we have chosen to build as much as possible of the extension at source level, except in case of major inefficiencies or limited functionality.
Apparently, this looks a difficult problem because answer_source and get operations provide a fixed communication flow between the answer producer and the answer consumer. Note however, that we can use an Answer Source constructor to emulate both linear (usable once) and conventional assert-style operations, by keeping the set of Answer Source engines representing references to 'dynamic clauses' on a list, as in:
assert_(Clause,Engines,[E|Engines]):-
answer_source(repeat,Clause,E).
linear_assert(Clause,Engines,[E|Engines]):-
answer_source(true,Clause,E).
clause_(Engines,Head,Body):-
member(E,Engines),
get(E,the((Head:-Body))).
The trick in the case of conventional assert is to force
indefinite backtracking inside the producer Answer Source, with
repeat/0, a pure predicate defined as usual:
repeat.
repeat:-repeat.
On the other hand, the usable once, linear_assert operation only executes the goal true/0 - and therefore it will only succeed once, before returning the answer no.
We have not shown how a retract-like operation is implemented - but this can easily achieved by removing the engine reference from the list of engines, so that clause/3 cannot see it anymore.
Note that these dynamic database operations are in fact backtrackable, as they depend on the list of engines maintained by the consumer program. As such, they are closer to BinProlog's linear and intuitionistic assumptions [26]. Scoped implications (as in Lambda Prolog, Lygon [32], Lolli [13,12]) can be implemented using logical variables to close the scope of an implication. This is how they are actually implemented in BinProlog [22].
Our reference implementation does not use the emulation shown previously which is obviously inefficient and cannot be used elegantly as an implementation of failure persistent databases.
Instead, we provide a direct implementation of Database Fluents, which reflect to object level the interpreter's own handling of the Prolog database. As an additional benefit, multiple databases are provided.
Sequential Prolog data structures are mapped to Fluents naturally. For instance, list_source/2 creates a new Fluent based on a List, such that its get/2 operation will return one element of the list at a time. Similarly term_source/2 creates a Fluent from an N-argument compound term, such that its get/2 method will return first its function symbol then each argument. These built-ins are usable to emulate conventional Prolog operations like univ/2 (also known as =..) quite easily:
univ(T,FXs):-if(var(T),list_to_fun(FXs,T),fun_to_list(T,FXs)).
list_to_fun(FXs,T):-list_source(FXs,I),source_term(I,T).
fun_to_list(T,FXs):-term_source(T,I),source_list(I,FXs).
As they can be converted easily to/from Prolog data-structures, Fluents are usable as canonical representation for data objects as well as for computational processes (like in the case of answer_sources). Fast iteration on Fluents, using loops over efficient native data structures in the implementation language, replace recursion in the object language. Interoperation with external objects is also simpler as implmentation language operations can be applied to Fluents directly.
File and URL I/O operations are provided by encapsulation Java's Reader and Writer classes as Fluents. Clause and (wide, Unicode compatible) character Readers are seen as instances of Sources and therefore benefit form Source composition operations. Moreover, Prolog operations traditionally captive to predefined data specific implementation like DCGs, can be made to work generically and mapped directly to work on relevant Sources like File URL or Socket Readers.
Note that one can assume, at an abstract level, that arithmetics is part of Kernel Prolog through the usual extension of Horn Clauses with successor arithmetics.
Kernel Prolog provides a unique built-in for handling arithmetic functions,
compute(Operation,Arg1,Arg2,Result)
An enhanced is/2 evaluator, supporting execution of arbitrary user defined functions of N arguments provided as N+1 argument Prolog relations, is implemented at source level.
Arithmetic operations producing sequences like random number generators, primes, arithmetic or geometric series etc. can be implemented efficiently in the underlying language and provided in Kernel Prolog as fluents. Our reference implementation provides a generic
integer_source(MaxFuel,A,X,B).
built-in operation allowing iterated computation of X<-A*X+B at most MaxFuel times (or an infinite sequence if MaxFuel = 0).
Most Fluents are designed to be usable only once, by default, and release all resources held (automatically on backtracking or under programmer's control when their stop operation is invoked). While Fluent operations like split_fluent/3 can be used3 to duplicate most Source Fluents, the following alternative provides a more efficient alternative.
A Memoing Fluent is built easily on top of a Source Fluent by accumulating values in a List or dynamic array. A Memoing Fluent can be shared between multiple consumers which want to avoid recomputation of a given value.
Lazy Lists can be seen as an instance of Memoing Fluents: they accumulate successive values of a Source Fluent in a (reusable) list. The simple Lazy List abstraction in our reference implementation works as follows:
source_lazy_list(Source, LazyList)
creates a new LazyList object form a Source object:
lazy_head(LazyList, LazyHead)
extracts the current head element of the list. Iteration over the list is provided by
lazy_tail(LazyList, LazyTail)
which returns LazyTail, a new lazy list encapsulating the next stage of the Source fluent.
While complete automation of lazy lists through a form of attributed variable construct is possible, we have chosen a simpler implementation scenario based on the previously described operations, mainly because overriding unification with execution of an arbitrary procedure would introduce potential non-termination - something which would break the very idea of keeping the execution mechanism as close as possible to basic Horn Clause resolution, as available in classic Prolog.
Based on these operations, a lazy findall/3 is simply:
% creates lazy list form an answer source
lazy_findall(X,G,LazyList):-
answer_source(X,G,S),
source_lazy_list(S,LazyList).
In fact, the behavior of the lazy list encapsulating lazy_findall's advancement on alternative solutions produced by an Answer Source, is indistinguishable from a lazy list constructed from an ordinary list_source:
% creates a lazy list from a lazy_list(List,LazyList):-
list_source(List,S),
source_lazy_list(S,LazyList).
The following operations will produce a lazily growing reusable list, to be explored with lazy_element_of/2 in a way similar ordinary lists are explored with member/2.
% explores a lazy list in a way compatible with backtracking
% allows multiple 'consumers' to access the list, end ensures that
% the lazy list advances progressively and consistently
lazy_element_of(XXs,X):-
lazy_decons(XXs,A,Xs),
lazy_select_from(Xs,A,X).
% backtracks over the lazy list
lazy_select_from(_,A,A).
lazy_select_from(XXs,_,X):-lazy_element_of(XXs,X).
% returns a head/tail pair of a non-empty lazy list
lazy_decons(XXs,X,Xs):-
neq(XXs,[]),
lazy_head(XXs,X),
lazy_tail(XXs,Xs).
A minor change on Prolog's chronological backtracking is needed however: only the creation point of the lazy list is subject to trailing, and the complete lazy list is discarded at once. This is achieved easily in our reference implementation by giving to each lazy list its own (dynamically growing) trail, and by providing an undo operation which rewinds the trail completely when backtracking passes the lazy list object's creation point.
Multi-Variables are special Fluents which accumulate multiple values on an internal stack. As the stack is popped on backtracking multi-variables return to their previous values, therefore providing a form of backrackable destructive assignment. A new Multi-Variable is built with def(MultiVar,InitialValue), it is upated with set(MultiVar,NewValue) and its current value is retrived with val(MultiVar,Value)).
Among its applications, multi-stream DCGs, following the Assumption Grammars implementation model [26,4,22], which does not require a DCG preprocessor, but uses backrackable destructive assignment instead, for advancing the state of a given DCG stream.
dcg_def(MultiVar,Xs):-def(MultiVar,Xs).
dcg_val(MultiVar,Xs):-val(MultiVar,Xs).
dcg_connect(MultiVar,X):-val(MultiVar,[X|Xs]),set(MultiVar,Xs).
The resulting implementation initializes an input list with dcg_def/2, retrieves its current value with dcg_val/2 and advances with the dcg_connect/2 relation, which consumes/generates a terminal symbol each time is called.
We have shown that Kernel Prolog is basically as expressive as sequential, fixed execution order Prolog. An interesting open question is: is it expressive enough to emulate in an elegant (while possibly inefficient) way the basic XSB memoing scheme [31,21].
Let's observe that if an operation checking that a given term is a variant of another were available, we could associate a new Answer Source for solving a given goal (up to a variant) only once, and then explore the memoed results for extracting copies of answers.
We recognize here a basic element of the XSB engine [17]. However, there are a number of other issues in XSB, related to avoiding loops when the same goal variant shows up later in the execution of an open goal [5].
We will only sketch here the first steps towards XSB emulation in Kernel Prolog, i.e. we will add a form of memoing, allowing to reuse a given goal pattern, up to variant checking.
First, let us note that we can implement quite easily variant_of/2 as:
variant_of(Term,Variant):-
copy_term(Term,T1),
copy_term(Variant,T2),
numbervars(T1,T),
numbervars(T2,T).
with numbervars/2 expressed as usual in terms of successor arithmetics and var/1 (in practice, provided as a built-in, for efficiency).
Let us assume that a global store is implemented as a Database Fluent in which we can attach to each goal variant a unique persistent Answer Source. Goal variants can be represented as ground terms resulting from the numbervars/2 operation, on which a hash key can be computed (as in the orginal XSB implementation). Finally, to provide a memoing engine construct, which encapsulates the same functionality as an ordinary Answer Source, from outside, while making sure, internally, that the stream of solutions is computed only once, and shared through copying by all the consumers in the equivalence class of the answer variant, can be implemented by adapting our Lazy List construct to p| While more work is needed to orchestrate the suspend/resume mechanism of answer producers and answer consumers following some insights from work like [5], possibly within a multi-threaded implementation of Kernel Prolog (following our similar Jinni engine [23]), this implementation scenario shows that execution models going beyond Prolog's original LD-resolution model are relatively easy to express in our framework.
Besides the fact that our Answer Sources are instances of Fluents which provide a generic interaction mechanism with external stateful objects, independently of their execution mechanism, some other differences with Oz engines come from their different intended use:
New languages based on relatively pure subsets of Prolog like Mercury [20] have been designed as targets of more efficient implementation technologies and for their reliability in building large software systems. Flexible execution order is being used in systems like SICStus, GNU-Prolog and B-Prolog to support constraint solving and in systems like XSB for synchronizing answer production and answer consumption in tabling. While Horn Clauses with negation have been extensively studied and some of the techniques described in this paper might be well known to experienced Prolog programmers, the very idea of systematically exploring the gains in expressive power as a result of having multiple pure Prolog interpreters as first order objects, has not been explored yet, to our best knowledge.
While the set of bulit-ins suggested in this paper needs to be extended to cover Java events and interacion with GUI components and some key features of ISO Prolog [6] (most notably exceptions) are not covered so far, we think that the simpliciy of our design will help with the steap learning curb of Prolog and improve efficiency of real life Prolog programs by moving frequently used iterative patterns to the underlying implementation language.
The advent of component based software development and intelligent appliances requiring small, special purpose, self contained, still powerful processing elements, makes Kernel Prolog an appealing implementation technique for building logic programming components. In particular, in the case of small, wireless interconnected devices, subject to severe memory and bandwidth limitations, compact and orthogonally designed small language processors are instrumental. Our ongoing commercial Palm Prolog implementation will use a fast Horn Clause LD-resolution WAM emulator based on the Kernel Prolog design described in this paper.
Here are a few open issues and some ongoing or projected Kernel Prolog related developments:
By collapsing the semantic gap between Horn Clause logic and (most of) the full Prolog language into three surprisingly simple, yet very powerful operations, we hope to open the doors not only for an implementation technology for a new generation of lightweight Prolog processors but also towards a better understanding of the intrinsic elegance hiding behind the core concepts of the logic programming paradigm.
Our Horn Clause Solvers encapsulated as Fluents provide the ability to communicate between distinct OR-branches as an practical alternative to the use assert/retract based side effects, in implementing all-solution predicates. Moreover, lazy variants of all solution predicates are provided as a natural extension to Fluent based lazy lists.
Fluents provide a uniform approach to interoperate with stateful external objects, handle I/O operations in a generic way and allow to specify precise and automated resource release, consistently with Prolog's LD-resolution process.
Finally, high level Fluent Composers allow combining component functionality in generic, data representation independent ways.
It is usual to see interpreters for a fairly complex language like Prolog spread over thousands of line of code. In the spirit of Evolving Algebras [8], our interpreter only focuses on the transitive closure of the unfolding operation and on handling backtracking with a simple orStack, containing Unfolder Sources with elements left to iterate over (and implementing last call optimization when the Unfolder is reaching a stopped state.
Our tiny Interpreter is provided as an override to the get() method of the Source abstract class (seen at Prolog level as the get/2 built-in).
public Term get() {
if(null==orStack) return null;
Clause answer=null;
while(!orStack.isEmpty()) {
Unfolder I=(Unfolder)orStack.pop();
answer=I.getAnswer();
if(null!=answer) break;
Clause goal=(Clause)I.get();
if(null!=goal) {
if( I.notLastClause() )
orStack.push(I);
else
I.stop();
if(null==answer)orStack.push(new Unfolder(goal,this));
}
}
Term head;
if(null==answer) {
head=null;
stop();
}
else
head=answer.getHead();
return head;
}
Note that our design ensures that after producing a solution and returning, calling the interpreter will simply move the state of the Fluent to the next solution. This is clear simplification over Jinni [23] where answer producer Interpreter threads had to synchronize with their answer consuming caller threads.
The Unfolder class provides the stepping operation also as a get method of a Source Fluent. Except for the backtracking process (that it has to take care of by using its orStack), the Interpreter appears as a composition of Unfolder Fluents.
public Term get() {
if(null==e) return null;
Clause unfolded_goal=null;
while(e.hasMoreElements()) {
Term T=(Term)e.nextElement();
prog.getTrail().unwind(oldtop);
unfolded_goal=T.toClause().unfold_with_goal(goal,prog.getTrail());
if(null!=unfolded_goal) break;
}
return unfolded_goal;
}
The underlying unification operation called by unfold_with_goal is distributed as unify_to methods in the Term subclass tree, collectively implementing various operations on Prolog terms and lists.
1 The most commonly used variation is Prolog's LD-resolution which combines a depth-first search rule with a left-to-right selection rule.
2 Such constructors are named by concatenating the type names they convert between. For instance, list_source will convert a list to a Source Fluent.
3 The astute reader might notice that Linear Logic provers provide similar operations. This is by no means accidental, a resource conscious proof procedure will usually provide explicit means to implement reuse.