BINPROLOG 4.00
USER GUIDE



 
Paul Tarau

Departement d'Informatique Universite de Moncton, Moncton, Canada, E1A 3E9, tarau@info.umoncton.ca, September 7, 1995


INTRODUCTION to BINPROLOG

  1. Binarization
  2. Machines Supported

USING BINPROLOG

  1. The Interactive Toplevel Shell
  2. Using Multiple Logic Engines
  3. Findall/3 with Multiple Engines
  4. Communication through Linear Assumptions
  5. Real Standalone Applications through Compilation to C
  6. Unix Pseudo-Executables
  7. Some Limitations/Features of BinProlog
  8. Other BinProlog Goodies and New Predicates
  9. Efficient Findall Based Meta-Programming
  10. Builtins

COMPILING to C

  1. Performance of C-Ified Code

THE BLACKBOARD

  1. Global Logical Variables
  2. Garbage-Collectible Permanent Objects.
  3. Assert and Retract
  4. Assumed Code, Intuitonistic and Linear Implication
  5. Overriding
  6. Language Enhancements Based on Linear Implication
  7. Problem Solving with Linear Implication
  8. The Blackboard as an Alternative to Assert and Retract
  9. The Low-Level Blackboard Operations
  10. An Useful Prolog Extension: Bestof/3
  11. Blackboard Based Abstract Data Types
  12. Blackboard Based Problem Solving
  13. A Linda Style Interface to the Blackboard

CONTINUATIONS as FIRST ORDER OBJECTS

  1. Continuation Manipulation VS. Intuitionistic/Linear Implication

BACKTRACKBLE DESTRUCTIVE ASSIGNMENT

  1. Updatable Logical Arrays in Prolog: Fixing the Semantics of Setarg/3

BIN PROLOG'S C-INTERFACE

  1. A Demo Program
  2. Calling C from BinProlog: Adding New Builtins
  3. Calling Prolog from C


INSTALLATION

EITHER:

    Edit `Makefile'. Change BINDIR and comment out ARCH_AND_OS,
    for example:

    BINDIR = /usr/local/bin
    ARCH_AND_OS = sparc.sunos

    then TYPE:
 
        make install

OR:

   Copy or symbolically link bin/bp.  to `bp'
   somewhere in your path, then type `bp'.

Normally the appropriate bp file (a C-ified self contained executable) is all you need to have BinProlog 4.00 running. For PCs, unzip the bp400.zip file and copy the 32 bit DOS or Windows (3.x, 95 or NT) file somewhere in your PATH. For the go32 based version you will have to edit bp.bat with your path information and then type bp. Something like `go32 ru.386 wam.bp' directly in the distribution directory should also work.
To start BinProlog use
$  bp  command-line options  wam-bytecode-file
or simply
$  bp
Sizes of the blackboard, heap, stack, trail and code areas can be passed as command line parameters etc, in Kbytes:

usage: [-h heap] [-s stack] [-t trail] [-c code] [-b bboard] [-a 2^atoms] [-d 2^hashtable entries] [-i size of IO-buffer] [-q quietness] wamfile (default: wam.bp).


OBTAINING BINPROLOG

The ORIGINAL DISTRIBUTION SITE for BinProlog(1) is:
    ftp clement.info.umoncton.ca (139.103.16.2)
in the directory:
    /pub/BinProlog.
The ftp server clement.info.umoncton.ca is a Sparcstation ELC with SUNOS 4.1.1). Please send comments and bug reports to binprolog@info.umoncton.ca.


INTRODUCTION to BINPROLOG

