|
|
|
!!!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
|
