Logic and constraints
System.put_env("AL_MNESIA_DISTRIBUTED", "false")
System.put_env(
"AL_MNESIA_DIR",
Path.join(System.tmp_dir!(), "al_livebook_#{:erlang.unique_integer([:positive])}")
)
Mix.install(
[{:al, github: "anoma/AL-Ex"}],
config: [al: [transaction_programs: [AL.TransactionProgram.Bootstrap], natives: []]]
)
Setup
This notebook is self-contained. The cell above installs AL directly, no separate node, no cookie, nothing to attach to. The first run compiles AL and its dependencies from scratch, which takes a minute or two. Reopening this notebook later is fast, since Mix.install caches by the exact dependency and config combination. State here is throwaway. It lives only for this notebook's session and disappears when the session ends.
If you already have a real AL node running and want the persistent, shared store instead, see the intro for how to attach to it instead.
Mix.install has to finish running before AL's macros (run, defclass, and the rest) can be brought into scope, so that happens in its own cell here.
use AL
AL.Branch.head()
Run a method backwards
run do
factorial(n, 120)
end
=: a real constraint
= doesn't care which side is open. It's a real constraint, checked at bind time like dif, not a one-shot evaluation.
run do
n = 5
n1 = n - 1
end
The var can just as easily be buried inside the expression, on either side. No separate mode is needed.
run do
x = 10
x = y + 3
end
Propagate constraints about and between objects
run do
defclass :rectangle, super: :value, ivars: [:width, :height, :perimeter] do
defmethod(:init, [self, args, new]) do
get(args, :width, w)
get(args, :height, h)
get(args, :perimeter, p)
p = 2 * w + 2 * h
new = %{class: :rectangle, width: w, height: h, perimeter: p}
end
defmethod(:area, [self, result]) do
get(self, :width, w)
get(self, :height, h)
result = w * h
end
end
new(:rectangle, %{width: w, height: 3, perimeter: 16}, r)
area(r, a)
end
Comparisons narrow instead of failing
< > <= >= don't need a ground operand. An open var just gets its interval narrowed instead.
run do
y > 1
end
y is still open here, just narrowed rather than bound to one value. Only a genuinely non-numeric ground operand still hard-fails, since there's no interval to narrow against it.
run do
y > :not_a_number
end
Posting order doesn't matter
Posting x < y alone narrows nothing observable, since both sides are still open. But once y < 5 is posted too, x is transitively bound to satisfy the whole chain, without x < y ever being re-checked by hand. This is the propagator sitting parked and re-firing on its own, not a one-shot check.
run do
x < y
y < 5
x = 2
end
run do
x < y
y < 5
x = 10
end
The second one fails: 10 can't be less than something itself less than 5. Nothing about the order you posted the constraints in mattered, only what they jointly imply.
Infer an object's identity from its class and a slot
An open receiver turns the last two calls below into a search, not a lookup.
run branch: Examples.Support.branch() do
defclass :direct_vehicle, super: :object do
end
defclass :direct_car,
super: :direct_vehicle,
ivars: [%{name: :color, default: :red}] do
end
defclass :direct_hydrant,
super: :object,
ivars: [%{name: :color, default: :red}] do
end
new(:direct_car, car)
new(:direct_hydrant, hydrant)
findall(x, direct) do
class(x, :direct_vehicle)
label(x)
get(x, :color, :red)
end
findall(x, inherited) do
isa(x, :direct_vehicle)
label(x)
get(x, :color, :red)
end
findall(x, constrained_first) do
isa(x, :direct_vehicle)
get(x, :color, :red)
label(x)
end
class(car, :direct_car)
not [class(car, :direct_vehicle)]
isa(car, :direct_vehicle)
isa(candidate, ancestor)
ancestor = :direct_vehicle
candidate = car
end
dif and all_dif
dif(a, b) never resolves by binding anything itself. It only rules out bindings that would make its two sides equal.
run do
dif(x, 1)
x = 2
end
run do
dif(x, 1)
x = 1
end
Posted on a still-open var, dif drives backtracking directly. member's first clause offers x = 1, which violates the constraint and fails, so it falls through to x = 2 without 1 ever surfacing as a candidate.
run do
dif(x, 1)
member([1, 2, 3], x)
end
all_dif is the same idea over a whole list at once: every pair has to satisfy dif.
run do
all_dif([1, 2, 3])
end
run do
all_dif([1, 2, 1])
end
Combined with in_domain below, all_dif can force values by elimination alone, with no search: if two elements can only be 1 or 2, and two more overlap with different ranges, the ones with no other option get pinned down directly.
run do
in_domain(a, [1, 2])
in_domain(b, [1, 2])
in_domain(c, [2, 3])
in_domain(d, [3, 4])
all_dif([a, b, c, d])
end
in_domain and label
in_domain(var, values) restricts a var to a finite set, the same way dif/bounds do: a real constraint on the var, not a class with a :domain method.
run do
in_domain(x, [:a, :b, :c])
findall(x, all) do
label(x)
end
end
Posting in_domain twice narrows by intersection.
run do
in_domain(y, [:a, :b, :c, :d])
in_domain(y, [:c, :d, :e])
findall(y, all) do
label(y)
end
end
A domain narrowed down to exactly one value binds automatically, no label needed.
run do
in_domain(z, [:only_one])
end
label is the one place a bounded-but-still-open var actually becomes concrete. Inequalities and in_domain alone only ever narrow, they never enumerate. On an already-ground term, label is a no-op.
run do
label(5)
x = 5
end
On a genuinely open, bounded var, label enumerates every value as ordinary backtracking alternatives, cheapest first.
run do
x >= 3
x <= 5
label(x)
end
A domain that's still open on at least one side has nothing finite to enumerate, so label fails rather than looping forever.
run do
x >= 3
label(x)
end
How label chooses witnesses
label(term) is the explicit boundary between describing possible values and enumerating concrete ones. It follows this order:
- If
termis already ground, succeed without changing it. - If it has an explicit finite domain, create one backtracking alternative per compatible member.
- If it has finite integer bounds, enumerate the integers within those bounds.
- If it is one side of an open
superor slot relation, enumerate the distinct values found in real relation rows. A known value on the other side filters that search. - If it has object constraints, enumerate every compatible existing durable identity. Only real durable IDs are candidates.
- Also find every compatible exact value class. For each one, ask the class's
witnessmethod for a concrete value. Numbers and lists provide their own witnesses; ordinary value classes normally construct one through their initialization protocol. - Propagate all existing
class,isa, selected-method, slot, domain, bounds, anddifconstraints through each candidate. Reject a candidate as soon as any constraint conflicts.
Each surviving candidate is an ordinary choicepoint, so findall can collect all of them. An isa constraint permits exact instances of that class and its descendants; a class constraint permits only that exact class. Intersecting isa constraints keep only common descendants.
Labeling a class variable in an open relation such as class(object, exact_class) only chooses a class name. It does not construct object. Label the object separately when a concrete object or value is required.
If AL cannot derive a finite domain, a relational row, a durable identity, or a value witness, label fails. It never guesses from an unbounded space.
either: disjunctive constraints
or between two constraints is a real disjunction (AL.Var.Bounds.either), not alternative's backtracking choicepoint. If one side gets refuted, the other is applied for real.
run do
a = 4
(a = 5) or (b = 7)
end
If neither side can be decided yet, either just stays parked, undetermined, rather than guessing.
run do
(a = 5) or (b = 6)
end
Both a and b are still open there. either is reactive too: post it before anything is ground, and it resolves once a refutation actually arrives.
run do
(a = 5) or (b = 7)
a = 4
end
Putting findall, =, either, and label together: every multiple of 3 or 5 below 20, with no duplicates. 15 is a multiple of both and would show up twice under a naive backtracking alternative. It doesn't here, because either resolves by elimination rather than by trying both branches.
run do
findall(candidate, candidates) do
candidate < 20
candidate > 0
(candidate = x * 5) or (candidate = y * 3)
label(candidate)
end
end