@c -*-texinfo-*-
@node UserManual, ReferenceManual, Top, Top
@comment  node-name,  next,  previous,  up
@chapter User Manual

@menu
* Introduction::                Introduction
* About::                       About Parallel Parlog
* EnteringExiting::             Entering and Exiting the Parallel Parlog System
* Running::                     Running Queries
* LoadingCompiling::            Loading and Compiling
* Tracing::                     Tracing
* Errors::                      Error Messages
* Modules::                     Modules
* GuardSafety::                 Guard Safety Considerations
@end menu

@node Introduction, About,  , UserManual
@comment  node-name,  next,  previous,  up
@section Introduction

The first part of this document is a user manual in tutorial form, and
may be read while trying out the examples at a terminal.  The second
part is a reference manual, and contains a definition of Parallel Parlog
and documentation on system predicates.  The reader is assumed to have
some knowledge of Parlog and Unix.  In the rest of document, we will use
the notation @code{pred/n} to denote a predicate with name @code{pred}
and number of arguments (also known as the @dfn{arity}) @code{n}.  The
notation `@kbd{@key{<CR>}}' indicates that the `return' key should be
typed.

@node About, EnteringExiting, Introduction, UserManual
@comment  node-name,  next,  previous,  up
@section About Parallel Parlog

Parallel Parlog is an implementation of Parlog for shared memory
multiprocessor machines. Versions currently exist for the Sequent
Balance and Symmetry, BBN Butterfly, Encore Multimax and Alliant FX/8.
Uniprocessor
versions are also available for Sun3 and Sun4 workstations. The syntax
is standard Parlog and is compatible with the SPM [Foster et al. 1986]
and MacParlog [Conlon and Gregory 1989]

The language is as defined in [Gregory 1987], except for the
@dfn{non-flat guard restriction} (@pxref{GuardSafety}),
the restricted form of the metacall (@pxref{Metalevel}), and the
introduction of a simple module scheme (@pxref{Modules}).

This manual describes the third release of the Parallel Parlog system,
V1.5, which contains a number of improvements over previous releases
V1.0 and V1.4.  Any program compiled on V1.0 will need to be
recompiled in order to be executed on the new release of the system.

The main feature of release V1.4 of the Parallel Parlog system is
a new memory management system that allows the different data areas
within the emulator [Crammond 1990] to dynamically expand (and contract)
as required. On machines that allow shared memory to be expanded during
execution this makes the new Parlog system somewhat more robust,
particularly when using many processors, and also more economical when
executing small programs, particularly on a single processor.
The latest release V1.5 adds many useful primitives and fixes
many of the bugs reported by users (@pxref{Changes}).

@node EnteringExiting, Running, About, UserManual
@comment  node-name,  next,  previous,  up
@section Entering and Exiting the Parallel Parlog System

The system can be entered by typing the command @file{parlog}.  This
command has one option @file{-nx} which specifies that the system should
execute on @file{x} processors.  On startup, the Parlog system displays
the following message on the screen:
@example
Parallel Parlog V1.5  -  10 Jan 1993
Copyright (C) 1993, Imperial College

