Department of Computer Science School of Computing and Mathematical Sciences

JStar

JStar Home


Example executions of Starlog/JStar Programs

Here are several small example programs, written in both JStar and Starlog syntax, with links to their execution traces, using three different example selection functions:

  1. Sequential Execution (do one tuple and one rule at a time).
  2. Event List Execution (do all the minimum tuples in parallel).
  3. Maximum Parallelism (be as eager as possible). This may generate tuples far into the future, so can be too resource hungry. It still does not do any speculative parallelism.

The final set of tuples generated by each program (the Gamma set) is the union of all tuples that appear in the New column. Each trace was generated with the Incremental Delta interpreter and lists the variables used in the interpreter (α, New, Delta, D0, D1 and D2). The executions of the other two interpreters (the Simple Interpreter and the Incremental Gamma Interpreter) are identical except they do not use D0, D1, or D2.

Primes Program with simple ordering

Here is the JStar syntax of a simple Primes program that prints primes between 1..18. This program would print the following output:

    prime: 2
    prime: 3
    prime: 5
    prime: 7
    prime: 11
    prime: 13
    prime: 17

// these all use the default order: [arg1, NameOfRelation]
data Num(value:int)
data Mult(multiple:int, increment:int)
data Prime(prime:int)
order {Num,Mult} < Prime < Println

rule startup() {
    for (v : 1..18) {  // NB. 'for' loops are parallel-only
        put Num(v)
    }
}

rule firstMultiple(p:Prime) {
    val sq = p.prime * p.prime
    put Mult(sq, p.prime)
}

rule nextMultiple(m:Mult) {
    put Mult(m.multiple + m.increment, m.increment)
}

rule prime(n:Num) {
    not Mult(n.value, _)
    put Prime(n.value)
    put Println(n.value, "prime: " + n.value)
}

Here is the corresponding Starlog syntax for the same program.

% These declarations define the allowable evaluation orderings.
% We order all tuples by their first argument, followed by an
%  enumerated constant (which is the same as the name of the tuple),
%  except for println, where the time argument is the second argument
%  for historical reasons.
stratify num(N)       by [N,num].
stratify mult(N,_)    by [N,mult].              
stratify prime(N)     by [N,prime]. 
stratify println(_,N) by [N,println].
stratify num << prime.               % Ensure primes are stratified late    
stratify mult << prime.
stratify prime << println.

type num(int).
type mult(int,int).
type prime(int).
type println(term,int).

num(2)   <-- true.
num(N+1) <-- num(N), max(L), N < L.    % Generate all numbers in range

mult(M, P) <-- prime(P), M is P * P, M =< 18.
mult(M, P) <-- mult(N, P), M is N + P, M =< 18.

prime(N) <-- num(N), not mult(N,_).    % Deduce prime numbers

println(prime(N),N) <-- prime(N).

Primes Program with second ordering

Primes program using a more complex ordering (TODO: explain the difference).

Running-Maximum Program

This program incrementally outputs the maximum of all input numbers seen so far. It illustrates input, negation, assignment and how to make large jumps in time. The input tuples, Input(time, num), could be lines of input from a text file or standard input, or numbers arriving sporadically in real-time from some input device. Whenever an input tuple causes the current maximum value to increase, a line like "max = N" is printed.

If the following input tuples were received:

    Input(1,13)
    Input(4,11)
    Input(7,23)
    Input(10,42)
the program would print this output (the output times shown are not part of the actual output):
    max = 13                   // time=1
    max = 23                   // time=7
    max = 43                   // time=10

JStar version of this Running-Maximum program. (Here all data tuples use the default stratification ordering. The before keyword handles the often-needed case of finding the most recent tuple before a given time - it is semantically equivalent to the complex negation in the Starlog version. The get? keyword means that 0 or 1 solutions are expected for the following query.)

data Input(time:int, num:int)
data Assign(time:int, key:string, value:int)
order Input < Assign < Println

rule firstInput(input:Input) {
    not Assign(before input.time, "max")
    put Assign(input.time, "max", input.num)
    put Println(input.time, "max = " + input.num)
}

rule otherInputs(input:Input) {
    get? prevAssign = Assign(before input.time, "max")
    when input.num > prevAssign.value
    put Assign(input.time, "max", prevAssign.value)
    put Println(input.time, "max = " + prevAssign.value)
}

To reduce the code duplication here, the two rules could be combined into one, by using an if-else statement, with a Java-like final variable to capture a value from both branches of the conditional.
rule calculateMax(input:Input) {
    final newMax:int
    if (get? prevAssign = Assign(before input.time, "max")) {
        when input.num > prevAssign.value
        newMax = prevAssign.value
    } else {
        newMax = input.num
    }
    put Assign(input.time, "max", newMax)
    put Println(input.time, "max = " + newMax)
}

Starlog syntax for the same program.

stratify input(Time, Num)            by [Time, input].
stratify assign(Time, Key, Value)    by [Time, assign].
stratify val(Time, Key)              by [Time, val].
stratify value(Time, Key, Value)     by [Time, value].
stratify value_neg(Time, Key, Value) by [Time, value_neg].
stratify println(Term, Time)         by [Time, println].
stratify input << val.
stratify val << value_neg.
stratify value_neg << value.
stratify value << assign.
stratify assign << println.

type input(int,int).
type assign(int, term, int).
type val(int, term).
type value(int, term, int).
type value_neg(int, term, int).
type println(term, int).

% some example input
input(1,13) <-- true.
input(4,11) <-- true.
input(7,23) <-- true.
input(10,42) <-- true.

println(max(T, M), T) <-- assign(T, max, M).

assign(T, max, N) <-- input(T, N), value(T, max, M), M < N.
assign(T, max, N) <-- input(T, N), not(value(T, max, _)).

val(T, max) <-- input(T, _).

%% This records the current assignment (when each input arrives).
value(T, K, M) <-- 
	val(T, K),
	assign(T0, K, M),
	T0 < T,
	not(U < T, T0 < U, assign(U, K, _)).

%% Note: the above compound negation is transformed to:
%%   not(value_neg(T, K, T0)), where value_neg is as follows:

value_neg(T, K, T0) <-- 
	val(T, K),
	assign(T0, K, _),
	T0 < T,
	assign(U, K, _),
	U < T,
	T0 < U.