search

mthom / scryer-prolog

A modern Prolog implementation written mostly in Rust.
BSD 3-Clause "New" or "Revised" License
1.93k stars 116 forks source link
iso-prolog-standard prolog prolog-implementation prolog-interpreter prolog-programming-language rust

readme

Announcing the Scryer Prolog Meetup 2024

This year we will meet at the Hotel Stefanie in Vienna to discuss present and future developments in the Scryer Prolog system.

Details here: https://www.digitalaustria.gv.at/eng/insights/Digital-Austria-Events-EN/Scryer-Prolog-Meetup-2024.html.

Many thanks to the Austrian Federal Ministry of Finance for hosting the event!

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.

Scryer Prolog passes all tests of syntactic conformity, variable_names/1 and dif/2.

The homepage of the project is: https://www.scryer.pl

Scryer Logo: Cryer

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:

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.

  1. Implement the global analysis techniques described in Peter van Roy's thesis, "Can Logic Programming Execute as Fast as Imperative Programming?"

  2. 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."

  3. Add concurrent tables to manage shared references to atoms and strings.

  4. Add some form of JIT predicate indexing.

Installing Scryer Prolog

Binaries

Precompiled binaries for several platforms are available for download at:

https://github.com/mthom/scryer-prolog/releases/tag/v0.9.3

Native Compilation

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.

Currently the only way to install the latest version of Scryer is to clone directly from this git repository, and compile the system. This can be done as follows:

$> git clone https://github.com/mthom/scryer-prolog
$> cd scryer-prolog
$> cargo build --release

The --release flag performs various optimizations, producing a faster executable.

After compilation, the executable scryer-prolog is available in the directory target/release and can be invoked to run the system.

On Windows, Scryer Prolog is easier to build inside a MSYS2 environment as some crates may require native C compilation. However, the resulting binary does not need MSYS2 to run. When executing Scryer in a shell, it is recommended to use a more advanced shell than mintty (the default MSYS2 shell). The Windows Terminal works correctly.

To build a Windows Installer, you'll need first Scryer Prolog compiled in release mode, then, with WiX Toolset installed, execute:

candle.exe scryer-prolog.wxs
light.exe scryer-prolog.wixobj

It will generate a very basic MSI file which installs the main executable and a shortcut in the Start Menu. It can be installed with a double-click. To uninstall, go to the Control Panel and uninstall as usual.

Scryer Prolog must be built with Rust 1.70 and up.

Building WebAssembly

Scryer Prolog has basic WebAssembly support. You can follow wasm-pack's official instructions to install wasm-pack and build it in any way you like.

However, none of the default features are currently supported. The preferred way of disabling them is passing extra options to wasm-pack.

For example, if you want a minimal working package without using any bundler like webpack, you can do this:

wasm-pack build --target web -- --no-default-features

Then a pkg directory will be created, containing everything you need for a webapp. You can test whether the package is successfully built by creating an html file, adapted from wasm-bindgen's official example like this:

<!DOCTYPE html>
<html>
    <head>
        <meta charset="UTF-8" />
        <title>Scryer Prolog - Sudoku Solver Example</title>
        <script type="module">
        import init, { eval_code } from './pkg/scryer_prolog.js';

        const run = async () => {
            await init("./pkg/scryer_prolog_bg.wasm");
            let code = `
            :- use_module(library(format)).
            :- use_module(library(clpz)).
            :- use_module(library(lists)).

            sudoku(Rows) :-
            length(Rows, 9), maplist(same_length(Rows), Rows),
            append(Rows, Vs), Vs ins 1..9,
            maplist(all_distinct, Rows),
            transpose(Rows, Columns),
            maplist(all_distinct, Columns),
            Rows = [As,Bs,Cs,Ds,Es,Fs,Gs,Hs,Is],
            blocks(As, Bs, Cs),
            blocks(Ds, Es, Fs),
            blocks(Gs, Hs, Is).

            blocks([], [], []).
            blocks([N1,N2,N3|Ns1], [N4,N5,N6|Ns2], [N7,N8,N9|Ns3]) :-
            all_distinct([N1,N2,N3,N4,N5,N6,N7,N8,N9]),
            blocks(Ns1, Ns2, Ns3).

            problem(1, [[_,_,_,_,_,_,_,_,_],
                        [_,_,_,_,_,3,_,8,5],
                        [_,_,1,_,2,_,_,_,_],
                        [_,_,_,5,_,7,_,_,_],
                        [_,_,4,_,_,_,1,_,_],
                        [_,9,_,_,_,_,_,_,_],
                        [5,_,_,_,_,_,_,7,3],
                        [_,_,2,_,1,_,_,_,_],
                        [_,_,_,_,4,_,_,_,9]]).

            main :-
            problem(1, Rows), sudoku(Rows), maplist(portray_clause, Rows).

            :- initialization(main).
            `;
            const result = eval_code(code);
            document.write(`<p>Sudoku solver returns:</p><pre>${result}</pre>`);
        }
        run();
        </script>    
    </head>
    <body></body>
