
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:
 Sequential Execution (do one tuple and one rule at a time).
 Event List Execution (do all the minimum tuples in parallel).
 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 parallelonly
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).
RunningMaximum 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 realtime
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 RunningMaximum program. (Here all data tuples use
the default stratification ordering. The before keyword handles the
oftenneeded 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 ifelse statement, with a Javalike
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.

