Descriptions of Some Programs in the Benchmark Suite

Several programs in the suite have become more or less standard for the evaluation of data-flow analyzers. Others, the more interesting ones, are real applications. Please note that the list below is rather incomplete: at present, only half of the benchmarks are described here.

Credits

Program Descriptions

action.pl

An interpreter for action semantics written by S. Diehl.

ac_fix.pl

A residential air conditioning diagnosis system, originally written in A.D.A. Prolog by C. Bredlau.

8puzzle.pl

A program to solve the ``Eight-Puzzle'' using iterative deepening.

air.clpr

A program to calculate excess air needed for a chemical reaction to proceed in some way, an example program included in the distribution of CLP(R) 2.0 by Monash University.

aircraft.pl

A program for reasoning on aircraft routes and profiles (author unknown).

ann.pl

A simplified clause annotator by M. Hermenegildo, R. Warren, and M. Muthukumar.

aqua_c.pl

The Aquarius Prolog compiler, by P. Van Roy.

arch1.pl

A machine learning program implementing Winston's incremental learning procedure, by S. Wrobel.

bmtp.pl

A sophisticated Boyer-Moore's theorem prover, apparently by H. Fujita, copyrighted by the Institute for New Generation Computer Technology.

boyer_wamcc.pl

A Boyer-Moore theorem prover written by E. Tick after the Lisp version by R. P. Gabriel.

bp0-6.pl

A graphs search program by E. Tick.

bridge.clpr

A bridge modeling program.

browse_wamcc.pl

The ``Browse'' program written by T. Dobry (with modifications by H. Touati) after the original LISP version by R. P. Gabriel.

bryant.pl

A Prolog implementation of ROBDDs by P. Schachte.

bup-all.pl

The BUP system, a parser generator from Definite Clause Grammars by Y. Matsumoto.

caslog.pl

A semi-automatic complexity analysis system for logic programs, by N.-W. Lin.

cg_parser.pl

A natural deduction CG parser with semantics, by B. Carpenter.

chasen-all.pl

ChaSen version 1.51, a Japanese morphological analysis system, by Y. Den, O. Imaichi, Y. Matsumoto, and T. Utsuro.

chat80.pl

A famous query answering system by F. Pereira and D. H. D. Warren.

chat_parser.pl

A parser for a set of English sentences taken from Chat80.

chemreac.risc

