The current focus of the operations is managed by object/1 and
message/1. Out/? puts a tuple Mes on the blackboard,
rd/? reads it and in/? removes it. Eval/? executes
the Goal part of the clause (Answer:-Goal) focussed by
object/1 and message/1. Then it puts the result
Answer back to the blackboard. As Answer itself can be
of the form (A:-G), a limited number of cascaded evals
are possible.
% out/1, rd/1, in/1
out(Mes):-object(Obj),message(Id),out(Obj,Id,Mes).
rd(Mes):-object(Obj),message(Id),rd(Obj,Id,Mes).
in(Mes):- object(Obj),message(Id),in(Obj,Id,Mes).
% out/2, rd/2, in/2
out(Id,Mes):-object(Obj),out(Obj,Id,Mes).
rd(Id,Mes):-object(Obj),rd(Obj,Id,Mes).
in(Id,Mes):-object(Obj),in(Obj,Id,Mes).
% out/3, rd/3, in/3
out(Obj,Id,_):-val(Obj,Id,_),!,fail.
out(Obj,Id,Mes):-saved(Mes,Sent),let(Obj,Id,Sent).
rd(Obj,Id,Mes):-val(Obj,Id,Mes).
in(Obj,Id,Mes):-val(Obj,Id,Mes),rm(Obj,Id).
% eval/0, eval/1, eval/2
eval:-object(Obj),message(Id),eval(Obj,Id).
eval(Id):-object(O),eval(O,Id).
eval(Obj,Id):-val(Obj,Id,(Answer:-Goal)),Goal,!,
saved(Answer,NewAnswer),
set(Obj,Id,NewAnswer).
% tools
object(New):-var(New),!,val('$object','$object',New).
object(New):-atomic(New),let('$object','$object',New).
message(New):-var(New),!,object(O),val(O,'$message',New).
message(New):-atomic(New),object(O),let(O,'$message',New).
CONTINUATIONS
as FIRST
ORDER OBJECTS
CONTINUATIONS
MANIPULATION VS.
INTUITIONISTIC /LINAIRE
IMPLICATION
Using intuitionistic implication (in fact, it should be -:
but let's forget this for a moment) we can write in BinProlog:
insert(X, Xs, Ys) :-
paste(X) => ins(Xs, Ys).
ins(Ys, [X|Ys]) :- paste(X).
ins([Y|Ys], [Y|Zs]):- ins(Ys, Zs).
used to nondeterministically insert an element in a list,
the unit clause paste(X) is available only within the scope of the
derivation for ins. This gives:
?- insert(a,[1,2,3],X).
X=[a,1,2,3];
X=[1,a,2,3];
X=[1,2,a,3];
X=[1,2,3,a]
With respect to the corresponding Prolog program
we are working with a simpler
formulation in which the element to be inserted does not have to percolate
as dead weight throughout each step of the computation, only to be used in
the very last step. We instead clearly isolate it in a global-value manner,
within a unit clause which will only be consulted when needed, and which
will disappear afterwards.
Now, let us imagine we are given the ability to write part of a proof state
context, i.e., to indicate in a rule's left-hand side not only the
predicate which should match a goal atom to be replaced by the rule's body,
but also which other goal atom(s) should surround the targeted one in
order for the rule to be applicable.
Given this, we could write, using BinProlog's @@
(which gives in its second argument the current continuation) a program
for insert/3 which strikingly resembles the intuitionistic
implication based program given above:
insert(X,Xs,Ys):-ins(Xs,Ys),paste(X).
ins(Ys,[X|Ys]) @@ paste(X).
ins([Y|Ys],[Y|Zs]):-ins(Ys,Zs).
Note that the element to be inserted is not passed to the recursive
clause of the predicate ins/2 (which becomes therefore simpler),
while the unit clause of the predicate ins/2 will communicate
directly with insert/3 which will directly `paste' the appropriate
argument in the continuation.
In this formulation, the element to be inserted is first given as
right-hand side context of the simpler predicate ins/2, and this predicate's
first clause consults the context paste(X) only when it is time to place it within the output list, i.e. when the fact ins(Ys,[X|Ys]),paste(X) is reached.
Thus for this example, we can also obtain the expressive power of
intuitionistic/linear implication
by this kind of (much more efficient)
direct manipulation of BinProlog's
first order continuations.
DIRECT BINAIRY
CLAUSE
PROGRAMMING
and
FULL-BLOWN
CONTINUATION
BinProlog 4.00 supports direct manipulation of binary clauses denoted
Head ::- Body.
They give full power to the knowledgeable programmer on
the future of the computation. Note that such a facility is not
available in conventional WAM-based systems where continuations
are not first-order objects.
We can use them to write programs like:
member_cont(X,Cont)::-
strip_cont(Cont,X,NewCont,true(NewCont)).
member_cont(X,Cont)::-
strip_cont(Cont,_,NewCont,member_cont(X,NewCont)).
test(X):-member_cont(X),a,b,c.
A query like
?-test(X).
will return X=a; X=b; X=c; X=whatever follows from the calling point of test(X).
catch(Goal,Name,Cont)::-
lval(catch_throw,Name,Cont,call(Goal,Cont)).
throw(Name,_)::-
lval(catch_throw,Name,Cont,nonvar(Cont,Cont)).
where lval(K1,K2,Val) is a BinProlog
primitive which unifies Val with a backtrackable global logical
variable accessed by hashing on two (constant or variable)
keys K1,K2.
This allows for instance to avoid execution of the infinite loop
from inside the predicate b/1.
loop:-loop.
c(X):-b(X),loop.
b(hello):-throw(here).
b(bye).
go:-catch(c(X),here),write(X),nl.
Notice that due to its simple translation semantics this program
still has a first order reading and that BinProlog's lval/3
is not essential as it can be emulated by an extra argument passed
to all predicates.
Although implementation of catch and throw requires full-blown
continuations, we can see that at user level, ordinary
clause notation is enough.
BACKTRACKBLE
DESTRUCTIVE ASSIGNMENT
UPDATABLE LOGICAL
ARRAYS in
PROLOG:FIXING
the SEMANTICS
of
SETARG/3
Let us recall that setarg(I,Term,Value) installs
Value as the I-th argument of Term and takes care to
put back the old value found there on backtracking.
Setarg/3 is probably
the most widely used
(at least in SICStus, Aquarius, Eclipse, ProLog-by-BIM, BinProlog),
incarnation of backtrackable mutable arrays (overloaded
on Prolog's universal term type).
Unfortunately setarg/3 lacks
a logical semantics and is implemented differently in
in various systems. This is may be the reason
why the standardization (see its absence from the Prolog ISO Draft)
of setarg/3
can hardly reach a consensus in the predictable future.
Ideally, setarg/3 should work as if a new term
(array) had been created
identical to the old one, except for the given element.
There's no reason to `destroy' a priori the content of the updated
cell or to make it subject to ugly side effects. Should this have
to happen for implementation reasons, a run-time error should
be produced, at least, although
this is not the case in any implementation
we know of.
Let us start with an inefficient but fairly clean array-update
operation, setarg/4.
setarg(I,OldTerm,NewValue,NewTerm):-
functor(OldTerm,F,N),
functor(NewTerm,F,N),
arg(I,NewTerm,NewValue),
copy_args_except_I(N,I,OldTerm,NewTerm).
copy_args_except_I(0,_,_,_):-!.
copy_args_except_I(I,I,Old,New):-!,I1 is I-1,
copy_args_except_I(I1,I,Old,New).
copy_args_except_I(N,I,Old,New):-N1 is N-1,arg(N,Old,X),arg(N,New,X),
copy_args_except_I(N1,I,Old,New).
We can suppose that functor and arg are specified by a (finite)
set of facts describing their behavior on
the signature of the program. For a given program,
we can obviously see setarg/4 as being
specified similarly by a finite set of facts.
Furthermore,suppose that all
uses of setarg/3 are replaced by calls to setarg/4 with the new states
passed around with DCG-style chained variables.
This looks like a good definition of the intended meaning of
a program using setarg/3.
We will show that actual implementations (Sicstus and BinProlog)
can be made to behave accordingly to this semantics through a
small, source level wrapping into a suitable ADT.
Let '$box'/1 be a new functor not in the signature of any
user program. By defining
safe_arg(I,Term,Val):-arg(I,Term,'$box'(Val)).
safe_setarg(I,Term,Val):-setarg(I,Term,'$box'(Val)).
Using '$box'/1 in safe_arg/3 (safe_setarg/3)
ensures that cell I of the functor Term
will be indirectly accessed (updated) even if it contains a variable
which in a WAM would be created on place and therefore
it would be subject of unpredictable side-effects.
The reason of the draconian warning in some Prolog manuals
manual
- ...setarg is only safe if there is no further use of the old value of the replaced argument...
will therefore disappear and a purely logical setarg
(with a translation semantics expressible in
term of setarg/4) can be implemented.
Not only this ensures referential transparency
and allows normal
references to the old content of the updated
cells but it also makes incompatible implementations
of setarg (Sicstus, Eclipse, BinProlog) work exactly
the same way(6).
To finish the job properly, something like the following ADT
can be created.
new_array(Size,Array):-
functor(Array,'$array',Size).
update_array(Array,I,Val):-
safe_setarg(I,Array,Val).
access_array(Array,I,Value):-
safe_arg(I,Array,Value).
We suggest to use this ADT in your program instead of basic setarg
when performance is not an absolute requirement.
A new change_arg/3 builtin has been added to BinProlog to allow,
efficient failure-driven iteration with persistent information.
It works like setarg/3 except that side-effects are permanent.
Sould unsafe heap objects be generated through the precess
change_arg/3 signals a run-time error. This is not the case
as far the result is either a constant (which is does not need
new heap allocation) or the result of moving a preexistent
heap object to a new location.
For instance the (Haskell-style) fold/4 predicate
(see library/high.pl) uses change_arg/3 to avoid painful
iteration and slow side-effects on the dynamic database.
The implementation is competitive is speed
with hand-written explicitely recursive code and uses
only memory proportional to the size of the answer.
% fold,foldl based on safe failure driven destructive change_arg
foldl(Closure,Null,List,Final):-fold(Closure,Null,X^member(X,List),Final).
fold(Closure,Null,I^Generator,Final):-
fold0(s(Null),I,Generator,Closure,Final).
fold0(Acc,I,Generator,Closure,_):-
term_append(Closure,args(SoFar,I,O),Selector),
Generator,
arg(1,Acc,SoFar),
Selector,
change_arg(1,Acc,O),
fail.
fold0(Acc,_,_,_,Final):-
arg(1,Acc,Final).
?- foldl(+,0,[1,2,3],R).
?- fold(*,1,X^member(X,[1,2,3]),R).
'INVISIBLE'
GRAMMARS
By using backtrackable setarg/3 and logical global variables (lval/3)
we can implement easily
a superset of DCG grammars practically equivalent with
Peter VanRoy's Extended DCGs. We call them Hidden Accumulator Grammars
as no preprocessor is involved in their implementation.
It turns out that the technique
has the advantage of `meta-programming for free' (without the
expensive phrase/3), allows source level debugging and can be made
more space and time efficient than the usual preprocessing based
implementation. On real examples, their best
use is for writing a Prolog compiler
(they can contribute to the writing of compact and efficient code
with very little programming effort) and for large natural language processing systems.
Basically, they work as follows:
% tools
begin_dcg(Name,Xs):-lval(dcg,Name,Xs-Xs).
end_dcg(Name,Xs):-lval(dcg,Name,Xs-[]).
w(Word,Name):-
lval(dcg,Name,State),
State=_-[Word|Xs2],
setarg(2,State,Xs2).
begin_dcg(Xs):-begin_dcg(default,Xs).
end_dcg(Xs):-end_dcg(default,Xs).
w(Word):-w(Word,default).
% grammar
x:-ng,v.
ng:-a,n.
a:-w(the).
a:-w(a).
n:-w(cat).
n:-w(dog).
v:-w(walks).
v:-w(sleeps).
% test
go:-begin_dcg(Xs),x,end_dcg(Ys),write(Ys),nl,fail.
?- go.
[the,cat,walks]
[the,cat,sleeps]
[the,dog,walks]
[the,dog,sleeps]
[a,cat,walks]
[a,cat,sleeps]
[a,dog,walks]
[a,dog,sleeps]
The program can be found in progs/setarg_dcg.pl.
For reasons of efficiency (i.e. to equal or beat preprocessor based DCGs
in terms of both space and time)
BinProlog's `Hidden Accumulator Grammars' have been implemented in C and are
accessible through the following set of builtins:
dcg_connect/1 % works like 'C'/3 with 2 hidden arguments
dcg_def/1 % sets the first hidden DCG argument
dcg_val/1 % retrives the current state of the DCG stream
dcg_tell/1 % focus on a given DCG stream (from 0 to 255)
dcg_telling/1 % returns the number of the current DCGs stream
% INVISIBLE DCG connect operation: normally macro-expanded
'#'(Word):-dcg_connect(Word).
% example: ?-dcg_phrase(1,(#a,#b,#c),X).
dcg_phrase(DcgStream,Axiom,Phrase):-
dcg_telling(X),dcg_tell(DcgStream),
dcg_def(Phrase),
Axiom,
dcg_val([]),
dcg_tell(X).
Starting with BinProlog 3.33 dcg_tell/1 is backtrackable, mostly like
lval/3. Admissible values for X in dcg_tell(X) are ranging from 1 to
255, which gives (I hope) enough distinct DCG streams for any
application.
Invisible grammars consume no heap, as they are based on
backtrackable destructive assigment implemented with a technique
called value trailing like setarg/3. They
consume trail only when a nondeterministic situation (choice-point)
arrises.
If you try the following program:
% grammar
ax:-ng,v.
ng:-a,n.
a:-dcg_connect(the).
a:-dcg_connect(a).
n:-dcg_connect(cat).
n:-dcg_connect(dog).
v:-dcg_connect(walks).
v:-dcg_connect(sleeps).
go:-
st(H,T),
dcg_def(Xs),ax,dcg_val([]),
pp(Xs,H,T),nl,
fail.
st(H,T):-statistics(global_stack,[H,_]),statistics(trail,[T,_]).
pp(O,H0,T0):-
st(H1,T1),T is T1-T0,H is H1-H0,
write([heap=H,trail=T]),write('==>'),write(O),nl,fail.
pp(_,_,_).
it will print out something like:
[heap = 308,trail = 44]==>[the,cat,walks]
[heap = 308,trail = 32]==>[the,cat,sleeps]
[heap = 308,trail = 32]==>[the,dog,walks]
[heap = 308,trail = 20]==>[the,dog,sleeps]
[heap = 308,trail = 44]==>[a,cat,walks]
[heap = 308,trail = 32]==>[a,cat,sleeps]
[heap = 308,trail = 32]==>[a,dog,walks]
[heap = 308,trail = 20]==>[a,dog,sleeps]
BINPROLOG'S
C-INTERFACE
To be able to extend BinProlog and possibly embedd it as logic
engine in your no run-time fee application you will need
a BinProlog C-source code
licence. See the files SOURCE.LICENCE and PRICING for more information.
You can also interact with other languages under UNIX using the
bidirectional pipe based interface starting from BinProlog's Tcl/Tk
interfaced (see directory TCL).
The following sequence of quick examples shows how it works.
A DEMO
PROGRAM
Starting with version 3.39 the C-interface has been moved in
directory c_inter. The discussion which follows basically explains
the content of the files c.c c.h and c.pl in this directory.
Once BinProlog is correctly installed as file "bp" somewhere in
your path along with the libraries bp.o and wam.o which should
be in directory
../src and you have a C-compiler around, you can simply
do make in directory c_inter to create a standalone application
which integrates the functionality of the C-code in file c.c.
To test the resulting standalone executable c_binpro,
try out the demo c_test
defined in file c.pl.
Start running it by typing c_binpro
and then type c_test. at the
Prolog prompt. To avoid the prompt and directly launch
the application add main:-c_test." in file c.pl before
typing make.
CALLING C
from
BINPROLOG:
ADDING NEW
BUILTINS
New builtins are added in headers.pl and after a "make realclean; make"
a new version of BinProlog containing them is generated automatically.
Starting from headers.pl the system will first generate the files
defs.h, prof.h, builtins.pl and then recompile itself.
For this recompilation either a previous version of
BinProlog(7)or SICStus Prolog is used.
An example of declaration in headers.pl is:
b0(+/3,arith(1),in_body). % arity=3+1 by binarization
Notice that arith(1) means that it is "like an arithmetic functions" which returns one
value, i.e this should be used as in
+(0,1,Result).
I would suggest to start with the simplest form of interaction:
a call of your own C-code from BinProlog. Try modifying in the file
c.c (provided with the C-sources of BinProlog,
in directory c_inter),
the function new_builtin() which looks as follows:
/*
New builtins can be called from Prolog as:
new_builtin(0,,)
X(1) contains the integer `opcode' of your builtin
X(2) contains your input arg
regs[I] contains something that will be unified with what you return
(the precise value of I depends on the register allocator).
You are expected to `return' either
- a non-null object that will be unified with , or
- NULL to signal FAILURE
As the returned object will be in a register this
can be used for instance to add a garbage collector
that moves every data area around...
*/
term new_builtin(H,regs,A,P,wam)
register term H,regs,*A;
register instr P;
register stack wam;
{ BP_check_call();
switch(BP_op)
{
/* for beginners ... */
case 0:
/* this just returns your input argument (default behavior) */
break;
case 1:
BP_result=BP_integer(13); /* this example returns 13 */
break;
case 2:
BP_result=BP_atom("hello"); /* this example returns 'hello' */
break;
/* for experts ... */
case 3: /* iterative list construction */
{ cell middle,last,F1,F2; int i;
BP_make_float(F1, 77.0/2);
BP_make_float(F2, 3.14);
BP_begin_put_list(middle);
BP_put_list(BP_integer(33));
BP_put_list(F1);
BP_put_list(BP_string("hello"));
BP_put_list(F2);
BP_end_put_list();
BP_begin_put_list(last);
for(i=0; i<5; i++) {
BP_put_list(BP_integer(i));
}
BP_end_put_list();
BP_begin_put_list(BP_result);
BP_put_list(BP_string("first"));
BP_put_list(middle);
BP_put_list(last);
BP_put_list(F1);
BP_put_list(F2);
BP_end_put_list();
} break;
case 4: /* cons style list construction */
BP_begin_cons();
BP_result=
BP_cons(
BP_integer(1),
BP_cons(
BP_integer(2),
BP_nil
)
);
BP_end_cons();
break;
case 5: /* for hackers only ... */ ;
BP_result=(cell)H;
H[0]=g.DOT;
H[1]=X(2);
H[2]=g.DOT;
H[3]=BP_integer(99);
H[4]=g.DOT;
H[5]=(cell)(H+5); /* new var */
H[6]=g.DOT;
H[7]=(cell)(H+5); /* same var as previously created */
H[8]=g.DOT;
H[9]=BP_atom("that's it");
H[10]=g.NIL;
H+=11;
break;
case 6:
BP_fail();
break;
case 7:
{ cell T=BP_input;
if(BP_is_integer(T))
{fprintf(g.tellfile,"integer: %ld\n",BP_get_single_integer(T));
BP_result=BP_integer(-1);
}
else
BP_fail();
}
break;
case 8: /* for experts: calling BinProlog from C */
{ cell L,R,Goal;
BP_begin_put_list(L);
BP_put_list(BP_string("one"));
BP_put_list(BP_integer(2));
BP_put_list(BP_string("three"));
BP_put_list(BP_input); /* whatever comes as input */
BP_end_put_list();
BP_put_functor(Goal,"append",3);
BP_put_old_var(L);
BP_put_old_var(L);
BP_put_new_var(R);
BP_prolog_call(Goal); /* this will return NULL on failure !!!*/
BP_put_functor(Goal,"write",1);
BP_put_old_var(R);
BP_prolog_call(Goal); /* calls write/1 */
BP_put_functor(Goal,"nl",0);
BP_prolog_call(Goal); /* calls nl/0 */
BP_result=R; /* returns the appended list to Prolog */
}
break;
case 10: /* for experts: calling BinProlog from C */
{ cell L,R,Goal;
BP_begin_put_list(L);
BP_put_list(BP_string("one"));
BP_put_list(BP_integer(2));
BP_put_list(BP_string("three"));
BP_put_list(BP_input); /* whatever comes as input */
BP_end_put_list();
BP_put_functor(Goal,"cut_test",3); /* see c.pl */
BP_put_old_var(L);
BP_put_old_var(L);
BP_put_new_var(R);
BP_prolog_call(Goal); /* this will return NULL on failure !!!*/
BP_put_functor(Goal,"write",1);
BP_put_old_var(R);
BP_prolog_call(Goal); /* calls write/1 */
BP_put_functor(Goal,"nl",0);
BP_prolog_call(Goal); /* calls nl/0 */
BP_result=R; /* returns the appended list to Prolog */
}
break;
case 11: /* CALLING BinProlog on a NEW ENGINE from C*/
{ stack Engine;
cell Goal,Answer;
cell Xs,X;
BP_begin_put_list(Xs);
BP_put_list(BP_string("new_engine_test"));
BP_put_list(BP_input); /* whatever comes as input */
BP_put_list(BP_integer(100));
BP_put_list(BP_integer(200));
BP_put_list(BP_integer(300));
BP_end_put_list();
BP_put_functor(Goal,"member",2);
BP_put_new_var(X);
BP_put_old_var(Xs);
Engine=BP_create_engine(wam,100,50,50);
BP_load_engine(Engine,Goal,X);
while((Answer=(cell)ask_engine(Engine)))
{ cell Goal1;
BP_put_functor(Goal1,"write",1);
BP_put_old_var(X);
BP_prolog_call(Goal1); /* calls write/1 */
BP_put_functor(Goal1,"nl",0);
BP_prolog_call(Goal1); /* calls nl/0 */
}
BP_result=X; /* returns the now free variable */
BP_destroy_engine(Engine);
}
break;
case 12: /* CALLING from C BinProlog on a NEW ENGINE.
The friendliest way... */
{ stack Engine;
cell Goal,Answer;
cell Xs,X;
BP_sread("[0,s(0),s(s(0)),[a,b,c]]",Xs);
BP_put_functor(Goal,"member",2);
BP_put_new_var(X);
BP_put_old_var(Xs);
Engine=BP_create_engine(wam,100,50,50);
BP_load_engine(Engine,Goal,X);
while((Answer=(cell)ask_engine(Engine)))
{
printf("Answer = %s\n",BP_swrite(Answer));
}
BP_result=X; /* returns the now free variable */
BP_destroy_engine(Engine);
}
break;
/* EDIT AND ADD YOUR CODE HERE....*/
default:
return LOCAL_ERR(X(1),"call to unknown user_defined C function");
}
return H;
}
CALLING
PROLOG from
C
Normally this is done after a first call from Prolog to C
(this gives a chance to the prolog system to get initialized).
The most flexible technique is based on mutiple engines. Take a look
at case 11 and case 12 in the previous section.
The lower-level interface, (which follows) is still usable
but less recommended.
/* this can be used to call Prolog from C : see example if0 */
term bp_prolog_call(goal,regs,H,P,A,wam)
register term goal,regs,H,*A;
register instr P;
register stack wam;
{
PREP_CALL(goal);
return bp(regs,H,P,A,wam);
}
/* simple example of prolog call */
term if0(regs,H,P,A,wam)
register term regs,H,*A;
register instr P;
register stack wam;
{ term bp();
cell goal=regs[1];
/* in this example the input GOAL is in regs[1] */
/* of course you can also build it directly in C */
/* unless you want specific action on failure,
use BP_prolog_call(goal) here */
H=bp_prolog_call(goal,regs,H,P,A,wam);
if(H)
fprintf(stderr,"success: returning from New WAM\n");
else
fprintf(stderr,"fail: returning from New WAM\n");
/* do not forget this !!! */
return H; /* return NULL to signal failure */
}
BinProlog's main() should be the starting point of your program
to be able to initialize all data areas. To call back from C you
can follow the example if0. A sustained BinProlog-C dialog
can be set up by using the 2 techniques described previously.
An example of using the C-interface (composed of files c.h c.c c.pl)
can be found in directory c_inter.
If you whish you can create
a standalone C-executable by using BinProlog's compilation to C
(see directories pl2c, dynpl2c) you can
simply type `make' in directory c_inter.
EXAMPLE
PROGRAMS
The directory progs contains a few BinProlog benchmarks and applications.
allperms.pl: permutation benchmarks with findall
bestof.pl: an implementation of bestof/3
bfmeta.pl: breadth-first metainterpreter
bp.pl: float intensive neural net learning by back-propagation
cal.pl: calendar: computes the last 10000 fools-days
fcal.pl: calendar: with floats
chat.pl: CHAT parser
choice.pl: Choice-intensive ECRC benchmark
cnrev.pl: nrev with ^/2 as a constructor instead of ./2
cube.pl: E. Tick's benchmark program
fibo.pl: naive Fibonacci
ffibo.pl: naive Fibonacci with floats
hello.pl: example program to create stand-alone Unix application
knight.pl: knight tour to cover a chess-board (uses the bboard)
lknight.pl: knight tour to cover a chess-board (uses the lists)
ltak.pl: tak program with lemmas
lfibo.pl: fibo program with lemmas
lq8.pl : 8 queens using global logical variables
maplist.pl: fast findall based maplist predicate
nrev.pl: naive reverse
nrev30.pl: small nrev benchmark to reconsult for the meta-interpreter
or.pl: or-parallel simulator for binary programs (VT100)
other_bm*: benchmark suite to compare Sicstus, Quintus and BinProlog
puzzle.pl: king-prince-queen puzzle
q8.pl: fast N-queens
qrev.pl: quick nrev using builtin det_append/3
subset.pl: findall+subset
tetris.pl: tetris player (VT100)
RELATED WORK
Some BinProlog related papers can be found at
clement.info.umoncton.ca in the file papers.tar.Z.
The reader interested in the internals of BinProlog and other
issues related to binary logic programs, their transformations
and performance evaluation is referred to
[Tarau90:PLILP],[Tarau91:JAP],
[Tarau91:RU],[Demoen90:KUL],
[Demoen91:RU], [Tarau92:WAMOpt],
[Tarau92:ECO],[LOPSTR93:Neumerkel],
[Neum92],
[Tarau93:GULP],
[Tarau93a],[kdb93f],
[WA83],
[lindgren], [TD94:WE],
[TA94:JFPL],
[TN94:PLILP],[kdb93j],[kdb93d]
REFERENCES
-
[kdb93f] K. De Bosschere and P. Tarau.
- Blackboard-based logic programming. In Proceedings of the 1993
ILPS Conference, Vancouver, Canada, 1993, poster.
-
[kdb93d] K. De Bosschere and P. Tarau.
- Blackboard Communication in Logic Programming, In Proceedings of the PARCO'93 Conference, Grenoble, France, Sept. 1993
-
[kdb93j] K. De Bosschere and P. Tarau.
- High Performance Continuation Passing Style Prolog-to-C Mapping.
In E.Deaton, D.Oppenheim, J.Urban and H.Berghel, editor, In Proceedings of the 1994 ACM Symposium on Applied Computing, pages 383-387, Phoenix/AZ,
Mar. 1994. ACM Press
-
[Demoen90:KUL] B. Demoen.
- On the Transformation of a Prolog Program to a more efficient Binary Program. Technical Report 130, K.U.Leuven, Dec. 1990.
-
[Demoen91:RU] B. Demoen and A. Marien.
- Implementation of Prolog as binary definite Programs, In A. Voronkov, editor, Logic Programming, RCLP Proceeding, number 592 in Lecture Notes in Artificial Intelligence, pages 165-176, Berlin, Heidelberg, 1992. Springer-Verlag.
-
[lindgren] T. Lindgren.
- Compiling logic programs using a binary continuation style, Dec. 1992.
draft, Uppsala University.
-
[Neum92] U. Neumerkel.
- Specialization of Prolog Programs with Partially Static Goals and Binarization, PhD thesis,Technische Universitat Wien, 1992.
-
[LOPSTR93:Neumerkel] U. Neumerkel.
- A transformation based on the equality between terms. In
Logic Program Synthesis and Transformation, LOPSTR 1993.
Springer-Verlag, 1993.
-
[Tarau91:JAP] P. Tarau.
- A Simplified Abstract Machine for the Execution of Binary
Metaprograms. In Proceedings of the Logic Programming Conference'91
pages 119-128, ICOT, Tokyo, Jul. 1991.
-
[Tarau92:ECO] P. Tarau.
- Ecological Memory Managment in a Continuation Passing Prolog Engine.
In Y. Bekkers and J. Cohen, editor, Memory Management International Workshop IWMM 92 Proceedings, number 637 in Lecture Notes in Computer Science,
pages 344-356. Springer, Sept. 1992.
-
[Tarau91:RU] P. Tarau.
- Program Transformations and WAM-support for the Compilation of Definite Metaprograms. In A. Voronkov, editor, Logic Programming, RCLP Proceedings, number 592 in Lecture Notes in Artificial Intelligence,
pages 462-473, Berlin, Heidelberg, 1992. Springer-Verlag.
-
[Tarau92:WAMOpt] P. Tarau.
- WAM-optimizations in BinProlog: towards a realistic Continuation Passing Prolog Engine.Technical Report 92-3, Dept. d'Informatique, Universite de Moncton, Jul. 1992. available by ftp from clement.info.umoncton.ca
-
[Tarau93a] P. Tarau.
- An efficient specialization of the WAM for continuation passing binary programs. In Proceedings of the 1993 ILPS Conference, Vancouver, Canada
1993. poster.
-
[Tarau93:GULP] P. Tarau.
- Language issues and programming techniques in BinProlog. In
D. Sacca, editor, Proceeding of the GULP'93 Conference,
Gizzeria Lido, Italy, June 1993.
-
[TA94:JFPL] P. Tarau.
- Low level issues in implementing a high-performance continuation passing binary prolog engine. In M.-M. Corsini, editor, Proceedings of JFPL'94
-
[Tarau90:PLILP] P. Tarau and M. Boyer.
- Elementary Logic Programs.In P. Deransart and J. Maluszynski, editor,
Proceedings of Programming Language Implementation and Logic Programming,
number 456 in Lecture Notes in Computer Science, pages 159-173.
Springer, Aug. 1990.
-
[TD94:WE] P. Tarau and B. Demoen.
- Language embedding by dual compilation and state mirroring.
In Proceedings of 6-th Workshop on Logic Programming Environments, Santa Margherita Ligure, 1994, June 1994.
-
[tdb95] P. Tarau, B. Demoen and K. De Bosschere.
- The power of partial translation: an experiment with the c-ification of binary prolog. In Proceedings of the 1995 ACM Symposium on Applied
Computing, Nashville/TN, Feb. 1995. ACM Press.
-
[TN94:PLILP] P. Tarau and U. Neumerkel.
- A Novel Term Compression Scheme and Data Representation in the BinWAM.
In Proceedings of Programming Language Implementation and Logic Programming, Lecture Notes in Computer Science. Springer, Sept. 1994.
-
[WA83] D. H. D. Warren.
- An Abstract Prolog Instruction Set. Technical Note 309,
SRI International, Oct. 1983.
APPENDIX
Here is the list of currently visible public predicates exported
by module Prolog.
!/0
(#)/1
(#)/3
* /3
(+)/2
(+)/3
(++)/3
(,)/2
(-)/2
(-)/3
(-:)/2
(->)/2
(.)/2
(.)/3
/ /3
// /3
(/\)/3
(:)/2
(:=:)/2
(;)/2
(<)/2
<< /3
(=)/2
(=..)/2
(=:=)/2
(=<)/2
(==)/2
(=>)/2
(=\=)/2
(>)/2
(>=)/2
>> /3
(@<)/2
(@=<)/2
(@>)/2
(@>=)/2
C/3
(\)/2
(\)/3
(\+)/1
(\/)/3
(\=)/2
(\==)/2
^ /2
abolish/2
abort/0
acos/2
add_cont/3
add_instr/4
add_true/2
all/3
all_but_at_least/4
append/3
appendN/2
append_conj/3
append_disj/3
apropos/1
apropos/2
arg/3
argn/3
arith_dif/2
arith_eq/2
asin/2
ask_engine/2
asm/0
asm/1
assert/1
asserta/1
assertz/1
assumed/1
assumei/1
assumel/1
atan/2
atom/1
atomic/1
bagof/3
bb/0
bb/1
bb_change_arg/3
bb_def/2
bb_def/3
bb_element/2
bb_get/4
bb_let/2
bb_let/3
bb_list/1
bb_list0/3
bb_op/3
bb_put/2
bb_reset/0
bb_rm/1
bb_rm/2
bb_set/2
bb_set/3
bb_val/2
bb_val/3
boot/0
bu0/3
bu1/1
bu_ctr/2
call/1
change_arg/3
char_in_cmd/2
clause/2
cmake/0
cmake/1
cmake/2
cnl/0
co/0
compare/3
compare0/3
compile/1
compound/1
consult/1
copy_term/2
copy_term/3
cos/2
create_engine/4
ctime/1
current_module/1
current_op/3
current_predicate/1
current_predicate/2
cwrite/1
dcg_connect/1
dcg_def/1
dcg_phrase/2
dcg_phrase/3
dcg_tell/1
dcg_telling/1
dcg_val/1
debug/1
def/3
destroy_engine/1
det_append/3
det_append0/3
dir/0
display/1
do_body/1
drop_at_least/2
(dynamic)/1
ed/0
edit/0
edit/2
emacs/0
erase/1
errmes/2
exists_file/1
exp/2
expand_term/2
expr/2
fail/0
false/0
fast_write/1
file_extension_list/1
file_library/2
file_search_path/1
find_at_most/4
find_file/2
find_while/4
findall/3
findall/4
findall_conj/3
findall_conj/4
findall_disj/3
findall_disj/4
findall_load_heap/1
findall_store_heap/1
findall_workhorse/5
float/1
float/2
float_fun/3
float_fun2/4
flush/0
for/3
free_variables/4
functor/3
gc_call/1
gc_read/1
gc_read_clause/1
gensym/2
get/1
get0/1
get_code/1
greater/2
greater_eq/2
ground/1
halt/0
halt/1
has_fuel/1
help/1
if/3
if0/3
include/1
init_gensym/1
input_float/4
instance/2
integer/1
integer/2
interactive/1
(is)/2
is_assumed/1
is_builtin/1
is_compiled/1
is_dynamic/1
is_module/1
is_prolog/1
is_public/1
iso_close_stream/2
iso_eof/1
iso_get_byte/2
iso_lseek/4
iso_open_stream/3
iso_peek_byte/2
iso_put_byte/2
iso_read_term/3
iso_write_term/3
ith_clause/4
kcmake/0
keysort/2
kmake/0
length/2
less/2
less_eq/2
let/3
lift_heap/2
list2term/2
list_asm/3
listing/0
listing/1
listing/2
log/2
log/3
ls/0
lval/3
lwrite/1
main/1
make/0
make/1
make/2
make/4
make/5
make0/4
make_appl/1
make_cmd/2
make_executable_unix_appl/3
make_file_name/4
member/2
member_i/4
meta_interpreter/1
metacall/1
mod/3
(module)/1
(module)/2
module_call/2
module_name/3
module_predicate/3
modules/1
my_edit/1
name/2
new_builtin/3
nl/0
nonvar/1
(nospy)/1
(not)/1
notepad/0
nth_answer/2
nth_member/3
number/1
numbervars/3
older_file/2
op/3
op0/3
or/2
otherwise/0
patch_it/4
phrase/2
phrase/3
pico/0
portable_display/1
portray/1
portray_clause/1
pow/3
pp_clause/1
pp_term/1
predicate_property/2
print/1
profile/0
(public)/1
put/1
put_code/1
quiet/1
quietmes/1
random/1
read/1
read_clause/1
read_term/2
read_tokens/2
read_with_singletons/3
reconsult/1
repeat/0
restart/0
retract/1
retractall/1
rm/2
saved/2
see/1
see_at/1
see_tell/2
see_tell_at/2
seeing/1
seeing_at/1
seeing_telling/2
seeing_telling_at/2
seen/0
seen_told/1
self_info/1
set/3
set_c_threshold/1
set_c_trace/1
setarg/3
setof/3
setref/2
shell/1
show_code0/2
sin/2
skip_until/2
skip_when/2
sort/2
(spy)/1
spy_goal/1
spying/1
sqrt/2
sread/2
load_engine/3
stat0/3
stat_dict/2
statistics/0
statistics/2
string_op/3
strip_cont/3
strip_cont0/2
swrite/2
symcat/3
system/1
tab/1
take_at_most/2
tan/2
tell/1
tell_at/1
telling/1
telling_at/1
term2list/4
term_append/3
term_chars/2
termcat/3
textedit/0
told/0
top_read_term/2
toplevel/0
tr_body/2
trace/1
true/0
ttyin/1
ttynl/0
ttyout/1
ttyprin/1
ttyprint/1
ttyput/1
ttywrite/1
ttywriteln/1
unix/1
unix_access/2
unix_argc/1
unix_argv/2
unix_cd/1
unix_getenv/2
unix_kill/2
user_error/2
val/3
var/1
vars_of/2
vi/0
warn_singletons/3
while/2
write/1
write_float/1
writeq/1
BinProlog's default operator definitions (see file oper.pl) are the following:
:-op(1000,xfy,',').
:-op(1100,xfy,(';')).
:-op(1200,xfx,('-->')).
:-op(1200,xfx,(':-')).
:-op(1200,fx,(':-')).
:-op(700,xfx,'is').
:-op(700,xfx,'=').
:-op(500,yfx,'-').
:-op(500,fx,'-').
:-op(500,yfx,'+').
:-op(500,fx,'+').
:-op(400,yfx,'/').
:-op(400,yfx,'*').
:-op(650,xfy,'.').
:-op(700,xfx,'>=').
:-op(700,xfx,'>').
:-op(700,xfx,'=<').
:-op(700,xfx,(<)).
:-op(700,xfx,(=\=)).
:-op(700,xfx,(=:=)).
:-op(300,fy,(~)).
:-op(200,xfy,(^)).
:-op(300,xfx,(mod)).
:-op(400,yfx,(>>)).
:-op(400,yfx,(<<)).
:-op(400,yfx,(//)).
:-op(500,yfx,(#)).
:-op(500,fx,(#)).
:-op(500,yfx,(\/)).
:-op(500,yfx,(/\)).
:-op(700,xfx,(@>=)).
:-op(700,xfx,(@=<)).
:-op(700,xfx,(@>)).
:-op(700,xfx,(@<)).
:-op(700,xfx,(\==)).
:-op(700,xfx,(==)).
:-op(700,xfx,(=..)).
:-op(700,xfx,(\=)).
:-op(900,fy,(not)).
:-op(900,fy,(\+)).
:-op(900,fx,(spy)).
:-op(900,fx,(nospy)).
:-op(1050,xfy,(->)).
:-op(1050,xfx,(@@)).
:-op(1150,fx,(dynamic)).
:-op(1150,fx,(public)).
:-op(1150,fx,(module)).
:-op(1200,xfx,(::-)).
:-op(900,yfx,(:)).
:-op(600,xfx,(:=:)).
:-op(950,xfy,(-:)).
:-op(950,xfy,(=>)).
:-op(600,xfx,(<=)).
:-op(700,xfx,(=:)).
:-op(700,xfx,(:=)).
(1)
BinProlog Copyright (C) Paul Tarau 1992-94 All rights reserved
(2)
Take care if you use your own binary clauses to keep always
the continuation as a last argument of the last embedded continuation `predicate'.
Look at the asm/0 tracer how BinProlog itself does this.
(3)
Is/2 now accepts execution of any predicate of arity n+1 as a function
of arity n.
(4)
This is usually better to be left to a system person who also can ensure that users
inherit the BP_PATH environment variable. An individual user
can also put something like setenv BP_PATH /usr/local/BinProlog
his or her .cshrc or .login file, to access the shared
BinProlog programs.
(5)
We suggest avoiding these operations because they are not garbage collection-safe in
BinProlog 4.00.
(6)
A further ambiguity in some implementations of setarg/3 comes from the fact
that it is not clear if the location itself or its dereferenced contents should be mutated
(7)
Use "make remake" if BinProlog is the only Prolog around.