</html>

Then you can serve it with your favorite http server like python -m http.server or npx serve, and access the page with your browser.

Docker Install

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 f to see up to the next multiple of 5 answers, and a to see all answers. Press h to show a help message.

Use TAB to complete atoms and predicate names in queries. For instance, after consulting the program above, typing decl followed by TAB yields declarative_world. Press TAB repeatedly to cycle through alternative completions.

To quit Scryer Prolog, use the standard predicate halt/0:

?- halt.

Starting Scryer Prolog

Scryer Prolog can be started from the command line by specifying options, files and additional arguments. All components are optional:

scryer-prolog [OPTIONS] [FILES] [-- ARGUMENTS]

The supported options are:

   -h, --help             Display help message
   -v, --version          Print version information and exit
   -g, --goal GOAL        Run the query GOAL after consulting files
   -f                     Fast startup. Do not load initialization file (~/.scryerrc)
   --no-add-history       Prevent adding input to history file (~/.scryer_history)

All specified Prolog files are consulted.

After Prolog files, application-specific arguments can be specified on the command line. These arguments can be accessed from within Prolog applications with the predicate argv/1, which yields the list of arguments represented as strings.

Prolog files can also be turned into shell scripts as explained in https://github.com/mthom/scryer-prolog/issues/2170#issuecomment-1821713993.

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

A very compact internal representation of strings is one of the key innovations of Scryer Prolog. This means that terms which appear as lists of characters to Prolog programs are stored in packed UTF-8 encoding by the engine.

Without this innovation, storing a list of characters in memory would use one WAM memory cell per character, one cell per list constructor, and one cell for each tail that occurs in the list. Since one cell takes 8 bytes in the WAM as implemented by Scryer Prolog, the packed representation yields an up to 24-fold reduction of memory usage, and corresponding reduction of memory accesses when creating and processing strings.

Scryer Prolog's compact internal string representation makes it ideally suited for the use case Prolog was originally developed for: efficient and convenient text processing, especially with definite clause grammars (DCGs) as provided by library(dcgs) and library(pio) to transparently apply DCGs to files.

In Scryer Prolog, the default value of the Prolog flag double_quotes is chars, which is also the recommended setting. This means that lists of characters can be written as double-quoted strings, in the tradition of Marseille Prolog.

For example, the following query succeeds:

?- "abc" = [a,b,c].
   true.

This shows that the string "abc", which is represented as a sequence of 3 bytes internally, appears to Prolog programs as a list of characters.

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.

The efficient internal representation of strings and partial strings was first proposed and explained by Ulrich Neumerkel in issues #24 and #95, and Scryer Prolog is the first Prolog system that implements it.

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:

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:

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:

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.

Applications

Scryer Prolog's strong commitment to the Prolog ISO standard makes it ideally suited for use in corporations and government agencies that are subject to strict regulations pertaining to interoperability, standards compliance and warranty.

Successful existing applications of Scryer Prolog include the DocLog system which generates Scryer's own documentation and homepage, Symbolic Analysis of Grants by the Austrian Federal Computing Center, and parts of the precautionary package for the analysis of dose-escalation trials in the safety-critical and highly regulated domain of oncology trial design, described in An Executable Specification of Oncology Dose-Escalation Protocols with Prolog.

Scryer Prolog is also very well suited for teaching and learning Prolog, and for testing syntactic conformance and hence portability of existing Prolog programs.

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 or visit our #scryer IRC channel on Libera!