Scryer Prolog
Scryer Prolog aims to become to ISO Prolog what GHC is to Haskell: an open source industrial strength production environment that is also a testbed for bleeding edge research in logic and constraint programming, which is itself written in a high-level language.
Phase 1
Produce an implementation of the Warren Abstract Machine in Rust, done according to the progression of languages in Warren's Abstract Machine: A Tutorial Reconstruction.
Phase 1 has been completed in that Scryer Prolog implements in some form all of the WAM book, including lists, cuts, Debray allocation, first argument indexing, last call optimization and conjunctive queries.
Phase 2
Extend Scryer Prolog to include the following, among other features:
- call/N as a built-in meta-predicate.
- ISO Prolog compliant throw/catch.
- Built-in and user-defined operators of all fixities, with custom associativity and precedence.
- Bignum, rational number and floating point arithmetic.
- Built-in control operators (
,
,;
,->
, etc.). - A revised, not-terrible module system.
- Built-in predicates for list processing and top-level declarative
control (
setup_call_cleanup/3
,call_with_inference_limit/3
, etc.) -
Default representation of strings as lists of characters, using a packed internal representation. -
term_expansion/2
andgoal_expansion/2
. - Definite Clause Grammars.
- Attributed variables using the SICStus Prolog interface and
semantics. Adding coroutines like
dif/2
,freeze/2
, etc. is straightforward with attributed variables.- Support for
verify_attributes/3
- Support for
attribute_goals/2
andproject_attributes/2
-
call_residue_vars/2
- Support for
-
if_/3
and related predicates, following the developments of the paper "Indexingdif/2
". - All-solutions predicates (
findall/{3,4}
,bagof/3
,setof/3
,forall/2
). - Clause creation and destruction (
asserta/1
,assertz/1
,retract/1
,abolish/1
) with logical update semantics. - Backtrackable and non-backtrackable global variables via
bb_get/2
bb_put/2
(non-backtrackable) andbb_b_put/2
(backtrackable). - Delimited continuations based on reset/3, shift/1 (documented in "Delimited Continuations for Prolog").
- Tabling library based on delimited continuations (documented in "Tabling as a Library with Delimited Control").
- A redone representation of strings as difference lists of characters, using a packed internal representation.
- clp(B) and clp(ℤ) as builtin libraries.
- Streams and predicates for stream control.
- A simple sockets library representing TCP connections as streams.
- Incremental compilation and loading process, newly written, primarily in Prolog.
- A compacting garbage collector satisfying the five properties of "Precise Garbage Collection in Prolog." (in progress)
- Mode declarations.
Phase 3
Use the WAM code produced by the completed code generator to get JIT-compiled and -executed Prolog programs. The question of how to get assembly from WAM code is something I'm still considering.
It's my hope to use Scryer Prolog as the logic engine of a low level (and ideally, very fast) Shen implementation.
Nice to have features
There are no current plans to implement any of these, but they might be nice to have in the future. They'd make a good project for anyone wanting to contribute code to Scryer Prolog.
-
Implement the global analysis techniques described in Peter van Roy's thesis, "Can Logic Programming Execute as Fast as Imperative Programming?"
-
Add unum representation and arithmetic, using either an existing unum implementation or an ad hoc one. Unums are described in Gustafson's book "The End of Error."
-
Add concurrent tables to manage shared references to atoms and strings.
-
Add some form of JIT predicate indexing.
Installing Scryer Prolog
Native Install (Unix Only)
First, install the latest stable version of Rust using your preferred method. Scryer tends to use features from newer Rust releases, whereas Rust packages in Linux distributions, Macports, etc. tend to lag behind. rustup will keep your Rust updated to the latest stable release; any existing Rust distribution should be uninstalled from your system before rustup is used.
Scryer Prolog can be installed with cargo, like so:
$> cargo install scryer-prolog
cargo will download and install the libraries Scryer Prolog uses
automatically from crates.io. You can find the scryer-prolog
executable in ~/.cargo/bin
.
Publishing Rust crates to crates.io and pushing to git are entirely distinct, independent processes, so to be sure you have the latest commit, it is recommended to clone directly from this git repository, which can be done as follows:
$> git clone https://github.com/mthom/scryer-prolog
$> cd scryer-prolog
$> cargo run [--release]
The optional --release
flag will perform various optimizations,
producing a faster executable.
Docker Install (All Platforms)
First, install Docker on Linux, Windows, or Mac.
Once Docker is installed, you can download and run Scryer Prolog with a single command:
$> docker run -it mjt128/scryer-prolog
To consult your Prolog files, bind mount your programs folder as a Docker volume:
$> docker run -v /home/user/prolog:/mnt -it mjt128/scryer-prolog
?- consult('/mnt/program.pl').
true.
This works on Windows too:
$> docker run -v C:\Users\user\Documents\prolog:/mnt -it mjt128/scryer-prolog
?- consult('/mnt/program.pl').
true.
Tutorial
Prolog files are loaded by specifying them as arguments on the command
line. For example, to load program.pl
, use:
$> scryer-prolog program.pl
Loading a Prolog file is also called “consulting” it. The built-in
predicate consult/1
can be used to consult a file from within
Prolog:
?- consult('program.pl').
As an abbreviation for consult/1
, you can specify a list of
program files, given as atoms:
?- ['program.pl'].
The special notation [user]
is used to read Prolog text from
standard input. For example,
?- [user].
hello(declarative_world).
hello(pure_world).
Pressing RETURN
followed by Ctrl-d
stops reading from
standard input and consults the entered Prolog text.
After a program is consulted, you can ask queries about the predicates it defines. For example, with the program shown above:
?- hello(What).
What = declarative_world
; What = pure_world.
Press SPACE
to show further answers, if any exist. Press RETURN
or
.
to abort the search and return to the toplevel prompt.
Press h
to show a help message.
To quit Scryer Prolog, use the standard predicate halt/0
:
?- halt.
Dynamic operators
Scryer supports dynamic operators. Using the built-in arithmetic operators with the usual precedences,
?- write_canonical(-5 + 3 - (2 * 4) // 8), nl.
-(+(-5,3),//(*(2,4),8))
true.
New operators can be defined using the op
declaration.
First instantiated argument indexing
Scryer Prolog indexes on the leftmost argument that is not a variable in all clauses of a predicate's definition. We call this strategy first instantiated argument indexing.
A key motivation for first instantiated argument indexing is to enable
indexing for meta-predicates such as maplist/N
and foldl/N
, whose
first argument is a partial goal that is a variable in the definition
of these predicates and therefore cannot be used for indexing.
For example, a natural definition of maplist/2
reads:
maplist(_, []).
maplist(Goal_1, [L|Ls]) :-
call(Goal_1, L),
maplist(Goal_1, Ls).
In this case, first instantiated argument indexing automatically uses the second argument for indexing, and thus prevents choicepoints for calls with lists of fixed lengths (and deterministic goals). Conveniently, no auxiliary predicates with reordered arguments are needed to benefit from indexing in such cases.
Conventional first argument indexing naturally arises as a special case of this strategy, if the first argument is instantiated in any clause of a predicate's definition.
Strings and partial strings
In Scryer Prolog, the default value of the Prolog flag double_quotes
is chars
, which is also the recommended setting. This means that
double-quoted strings are interpreted as lists of characters, in the
tradition of Marseille Prolog.
For example, the following query succeeds:
?- "abc" = [a,b,c].
true.
Internally, strings are represented very compactly in packed UTF-8 encoding. A naive representation of strings as lists of characters would use one memory cell per character, one memory cell per list constructor, and one memory cell for each tail that occurs in the list. Since one memory cell takes 8 bytes on 64-bit machines, the packed representation used by Scryer Prolog yields an up to 24-fold reduction of memory usage, and corresponding reduction of memory accesses when creating and processing strings.
Scryer Prolog uses the same efficient encoding for partial strings,
which appear to Prolog code as partial lists of characters. The
predicate partial_string/3
from library(iso_ext)
lets you
construct partial strings explicitly. For example:
?- partial_string("abc", Ls0, Ls).
Ls0 = [a,b,c|Ls].
In this case, and as the answer illustrates, Ls0
is
indistinguishable from a partial list with tail Ls
, while
the efficient packed representation is used internally.
An important design goal of Scryer Prolog is to automatically use
the efficient string representation whenever possible. Therefore, it
is only very rarely necessary to use partial_string/3
explicitly. In
the above example, posting Ls0 = [a,b,c|Ls] yields
the exact same internal representation, and has the advantage that
only the standard predicate (=)/2
is used.
Definite clause grammars as provided by
library(dcgs)
, and the predicates from
library(lists)
, are ideally suited for reasoning
about strings.
Partial strings were first proposed by Ulrich Neumerkel in issue #95.
Occurs check and cyclic terms
The occurs check is an element of algorithms that perform syntactic unification, causing the unification to fail if a variable is unified with a term that contains that variable as a proper subterm. For efficiency, the occurs check is omitted by default in Scryer Prolog and many other Prolog systems.
In Scryer Prolog, performing unifications which succeed only if the occurs check is omitted yield cyclic terms, also called rational trees. For example:
?- X = f(X), Y = g(X,Y).
X = f(X), Y = g(f(X),Y).
The creation of cyclic terms often indicates a programming mistake in the formulation of Prolog predicates, and to obtain logically sound results it is desirable to either perform all unifications with occurs check enabled, or let Prolog throw an error if enabling the occurs check is necessary to prevent a unification.
Scryer Prolog supports this via the Prolog flag occurs_check
. It can
be set to one of the following values to obtain the desired behaviour:
false
Do not perform the occurs check. This is the default.true
Perform all unifications with the occurs check enabled.error
Yield an error if a unification is performed that the occurs check would have prevented.
Especially when starting with Prolog, we recommend to add the
following directive to the ~/.scryerrc
configuration file so that
programming mistakes in predicates that lead to the creation of cyclic
terms are indicated by errors:
:- set_prolog_flag(occurs_check, error).
Scryer Prolog implements specialized reasoning to make unifications fast in many frequently occurring situations also if the occurs check is enabled.
Tabling (SLG resolution)
One of the foremost attractions of Prolog is that logical consequences of pure programs can be derived by various execution strategies that differ regarding essential properties such as termination, completeness and efficiency.
The default execution strategy of Prolog is depth-first search with chronological backtracking. This strategy is very efficient. Its main drawback is that it is incomplete: It may fail to find any solution even if one exists.
Scryer Prolog supports an alternative execution strategy which is
called tabling and also known as tabled execution and
SLG resolution. To enable tabled execution for a predicate, use
library(tabling)
and add a (table)/1
directive for the desired predicate indicator. For example, if we
write:
:- use_module(library(tabling)).
:- table a/0.
a :- a.
Then the query ?- a.
terminates (and fails), whereas it
does not terminate with the default execution strategy.
Scryer Prolog implements tabling via delimited continuations as described in Tabling as a Library with Delimited Control by Desouter et. al.
Constraint Logic Programming (CLP)
Scryer Prolog provides excellent support for Constraint Logic Programming (CLP), which is the amalgamation of Logic Programming (LP) and Constraints.
In addition to built-in support for dif/2
,
freeze/2
,
CLP(B) and CLP(ℤ),
Scryer provides a convenient way to implement new user-defined
constraints: Attributed variables are available via
library(atts)
as in SICStus Prolog,
which is one of the most sophisticated and fastest constraint systems
in existence. In library(iso_ext)
,
Scryer provides predicates for backtrackable (bb_b_put/2
) and
non-backtrackable (bb_put/2
) global variables, which are needed to
implement certain types of constraint solvers.
These features make Scryer Prolog an ideal platform for teaching, learning and developing portable CLP applications.
Modules
Scryer has a simple predicate-based module system. It provides a
way to separate units of code into distinct namespaces, for both
predicates and operators. See the files
src/lib/*.pl
for
examples.
At the time of this writing, many predicates reside in their own modules that need to be imported before they can be used. The modules that ship with Scryer Prolog are also called library modules or libraries, and include:
lists
providinglength/2
,member/2
,select/3
,append/[2,3]
,foldl/[4,5]
,maplist/[2-9]
,same_length/2
,transpose/2
etc.dcgs
Definite Clause Grammars (DCGs), a built-in grammar mechanism that uses the operator(-->)/2
to define grammar rules, and the predicatesphrase/[2,3]
to invoke them.dif
The predicatedif/2
provides declarative disequality: It is true if and only if its arguments are different, and delays the test until a sound decision can be made.reif
providingif_/3
,tfilter/3
and related predicates as described in Indexing dif/2.clpz
CLP(ℤ): Constraint Logic Programming over Integers, providing declarative integer arithmetic via(#=)/2
,(#\=)/2
,(#>=)/2
etc., and various global constraints and enumeration predicates for solving combinatorial tasks.pairs
By convention, pairs are Prolog terms with principal functor(-)/2
, written asKey-Value
. This library providespairs_keys_values/3
,pairs_keys/2
, and other predicates to reason about pairs.si
The predicatesatom_si/1
,integer_si/1
,atomic_si/1
andlist_si/1
implement sound type checks. They raise instantiation errors if no decision can be made. They are declarative replacements for logically flawed lower-level type tests. For instance, instead ofinteger(X)
, writeinteger_si(X)
to ensure soundness of your programs. "si" stands for sufficiently instantiated, and also for sound inference.debug
Various predicates that allow for declarative debugging.pio
phrase_from_file/2
applies a DCG nonterminal to the contents of a file, reading lazily only as much as is needed. Due to the compact internal string representation, also extremely large files can be efficiently processed with Scryer Prolog in this way.lambda
Lambda expressions to simplify higher order programming.charsio
Various predicates that are useful for parsing and reasoning about characters, notablychar_type/2
to classify characters according to their type, and conversion predicates for different encodings of strings.error
must_be/2
andcan_be/2
complement the type checks provided bylibrary(si)
, and are especially useful for Prolog library authors.tabling
The operator(table)/1
is used in directives that prepare predicates for tabled execution (SLG resolution).format
The nonterminalformat_//2
is used to describe formatted output, arranging arguments according to a given format string. The predicatesformat/[2,3]
,portray_clause/[1,2]
andlisting/1
provide formatted impure output.assoc
providingempty_assoc/1
,get_assoc/3
,put_assoc/4
etc. to manage elements in AVL trees which ensure O(log(N)) access.ordsets
represents ordered sets as lists.clpb
CLP(B): Constraint Logic Programming over Boolean variables, a BDD-based SAT solver provided via the predicatessat/1
,taut/2
,labeling/1
etc.arithmetic
Arithmetic predicates such aslsb/2
,msb/2
andnumber_to_rational/2
.time
Predicates for reasoning about time, includingtime/1
to measure the CPU time of a goal,current_time/1
to obtain the current system time, the nonterminalformat_time//2
to describe strings with dates and times, andsleep/1
to slow down a computation.files
Predicates for reasoning about files and directories, such asdirectory_files/2
,file_exists/1
andfile_size/2
.cont
Provides delimited continuations viareset/3
andshift/1
.random
Probabilistic predicates and random number generators.http/http_open
Open a stream to read answers from web servers. HTTPS is also supported.http/http_server
Runs a HTTP/1.0 web server.sgml
load_html/3
andload_xml/3
represent HTML and XML documents as Prolog terms for convenient and efficient reasoning. Uselibrary(xpath)
to extract information from parsed documents.csv
parse_csv//1
andparse_csv//2
can be used withphrase_from_file/2
orphrase/2
to parse csvserialization/abnf
DCGs describing the ABNF grammar core (RFC 5234), which is used to describe many IETF syntaxes, such as HTTP v1.1, SMTP, iCalendar, and more.serialization/json
json_chars//1
can be used withphrase_from_file/2
orphrase/2
to parse and generate JSON.xpath
The predicatexpath/3
is used for convenient reasoning about HTML and XML documents, inspired by the XPath language. This library is often used together withlibrary(sgml)
.sockets
Predicates for opening and accepting TCP connections as streams. TLS negotiation is performed via the optiontls(true)
insocket_client_open/3
, yielding secure encrypted connections.os
Predicates for reasoning about environment variables.iso_ext
Conforming extensions to and candidates for inclusion in the Prolog ISO standard, such assetup_call_cleanup/3
,call_nth/2
andcall_with_inference_limit/3
.crypto
Cryptographically secure random numbers and hashes, HMAC-based key derivation (HKDF), password-based key derivation (PBKDF2), public key signatures and signature verification with Ed25519, ECDH key exchange over Curve25519 (X25519), authenticated symmetric encryption with ChaCha20-Poly1305, and reasoning about elliptic curves.uuid
UUIDv4 generation and hex representation
To use predicates provided by the lists
library, write:
?- use_module(library(lists)).
To load modules contained in files, the library
functor can be
omitted, prompting Scryer to search for the file (specified as an
atom) from its working directory:
?- use_module('file.pl').
use_module
directives can be qualified by adding a list of imports:
?- use_module(library(lists), [member/2]).
A qualified use_module
can be used to remove imports from the
toplevel by calling it with an empty import list.
The (:)/2
operator resolves calls to predicates that might not be
imported to the current working namespace:
?- lists:member(X, Xs).
The [user] prompt can also be used to define modules inline at the REPL:
?- [user].
:- module(test, [local_member/2]).
:- use_module(library(lists)).
local_member(X, Xs) :- member(X, Xs).
The user listing can also be terminated by placing end_of_file.
at
the end of the stream.
Configuration file
At startup, Scryer Prolog consults the file ~/.scryerrc
, if the file
exists. This file is useful to automatically load libraries and define
predicates that you need often.
For example, a sensible starting point for ~/.scryerrc
is:
:- use_module(library(lists)).
:- use_module(library(dcgs)).
:- use_module(library(reif)).
Development environment
To write and edit Prolog programs, we recommend GNU Emacs with the Prolog mode maintained by Stefan Bruda.
Use ediprolog to consult Prolog code and evaluate Prolog queries in arbitrary Emacs buffers.
Emacs definitions that show Prolog terms as trees are available in tools.
To debug Prolog code, we recommend the predicates from
library(debug)
, most notably:
(*)/1
to "generalize away" a Prolog goal. Use it to debug unexpected failures by generalizing your definitions until they succeed. Simply place*
in front of a goal to generalize it away.($)/1
to emit a trace of the execution, showing when a goal is invoked, and when it has succeeded. Place$
in front of a goal to emit this information for that goal.
This way of debugging Prolog code has several major benefits, such as: It stays close to the actual Prolog code under consideration, it does not need additional tools and formalisms for its application, and further, it encourages declarative reasoning that can in principle also be performed automatically.
Support and discussions
If Scryer Prolog crashes or yields unexpected errors, consider filing an issue.
To get in touch with the Scryer Prolog community, participate in discussions!