A program for the analysis of chemical reactions presented in O. Caprotti, RISC-CLP(R-Trees): RISC-CLP(Real) Handles Symbolic Functions, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems (DISCO'93), Springer-Verlag, 1993.

chess.pl

A Prolog chess program, originally the result of the Artificial Intelligence Project at the ``Computer-Club der RWTH Aachen'' (KI --- Gruppe 89/90), ported to standard Prolog by M. Ostermann.

circuit.clpr

A simple circuit simulator.

cobweb.pl

A machine learning program implementing Gennari's incremental concept formation algorithm, by J.-U. Kietz.

crip.pl

A program to compute counter-models to intuitionistic propositional formulae using a calculus without loop-checking, by L. Pinto and R. Dyckhoff (based on a paper by the same authors at the Symposia Gaussiana conference, Munich, 1993).

critical.clpr

A scheduling program.

crypt_wamcc.pl

A program written by P. Van Roy for solving crypto-multiplication problems.

cs2.pl

A cutting-stock program.

csg.clpr

A program for semi-deciding the intersection of two solids in CSG representation.

cugini_utilities.pl

The so called ``Cugini Utilities'', by J. Cugini.

curry2indy.pl

Curry to INDY translator by E. Campos and M. Albert.

demo_fsa2.pl

A program for tracing a finite state machine, by P. J. Hancox.

difflists.pl

A collection of useful predicates for difference lists, from The Art of Prolog, by L. Sterling and E. Y. Shapiro, The MIT Press, 1986.

disj_r.pl

The generate and test version of a disjunctive scheduling program.

dnf.clpr

A program, from the CLP(R) 1.2 test-suite, to put boolean formulae in disjunctive normal form.

dposan.pl

A (buggy version of a) data-flow analyzer for groundness employing Pos and some abstractions of it, by A. King.

eliza.pl

A Prolog version by V. Patel of the famous Eliza program.

files.pl

A natural language interface to the Unix file system written by D. Mazzoni.

ftfsg.pl

A compiler and parser for flexible typed feature structure grammars, by M. Dahllof.

ftfsg2.pl

A compiler and parser for flexible typed feature structure grammars with a graphical interface, by M. Dahllof.

ga.pl

A simple genetic algorithm implemented in Prolog.

gnup-1.1.0_pl2wam.pl

The Prolog to WAM compiler distributed with GNU Prolog 1.1.0., by D. Diaz.

grammar.pl

A simple sentence parser.

ileanTAP.pl

An intuitionistic theorem prover by J. Otten.

ime_v2-2-1.pl

A program by L. Zhuhai for solving linear multiple equations using Gauss method.

index.pl

INDEX: an experimental system for inductive data engineering written by P. A. Flach. For more information, see ``Predicate Invention in Inductive % Data Engineering'', in Proc. ECML '93, P. Brazdil (ed.), LNAI 667, Springer Verlag.

Below follows an example session with INDEX, an experimental system for % inductive data engineering. INDEX was implemented by Peter A. Flach. % The system is described in the paper "Predicate Invention in Inductive % Data Engineering", in Proc. ECML '93, P. Brazdil (ed.), LNAI 667, % Springer Verlag.

indy2curry.pl

A Syntax translator from INDY to Curry by S. Escobar.

jugs

A program to solve the ``Jugs'' puzzle, i.e., given two jugs of known capacities, you have to obtain a specified amount by filling jugs, emptying jugs, and pouring the contents of one jug into the other jug.

kalah

An alpha-beta procedure.

km-all

The ``Kilimanjaro'' Prolog compiler, by T. Lindgren.

knight

A program to find a knight's tour on an n × n chessboard so that the knight visits each square exactly once, inspired by an heuristic given in Advanced Prolog by P. Ross.

laplace.clpr

A program from the CLP(R) 1.2 test-suite solving the Dirichlet problem for Laplace's equation using Leibman's five-point finite-difference approximation.

lc.pl

A theorem prover for propositional Dummett logic LC, i.e., intuitionistic logic plus (A → B) ∨ (B → A), written by R. Dyckhoff.

ldl-all.pl

Version 3.4.7 of LDL, the Language Development Laboratory, copyrighted by the University of Rostock, Germany.

LeanTaP.pl

A tableau-based theorem prover for formulae in negation normal form by B. Beckert and J.Posegga.

lg_sys.pl

A huge program for computational linguistics, LexGram version 0.9.2 by E. Koenig, which includes the entire CUF system version 2.31. The CUF system implements the Comprehensive Unification Formalism, a formalism for unification grammars that was developed within the ESPRIT project DYANA and extended within projects DYANA-2 (ESPRIT) and B5 (SFB 340) at the Institut für Maschinelle Sprachverarbeitung (IMS), Universität Stuttgart, who holds the copyright.

life.pl

A program written by J. Andrews, with changes by W. Clocksin, for playing J. H. Conway's ``Game of Life''.

lilp.pl

LILP (Lambda Inductive Logic Programming): a system for learning predicate definitions from positive-only examples by Z. Markov.

linger_old.pl

An old version of the ``Language INdependent Grammatical Error Reporter'', by J. Barchan and J. Wusteman.

linsys.pl

A routine that solves an arbitrarily large system of linear equations, by G. Brenner.

linTAP.pl

A theorem prover for Multiplicative Linear Logic M?LL, i.e., multiplicative linear logic with positive `?' and negative `!', written by J. Otten.

linus.pl

LINUS, a system that allows the use of background knowledge in learning. It can be used to learn relations (i.e., as an ILP system) or to take into account background knowledge for propositional learning tasks. By N. Lavrac, S. Dzeroski, and M. Grobelnik.

ljt.pl

An intuitionistic theorem prover using LWB syntax, by R. Dyckhoff. For more information see ``Contraction-free calculi for intuitionistic logic'' by the same author, appeared in the Journal of Symbolic Logic, 1992.

llprover.pl

A linear logic theorem prover for SICStus Prolog by N. Tamura with TeX form output by E. Sugiyama.

log_interpreter.pl

Version 3.0.8 of the {log} interpreter by A. Dovier, E. Omodeo, C. Piazza, E. Pontelli, and G. Rossi.

lojban.pl

The Lojban semantic analyzer by N. Nicholas.

loops.pl

A program to compute a list of all the minimal cycles in a directed graph, by R. Bagnara.

lpe.pl

Full machinery for Lazy Partial Evaluation, by P. Clark and R. Holte.

lptp-1.06.pl

Version 1.06 of LPTP, a Logic Program Theorem Prover by R. F. Staerk.

map.pl

A tool for transforming logic programs by S. Renault.

markus.pl

The Markus system for the induction of Prolog programs, by M. Grobelnik.

mastermind.pl

A program implementing the game ``Mastermind'', rewritten by H. Koenig and T. Hoppe after code by M. H. van Emden Also in H. Coelho and J. C. Cotta, ``Prolog by Example'', Symbolic Computation, Springer-Verlag, Berlin, 1988).

