The Starlog Project
A new Logic Programming Language

The Starlog Project

Waikato University crest
Computing and Mathematical Sciences

Valid HTML 4.01!

 
!!!STOP PRESS!!! As a follow-on to the Starlog project, we are now developing a new language, called JStar, that shares many of the advantages of Starlog, but is designed to be efficiently implemented on parallel computers. See the JStar Web Page for more details.


What is Starlog?

Starlog is a pure-logic programming language designed to overcome some of the problems inherient in traditional approaches to logic programming. As a result, Starlog is designed to be a general purpose programming language, and is particularly useful for simulation, and for modelling reactive systems. Although most logic programming languages (e.g. Prolog) are query driven (i.e. are evaluated  "top-down"), Starlog programs are evaluated "bottom-up". That is, as a Starlog program executes, it builds a model of all the true facts that can be derived from rules in the program. The evaluation of Starlog programs is controlled using a stratification order.

Motivation

Traditionally, logic programming languages have never been able to compete with the popularity of other language paradigms. We attribute this to:
  • Most implementations of logic programs being less efficient at run time than equivalent programs from other language paradigms.
  • The introduction of extra-logical operators that improve efficiency often break the declarative semantics of logic programs.
  • Common programming facilities (such as side-effects) either have no declarative semantics or are achieved using inelegant solutions.
  • The use of depth-first resolution techniques (prevalent in the most logic programming languages) can be inefficient for many search problems (especially those involving cycles).
Based on these observations, Starlog was designed as an alternative approach to programming in pure logic. Many of the failings of other logic programming languages can be overcome using the bottom-up evaluation technique. Bottom-up evaluation avoids problems associated with cyclic relations, and allows side-effects to be performed without compromising the declarative semantics of a program. Unlike top-down evaluation, where the efficiency of a program is related to the efficiency of recursive clause processing, the efficiency of bottom-up evalution is more closely related to the access properties of run time data. Therefore, improvements in the run time performance of bottom-up evaluation can be achieved by improving access to data.

Starlog Concepts

To control bottom-up evaluation Starlog programs specify a stratification order. In other words, programs include a description of the partial order that facts are derived. A stratification order is useful for two reasons. (1) By controlling the order that facts are derived the efficiency of a program can be improved. In this way programmers can avoid redundant computations (which is the key critisim of bottom-up evaluation). (2) Using a stratification order allows programs to use stratified negation to conclusively deduce when facts will never be derived by a program.

Using Starlog we advocate a data structure free programming style. That is, predicates in Starlog programs do not contain compound terms for their arguments. This greatly simplifies logic programs and their implementations, lowers the learning curve for new programmers, and forces the programmer to think of all program constructs as relations. Moreover, implementations of Starlog programs can decide how to store and index relations in an internal database, which is usually much more desirable for programmers.

Input and output in Starlog can be achieved elegantly using bottom-up evaluation. Because bottom-up evaluation applies all rules independently, some rules can generate side-effects when a new fact "output" is derived. Because rules do not interfere with each other, adding side-effects to a program can be achieved without changing any of the existing rules. Input can be requested by producing "input request" tuples. Input is received in the form of a new fact which can be refered to by any rule.

Examples

To demonstrate the expressiveness of Starlog we provide two example programs. The first example is a program to derive hamming numbers. The last rule in this program demonstrates how side-effects can be performed by a Starlog program without modifying the other rules in the program.

% Hamming Number Program
%-----------------------------------------------------------------------
% Generates all numbers between 1 and 100,000 whose prime factors are
% only 2, 3 and 5, in ascending order.

% Header
stratify hamming(N) by [N,hamming]. % Order hamming numbers on their value
stratify print(N) by [N,print]. % Order prints on their value
stratify hamming << print. % Derive hamming values before printing

% Program
hamming(1).                                  % Initial Fact

hamming(New) <-- hamming(Old),                % Generates multiples of 2
                New is Old*2, New < 100000.
hamming(New) <-- hamming(Old),                % Generates multiples of 3
                New is Old*3, New < 100000.
hamming(New) <-- hamming(Old),                % Generates multiples of 5
                New is Old*5, New < 100000.

