HOPES: Higher-Order PROLOG with Extensional Semantics

HOPES is a prototype interpreter for a higher-order PROLOG-like language.

The syntax of the language extends that of PROLOG by supporting higher-order constructs (such as higher-order predicate variables, partial application and lambda terms). In particular, the syntax allows clauses (and queries) that contain uninstantiated predicate variables. The interpreter implements a higher-order top-down SLD-resolution proof procedure described in CKRW13 together with the semantics of the language.

HOPES has all the advantages of a higher-order system but continues to keep the flavor of classical PROLOG programming.

Introduction

In HOPES one can express popular functional operators such as map:

map(R,[],[]).
map(R,[X|Xs],[Y|Ys]) :- R(X,Y), map(R,Xs,Ys).

Apart from using functional operators in a logic programming context, we can also express naturally relational operators and graph operators:

join(R,Q)(X) :- R(X), Q(X).
union(R,Q)(X) :- R(X).
union(R,Q)(X) :- Q(X).
singleton(Y)(X) :- X = Y.
diff(R,Q)(X) :- R(X), not(Q(X)). 
tc(G)(X,Y) :- G(X,Y).
tc(G)(X,Y) :- G(X,Z), tc(G)(Z,Y).

The definition of higher-order predicates together with the use of partial applications can lead to a different programming style that blends the functional and the logic programming. The following HOPES snipset shows how we can define except (i.e. the predicate that succeeds for all elements of R except Y) by reusing (possibly) partially applied operators.

except(R,Y)(X) :- diff(R, singleton(Y)).

As in classical PROLOG it is not required to use in a query some variables as input and some variables as output. Along that lines, HOPES also support queries that may have unbound predicate variables. For example, one can query

?- tc(G)(a, b).

to ask for potential graphs G whose transitive closure contains (a,b). In that case the interpreter will systematically (and in a sophisticated way) investigate all finite instantiations of these variables. The answers will be sets that represent the extension of G even if no such predicate is currently defined in the program. For example, potential answers of the aforementioned query will be:

G = { (a,b) } ;
G = { (a,X1), (X1,b) } ;
G = { (a,X1), (X1,X2), (X2,b) };

Getting Started

Building HOPES

In order to build HOPES you must have installed the GHC compiler version 6 or higher and the cabal system. You can download GHC from http://www.haskell.org/ghc/. The following sequence of cabal commands will install any depedencies and build the project.

It is recommended that you use a cabal sandbox for the build.

$ cabal update
$ cabal sandbox init
$ cabal install --only-dependencies
$ cabal configure && cabal build

Note for Windows

Microsoft Windows compilations are not yet tested but there should be no problem as far as GHC and cabal are installed in the system.

Running some examples

In pl/examples directory there are some hopes examples to getting started. To load an example you must type

-? :l pl/examples/file.pl