BinProlog has been designed and implemented by Paul Tarau mostly at the University of Moncton, Canada, and is based on his BinWAM abstract machine, a specialization of the WAM for the efficient execution of binary logic programs.
BinProlog is a fast and small Prolog compiler, based on the transformation of Prolog to binary clauses. The compilation technique is similar to the Continuation Passing Style transformation used in some ML implementations.
Although it (used to) incorporate some last minute research experiments, which might look adventurous at the first sight, BinProlog is a fairly robust and complete Prolog implementation featuring both C-emulated execution and generation of standalone applications by compilation to C. Some of its features are:
  • source-level transformation based stateless module system
  • dynamic code,
  • intuitionistic and linear implication,
  • efficient high-order programming builtins,
  • logical global variables,
  • backtrackable destructive assignment,
  • circular term unification,
  • extended DCGs (now built in the engine as `Hidden Accumulator grammars'),
  • continuation manipulation primitives,
  • a garbage-collected hashing based global dictionary for constant-time sparse arrays and graphs,
  • C-compatible floating point operations,
  • a C-interface etc.
New features added in version 3.30:
  • source-level modules
  • faster compilation to C and faster resulting C-code
  • very small (dynamically linked) standalone executables (5K) for Solaris 2.x
  • improved (fileevent based) Tcl/Tk interface now running under tcl7.4b2 and tk4.0b2
  • help/1 detecting near-matching predicate definitions
  • help warnings for singleton variables
  • spy/1 for debugging compiled code
New features added in version 4.00:
  • an efficient copyiing heap garbage collector developed by Bart Demoen and Geert Engels
  • new version of Multi-BinProlog developed by Koen de Bosschere
  • ability to start multiple engines from Prolog or C
  • improved C-interface now moved to its own directory c_inter
  • one file 32 bit DOS and Windows 3.1 executables (see directory pc)
The bp command starts the BinProlog toplevel.
Prolog sources for the compiler and builtins are in directory src.
The directories pl2c and dynpl2c contain various project (*.pro) files and a makefile for generating a standalone applications through compilation to C.
The directory TCL contains a bidirectional pipe based BinProlog to Tcl/Tk interface.
The directory cparser contains Koen De Bosschere's ISO Prolog parser (written in C) and BinProlog standalones based on the parser (cbp.*).
The directory multi contains Koen De Bosschere's a blackboard based distributed programming extension to BinProlog and BinProlog executables which integrate them (mbp.*).

BINARIZATION

BinProlog is a small, program-transformation based compiler. Everything is converted to Continuation Passing Binary Clauses:

A rule like

    a(X):-b(X),c(X,Y),d(Y).
becomes
    a(X,Cont):-b(X,c(X,Y,d(Y,Cont))).
A fact like
    a(13).
becomes
    a(13,Cont):-true(Cont).
A predicate using metavariables like
    p(X,Y):-X,Y.
becomes
    p(X,Y,Cont);-call(X,call(Y,Cont))).
with true/1 and call/2 efficient builtins in BinProlog.
You can now try out in BinProlog 4.00 your own binary programs by using ::- instead of :- so that the preprocessor will not touch them(2). Otherwise, from the outside, BinProlog looks like any other Prolog.
Binarization allows a significant simplification of the Prolog engine, which can be seen as specialization of the WAM for the execution of Continuation Passing Binary Programs.
As a consequence, a very small emulator (about 60K on Solaris) that often fits completely in the cache of the processor, a more efficient new data representation and some low-level optimizations make BinProlog probably the fastest freely available C-emulated Prolog at this time (812 KLIPS on a Sparcstation 20-41).
This means 3-5 times faster than C-Prolog, 2-3 times faster than SWI-Prolog, 1.5-2 times faster than (X)SB-Prolog and close to C-emulated Sicstus 2.1.

MACHINES SUPPORTED

This distribution contains the Prolog source of the compiler and executable emulators for:
  - Sparc - SunOS 4.x, Solaris 2.x;
  - DEC Alpha - 64 bit
  - 68k NeXT - Mach; SUN3 - SunOS 4.x
  - MIPS - DEC and SGI;
  - IBM R6000;
  - 386-486-Pentium (MsDOS+Windows - with 32bits DOS-extender 
    go32 ver. 1.10, Linux, FreeBSD).
As the implementation makes no assumption about machine word size it is likely to compile even on very strange machines that have a C-compiler. BinProlog's integers are inherited from the native C-system. For example on DEC ALPHA machines BinProlog has 64 - 3 = 61 bit integers. On 32-bit systems it has 32 - 2 = 30 bit integers. Floating point is double (64 bits) and it is guaranteed that computations in Prolog will always give the same results as in the underlying C. As a matter of fact BinProlog does not really know that it has floats but how this happens is rather long to explain here.


USING BINPROLOG

BinProlog uses R.A. O'Keefe's public domain tokenizer and parser and write utilities (see the files read.pl, write.pl), DCGs and a transformer to binary programs. It compiles itself in less than 1 minute on a Sparcstation 10-40.
The system has very fast (heap-based) copy_term/2, findall/3 and findall/4 predicates, floating point, global logical variables, but still lacks full garbage collection.
A new term compression technique [TN94:PLILP] (joint work with Ulrich Neumerkel) reduces heap-consumption and adds some extra speed . Ulrich's iterative copy_term/2 algorithm further accelerates BinProlog's `copy-once' heap-based findall/3 and findall/4 so that findall-intensive programs may run 2-3 times faster in BinProlog than in other (even native code) implementations.
All data areas are now user configurable, and all except the heap are garbage collected. A garbage collector for the heap will be released soon.
Although other Prolog's assert and retract primitives are emulated in BinProlog, their functionality has been decomposed in separate simpler operations that give also improved efficiency.
For permanent information BinProlog has a new, garbage-collected data area, the blackboard, where terms can be stored and accessed efficiently with a a 2-key hashing function using something like
?-bb_def(likes,joe,[any(beer),good(vine),vegetarian(food)]).
and updated with something like
?-bb_set(likes,joe,nothing).
or
?-bb_rm(likes,joe).
To get its value:
?-bb_val(likes,joe,What).
BinProlog 4.00 has also backtrackable global variables, with 2-keyed names.
Try:
?- Person=joe, friend#Person:=:mary, bb.
and then
?- friend # joe:=:X.
The blackboard can be used either directly or through an assert-retract style interface.
A small exercise: if you want backtrackable behaviour of assert and retract you can modify extra.pl and use A#B:=:X style global variables in their definition, instead of bb_def/3 etc.
The blackboard also gives constant-time sparse arrays and lemmas. For example try:
?- for(I,1,99),bb_def(table,I,f(I,I)),fail.
?- bb.
BinProlog 4.00 has Edinburgh behaviour and tries to be close to Sicstus and Quintus Prolog on the semantics of builtins without being too pedantic on what's not really important.
All the basic Prolog utilities are now supported (dynamic clauses, a metainterpreter with tracing facility, sort, setof, dynamic operators floating point operations and functions).
A fast deterministic append det_append/3 (i,i,o) has been added. Naive reverse using det_append/3 makes more than 3 MegaLIPS on a Sparc 20-41 (a 3-times speed-up).
Almost all the builtins are now expanded inline resulting in improved heap consumption and performance.
A few programs (an automatic Tetris player, a knight-tour, an OR-parallel simulator, Fibonacci, Tak with lemmas, a small neural-net simulator backprop.pl) illustrate some of the new features. A few well-known benchmarks have been added to help compare BinProlog with other implementations.
BinProlog has supported from start 30 bit integer arithmetic. Now it has also floating point operations and functions like sin, cos, tan, log, exp, pow, etc. They can be used either through the is/2 interface(3):
?- X is cos(3.14)+sin(0).
or in relational form
?- cos(1,X).
Note that you should use something like Y=3+4, X is 1+expr(Y) instead of Y=3+4, X is 1+Y which will not work in compiled code.
Floating point has the same precision and semantics as the type double in C. Floating point operations are close in speed to emulated Sicstus. To try them out use the toy neural-network simulator backprop.pl. This program uses also constant time arrays and is therefore unusually fast compared to its execution in other Prologs like Quintus or Sicstus.

THE INTERACTIVE TOPLEVELSHELL

To see the command line options:
      $  bp -help
To compile and load file or file.pl or file.pro
      ?-[file].
BinProlog searches them in the directories ., ./progs and ../src ../library, relative to the BP_PATH environment variable which defaults silently to the current directory if undefined. The dirctory ./myprogs is also searched for possible user programs. While compatible to previous configurations which where single user minded, this allows installing the BinProlog distribution for shared use in a place like /usr/local/BinProlog
(4)

USING MULTIPLE LOGIC ENGINES

A new (experimental) feature added starting with version 3.39 allows launching multiple Prolog engines having their own stack groups (heap, local stack and trail). An engine can be seen as an abstract data-type which produces a (possibly infinite) stream of solutions as needed. To create an engine use:
     % :-mode create_engine(+,+,+,-).
     create_engine(HeapSize,StackSize,TrailSize,Handle)
The Handle is a unique integer denoting the engine for further processing. To `fuel' the engine with a goal and an expected answer variable do:
     % :-mode load_engine(+,+,+).
     load_engine(Handle,Goal,AnswerVariable)
No processing except the initialization of the engine takes place and no answer is returned with this operation. Think about it as simply puting gas in your car.
To get an answer from the engine do:
     % :-mode ask_engine(+,-).
     ask_engine(Handle,Answer)
If you want to keep the answer for further processing before asking for the next one, use copy_term/2 as the original will go away as the engine backtracks. Note that nothing nasty (as unsafe references to dead heap cells) happens even if you forget to do this, except that the bindings in the `master' engine will be undone.
When the stream of answers reaches its end, ask_engine/2 will simply fail.
If for some reasons you are not interested in the engine anymore, do
     % :-mode destroy_engine(+).
     destroy_engine(Handle)
to free the data areas allocated for the engine. If you want to submit another query before using the complete stream of answers, it is more efficient to reuse an existing engine with load_engine/3, instead of destroying it and creating a new one.
Try out the following example (see more in files library/engines, progs/engtest.pl):
 ?-create_engine(256,64,64,E),
    load_engine(E,append(As,Bs,[A,B,B,A]),As+Bs),
    ask_engine(E,R1),write(R1),nl,
    ask_engine(E,R2),write(R2),nl,
    load_engine(E,member(X,[1,2,3]),X),
    ask_engine(E,R3),write(R3),nl,
    ask_engine(E,R4),write(R4),nl,
    destroy_engine(E).
As engines will be assigned to real processors in future multi-threaded implementations this reusability of a given engine for execution of multiple goals is intended to allow precise control to the programmer over the resurces of a system. Preemptive multitasking handled either with thread libraries, when available and efficient, or by BinProlog itself otherwise, is planned in the near future.
This `super-scalar' performance improvement can already be tested with the companion (Solaris 2.x only) Linda implementation in directory multi (see file multi/myprogs/mcolor.pl).
If an engine fails due to the overflow of a given data area, it will warn you and fail. The warnings are disabled with quietness levels higher than 6 (command line switch -q6). This allows use of engines to quietly recover from ressource errors.
For owners of BinProlog's C-source licenses, C-functions with similar names and semantics as the predicates described in this section are available to allow embedding of multiple independent Prolog engines in their C-applications.

FINDALL/3 with MULTIPLE ENGINES

The file library/engines.pl contains som examples of how multiple engines can be used for implementing for instance all-solution predicates. Here is a re-entrant find_all/3.
find_all(X,Goal,Xs):-
   default_engine_params(H,S,T),
   find_all(H,S,T,X,Goal,Xs).

find_all(H,S,T,X,Goal,Xs):-
   create_engine(H,S,T,Handle),
   load_engine(Handle,Goal,X),
   collect_answers(Handle,Xs),
   destroy_engine(Handle).

collect_answers(Handle,[X|Xs]):-ask_engine(Handle,A),!,
   copy_term(A,X),
   collect_answers(Handle,Xs).
collect_answers(_,[]).

default_engine_params(128,32,32).

COMMUNICATION THROUGH LINEAR ASSUMPTIONS

A more interesting application is based on the synergy between intuitionistic and linear implication and their continuation passing counterparts assumei/1 and assume/0 and multiple engines.
The following extension is available with :-[library(engines)].
The concrete syntax is Answer<=Producer=>Consumer or Answer<=Producer when the Consumer is the (implicit) current AND-continuation. Producer is started on a separate engine. It produces linear facts of the form Answer, from computed answers of Goal, originating fro distinct OR-branches. They are usable by Consumer as if they were assumed through use of linear implication, i.e. they are consumed one-by-one. This hides the intricacies of starting a new `orthogonal' logic engine into a simple, easy to use abstraction. The actual implementation follows (see also file library/engines.pl):
% executes Producer on an `orthogonal' OR-engine
Answer<=Producer=>Consumer:-!, % the consumer is explicit
   cross_run(Producer,Answer,Consumer).
Answer<=Producer:-             % the consumer is in the `future'
   cross_run_with_current_continuation(Producer,Answer).

cross_run(Producer,Answer,Consumer):-
   default_engine_params(H,S,T),
   cross_run(H,S,T,Producer,Answer,Consumer).

cross_run(H,S,T,Producer,Answer,Consumer):-
   compound(Answer),copy_term(Answer,A),
   new_engine(H,S,T,Producer,Answer,Handle),
  (A:-ask_or_kill(Handle,A))=>Consumer,
  destroy_engine(Handle).

cross_run_with_current_continuation(Producer,Answer):-
   default_engine_params(H,S,T),
   cross_run_with_current_continuation(H,S,T,Producer,Answer).

cross_run_with_current_continuation(H,S,T,Producer,Answer):-
   compound(Answer),copy_term(Answer,A),
   new_engine(H,S,T,Producer,Answer,Handle),
   assumei((A:-ask_or_kill(Handle,A))).

ask_or_kill(Handle,Answer):-ask_engine(Handle,Answer),!.
ask_or_kill(Handle,_):-destroy_engine(Handle),fail.

new_engine(H,S,T,Goal,Answer,Handle):-
   create_engine(H,S,T,Handle),
   load_engine(Handle,Goal,Answer).

% overridable default engine sizes for heap,stack,trail
default_engine_params(H,S,T):-assumed(engine_params(H,S,T)),!.
default_engine_params(128,32,32).
The following example shows how and OR-stream of answers seen as linear assumptions from an `orthogonal' engine can be used in and AND-branch.
?- a(X)<=member(X,[1,2,3])=>(a(A),a(B),a(C),write([A,B,C]),nl).

[1,2,3]
If found interesting, a truly parallel, highly efficient implementation will be made available in future releases.
The same abstraction is already supported in the companion Multi-BinProlog engine, through use of real Solaris 2.4 threads (see file multi/myprogs/ortho.pl. On multiple processor Sparcs this extension should allow super-linear speed-up, in the hands of a good programmer, as the answer is speculatively computed in parallel with the computations performed by Consumer,. We have verified that when multiple processors are available, Multi-BinProlog background processes will tend to execute on different processors, with super-linear speed-up (see file multi/myprogs/mcolor.pl and scripts seq, and par in the same directory).

REAL STANDALONE APPLICATIONS through COMPILATION to C

Starting with version 3.30 it is possible to separately compile user applications and just link them with the emulator library and the C-ified compiler (see directory pl2c,). This allows creation of a fully C-ified application in a few seconds.
Just type make PROJ=queens in directory pl2c. The standalone application queens is ready to be executed by typing queens. The generated C-code can be seen in files queens.h and queens.c.
Moreover, on systems with dynamic linking like Solaris 2.x true executables of size starting at about 6K can be created starting with version 3.30 (see directory dynpl2c).
If you define a predicate main/0 then your executable will start directly from there instead of the usual interactive top-level. Calling it with a high quietness-level (i.e. command line switch -q5) will suppress warnings and unwanted messages.

UNIX PSEUDO-EXECUTABLES

The following still works, although the new C-ification technique (see directories pl2c, dynpl2c) can now create true one-file standalones.

It is possible to create (as in the past) a small runtime application (called "newappl.bp"), from .pl as follows:

    ?-make_appl('.pl').
Deliver the appropriate "bp" file (the Prolog engine) with your application. The user must type:
        $ bp newappl.bp
to start it.

Note: the file must contain a clause

      main(X):-...
That's where execution starts. BinProlog's shell is nothing but such an application which starts with a toplevel loop i.e. something like:
      main(X):-toplevel(X).
As a new feature, you can override this behaviour, even for the standard BinProlog system containing the predicate main/1 (which starts the interactive top-level), by defining a predicate main/0 in your program file. In this case, main/0 becomes the new starting point.
You can also generate (on UNIX systems) stand-alone executables that dynamically start the emulator (thanks to Peter Reintjes for suggesting this). You can do something like:
 
% FILE: hello.pl

main(true):-write(hello),nl.

% DO:
% ?-make_executable_unix_appl(
%     '/usr/local/bin/bp -q5', % AbsolutePathToEmulator (q=quietness)
%     'hello.pl',              % SourceFile
%      hello).                 % ExecutableFile
In the case of the "hello.pl" program, the user must type, at the Unix prompt:
     $ hello
to start it.

The code of this primitive is at the end of the file co.pl.

Again, we recommend using the C-ification technique which can already speed up most applications and in the future will generate very fast code competitive with native code compilers.

You can bootstrap the compiler, after modifying the *.pl files by:

     ?- boot.
     ?- make.
or, similarly for any other project having a top *.pro file:
     ?-make(ProjectFile).
     ?-make(ProjectFile,Module).
or
     ?-cmake(ProjectFile).
     ?-cmake(ProjectFile,Module).
if you intend to generate C-code and possibly hide non-public predicates inside a module.

This allows to integrate your preferences and extensions written in Prolog to the BinProlog kernel.

Make sure you keep a copy the original wam.bp in a safe place, in case things go wrong when you type ?-boot.

SOME LIMITATIONS/FEATURES of BINPROLOG

We passed Occam's razor on a few "features" of Prolog that are obsolete in modern programming environments and on some others that are, in our opinion, bad software practice.
Only one file at a time can be compiled in the interactive environment:
    ?-[myfile].
or
    ?- compile(myfile).
Now BinProlog supports an include directive:
:-[include1].
:-[include2].
....
This suggest to make a project (*.pro) file using a set of include directives each refereing to a *.pl file. When compiled to a file (by using the ?-make(MyProject) command) a make-like memoing facility will avoid useless recompilation of the included (*.pl) files by creation of precompiled (*.wam) files. For large projects this is the recommended technique. Creation of C-ified standalone files is also possible (see the pl2c directory).

Programs that work well can be added to the BinProlog kernel. This avoids repeated recompilation of working code and predicates in the kernel are protected against name clashing.

New programs can be loaded in the interactive environment. When they work well, they migrate to the kernel. You can prepare a good Makefile to automate this job. When everything is OK you can deliver it as a run-time-only application. Releases after 3.30 contain a basic make facility which avoids to recompile included *.pl files when a newer *.wam file exists.
Programs are searched with suffixes "", ".pl", ".pro" in the directories ., ./progs and ./myprogs.
There's no limit on the number of files you can compile to disk:
    ?- compile(wam,[file1,file2,...],'application.bp').
Now BinProlog does implement consult/1, reconsult/1 and listing/0 for interpreted code but use of compile/1 is highly recommended instead. See the file extra.pl for the implementation. Faster than asserted code is so called assumed code (see the next sections) i.e. intuitionistic and linear implication.

Here are some other limitations/features:

  • Clauses of a predicate must be grouped.
  • Clauses having undefined predicates occurring right after the head are rejected.
  • ARITY is limited to 255.
  • Contrary to previous versions, an experimental but fairly robust copying heap garbage collector is now implemented (thanks to Bart Demoen and Geert Engels). nogc/0 switches it off, gc/0 switches it on. Gc activation messages can be made silent using quietness levels like -q3- on the command-line. Moreover, the blackboard, dynamic code space, the string space and the hashing table ARE garbage collected before loading a new program.
Mode is interactive by default (for compatibility with other Prologs) but if you use a modern, windows based environment you may want to switch it off with:
?- interactive(no). 
or turn it on again with
?- interactive(yes). 

OTHER BINPROLOG GOODIES and NEW PREDICATES

A few BinProlog specific predicates are available:
  • restart/0 - cleans every data area
  • cwrite/1 - fast but restricted write
  • symcat/3 (i,i,o) returns a new symbol of the form first_second.
  • gensym/2 (i,o) forms a new name of the form name_counter.
  • sread/2 (i,o) reads from a name a (ground) term, swrite(i,o) writes a term to a name.
  • term termcat/3 (i,i,o) adds its second argument as last argument of its first argument and returns the new term
  • term_chars/2 converts between a ground term and its string representation
  • not/1 is a form of sound negation
  • for/3 as for instance in ?-for(I,1,5),write(I),nl,fail generates a failure driven loop
It is a good idea to take a look at BinProlog's *.pl for other builtin-or-library predicates before implementing them yourself. The file write.pl contain various output predicates like
  • write/1
  • writeq/1
  • portray_clause/1
  • print/1
  • display/1
  • ttyprint/1
  • ttynl/1
You can extend BinProlog by adding new predicates to the file extra.pl and then use the predicate boot/0 defined in the file co.pl.

EFFICIENT FINDALL BASED META-PROGRAMMING

BinProlog's findall/3 is so efficient that you can afford (with some care) to use it instead of explicit (and more painful) first-order programs as in:
% maplist with findall
maplist(Closure,Is,Os):-
     Closure=..L1,
     det_append(L1,[I,O],L2),
     P=..L2,
     findall(O,map1(P,I,Is),Os).

map1(P,I,Is):-member(I,Is),P.
This can be used as follows:
?- maplist(+(1),[10,20,30],T).
=> T=[11,21,31]
Note that constructing Closure only once (although this may not be in any Prolog text-book!) is more efficient than doing it at each step.
The predicate gc_call(Goal) defined in the file lib.pl executes Goal in minimal space. It is explained in the Craft of Prolog by R.A. O'Keefe, MIT Press. Do not hesitate to use it. BinProlog offers a very fast, heap-oriented findall, so you can afford to use gc_call. In good hands, it is probably faster than using assert/retract or the usual mark-and-sweep garbage collector of other implementations.

BUILTINS

The following (user-level) builtins are supported, with semantics (intended to be) close to SICSTUS and QUINTUS Prolog.
fail/0
nl/0
var/1
nonvar/1
integer/1
atomic/1
+/3   % arithmetic offers also the usual is/2 interface
-/3
* /3
// /3
mod/3
<< /3
>> /3
/\ /3
\/ /3
# /3    % bitwise XOR
\ /3     % bitwise NOT
random/1 % returns an integer, not a float
get0/1
put/1
< /2
> /2
=< /2
>= /2
=:= /2
=\= /2
compare/3
seeing/1
seen/0
telling/1
told/0
copy_term/2
functor/3
arg/3
name/2
abort/0
is_compiled/1 % checks if a predicate is compiled
Other useful predicates are defined in the file lib.pl and work as expected.
true/0,
=/2,
.. -> .. ; ..
;/1
call/1
\+/1
repeat/0
findall/3
findall/4
for/3
numbervars/4
see/1
tell/1
system/1
statistics/0
statistics/2
atom/1
compound/1
=../2
length/2
tab/1
get/1
== /2
\== /2
A @< B 
A @> B
A @=< B
A @>= B 
compile/1 - see co.pl for the compiler
read/1  - see the file: read.pl
write/1 - see the file: write.pl
halt/0,
halt(ReturnCode),
listing/0, % only for interpreted code
listing(Pred,Arity),
assert/1,
asserta/1, 
assertz/1,
retract/1,
retractall/1
erase/1,
dynamic/1,
instance/2,
clause/2,
clause/3,
consult/1,   % usable for debugging or dynamic code
reconsult/1, % they override compiled definitions !!!
setof/3,
bagof/3, 
sort/3, 
keysort/3,
setarg/3, % backtrackable update of arg I of term T with new term X

is_builtin/1 % lists the system-level builtins (written in C):
current_predicate/1 % lists/checks existence of a  predicate/arity
predicate_property/2 % lists/checks if a property (arg 2) is associated with a head (arg 1)
Operators are defined and retrieved with
:-op/3, current_op/3. 
Including files are supported. For compile/1 use
:-compile(file). 
or
:-[file]. % this calls the compiler too !!!
For consulting included interpreted code within an embedding reconsult/1 use:
:-consult(file). 
in your (unique) top-level file. This overcomes the limitation of having only one top-level file.


SOURCE-LEVEL STATELES MODULES

(module)/1
current_module/1
is_module/1          - checks/generates an existing module-name
module_call/2, ':'/2 - calls a predicate hidden in a module
module_name/3        - adds the name of a module to a symbol
module_predicate/3   - adds the name of a module to a goal
modules/1            - gives the list of existing modules
The following example:
:-module m1.
:-public d/1.

a(1).
a(2).
a(3).
a(4).

d(X):-a(X).

:-module m2.

:-public b/1.

b(X):-c(X).

c(2).
c(3).
c(4).
c(5).
c(6).

:-module m3.

:-public test/1.

test(X):-b(X),d(X).

:-module user.

go:-modules(Ms),write(Ms),nl,fail.
go:-test(X),write(X),nl,fail.
Executiong ?-go. will generate the following output:
[user/0,m1/0,m2/0,m3/0]
2
3
4
Starting with version 3.30, predicates in the BinProlog system itself which are not intended to be used by applications, are hidden in the module prolog but can be accessed by calling them with 'prolog:my_predicate'(...).
Explicit naming of the module where the hidden predicate is defined should be used when call/1, findall/3 etc. uses a hidden predicate, even if it is in the module itself.
This draconian constraint is motivated by simplicity of BinProlog's stateless purely source-level module system. Basically predicates in a module have their names prefixed as in 'my_current_module:my_predicate' in a preprocessing step, except if they are declared public or are known to the system as being so (i.e. in the case of builtins).
This basic concept of modules (essentially the same as what can be achieved with extern and static, declarations in C) covers only compiled code, and is mostly intended to ensure multiple name spaces with a very simple semantics and no additional space or time overhead. On the other hand use of linear and intutionistic implication is suggested for dynamic modular and hypothetical reasoning constructs.
Meta-predicate declarations are not supported at this time (mostly because they are at least as cumbersome as just puting the right name extension in argument positions which require it :-)), but they might be added in the future if a significant number of users will ask to have them.
Note that builtins and predicates defined in a special module user are always public. A public predicate keeps its name unchanged in the global name space while hidden predicates have their names prefixed by the name of the module in their definitions and in all their statically obvious (first-order) uses.
Alternatively, module/2 allows to define a module and its public predicates with one declaration as in:
:-module(beings,[cat/4,dog/4,chicken/2,fish/0,maple/1,octopus/255]).


EDITING , APROPOS/1 , TRACE/1 , SPY/1 , NOSPY/1

To edit a file and then compile it use:
     ?- edit(,).
To edit and recompile the currently compiled file using the emacs editor type:
     ?- ed.
To edit and recompile the currently compiled file using the edit editor (under DOS) type:
    ?- edit.
To simply recompile the last file type:
    ?- co.
The debugger/tracer uses R.A. O'Keefe's public domain meta-interpreter. You can modify it in the file "extra.pl".

DCG-expansion is supported by the public domain file dcg.pl.

To debug a file type:
?- reconsult(FileName).
and then
?- trace(Goal).
For interactivity, both the toplevel and the debugger depend on
?-interactive(yes).
or
?-interactive(no).
My personal preference is using interactive(no) within a scrollable window. However, as traditionally all Prologs hassle the user after each answer BinProlog 4.00 will do the same by default.
If you forget the name of some builtin, apropos/1 (or help/1) will give you some (flexible up to one misspelled or missing letter) matches with their arities.
You can use the debugger to debug compiled code with the following trick if you always debug bottom-up i.e. if you ensure that tools work before to using them. For example, on top of the compiled file allperms.pl you can temporarily interpret perm/2, insert/3 etc. to be able to trace them while keeping uninteresting predicates compiled. By the way, this allows, to trace/debug parts of the kernel itself in particular.
The following terminal session shows an example:
?- [allperms].
compiling(to(mem),progs/allperms.pl,...)
compile_time(230)
?- consult(user).
% using compile/1 is MUCH faster
reconsulting(user)
g0(N):-nats(1,N,Ns),perm(Ns,_),fail.
g0(_).
WARNING: redefining compiled predicate(g0/1)
perm([],[]).
perm([X|Xs],Zs):-
        perm(Xs,Ys),
        insert(X,Ys,Zs).

insert(X,Ys,[X|Ys]).
insert(X,[Y|Ys],[Y|Zs]):-
        insert(X,Ys,Zs).
WARNING: redefining compiled predicate(perm/2)
WARNING: redefining compiled predicate(insert/3)
reconsulted(user,time = 20)
yes
?- interactive(no).
yes
?- trace(g0(3)).
Call: g0(3)
 Call: nats(1,3,_645)
  compiled(nats(1,3,_645))
 Exit: nats(1,3,[1,2,3])
 Call: perm([1,2,3],_648)
   Call: perm([2,3],_1095)
    Call: perm([3],_1362)
     Call: perm([],_1629)
     Exit: perm([],[])
     Call: insert(3,[],_1362)
     Exit: insert(3,[],[3])
    Exit: perm([3],[3])
    Call: insert(2,[3],_1095)
    Exit: insert(2,[3],[2,3])
   Exit: perm([2,3],[2,3])
   Call: insert(1,[2,3],_648)
   Exit: insert(1,[2,3],[1,2,3])
  Exit: perm([1,2,3],[1,2,3])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[1,2,3])
   Redo: insert(1,[2,3],[1,2,3])
    Call: insert(1,[3],_2683)
    Exit: insert(1,[3],[1,3])
   Exit: insert(1,[2,3],[2,1,3])
  Exit: perm([1,2,3],[2,1,3])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[2,1,3])
   Redo: insert(1,[2,3],[2,1,3])
    Redo: insert(1,[3],[1,3])
     Call: insert(1,[],_2945)
     Exit: insert(1,[],[1])
    Exit: insert(1,[3],[3,1])
   Exit: insert(1,[2,3],[2,3,1])
  Exit: perm([1,2,3],[2,3,1])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[2,3,1])
   Redo: insert(1,[2,3],[2,3,1])
    Redo: insert(1,[3],[3,1])
     Redo: insert(1,[],[1])
     Fail: insert(1,[],_2945)
    Fail: insert(1,[3],_2683)
   Fail: insert(1,[2,3],_648)
   Redo: perm([2,3],[2,3])
    Redo: insert(2,[3],[2,3])
     Call: insert(2,[],_2421)
     Exit: insert(2,[],[2])
    Exit: insert(2,[3],[3,2])
   Exit: perm([2,3],[3,2])
   Call: insert(1,[3,2],_648)
   Exit: insert(1,[3,2],[1,3,2])
  Exit: perm([1,2,3],[1,3,2])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[1,3,2])
   Redo: insert(1,[3,2],[1,3,2])
    Call: insert(1,[2],_2945)
    Exit: insert(1,[2],[1,2])
   Exit: insert(1,[3,2],[3,1,2])
  Exit: perm([1,2,3],[3,1,2])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[3,1,2])
   Redo: insert(1,[3,2],[3,1,2])
    Redo: insert(1,[2],[1,2])
     Call: insert(1,[],_3207)
     Exit: insert(1,[],[1])
    Exit: insert(1,[2],[2,1])
   Exit: insert(1,[3,2],[3,2,1])
  Exit: perm([1,2,3],[3,2,1])
  Call: fail
   compiled(fail)
  Fail: fail
  Redo: perm([1,2,3],[3,2,1])
   Redo: insert(1,[3,2],[3,2,1])
    Redo: insert(1,[2],[2,1])
     Redo: insert(1,[],[1])
     Fail: insert(1,[],_3207)
    Fail: insert(1,[2],_2945)
   Fail: insert(1,[3,2],_648)
   Redo: perm([2,3],[3,2])
    Redo: insert(2,[3],[3,2])
     Redo: insert(2,[],[2])
     Fail: insert(2,[],_2421)
    Fail: insert(2,[3],_1095)
    Redo: perm([3],[3])
     Redo: insert(3,[],[3])
     Fail: insert(3,[],_1362)
     Redo: perm([],[])
     Fail: perm([],_1629)
    Fail: perm([3],_1362)
   Fail: perm([2,3],_1095)
  Fail: perm([1,2,3],_648)
  Redo: nats(1,3,[1,2,3])
  Fail: nats(1,3,_645)
 Exit: g0(3)
Starting with version 3.08 spy/1 and nospy/1 allow to watch entry and exit from compiled predicates. Note that they should be in the file to be compiled, before any use of the predicate to be spied on as in:
% FILE: jbond.pl
:-spy a/1.
:-spy c/1.

b(X):-a(X),c(X).

a(1).
a(2).

c(2).
c(3).
This gives the following interaction:
?-[jbond].
......
?- b(X).

Call: a(_2158) : ;
 !!! compiled(a/1)
Exit: a(1)
Call: c(1) : ;
 !!! compiled(c/1)
Fail: c(1)
Redo: a(1)
Exit: a(2)
Call: c(2) : ;
 !!! compiled(c/1)
Exit: c(2)
X=2;

Redo: c(2)
Fail: c(2)
Redo: a(2)
Fail: a(_2158)
no
Although these are very basic debugging facilities you can enhance them at your will and with some discipline in programming they may be all you really need. Anyway, future of debugging is definitely not by tracing. One thing is to have stronger static checking. In dynamic debugging the way go is to have a database of trace-events and then query it with high level tools. We plan to add some non-tracing database-oriented debugging facilities in the future.

You can generate a kind of intermediate WAM-assembler by

   ?- compile(asm,[file1,file2,...],'huge_file.asm').
A convenient way to see interactively the sequence of program transformations BinProlog is based on is:
?- asm.
a-->b,c,d.


DEFINITE:
a(A,B) :- 
        b(A,C),
        c(C,D),
        d(D,B).

BINARY:
a(A,B,C) :- 
        b(A,D,c(D,E,d(E,B,C))).

WAM-ASSEMBLER:
clause_? a,3
firstarg_? _/0,6
put_structure d/3,var(4-4/11,1/2)
write_variable put,var(5-5/10,1/2)
write_value put,var(2-2/6,2/2)
write_value put,var(3-3/7,2/2)
put_structure c/3,var(3-8/14,1/2)
write_variable put,var(2-9/13,1/2)
write_value put,var(5-5/10,2/2)
write_value put,var(4-4/11,2/2)
execute_? b,3


COMPILING to C

Partial C-ification
[tdb95] is a translation framework which `does less instead of doing more' to improve performance of emulators close to native code systems.
Starting from an emulator for a language L written in C, we translate to C a subset of its instruction set (usually frequent and fine-grained instructions which are executed in contiguous sequences) and then simply use a compiler for C to generate a unique executable program.
A translation threshold allows the programmer to empirically fine-tune the C-ification process by choosing the length of the emulator instruction sequence, starting from which, translation is enabled. The process uses a reasonable default value and can be easily controlled by the programmer
:-set_c_threshold(Min,Max).
will ensure that only emulated sequences of length between Min and Max get translated to C. This allows to handle gracefully the size/speed tradeoff.
Communication between the run-time system (still under the control of the emulator) and the C-ified chunks is handled as follows.
The emulated code representation of a given program (in particular the compiler itself) is mapped to a C data structure which allows exchange of symbol table information at link time.
To be able to call a C-routine from the emulator we have to know its address. Unfortunately, the linker is the only one that knows the eventual address of a C-routine. A simple and fully portable technique to plug the address of a C-routine into the byte code is to C-ify the byte-code of the emulator into a huge C array of records, containing the symbolic address of the C-chunks. After compilation, and linking with the emulator, the linker will automatically resolve all the missing addresses and generate warnings for the missing C-routines.
This is compiled together with the C-code of the emulator to a stand alone executable with performance in the range between pure emulators and native code implementations.
The method ensures a strong operational equivalence between emulated and translated code which share exactly the same observables in the run-time system.
An important characteristic is easy debugging of the resulting compiler, coming from the full sharing of the run-time system between emulated and compiled code and the following property we call instruction-level compositionality: if every translated instruction has the same observable effect on a (small) subset of the program state (registers and a few data areas) in emulated and translated mode, then arbitrary sequences of emulated and translated instructions are operationally equivalent.
Currently C-ification covers term creation on the heap and frequently used inline operations which can be processed in Binary Prolog before calling the `real goal' in the body.
Chunks containing small built-ins that do not require a procedure call will generate `leaf-routines' in C (which are called efficently and do not use stack space).
On the other hand large built-ins implemented as macros in the emulator would make code size explode. Implementing them as functions to be called from the C-chunk would require code duplication and it would destroy the leaf-routine discipline which is particularly rewarding on Sparcs. We have chosen to implement them through an abstraction with a coroutining flavor:anti-calls. Note that calling a built-in from a C-chunk is operationally equivalent to the following sequence:
  • return from the chunk,
  • execute the built-in in the emulator (usually a macro),
  • call a new leaf-routine to resume the work left from the previous leaf-routine.
Overall, anti-calls can be seen as form of coroutining (jumping back and forth) between native and emulated code. Anti-calls can be implemented with the direct-jump technique even more efficiently, although for portability reasons we have chosen a conventional return/call sequence, which is still fairly efficient as a return/call costs the same as a call/return. Moreover, this allows the chunks to remain leaf-routines, while delegating overflow and signal handling to the emulator. Note that excessively small chunks created as result of anti-calls are removed by an optimizing step of the compiler with the net result that such code will be completely left to the emulator. This is of course more compact and provable to be not slower, than its fully C-expanded alternative.

PERFORMANCE of C-IFIED CODE

The speed-up clearly depends on the amount of C-ification and on the statistical importance of C-ified code in the execution profile of a program (see figure 1). We have noticed between 10-20% speed increase for programs which take advantage of C-ified code moderately, As these programs spend only 20-30% of their time in C-ified sequences performances are expected to scale correspondingly when we extend this approach to the full BinProlog instruction set and implement low-level gcc direct jumps instead of function calls and anti-calls.
Code-sizes for C-ified BinProlog executables (dynamically linked on Sparcs with Solaris 2.3) are usually even smaller than `compact' Sicstus code which uses classical instruction folding (a few hundreds of opcodes) to speed-up the emulator.
The following table shows some code-size/execution-speed variations with respect to the threshold for the semi-ring (SEMI3) benchmark. Clearly, excessively small

Bmark/Compiler emBP C-BP emSP natSP
NREV (KLIPS) 445 455 412 882
CAL (ms) 490 310 590 310
FIBO (ms) 1730 1320 1400 800
TAK (ms) 610 470 400 180
SEMI3 (ms) 1810 1410 1810 1310
QUEENS (ms) 3170 2220 2840 1070

Figure 1: Performance of emulated (emBP) and partially C-ified BinProlog 3.22 (C-BP) compared to emulated (emSP) and native (natSP) SICStus 2.1_9 on a Sparc 10/20).

chunks can influence adversely not only on size but also on speed. Something like threshold=20, looks like a practical optimum for this program.

threshold:   0    4    8    20  30  1000 emBP emSP natSP
size:  (K)  34.5 32.2 29.9 16.3 13.1 12.9  4.8 22.0 31.9
speed: (ms) 1480 1430 1440 1450 1810 1790 1800 1810 1310


THE BLACKBOARD

A new interface has been added to separate backtrackable and surviving uses of blackboard objects so this primitive and the def/3, set/3, rm/2 of previous version although still available should be replaced either with:
  • global logical variables
  • garbage-collectible permanent objects.

GLOBAL LOGICAL VARIABLES

Syntax: A#B:=:X, or lval(A,B,X).
where X is any term on the heap. It has simply a global name A#B, i.e. an entry in the hashing table with keys A and B. The address in the table (C-pointers are the same as logical variables in BinProlog) is trailed such that on backtracking it will be unbound (i.e. point to itself). Unification with A#B:=:Y is possible at any point in the program which knows the `name' A#B.
Although a global logical variable cannot be changed it can be further instantiated as it happens to ordinary Prolog terms. Backtracking ensures they vanish so that no unsafe reference can be made to them.
The program lq8.pl is an efficient 8-queens program using global logical variables to simulate the chess-board.

GARBAGE-COLLECTIBLE PERMANENT OBJECTS.

On the other hand, if bb_def/3 or bb_set/3 is used to name objects on the blackboard, they "survive" backtracking and can afterwards be retrieved as logical variables using bb_val/3.
bb_def/3    (i,i,i) defines a value
bb_set/3    (i,i,i) updates a value
bb_rm/2     (i,i) removes a value
bb_val/3    (i,i,o) retrieves the value
They are quite close to the recorda/recordz family of other Prologs although they offer better 2-key indexing, are simpler and can be used to do much more things efficiently.
You can look to the program progs/knight.pl on how to use them to implement in a convenient and efficient way programs with backtrackable global arrays.
They can be used to save information that survives backtracking in a way similar to other Prolog's assert and retract and are safe with respect to garbage collection of the blackboard.
The predicate bb_list/1 gives the content of the blackboard as a heap object (list), while bb/0 simply prints it out.
These predicates offer generally faster and more flexible management of dynamic state information than other Prolog's dynamic databases.

ASSERT and RETRACT

For compatibility reasons BinProlog has them, implemented on top of the more efficient blackboard manipulation builtins.
This is an approximation of other Prologs assert and retract predicates. It tries to be close to Sicstus and Quintus with their semantics. For efficiency and programming style reasons I strongly suggest not to use them too much.
If you want maximal efficiency use bb_def/3, bb_set/3, bb_val/3, bb_rm They give you access to a very fast hashing table --> value, the same that BinProlog uses internally for indexing by predicate and first argument. They are close to other Prolog's `record' family, except that they do even less.
To use dynamic predicates it is a good idea to declare them with dynamic/1 although asserts will now be accepted even without such a declaration. To define dynamic code in a file you compile, dynamic declarations are mandatory.
To activate an asserted predicate it is a good idea to alway call it with
     ?-metacall(Goal).
instead of
     ?- Goal.
However, this is not a strong requirement anymore, as an important number of users were unhappy with this restriction.
The dynamic predicates are:
assert/1
asserta/1
assertz/1

retract/1
clause/2
metacall/1
abolish/2
You can easily add others or improve them by looking to the sources in the file extra.pl.

ASSUMED CODE , INTUTIONISTIC and LINEAR IMPLICATION

Intuitionistic assumei/1 adds temporarily a clause usable in later proofs. Such a clause can be used an indefinite number of times, mostly like asserted clauses, except that it vanishes on backtracking. Its scoped version Clause=>Goal or [File]=>Goal makes Clause or the set of clauses found in File available only during the proof of Goal. Both vanish on backracking. Clauses are usable an indefinite number of times in the proof, i.e. for instance ?-assumei(a(13)),a(X),a(Y) will succed.
Linear assumel/1 adds temporarily a clause usable at most once in later proofs. This assumption also vanishes on backtracking. Its scoped version Clause-:Goal or [File]-:Goal makes Clause or the set of clauses found in File available only during the proof of Goal. Both vanish on backracking. Each clause is usable at most once in the proof, i.e. for instance ?-assumel(a(13)),a(X),a(Y) will fail.
You can freely mix linear and intutionistic clauses and implications for the same predicate. Try out something like
?-a(10)-:a(11)=>a(12)-:a(13)=>(a(X),a(X)).
X=11;
X=13;
no
This shows that a(10) and a(12) are consumed after their first use while a(11) and a(13) are reusable indefinitely.
See the relatively straightforward implementation of these predicates in the file extra.pl.
Note that BinProlog's linear implication succeeds even if not all the assumptions are consumed while in systems like Lolli this is a strong requirement. Quantifiers and other linear operators are not implemented at this time, but can be added in the future if there's enough demand for them.

OVERRIDING

Assumed predicates will override similarly named dynamic predicates which in turn will override compiled ones. Note that overriding is done at predicate, not clause level. Note also that multifile compiled clauses are still forbidden. However, multifile assumed and dynamic code is now accepted. BinProlog 4.00 (with C-source license allowing recompilation with -D JUMP_COMPRESS=0 allows a stronger overriding mechanisme. The new builtin override(OldPred,NewPred) backtrackably overrites the header of the compiled definition of OldPred to with a jump instruction to the definiton of compiled predicate NewPred. The builtin also works with C-ified code, which, usually benefits in speed from recompilation with -DJUMP_COMPRESS=0-<>.

LANGUAGE ENHANCEMENTS BASED on LINEAR IMPLICATION

Linear implication can be used to quickly add some language enhancements to a Prolog system. For instance, to add a switch ... case statement one can write simply:
switch(Selector,Body):-
    case(Selector)-:Body.

test(X):-
    switch(X, (
        case(1)->write(one) ;
        case(2)->write(two) ;
        otherwise->write(unexpected(X))
  ))
 ,nl.

% ?-test(2),test(13).
Clearly, this is a very compact way, useful at least as a specification. Note that this can be done as well with macro expansion, possibly more efficiently, but also with much more work.

PROBLEM SOLVING with LINEAR IMPLICATION

Linear implication is a serious and very convenient problem solving tool, which allows avoiding explicit handling of complex data-structures. Let's suppose we want to walk through a (possibly circular) graph structure without looping.
With linear implication this becomes:
path(X,X,[X]).
path(X,Z,[X|Xs]):-linked(X,Y),path(Y,Z,Xs).

linked(X,Y):-c(X,Ys),member(Y,Ys).

go(Xs):-
   c(1,[2,3]) -: c(2,[1,4]) -: c(3,[1,5]) -: c(4,[1,5]) -:
   path(1,5,Xs).

or

path(X,X,[X]).
path(X,Z,[X|Xs]):-c(X,Y),path(Y,Z,Xs).

% data

go(Xs):-
  (c(1,X1):-c1(X1)) -: 
  (c(2,X2):-c2(X2)) -: 
  (c(3,X3):-c3(X3)) -: 
  (c(4,X4):-c4(X4)) -:
  path(1,5,Xs).

c1(2).
c1(3).

c2(1).
c2(4).
Some finite domain constraint solving can also be done quite efficiently (1.3 seconds on a Sparc 10-20 for the SEND + MORE = MONEY puzzle - see file progs/lconstr.pl).
% Program: linear implication based FD constraint solving
% Author: Paul Tarau, 1995

% cryptarithmetic puzzle solver -see progs/lconstr.pl
% a kind of "constraint solving with linear implication"

example1(
   [s,e,n,d,m,o,r,e,y]=[S,E,N,D,M,O,R,E,Y],
   [S,E,N,D]+
   [M,O,R,E]=
 [M,O,N,E,Y],
 _
).

% Addition of two numbers - simplified version -
sum(As, Bs, Cs) :- sum(As, Bs, 0, Cs).

sum([], [], Carry, [Carry]).
sum([A|As], [B|Bs], Carry, [C|Cs]) :- !,
        add2digits(A,B,Carry,C,NewCarry),
        sum(As, Bs, NewCarry, Cs).

add2digits(A,B,Carry,Result,NewCarry):-
  bind(A),bind(B),
  add_with_carry(10,A,B,Carry,Result,NewCarry).

add_with_carry(Base,A,B,Carry,Result,NewCarry):-
  S is A+B+Carry,
  Result is S mod Base,
  NewCarry is S // Base,
  new_digit(Result).

bind(A):-var(A),!,digit(A).
bind(_).

new_digit(A):-digit(A),!.
new_digit(_).

solve(As,Bs,Cs,Z):-
  digit(0)-:digit(1)-:digit(2)-:digit(3)-:digit(4)-:digit(5)-:
  digit(6)-:digit(7)-:digit(8)-:digit(9)-:
  ( sum(As,Bs,Cs),
    Z>0
  ).

puzzle:-
    init(Vars,Puzzle,Names),
    Puzzle=(Xs+Ys=Zs),Zs=[Z|_],
    reverse(Xs,As),                   % see progs/lconstr.pl
    reverse(Ys,Bs),
    reverse(Zs,Cs),
      solve(As,Bs,Cs,Z),
      show_answer(Vars,Names,Puzzle), % see progs/lconstr.pl
    fail.
puzzle:-
    write('no (more) answers'),nl,nl.

go:-
  (init(X,Y,Z):-example1(X,Y,Z))-:puzzle,
  fail.
Notice how linearly assumed digit/1 facts are consumed by bind/1 and new_digit/1 to enforce constraints as early as possible inside the addition loop.

THE BLACKBOARD as an ALTERNATIVE to ASSERT and RETRACT

Designed in the early stages of Prolog, assert and retract have been overloaded with different and often conflicting requirements. They try to be both the way to implement permanent data structures for global state information, self-modifying code and tools for Prolog program management. This created not only well-known semantical but also expressivity and efficiency problems.
This unnecessary overloading is probably due to some of their intended uses in interpreted Prologs like implementing the consult/1 and reconsult/1 code-management predicates that can be replaced today by general purpose makefiles. As a consequence, their ability to express sophisticated data structures is very limited due mostly to unwanted copying operations (from heap to dynamic code area and back) and due to their non-backtrackable behaviour.
For example, to ensure indefinite number of uses of an asserted clause most Prologs either compile it on the fly or do some form of copying (usually twice: when asserting and when calling or retracting). This is not only a waste of resources but also forbids use of asserted clauses for dynamically evolving global objects containing logical variables, one of the most interesting and efficient data structure tricks in Prolog. Worst, variables representing global data structures have to be passed around a s ex tra arguments, just to bore programmers and make them dream about inheritance and objects oriented languages. This also also creates error prone maintenance problems. Just think about adding a new seventh argument to a 10-parameter Prolog predicate having 10 clauses and being called 10 times.
Those are the main reasons for the re-design of these operations using BinProlog's blackboard.
Objects on the blackboard have indefinite extent. However, their names are "rigid designators" that can change their reference. Data objects do not disappear just because they have no names anymore. This is the main difference with variables in languages with destructive assignment. If the garbage collector "can prove" that an object or some part of it is will never be used again, the space will be recuperated automatically. Although objects cannot be "changed" they can be further instantiated as it happens to ordinary Prolog terms.
Efficient access to objects on the blackboard or part of them is based on an efficient 2-key hashing table, internal to BinProlog's run-time system.

THE LOW-LEVEL BLACKBOARD OPERATIONS

Six low-level(5) primitives def/3, set/3, val/3, rm/2, copy_term/2, save_term/2 are used in BinProlog 4.00 to fully replace assert and retract while keeping distinct their overloaded naming and copying function.

NAMING PRIMITIVES

The first four are simply an interface to BinProlog's unique global hashing table working as an

    Atomic-key1,Atomic-key2-->HeapOrBlackboardObject.
function.
  • def/3: (i,i,i) defines a value (usable only once) or fails;
  • set/3: (i,i,i) updates a value that has been defined or warns and fails;
  • val/3: (i,i,o) retrieves the value or fails if absent;
  • rm/3: (i,i) deletes the value or fails if absent.
We call them naming primitives as they are used to name arbitrary heap or blackboard objects for definition, update and access function. Naming objects on the heap is generally unsafe and should be hidden from the user except for constants which are actually copied in the hashing table instead of being pointed to. This frequent case has been given to end users as an efficient 2-keys, 1-value dictionary since the first release of BinProlog.
If blackboard operations are backtrackable heap objects can be safely named. This suggested the implementation of global logical variables in BinProlog 4.00.
Otherwise, in BinProlog's gc-safe transfers to and from the blackboard are doing with a very efficient copying algorithm.
Not that if the garbage collector is not used naming objects on the blackboard is safe as they are always at a lower address than the base of the heap. As a consequence they survive backtracking while keeping their behaviour as close as possible to the behaviour of usual heap objects. This usage is compatible with BinProlog 1.71 but not recommended in BinProlog 4.00.

COPYING PRIMITIVES

Copy_term/2 is Prolog's usual primitive extended to copy objects from the heap and also from blackboard to the current top of the heap. We refer to [Tarau92:ECO] for the implementation and memory management aspects of these primitives. Save_term/2 copies an object possibly distributed over the heap and the blackboard to a new blackboard object. It also takes care not to copy parts of the object already on the blackboard.

Remark that having known modes and argument types helps in the case of partial evaluation or type inference systems. Separating Prolog's asserts two main functions (naming+copying) in lower level operations allows program transformers to go inside more complex blackboard operations and possibly use the typing and mode information that comes from def/3, set/3 and val/3 to infer it for other predicates.

AN USEFUL PROLOG EXTENSION: BESTOF/3

Bestof/3 is missing in all current Prolog implementations we know of. BinProlog's bestof/3 works like findall/3, but instead of accumulating alternative solutions, it selects successively the best one with respect to an arbitrary total order relation. If the test succeeds the new answer replaces the previous one. At the end, either the query has no answers, case in which bestof fails, or an answer is found such that it is better than every other answer with respect to the total order. The proposed syntax is
      ?-bestof(X,TotalOrder,Goal)
At the end, X is instantiated to the best answer. For example, the maximum of a list of integers can be defined simply as:
    max(Xs,X):-bestof(X,>,member(X,Xs)).
The following is an efficient implementation implementation using the blackboard.
% true if X is an answer of Generator such that
% X Rel Y for every other answer Y of Generator
bestof(X,Closure,Generator):-
  copy_term(X,Y),
  Closure=..L1,
  det_append(L1,[X,Y],L2),
  Test=..L2,
  bestof0(X,Y,Generator,Test).

bestof0(X,Y,Generator,Test):-
  inc_level(bestof,Level),
  Generator,
  update_bestof(Level,X,Y,Test),
  fail.
bestof0(X,_,_,_):-
  dec_level(bestof,Level),
  val(bestof,Level,X),
  rm(bestof,Level).

% uses Rel to compare New with so far the best answer
update_bestof(Level,New,Old,Test):-
  val(bestof,Level,Old),!,
  Test,
  bb_set(bestof,Level,New).
update_bestof(Level,New,_,_):-
  bb_let(bestof,Level,New).

% ensure correct implementation of embedded calls to bestof/3
inc_level(Obj,X1):-val(Obj,Obj,X),!,X1 is X+1,bb_set(Obj,Obj,X1).
inc_level(Obj,1):-bb_def(Obj,Obj,1).

dec_level(Obj,X):-val(Obj,Obj,X),X>0,X1 is X-1,bb_set(Obj,Obj,X1).
Note that precomputation of Test in bestof/3 before calling the workhorse bestof0/4 is much more efficient than using some form of apply meta-predicate inside bestof0/4.

BLACKBOARD BASED ABTRACT DATA TYPES

We will describe some simple uses of the blackboard to implement efficiently some basic abstract data types. They all use the saved/2 predicate instead of save_term/2. Saved/2 does basically the same work but also makes a call to the blackboard garbage collector if necessary. The reader can find the code in the file lib.pl of the BinProlog distribution.

BLACKBOARDN BASED FAILURE SURVIVING STACKS

A very useful data structure that can be implemented with the blackboard is a stack that survives failure but still allows the programmer to use some of the nice properties of logical variables.

The main operations are push/3 that saves a term to the blackboard and pushes it to a named stack, pop/3 that removes the top element from a named stack and unifies it with its third argument and stack/3 that simply gives access to the list on the blackboard representing the stack. The only operation that uses copying is push/3, although if the term that is pushed to the stack has already some subterms on the blackboard, such subterms will not be copied again.
The implementation is straightforward:
push(Type,S,X):-
  default_val(Type,S,Xs,[]),
  saved([X|Xs],T),
  set(Type,S,T).

pop(Type,S,X):-
  default_val(Type,S,V,[]),
  V=[X|Xs],
  set(Type,S,Xs).

stack(Type,S,Xs):-val(Type,S,Xs).

default_val(X,Y,V,_):-val(X,Y,V),!.
default_val(X,Y,D,D):-def(X,Y,D).

CONSTANT TIME VECTORS

Defining a vector is done initializing it to a given Zero element. The vector_set/3 update operation uses saved/2, therefore the old content of vectors is also subject to garbage collection.

vector_def(Name,Dim,Zero):- Max is Dim-1,
  saved(Zero,BBVal),    
  for(I,0,Max), % generator for I from 0 to Max
    let(Name,I,BBVal), % def/3 or set/3 if needed
  fail.
vector_def(_,_,_).

vector_set(Name,I,Val):-saved(Val,BBVal),set(Name,I,BBVal).

vector_val(Name,I,Val):-val(Name,I,Val).
Building multi-dimensional arrays on these vectors is straightforward, by defining an index-to-address translation function.
The special case of a high-performance 2-dimension (possibly sparse) global array can be handled conveniently by using def/3, set/3, val/3 and saved/2 as in:
global_array_set(I,J,Val):-saved(Val,S),set(I,J,S).

BLACKBOARD BASED PROBLEM SOLVING

A COMPLETE KNIGHT TOUR

The following is a blackboard based complete knight-tour, adapted from Evan Tick's well known benchmark program.

% recommended use: ?-go(5).
go(N):-
        time(_),
          init(N,M),             % prepare the chess board
          knight(M,1,1),!,       % finds the first complete tour
        time(T),
  write(time=T),nl,statistics,show(N). % shows the answer

% fills the blackboard with free logical variables
% representing empty cell on the chess board
init(N,_):-
  for(I,1,N),     % generates I from 1 to N nondeterministically
    for(J,1,N),   % for/3 is the same as range/3 in the Art of Prolog
      bb_def(I,J,_NewVar),  % puts a free slot in the hashing table
  fail.
init(N,M):-
  M is N*N.                 % returns the number of cells

% tries to make a complete knight tour
knight(0,_,_) :- !.
knight(K,A,B) :-
  K1 is K-1,
  val(A,B,K),  % here we mark (A,B) as the K-th cell of the tour
  move(Dx,Dy), % we try a next move nondeterministically
  step(K1,A,B,Dx,Dy).

% makes a step and then tries more
step(K1,A,B,Dx,Dy):-
    C is A + Dx,
    D is B + Dy,
    knight(K1,C,D).

% shows the final tour
show(N):-
  for(I,1,N),
    nl,
    for(J,1,N),
      val(I,J,V),
      write(' '),X is 1-V // 10, tab(X),write(V),
  fail.
show(_):-nl.

% possible moves of the knight
move( 2, 1). move( 2,-1). move(-2, 1). move(-2,-1).
move( 1, 2). move(-1, 2). move( 1,-2). move(-1,-2).
Constant time access in this kind of problems to cell(I,J) is essential for efficiency as it is the most frequent operation. While the blackboard based version takes 39s in BinProlog for a 5x5 squares chess board, an equivalent program representing the board with a list of lists takes 147s in BinProlog, 167s in emulated Sicstus 2.1 and 68 seconds in native Sicstus 2.1. Results are expected to improve somewhat with binary trees or functor-arg representation of the board but they will still remain worse than with the blackboard based sparse array, due to their relatively high log(N) or constant factor. Moreover, representing large size (possibly updatable!) arrays with other techniques is prohibitively expensive and can get very complicated due to arity limits or tree balancing as it can see for example in the Quintus library.

A LEMMA BASEDTAK

The following tak/4 program uses lemmas to avoid heap explosion in the case of of a particularly AND intensive program with 4 recursive calls, a problem particularly severe in the case of the continuation passing binarization that BinProlog uses to simplify the WAM. To encode the 2 first arguments in a unique integer some bit-shifting is needed as it can be seen in tak_encode/3. To avoid such problems, hashing on arbitrary terms like Quintus Prolog's term_hash/2 looks a very useful addition to BinProlog.

tak(X,Y,Z,A) :- X =< Y, !, Z = A.
tak(X,Y,Z,A) :-
        X1 is X - 1,    
        Y1 is Y - 1,    
        Z1 is Z - 1,    
        ltak(X1,Y,Z,A1), 
        ltak(Y1,Z,X,A2), 
        ltak(Z1,X,Y,A3), 
        ltak(A1,A2,A3,A).

ltak(X,Y,Z,A):-
        tak_encode(X,Y,XY),
        tak_lemma(XY,Z,tak(X,Y,Z,A),A).

tak_encode(Y,Z,Key):-Key is Y<<16 \/ Z.                
tak_decode(Key,Y,Z):-Y is Key>>16, Z is Key <<17>>17 .

%optimized lemma  --> O (instantiated executing G)
tak_lemma(P,I,_,O):-val(P,I,X),!,X=O.
tak_lemma(P,I,G,O):-G,!,def(P,I,O).

go:-    statistics(runtime,_), 
        tak(24,16,8,X),
        statistics(runtime,[_,T]),statistics, 
        write([time=T,tak=X]), nl.

We hope that we showed the practicality of BinProlog's blackboard for basic work on data structures and problem solving.
BinProlog's blackboard primitives make a clear separation between the copying and the naming intent overloaded in Prolog's assert and retract.
Our blackboard primitives give most of the time simpler and more efficient solutions to current programming problems than assert and retract while being closer to a logical semantics and more cooperative to partial evaluation.

A LINDA STYLE INTERFACE to the BLACKBOARD

The following predicates show how to do some Linda-style operations on top of the blackboard primitives.
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.