Offline Partial Evaluator for Prolog

                  __  __
 _ __  _ __ ___  / _|/ _|
| '_ \| '__/ _ \| |_| |_
| |_) | | | (_) |  _|  _|
| .__/|_|  \___/|_| |_|
|_|

A web interface is also available

Try also CPD lite, a lightweight approach to conjunctive partial evaluation for Prolog

`proff`: a Prolog offline partial evaluator `(v1.2)`

This is a simple implementation of an offline partial evaluator for Prolog programs. The current implementation contains 6 files:

proff.pl: this is the main module; it only loads the remaining modules and prints an initial message.
front_end.pl: this module contains facilities for reading in source programs, clearing the database or writing down residual programs.
size_change.pl: this module implements the size-change analysis that is performed on the source program.
bta.pl: this module implements a simple, monovariant binding-time anaylsis that helps to improve the precision of the specialization.
annotation.pl: this module includes an annotation procedure that takes the source program and the output of the size-change analysis and the BTA, and produces an annotated program that can be used to guarantee the termination of the specialisation phase.
peval.pl: this module contains the proper specialisation phase. It implements an unfolding strategy which is based on the program annotations; roughly, if an atom is, after replacing annotated subterms by fresh variables, a variant of an already unfolded atom, then it cannot be unfolded. Global termination is ensured by splitting conjunctions and generalizing away annotated arguments. This module also includes the renaming of the specialised clauses.

A technical description of the size-change analysis, the annotation procedure and the offline partial evaluator can be found in this paper.

The source code of the partial evaluator can be downloaded here: proff.tgz. Once you have downloaded this file, you should unpack it, e.g.

tar xvfz proff.tgz

so that a folder proff is created which contains the source files of the partial evaluator and a subfolder examples with several simple examples. In order to run the partial evaluator, you can follow these steps:

First, move to folder proff and load the file proff.pl in your Prolog environment (note that the partial evaluator has only been tested in SICStus Prolog so far):

[guest@localhost ~]$ tar cvfz proff.tgz
[guest@localhost ~]$ cd proff
[guest@localhost proff]$ sicstus -l proff
                  __  __
 _ __  _ __ ___  / _|/ _|     DSIC
| '_ \| '__/ _ \| |_| |_      Technical University of Valencia (Spain)
| |_) | | | (_) |  _|  _|
| .__/|_|  \___/|_| |_|       German Vidal & Salvador Tamarit
|_|

A simple offline partial evaluator for Prolog / v1.2 (Sep 2007)

Type h to see the available commands...

| ?- h.

Available commands:
  read_file            (r) - reads in a source program
  clear_database       (c) - deletes the stored program
  size_change_analysis (s) - performs the size change analysis
  bta                  (b) - computes a simple BTA
  program_annotation   (a) - applies the program annotation procedure
  peval                (p) - starts partial evaluation
  all                      - equivalent to r,s,b,a,p

yes
| ?-

Let us illustrate the stepwise process. First, you can read in a source file (only pure Prolog is allowed) and perform the size-change analysis, BTA, and program annotation on this program, e.g.:

| ?- read_file.
Filename? (type a dot at the end): 'examples/incList.pl'.
clauses stored: 16
File loaded!
yes
| ?- size_change_analysis.
Size-change analysis - runtime: 0 ms. / absolute time elapsed: 0 ms.
yes
| ?- bta.
Abstract atom? (type a dot at the end): incList(d,s,d).
BTA - runtime: 0 ms. / absolute time elapsed: 0 ms.
yes
| ?- program_annotation.
Program annotation - runtime: 0 ms. / absolute time elapsed: 0 ms.
yes
| ?-

Observe that r, s, b and a can also be used as a shorthand for read_file, size_change_analysis, bta, and program_annotation, respectively.

Now, you can partially evaluate the source program w.r.t. a given initial atomic query. For instance, the program incList:
```
incList([],_,[]).
incList([X|R],I,L) :- iList(X,R,I,L).

iList(X,R,I,[XI|RI]) :- nat(I),add(I,X,XI), incList(R,I,RI).

nat(0).
nat(s(X)) :- nat(X).

add(0,Y,Y).
add(s(X),Y,s(Z)) :- add(X,Y,Z).
```
defines a predicate incList that adds a given number to every element of a list. This program can be partially evaluated w.r.t. the initial query incList(L,s(s(s(s(0)))),LI) so that a new version of predicate incList is obtained that can be used to increment every list element by four:
```
| ?- peval.
Atom? (type a dot at the end): incList(L,s(s(s(s(0)))),LI).

Partial evaluation (stored in file examples/incList_pe.pl):

incList2_0([],[]).
incList2_0([A|B],[s(s(s(s(A))))|C]) :- incList2_0(B,C).

Partial evaluation terminated successfully!

Try loading the residual program 
and calling the partially evaluated predicate: incList2_0/2

Partial evaluation - runtime: 10 ms. / absolute time elapsed: 10 ms.
yes
| ?- 
```
You can load both programs incList.pl and incList_pe.pl in the Prolog environment and run bench (which is only used for benchmarking). The user can indicate which predicates are only intended for benchmarking using a fact of the form ignore_predicates([(predName,arity),(predName,arity),...]).
You may try partially evaluating of all examples in folder examples (detailed instructions appear in the source code of every example).
Please report any bug or comment to gvidal (at) dsic (dot) upv (dot) es.

MiST ELP GPLIS DSIC UPV

Last update / Germán Vidal

A web interface is also available

Try also CPD lite, a lightweight approach to conjunctive partial evaluation for Prolog

proff: a Prolog offline partial evaluator (v1.2)

`proff`: a Prolog offline partial evaluator `(v1.2)`