mdgtools-1.0.pl

A package for Multiway Decision Graphs (MDGs). MDGs represent and manipulate a subset of first-order logic formulas suitable for high-level hardware verification. Copyright by the University of Montreal.

metutor.pl

The ``Metutor'' means-ends tutoring system by N. C. Rowe, instantiated over the ``firefighting tutor'' example application.

mfoil.pl

The ``mFOIL'' inductive logic programming system. It is based on Quinlan's ``FOIL'' and includes several techniques for handling imperfect (noisy) data. Written by S. Dzeroski.

mixtus-all.pl

An automatic partial evaluator for full Prolog, by D. Sahlin.

nand_wamcc.pl

A program by B. Holmer implementing a rough approximation to the algorithm presented in E. S. Davidson, ``An Algorithm for NAND Decomposition Under Network Constraints'', IEEE Trans. Comp., vol. C-18, no. 12, Dec. 1969, p. 1098.

neural.clpr

A neural network simulation program.

noughts_and_crosses.pl

A program by D. Green to play an interactive game of noughts and crosses.

nbody.pl

A program solving the $n$-body problem for star clusters by E. Tick.

oldchina.pl

A prehistoric version of CHINA, when it was written in Prolog.

option.clpr

A program from the CLP(R) 1.2 test-suite for the algebraic combinations of options transactions.

palindrome.pl

A benchmark program from D. H. D. Warren's thesis.

pappiall.pl

The ``Pappi'' tool for computational linguistics: the system can be used to define and test principle-based grammatical theories. Written by S. Fong with help from several others.

parser_dcg.pl

A parser by R. Bagnara, based on Definite Clause Grammars, for both an imperative and a functional higher-order languages.

peephole1.pl

The peephole optimizer of SB-Prolog 3.0.

petsan.pl

A groundness data-flow analyzer for Prolog, using the Pos domain implemented by means of ROBDDs, by P. Schachte.

peval.pl

A self-applicable partial evaluator for the flow-chart language described in Chapter 4 of Partial Evaluation and Automatic Program Generation, by N. D. Jones, C. K. Gomard, and P. Sestoft, Prentice-Hall, 1993.

pg.pl

A program written by W. Older to solve a particular mathematical problem.

piza-0.9.22.pl

A version of PiZA: Prolog Z Animator by M. A. Hewitt.

plaiclp.pl

A version of PLAI, the UPM-CLIP framework and environment for developing global analyzers based on abstract interpretation.

