Powered by AppSignal & Oban Pro

Logic and constraints

livebooks/logic_and_constraints.livemd

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:

  1. If term is already ground, succeed without changing it.
  2. If it has an explicit finite domain, create one backtracking alternative per compatible member.
  3. If it has finite integer bounds, enumerate the integers within those bounds.
  4. If it is one side of an open super or slot relation, enumerate the distinct values found in real relation rows. A known value on the other side filters that search.
  5. If it has object constraints, enumerate every compatible existing durable identity. Only real durable IDs are candidates.
  6. Also find every compatible exact value class. For each one, ask the class's witness method for a concrete value. Numbers and lists provide their own witnesses; ordinary value classes normally construct one through their initialization protocol.
  7. Propagate all existing class, isa, selected-method, slot, domain, bounds, and dif constraints 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