print(Num) <-- hamming(Num). % Print each hamming number

This program generates the following sequence of hamming numbers:
1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 ... 98304 98415
The next program generates the sequence of prime numbers using a variation on the ``Sieve of Eratosthenes'' algorithm and uses negation to deduce which numbers are primes.

% Prime Number Program
%----------------------------------------------------------------------
% Generates prime numbers between 2 and 10,000 by finding all multiple
% values and then using negation to find values that are not multiple
% values.

% Header
stratify num(N) by [N,num].     % Order all tuples on their number
stratify mult(N) by [N,mult].     % argument      
stratify prime(N) by [N,prime].
stratify print(_,N) by [N,print].
stratify num << prime.               % Ensure primes are stratified late   
stratify mult << prime. % and prints are even later
stratify prime << print.
% Program
num(2).

num(M) <-- num(N), M is N+1,         % Generate all numbers in range
          M < 10000.
mult(M) <--  num(N), prime(P), N >= P, % Generate multiple values
           M is N*P, M < 10000.

prime(N) <-- num(N), not(mult(N)).    % Deduce prime numbers
print(Str,N) <-- prime(N),             % Output prime number in a string 
Str = '\nPrime number: '+N.

This program generates the following sequence:
Prime number: 2
Prime number: 3
Prime number: 5
Prime number: 7
Prime number: 11
Prime number: 13
Prime number: 17
Prime number: 19
Prime number: 23
Prime number: 29
Prime number: 31
Prime number: 37

Downloads

Currently there are three ways to execute Starlog programs:

We provide a compiler to compile Starlog programs into Java source code. The compiler performs a number of high-level code optimisations including the automatic selection of efficient data structures for the program's run time data. The latest version of the Starlog compiler has been tested under Linux (more specifically, Debian and Red Hat distributions) and Mac OSX. To use the compiler download the lastest version from here:
To install the compiler extract the starlog.0.2 directory from the tar, gzip archive. Change to the starlog.0.2 directory and run the install.sh script on the command line. If you require any additional instructions consult the README file.

We provide an interpreted environment implemented on Gnu Prolog designed to conservatively (and therefore safely) evaluate Starlog programs. This environment is ideal for program development and debugging. The interpreted environment is included with the compiler download.

We also have a compiler that generates code used by LEGO MINDSTORMS(TM) Robotics Invention System (using the LegOS kernel for the robot). Currently version 0.3 (2 June 2001) of the Starlog/LEGO compiler is available for beta-testing. This translates Starlog into C or Java, which can be compiled and run as a standalone program. Note that this compiler executes a subset of the Starlog language, and is no longer supported or updated by the project.

The Starlog/LEGO compiler is available in two forms:


Publications

Lunjin Lu, and Cleary, J.G., (1999). "An Operational Semantics of Starlog",. Proc. Principles and Practice of Declarative Programming 1999, Paris, pp. 131-162. Springer-Verlag. Archived at citeseer.ist.psu.edu/lu99operational.html

John Cleary, and Mark Utting, "Verification of Starlog Programs", Archived at citeseer.ist.psu.edu/453223.html

Roger Clayton, John G. Cleary, Bernhard Pfahringer, and Mark Utting, (2002)  "Optimising Tabling Structures for Bottom-Up Logic Programming", Preproceedings of the International Workshop on Logic Based Program Development and Transformations 2002, pp.57-75

J. Cleary, M. Utting, and R. Clayton, (2000) "Data Structures Considered Harmful", Proceedings of the Australasian Workshop on Computational Logic, Editor John Lloyd, pp. 111-120, 2000, Archived at citeseer.ist.psu.edu/445208.html

John G. Cleary, Roger Clayton, Mark Utting, and Bernhard Pfahringer, "A Semantics and Implementation of Stratified Logic Programs", Technical Report 03/2004, University of Waikato, Hamilton, New Zealand, 2004.

Roger Clayton, "Compilation of Bottom-Up Evaluation for a Pure Logic Programming Language", PhD Thesis,
University of Waikato, Hamilton, New Zealand, 2004.

Researchers


Prof John Cleary

Dr Bernhard Pfahringer

Dr Mark Utting

Roger Clayton