pmatch.pl

A text-dictionary matcher by A. Michiels.

plan.pl

A famous planning program by D. H. D. Warren.

poly10.pl

A program to symbolically raise polynomials to integer powers, written by R. Haygood and R. McGeer after the Lisp version by R. P. Gabriel.

press.pl

A program for solving equations taken from Chapter 23 of The Art of Prolog, by L. Sterling and E. Y. Shapiro, The MIT Press, 1986.

puzzle.pl

A version of the houses (zebra) program as presented in Constraint Satisfaction in Logic Programming, by P. Van Hentenryck, The MIT Press, 1989.

quotan.pl

A data-flow analyzer for groundness employing a quotient of Sharing, by A. King.

read.pl

A Prolog reader by D. H. D. Warren and R. O'Keefe, with modifications by A. Mycroft.

reducer.pl

A graph reducer for T-combinators by P. Van Roy.

reg.pl

The ``Regular Approximation Tool'' by J. Gallagher.

rings-on-pegs.clpr

A program solving a combinatorial puzzle involving rings joined with strings of various lengths to be placed on a pegboard on which a number of pegs are set.

rubik.pl

A Rubik's cube solver written by D. Merritt as described in Building Expert Systems in Prolog, Springer-Verlag, 1989.

sax.pl

The SAX natural language parsing system by Y. Matsumoto and Y. Den.

scc.pl

A program written by S. Diehl for computing the strongly-connected components of a graph.

sdda.pl

A data-flow analyzer that represents aliasing.

semi.pl

A program for playing with semigroups, by M. Carlsson.

sim.pl

A simulator for OR-parallel Prolog, by K. Shen.

sim_v5-2.pl

An algebra simplifier by L. Zhuhai.

simple_analyzer.pl

A simple data-flow analyzer written by P. Van Roy.

slice-all.pl

An interpreter, based on the SOS approach, for both an imperative and a functional higher-order languages, written by R. Bagnara.

spsys.pl

The SP system, comprises a collection of programs for performing specialization (partial evaluation), some other program transformations, and some program analyses. Copyright by J. Gallagher.

squares.clpq

A CLP(Q) program by A. Colmerauer that solves the difficult problem of tiling a rectangle with squares of all-different, a priori unknown sizes. The CLP(Q) translation of the original Prolog-III program, appeared in A. Colmerauer, An Introduction to Prolog III, Communications of the ACM, 33(7), 69-90, 1990, is due to C. Holzbaur.

synth.pl

A transformation system for functional logic programs based on needed narrowing.

tictactoe.pl

A program of tic-tac-toe by a student of A. K. Bansal.

trees1.pl

A program to draw compound terms as trees, by T. Grech.

trs.pl

An automated prover for first-order classical predicate logic based on a modified version of Gentzen's sequent calculus LK, by K. Sakai.

tsp.pl

A program to find near-optimal solutions to the Traveling Salesman Problem.

unify.pl

A compiler code generator for unification written by P. Van Roy.

vhdl97_parser.pl

A VHDL-AMS Parser and Pretty-Printer in Prolog. The original VHDL-87 parser written in Quintus Prolog is due to P. B. Reintjes (then at Microelectronics Center of North Carolina, Reasearch Triangle Park). This parser was revised to conform to the IEEE 1076-1993 standard of VHDL and ported to SWI-Prolog by K. Thirunarayan. Now it has been further revised to meet IEEE 1076.1 standard of VHDL (also called VHDL-AMS) and can be downloaded from http://www.cs.wright.edu/people/faculty/tkprasad/.

vsp.pl

A very simple top-down parser that allows the choice of depth-first or breadth-first control, by P. Hancox.

warplan.pl

The famous ``Warplan'' robot problem solver written by D. H. D. Warren.

yasmm.pl

Yet another program to solve the ``SEND + MORE = MONEY'' puzzle.

zebra.pl

Yet another version, written by Santos-Costa, of the houses (zebra) program.