| ?-
@end example
To exit Parlog, type the end of file character (usually
`@kbd{@key{CTL}-D}') or the command `@kbd{halt.}' followed by
@key{<CR>}.  Note that the full-stop must be typed at the end of
each command.

@node Running, LoadingCompiling, EnteringExiting, UserManual
@comment  node-name,  next,  previous,  up
@section Running Queries

In response to the `@kbd{| ?-}' prompt the user may enter any conjunction
of Parlog calls terminated by a full-stop.  This conjunction is
evaluated as a query, and if it is successful the bindings for the query
are printed out and the word `@kbd{yes}' appears.  Bindings are not
printed for void variables (denoted by an underscore). If the query
fails then this is indicated with `@kbd{no}'.  This is illustrated by the
following simple example:

@example
| ?- X is 1 + 2.
 X = 3

yes
| ?- _ is 1 + 2.

yes
| ?- X is 1 + 2, X is 2 + 2.

no
| ?- halt.
ncalls/utime = 461 / 0.02 = 23050.0 RPS
@end example

Normally a query is executed in the foreground which means that the
prompt for the next query will not appear until the last query has
run to completion (either succeeded, failed or deadlocked).  In some
cases, it is desirable to run background queries so that more than
one query can be executed in parallel.  This feature is particularly
useful for queries which are expected to suspend or take a long time
to finish as it allows the user to enter new queries without waiting
for the result.  To execute a query in the background, prefix the query
with a `@kbd{&&}'.  Note that the whole query must be run in the
background.  It is not possible to mix foreground and background
processing within a single query.

@example
| ?- create_channel(ch1,X) & data(X) & X=[H|_] & name(H,List).
data(_1511)
[deadlock]

| ?- && create_channel(ch2,X) & data(X) & X=[H|_] & name(H,List).

| ?- write_channel(ch2,hello).

yes
| ?-  X = [hello|_2081]
 H = hello
 List = [104,101,108,108,111]

yes
@end example

The evaluation of a query can be interrupted by typing the interrupt
character (usually `@kbd{@key{CTL}-C}'). This should produce the prompt
`@kbd{Parlog interruption ?}'.  By typing `@kbd{y@key{<CR>}}' to this
prompt, the execution of the query will be aborted; typing
`@kbd{n@key{<CR>}}' will cause the execution to resume.

Note: if the interrupt prompt does not appear on the screen within a few
seconds of typing an interrupt then the system has ``hung'' in some way.
The only rescue from this situation is to type the quit character
(usually `@kbd{@key{CTL}-\}').

@node LoadingCompiling, Tracing, Running, UserManual
@comment  node-name,  next,  previous,  up
@section Loading and Compiling

Users may define their own Parallel Parlog predicates by placing them in
a text file. The correct syntax for predicates is defined in the
Reference Manual (@pxref{Syntax}).  To make them available within the system,
a Parallel Parlog object code file should be generated by using the
@code{compile/1} predicate, and this should then be loaded with the
@code{load/1} predicate.

It is usual for the Parlog text file to have a @file{.par} extension and
the object file an @file{.o} extension, as in the following example, but
this is optional (@pxref{CompilationAndLoading}).

@example
tutorial% cat tst.par

mode biased_merge(?,?,^).
biased_merge([A|As],Bs,[A|Cs])<-
    biased_merge(As,Bs,Cs).
biased_merge(As,[B|Bs],[B|Cs])<-
    biased_merge(As,Bs,Cs).
biased_merge([],Bs,Bs).
biased_merge(As,[],As).

tutorial% parlog
Parallel Parlog V1.5  -  10 Jan 1993
Copyright (C) 1993, Imperial College

| ?- biased_merge([1,2],[3,4],X).
[Warning: the procedure biased_merge/3 is undefined]

no
| ?- compile(tst) & load(tst).
[loading compiler]
Compiling file tst.par
biased_merge / 3
File tst compiled.

yes
| ?- biased_merge([1,2],[3,4],X).
 X = [1,2,3,4]

yes
| ?- halt.

ncalls/utime = 5432 / 0.56 = 9700.0 RPS
tutorial% ls
tst.o                tst.par
tutorial%
@end example

Terms in the source file with the form `@code{<-ConjunctionOfGoals}'
are treated as commands, which are
executed automatically as the object file is loaded.

@node Tracing, Errors, LoadingCompiling, UserManual
@comment  node-name,  next,  previous,  up
@section Tracing

The Parallel Parlog system supports rudimentary tracing facilities,
through the use of spypoints.  A spypoint may be placed on a predicate
using the @code{spy/1} predicate.  Thereafter, each time the predicate
is called, the goal and the current state of its arguments is displayed
on the screen preceded by a `@kbd{Call:}' message. The user is then
prompted, and four kinds of response are possible.

@enumerate
@item When the user
types `@kbd{@key{<CR>}}', the traced call is executed and a further message
is displayed on termination of the call. This message is either
`@kbd{Exit:}' or `@kbd{Fail:}', followed by the goal and its
arguments.

@item Typing `@kbd{n@key{<CR>}}'
will cause the spypoint to be removed before executing the call.
Thereafter, further calls to the predicate will not be traced (but
existing calls will still be traced when they terminate).  Spypoints can
also be removed with the @code{nospy/1} predicate.

@item Typing `@kbd{a@key{<CR>}}' will abort the call.

@item Typing `@kbd{c goal@key{<CR>}}'
will cause @code{goal} to be executed. This can be useful for setting
further spypoints before proceeding with this call. Once @code{goal} has
completed, the user is prompted again for action on this call.
@end enumerate

@example
| ?- spy(biased_merge/3).

yes
| ?- biased_merge([1,2], [], [1,3]).
Call: biased_merge([1,2],[],[1,3]) ? 
Call: biased_merge([2],[],[3]) ? 
Fail: biased_merge([2],[],[3]) ? 
Fail: biased_merge([1,2],[],[1,3]) ? 

no
| ?- biased_merge([1,2], [], X).
Call: biased_merge([1,2],[],_2454) ? 
Call: biased_merge([2],[],_2546) ? 
Call: biased_merge([],[],_2594) ? 
Exit: biased_merge([],[],[]) ? 
Exit: biased_merge([2],[],[2]) ? 
Exit: biased_merge([1,2],[],[1,2]) ? 
 X = [1,2]

yes
| ?- biased_merge([1,2], [], X).
Call: biased_merge([1,2],[],_2911) ? a

| ?- biased_merge([1,2], [], X).
Call: biased_merge([1,2],[],_3102) ? n
 X = [1,2]

yes
| ?-

@end example

Notes:

@enumerate
@item
The emulator will continue to execute runnable goals while waiting for
the prompt to a traced call; thus potentially altering the scheduling
behaviour, particularly on one processor.

A consequence of this is that parallel invocations of a spied predicate
result in multiple `@kbd{Call:}' messages appearing, each requiring a
response. This is rather unsightly at times.

@item
A common fault that causes programs that work on one processor to fail
on multiple processors is the incorrect use of @code{var(X)} in a guard.
Such a guard may succeed `unexpectedly' because it runs in
parallel with a goal that eventually binds X.  Remember, @code{var(X)}
is time dependent and must be used with care in parallel programs.
@end enumerate

@node Errors, Modules, Tracing, UserManual
@comment  node-name,  next,  previous,  up
@section Error Messages

There are four sorts of error messages which the user may encounter :

@menu
* BuiltinErrors::               Builtin Errors
* SyntaxErrors::                Syntax Errors
* CompilerErrors::              Compiler Errors
* Deadlock::                    Deadlock
@end menu

@node BuiltinErrors, SyntaxErrors,  , Errors
@comment  node-name,  next,  previous,  up
@subsection Builtin Errors

When the system predicates are given incorrect input they generate
messages of the form :

@example
[Error:  message: builtin name and arguments]
@end example

@node SyntaxErrors, CompilerErrors, BuiltinErrors, Errors
@comment  node-name,  next,  previous,  up
@subsection Syntax Errors

The @code{read} predicates (@pxref{TermIO}) return error messages when
they are used with input that does not conform to Parlog syntax.  Since
the compiler and the top level query evaluator use these predicates, the
user will find the same messages displayed here.  The format is:

@example
**Syntax Error: offending term
@end example

The offending term is listed, and the place where the error occurred is
marked by the word `@kbd{<<here>>}'.

@node CompilerErrors, Deadlock, SyntaxErrors, Errors
@comment  node-name,  next,  previous,  up
@subsection Compiler Errors

The compiler may generate the following messages :

@table @code
@item **Syntax Error: @var{Term}
see above.

@item **Mode Declaration Error:  @var{Mode}
The mode is wrongly formatted; usually a `@kbd{^}' or `@kbd{?}' is missing.

@item **Compiler Error - Name/Arity mismatch:  @var{Name/Arity}
The clauses grouped together as one procedure with the sequential search
operator `@kbd{;}' do not share the same name and arity.

@item **Compiler Error:@var{Name/Arity}
Any other compiler error.

@item warning: is/2 before "@kbd{&}" in body cannot be optimised
This indicates that a call to @code{is/2} can potentially be optimised by
replacing the sequential conjunction operator `@kbd{&}' by the parallel
conjuction operator `@kbd{.}'.

@item warning: parallel deep guards detected
The compiler has detected two or more parallel non-flat
clauses(@pxref{GuardSafety}).  This warning may be ignored if the
programmer is sure that only one of the clauses will commit.
If this cannot be guaranteed, then the clauses should be separated
using `@kbd{&}'.

@item warning: some clause(s) have been ignored
The compiler has detected some redundant clauses.  For example, in the relation
@example
mode p(?).
p(X) <- X > 0 : positive(X).
p(X) <- X < 0 : negative(X).
p(X) <- X == 0 , zero(X).
@end example
the third clause can always commit since it has no guard.  The first two
clauses are thus ignored.  This is probably not what the programmer 
intended so the compiler gives the warning.  The fix is to
change the parallel clause separator `@kbd{.}' at the end of clause 2
to a sequential one `@kbd{;}', or to put a commit operator `@kbd{:}'
between the two body goals in clause 3.
@end table

After processing the source file, a summary of all of the error messages
is displayed. This is illustrated by the example session given below,
which captures a syntax error in the first predicate of the
@file{kkqueen.par} file.

@example
tutorial% cat kkqueen.par

mode gen(?, ^).
gen(N, [N|Xs]) <- 
  N > 0 :
  N1 is N-1,
  gen(N1, Xs).
gen(0, []).
                           
mode count(?, ?, ^).
count([], M M).
count([X|Xs], M, Total) <-
  M1 is M + 1,
  count(Xs, M1, Total).

tutorial% parlog
Parallel Parlog V1.5  -  10 Jan 1993
Copyright (C) 1993, Imperial College

| ?- compile(kkqueen).
[loading compiler]
Compiling file kkqueen.par
gen / 2

** Syntax Error: count([],M <<here>> M).
count / 3
File kkqueen partially compiled:
One or more syntax errors in or before:
count / 3
These clauses missing from the object code!

yes
| ?- halt.

ncalls/utime = 4978 / 0.51 = 9760.78 RPS
tutorial%
@end example

@node Deadlock,  , CompilerErrors, Errors
@comment  node-name,  next,  previous,  up
@subsection Deadlock

When the evaluation of a query cannot terminate because there are calls
suspended on input matching constraints, the system prints out all the
suspended calls and then the message :
@example
[deadlock]
@end example

Note: goals which were suspended before a previous deadlock, or were
executing before an interrupt was typed, may be displayed among the list
of goals suspended during this deadlock.

@node Modules, GuardSafety, Errors, UserManual
@comment  node-name,  next,  previous,  up
@section Modules

Parallel Parlog supports a simple module system to control the name
space of predicates. This is based on the notion of a @samp{current
module}, which is the place where a query currently looks for predicate
definitions.  The predicate @code{current_module/1} returns the name of
the current module, and @code{module/1} changes it
(@pxref{CompilationAndLoading}).

When predicates are loaded into the system, they are placed in the
current module. Thus a command such as @samp{<- module exmpl.} at the
top of the source file will cause the predicates in the object file to
be loaded into module @code{exmpl}. However, after the load is finished,
the current module becomes the module which was being used prior to the
load.

By default, predicates loaded into a module are private to that module
and can only be called by goals within that module. Predicates can be
made visible to all other modules by the @code{public/1} command, e.g.
@samp{public a/1, b/2, c/3.}, which means that it can be invoked from
any module. A public predicate is read-only in all modules other than
the one in which it is defined, so the definition of a public predicate
not in the current module cannot be replaced in subsequent loads by an
alternative (private) one.

Predicates can also be imported into modules without making them public
to all modules. This is a two stage process: firstly the predicates are
made exportable in the module in which they are defined with
@code{export/1}, and secondly they are imported with @code{import/2},
from the module in which they are defined into the current module.  For
example, suppose the current module is set to @code{foo}, then
@samp{export([a/1,b/2,c/3])} makes predicates @code{a/1}, @code{b/2} and
@code{c/3} all exportable. Now in module @code{bar}, the predicate
@code{b/2} can be imported from @code{foo} using
@samp{import(foo,[b/2]).}.

There are two predefined modules: @code{system} and @code{user}.  All
Parlog systems predicates, as defined in the reference manual, are
defined in module @code{system} and are made public. In this way, the
module mechanism is transparent to the user who does not wish to use it.
The query evaluator executes by default in module @code{user} so that
private predicates used by the system and compiler are invisible to the
user.

The binding of a call to a predicate in the appropriate module is done
at load time, thus incurring no overhead at run time. However, the
binding for interpreted calls, using @code{call/1}, is done at run time
in the context of the current module. Thus, the predicate must either be
in the current module or imported into it. A predicate within a given
module can be called explicitly using @samp{module#goal} syntax, e.g.

@example
| ?- system#assemble(file).
@end example

@node GuardSafety,  , Modules, UserManual
@comment  node-name,  next,  previous,  up
@section Guard Safety Considerations

The usual @dfn{guard safety} restrictions apply, which mean that
bindings of variables in a guard are not made visible to the body of the
clause until the guard has committed.

In addition, Parallel Prolog has a @dfn{non-flat guard restriction} which
means that OR-parallel search only works for clauses with flat guards.
Flat guards are guards which use only system predicates that can be
compiled in-line and include all unification primitives (except
@code{ground/1} and @code{\==/2}), all type tests, @code{is/2}, term
comparison and arithmetic comparison.  A guard is non-flat if it
contains user defined predicates or non-flat system predicates.
Non-flat guards are also called deep guards.
More details on flat and non-flat guards can be found in [Gregory 1987].

The consequence of this non-flat guard restriction is that the programmer
should ensure that all clauses containing deep guards (except the
last) should end with a sequential clause separator @code{`;'}.  This
coding strategy will ensure that a candidate non-flat clause will not be
tried in parallel with other candidates.

With this restriction, the if-then-else form of deep guard is still
possible (as seen in examples 1 and 2), but the or-parallel search
technique - two alternative guards executing in parallel - is not
(example 3).

@example
(1) mode p1(?,^).
    p1(X,S) <- try(X) : S=ok ;
    p1(X,S) <- S=failed.

(2) mode p2(?,?).
    p2([A|B],Y) <- g1(A), g2(A) : b1(B,Y);
    p2(X,[A|B]) <- g1(A), g2(A) : b2(B,X);
    p2(X,Y)     <- b3(X,Y).

(3) % this is not allowed:
    mode p3(?,?,?,^).
    p3(X,L,R,T) <- find(X,L,T1) : T=T1.
    p3(X,L,R,T) <- find(X,R,T2) : T=T2.
@end example

A warning message is issued by the compiler when parallel deep guards
are detected, such as in example 3.

There are transformations that automatically convert general Parlog into
the restricted form, and future releases may perform these during
compilation.  At present, the user is responsible for any alterations to
his code.  Example 3 could be rewritten using @code{call/3} as :

@example
p3(X,L,R,T) <- 
    call(find(X,L,T1),Res1,Con1),
    call(find(X,R,T2),Res2,Con2),
    wait_for_result(Res1,Res2,Con1,Con2,T1,T2,T).

mode wait_for_result(?,?,^,^,?,?,^).
wait_for_result(success,_,_,stop,T1,_,T) <- T=T1.
wait_for_result(_,success,stop,_,_,T2,T) <- T=T2.
@end example

There is another programming restriction which is the result of
the compiler trying to optimize code by compiling flat system predicates
to in-line code.  A side-effect of this is that the ordering of calls
in the guard can sometimes be very important. e.g.

@example
	(4)	longer(L1,L2) <- length(L1,A), length(L2,B), A>B : ...
	(5)	longer(L1,L2) <- length(L1,A), length(L2,B) & A>B : ...
	(6)	p <- X==Y, X=1, Y=2 : ...
	(7)	p <- X=1, Y=2, X==Y : ...
@end example

Examples 4 and 6 will deadlock under Parallel Parlog.  A workaround is
to either force a sequential evaluation (example 5) or re-order the calls
(example 7).  Note that since flat system predicates are compiled in-line,
the separators between the system predicates in example 7 are notionally
converted to `@kbd{&}' by the compiler.
