Fluents: a Uniform Extension of Kernel Prolog for Reflection and Interoperation with External Objects

Paul Tarau
University of North Texas & BinNet Corporation

http://logic.csci.unt.edu/tarau
tarau@cs.unt.edu

Kernel Prolog = Horn Clause Interpreters with LD-resolution ( Answer Sources)+ Fluents
redesigning key components of Prolog's system of built-in predicates
uniform interface for controlling multiple interpreters and external stateful objects
lazy, composable data structures
interoperation with the underlying Java system
crisp abstractions -> new design patterns
http://www.binnetcorp.com/kprolog/Main.html

Motivation

Logic Programming languages share a common kernel: Horn Clause Resolution
LP: reasoning with referentially transparent, stateless entities
the resolution process as such, is not stateless, as it proceeds in time, step by step
ability to reflect in the object language the resolution process provided by the underlying ''glass-box'' interpreter, in its full generality => the need of stateful primitives
similar abstractions:

file or socket streams in C, lazy list streams in Scheme
iterators in Java or C+, declarative I/O in Mercury
monadic constructs in Haskell and LambdaProlog

Fluent Classes and their Operations

Fluents are created with specific constructors, usually by converting from other Fluents or conventional Prolog data structures like Terms, Lists or Databases...

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:

abstract class Source extends Fluent {
Source(Prog p) {
super(p);
}
abstract public Term get();
}

Sinks

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;
}
}

Fluent Composers

Fluent composers provide abstract operations on Fluents. They are usually implemented with lazy semantics.

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
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: ex. 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.

Interpreters as Answer Sources

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.

The Answer Source constructor initializes a new interpreter.

answer_source(AnswerPattern,Goal,AnswerSource)

creates a new Horn Clause solver, uniquely identified by AnswerSource which shares code with the currently running program and is initialized with resolvent Goal.

get/2 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.

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.

`first_solution/3, once/1 and not/1`

% 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).

Reflective Meta-Interpreters

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).

Unfolders: fine grained control

unfolder_source(Clause,Source)

associative clause composition operation Å :

(A₀:-A₁,A₂,...,A_n)Å(B₀:-B₁,...,B_m) = (A₀:-B₁,...,B_m,A₂,...,A_n)q

with q = mgu(A₁,B₀).

^ Å C = C Å ^ = ^

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).

If-then-else

% 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.

Findall/3: by recursing over get/2

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.

Findall/3: with fluent operations

findall(X,G,Xs):- 
   answer_source(X,G,Solver),
   source_list(Solver,Xs).

Term copying and instantiation state detection:

copy_term(X,CX):-first_solution(X,true,the(CX)).

var(X):-copy_term(X,a),copy_term(X,b).

Built-ins as a Library of Fluents

Emulating (backtrackable) dynamic database operations

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))).

Database Fluents

Lists and Terms as Source Fluents

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).

File, Socket,URL I/O: char and clause readers and writers.

Lazy Arithmetics with Fluents

  integer_source(MaxFuel,A,X,B).

iterated computation of X<-A*X+B at most MaxFuel times

Memoing Fluents

Most Fluents: usable only once, by default, and release all resources
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.

Fluent based Lazy Lists

an instance of Memoing Fluents
they accumulate successive values of a Source Fluent in a (reusable) list

source_lazy_list(Source, LazyList)

  lazy_head(LazyList, LazyHead)

  lazy_tail(LazyList, LazyTail).

Lazy findall/3

% creates lazy list form an answer source

lazy_findall(X,G,LazyList):-
  answer_source(X,G,S),
  source_lazy_list(S,LazyList).

lazy_element_of/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).

Multi Variables and Fluent based DCGs

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 backtrackable destructive assignment. A new Multi-Variable is built with

def(MultiVar,InitialValue)
set(MultiVar,NewValue)
val(MultiVar,Value)).

multi-stream DCGs,

do not require a DCG preprocessor,

uses backtrackable destructive assignment 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).

Towards XSB resolution: Kernel Prolog + Memoing

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
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 the Lazy List construct to persistent Fluents

Adding Constraints

Kernel Prolog has an extensible unification algorithm (see Multi-Variables)
Constraint Stores as Fluents: put + collect
Assertional vs. Variable based constraints
propagation can be triggered on unification or on updating a Linda blackboard
uniform design patterns

Related work

similar to our Answer Sources: engines in Oz

main difference with Oz: we have encapsulated backtracking

pure subsets of Prolog: Mercury
Horn Clauses with negation have been extensively studied - can we adapt some results to better understand Answer Sources?

Future/Ongoing Work

executable specification of ISO Prolog in terms of Kernel Prolog
a study of Kernel Prolog's invariance under program transformations (unfolding)
expressiveness of multi-engine Datalog (conjectured as being Turing-equivalent)
type checking / type inference mechanisms for Kernel Prolog
lightweight engine creation and engine reuse techniques for Kernel Prolog
adapting Kernel Prolog for spoken I/O, using a new prototype based Natural Language style predicate syntax
Kernel Prolog as a basis of embedded Prolog component technology and Prolog based Palm computing
implementation technique for lightweight Web based Kernel Prolog interpreters - XML

Conclusion

uniform interoperation of Horn Clause Solvers with stateful entities (Fluents) ranging from external procedural and object oriented language services like I/O operations, to other, 'first class citizen' Horn Clause Solvers
as a result, a simplified Prolog built-in predicate system has emerged
Fluent Composers allow combining component functionality in generic, data representation independent ways
Lightweight Prolog implementation

Looking through the Walls of the Glass Box: a Kernel Prolog Interpreter in Java:

 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;
 }

Unfolder class:

 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;
  }