fprolog
extends standard Prolog to allow function declarations, with a syntax similar to that used in
functional languages such as ML.
Example fprolog source (examples/max.pl
):
% Function max2(X,Y) returns greater of X or Y
fun max2(X,Y) = if (X > Y) then X else Y.
% Function max(L) returns maximum element in list L
fun max([X]) = X;
max([X|L]) = max2(X,max(L)).
% Relation max(L,N) succeeds if N is the maximum element in list L
max(L,N) :- N = max(L).
And here is how we 'run' that fprolog
program:
$ prolog
Welcome to SWI-Prolog (threaded, 64 bits, version 7.6.4)
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.
Please run ?- license. for legal details.
For online help and background, visit http://www.swi-prolog.org
For built-in help, use ?- help(Topic). or ?- apropos(Word).
?- [fprolog].
true.
?- fconsult('examples/max.pl').
true.
?- max([1,3,4,7,3,5],N).
N = 7.
?-
fprolog
is a relatively small part of the work by Ian Lewis (under the supervision of William
Clocksin) for a PhD at the Computer Laboratory, University of Cambridge (1998):
PrologPF: Parallel Logic and Functions on the Delphi Machine
In particular, Chapter 5: Higher Order Functions in PrologPF.
See also an fprolog summary paper.
The idea (successful, by the way) was to parallelize Prolog using a particular technique of distributing work
among path processors by allocating non-overlapping parts of the search tree via oracles which define the
route to the root of given the subtree as a path through the original Prolog clauses leading to that node. This
technique is incompatible with the use of the Prolog extra-logical operator cut (i.e. !
) and
declarative functional support was found in practice to largely eliminate the need for this operator.
The technique has two important characteristics:
-
It targets a distributed machine in which the communication latency between a large number of workers was extremely high compared to the instruction execution speed within each worker, i.e. was designed to exploit the internet, contrasting with the bulk of parallel programming effort which requires exceptional communications bandwidth and low-latency between the workers for an effective speedup.
-
The parallization of the source program is automatic with the original programmer having made no consideration of the technique involved and the algorithm not being trivially parallelizable. This contrasts with much parallel programming effort which assumes the problem is simply decomposable into work elements that can easily be distributed among a pool of workers requiring the minimum of communication.
These are the latest versions of the ORIGINAL PrologPF files from the Computer Lab filer (ijl20).
The extensions to Prolog supported are:
o_code
or k_code
for parallism support via Oracles or Kappa.
f_code
for functional support in Prolog, where an argument to a relation can be a
function, declared in a 'fun' clause.
From cl_filer/wamcc/src/wamcc_ocode.pl
Used at compile / consult time to modify source program to include Oracle support via C macros.
From cl_filer/wamcc/src/wamcc_ocode_pl.pl
Used at compile / consult time to modify source program to include Oracle support via Prolog relations.
From cl_filer/wamcc/src/wamcc_kcode.pl
Almost identical to wamcc_ocode.pl, but injects 'kappa' oracle relations.
Used at compile / consult time to modify source program to include Kappa support
From cl_filer/wamcc/src/wamcc_fcode.pl
Used at compile / consult time to modify source program to replace function definitions with equivalent relations
From cl_filer/wamcc/src/f_utils.pl
Provides run-time functions that support PrologPF functions (e.g. function definitions for +, -).
From cl_filer/wamcc/src/o_utils_pl.pl
Provides run-time relations that support Prolog Oracle management code (i.e. build, follow oracles via Prolog relations such as o_next).
From cl_filer/wamcc/src/o_utils.pl
Provides run-time relations that support C-based oracles (i.e via relations defined with C macros).
From cl_filer/wamcc/src/o_utils.usr
Provides C macro-based relations for run-time oracle support
From cl_filer/wamcc/src/k_utils.pl
Provides relations (calling C macros) for run-time Kappa support
From cl_filer/wamcc/src/k_utils.usr
Provides C macros for run-time Kappa support