Writing rules

A complete guide to authoring yopl rules. After reading this page you should be able to define your own rule database, run it through any of the four solvers, and reach for the right control predicate when you need it.

What a rule is

A rule in yopl is a JavaScript function that, given a fresh batch of logical variables, returns an array of terms. The first element of that array is the rule's head; the remaining elements are the body.

const rules = {
  // factName: head and body factory
  greeting: () => [{args: ['hello, world']}]
};

Read this as Prolog's greeting('hello, world').. There is one rule named greeting, its head has one argument (the string 'hello, world'), and its body is empty.

The solver looks up rules by name, calls the rule function to get a fresh body each time the rule is tried, and tries to unify the rule's head arguments against the goal's arguments. On success, the body is evaluated as a sequence of goals.

Heads, terms, and the head / term helpers

Hand-writing {args: […]} and {name: …, args: […]} literals is error-prone. The system.js module exports two helpers:

import {head, term} from 'yopl/rules/system.js';

head(1, 2, 3); // → {args: [1, 2, 3]}
term('member', X, list); // → {name: 'member', args: [X, list]}

Use head for the rule head and term for body goals that invoke other rules. The two examples below are equivalent — the second is what you should normally write.

// raw object literals
const rulesA = {
  member: [(V, X) => [{args: [{value: V, next: X}, V]}], (V, X) => [{args: [{next: X}, V]}, {name: 'member', args: [X, V]}]]
};

// using head/term
import {head, term} from 'yopl/rules/system.js';
const rulesB = {
  member: [(V, X) => [head({value: V, next: X}, V)], (V, X) => [head({next: X}, V), term('member', X, V)]]
};

Logical variables

The variables passed to a rule body factory are fresh on every call. This is what gives yopl its Prolog-like behavior: each new attempt at a rule starts with a clean set of variables, even when the same rule is invoked recursively.

The number of variables you need to declare is the number of formal parameters in your rule function. The solver looks at rule.length and supplies that many variables (plus one extra used internally as a cut anchor — more on that below).

import {head, term} from 'yopl/rules/system.js';

const rules = {
  // last(List, Element) — Element is the last element of List
  last: [
    // Base case: a single-element list — element is the head.
    X => [head({value: X, next: null}, X)],
    // Recursive case: skip the head, recurse on the tail.
    (X, Y) => [head({next: X}, Y), term('last', X, Y)]
  ]
};

Two notes about this example:

• The first clause's parameter X is the value of the single-element list and the second argument of last. Unification matches both positions to the same logical variable.
• The recursive clause uses two variables: X is the tail of the list and Y is the (still unknown) last element. Inside the body, term('last', X, Y) recurses with the tail.

Single rule vs. disjunction

A rule can be written in two forms:

Single function — a rule with exactly one clause:

const rules = {
  greeting: () => [head('hello, world')]
};

Array of functions — a disjunction: try each clause in order, backtracking when one fails:

const rules = {
  last: [
    X => [head({value: X, next: null}, X)], // base case
    (X, Y) => [head({next: X}, Y), term('last', X, Y)] // recursive
  ]
};

The two forms behave identically when the disjunction has a single clause: {r: f} is the same as {r: [f]}.

Running a rule

Pick a solver based on whether you need a callback or generator interface, and synchronous or asynchronous evaluation:

import solve from 'yopl'; // sync callback
import gen from 'yopl/solvers/gen.js'; // sync generator
import asyncSolve from 'yopl/solvers/async.js'; // async callback
import asyncGen from 'yopl/solvers/asyncGen.js'; // async generator

All four take (rules, name, args, callback?) and search for every solution. Use assemble(variable, env) from deep6/traverse/assemble.js to extract bound values from the per-solution environment.

import {variable} from 'deep6/env.js';
import assemble from 'deep6/traverse/assemble.js';
import solve from 'yopl';

const X = variable('X');
solve(rules, 'last', [{value: 1, next: {value: 2, next: null}}, X], env => {
  console.log(assemble(X, env)); // 2
});

Inline goal functions

Sometimes you need behavior that isn't expressible as a chain of rule calls — a side effect, a numeric computation, a binding from native JavaScript data. For these cases a body goal may be a JavaScript function instead of a structured term:

const rules = {
  positive: X => [head(X), env => X.isBound(env) && X.get(env) > 0]
};

The inline goal function receives (env, goals, stack):

• env is the live unification environment. Use variable.get(env), variable.isBound(env), and env.bindVal(name, value) to read or write bindings.
• goals is the linked list of pending goal frames (rarely useful directly).
• stack is the solver's choice-point stack (used by cut).

Return values:

• true (or any truthy non-object) — succeed and advance to the next goal.
• false — fail and trigger backtracking.
• A goal frame object — replace the current continuation. call (see below) uses this to inject a goal that is computed at run time.

Use inline goals sparingly: they are powerful but bypass the unifier, which is what makes the rest of the system reversible.

Control predicates

The system.js module exports a small kit of control-flow predicates that mirror Prolog's standard library:

Helper	Purpose
fail	Always fails. Forces backtracking from the current branch.
halt	Exception-style abort: clears the entire proof search.
cut(sys)	Prolog ! — commits to the current rule clause; later clauses are not tried.
call(X)	Meta-call: evaluate X (a goal name, term, or bound variable) as a body goal.
isBound(...vars)	Succeeds when every supplied variable is currently bound.

cut requires a small ceremony. The solver gives every rule one extra logical variable beyond the formal parameters; collect it with a rest argument named by convention ...sys and pass it through to cut:

import {head, cut, fail, list, rest, term} from 'yopl/rules/system.js';

const rules = {
  // member that stops at the first match (like Prolog's memberchk)
  member: [(V, X, ...sys) => [head(list(V, rest(X)), V), cut(sys)], (V, X) => [head({next: X}, V), term('member', X, V)]]
};

Without cut, the same member predicate would enumerate every position at which V appears.

Building lists

yopl represents lists as JavaScript cons cells: {value, next} chains terminated by null. Two helpers make this convenient:

import {list, listHead, rest} from 'yopl/rules/system.js';

list(); // null
list(1, 2, 3); // {value: 1, next: {value: 2, next: {value: 3, next: null}}}
list(1, 2, rest(tail)); // last argument becomes the tail of the cons chain
listHead(1, 2, tail); // same as list(1, 2, rest(tail)) but the tail is positional

Use list when you have an explicit tail in mind, listHead when you are pattern-matching against the front of a list inside a rule head.

Composing rule libraries

Rule databases are plain JavaScript objects. Compose them by spreading the built-in libraries into your own:

import {rules as systemRules} from 'yopl/rules/system.js';
import {rules as compRules} from 'yopl/rules/comp.js';
import {rules as mathRules} from 'yopl/rules/math.js';

const rules = {
  ...systemRules,
  ...compRules,
  ...mathRules,
  // your own rules
  inRange: (X, L, H) => [head(X, L, H), term('le', L, X), term('le', X, H)]
};

Later spreads win on collisions, so your own rules can override library defaults if you wish.

A complete worked example: length

The length predicate relates a list to its length. Below is a forward-only version that computes the length of a known list using add from the math library.

import {variable} from 'deep6/env.js';
import assemble from 'deep6/traverse/assemble.js';
import solve from 'yopl';
import {head, term, rules as systemRules} from 'yopl/rules/system.js';
import {rules as mathRules} from 'yopl/rules/math.js';

const rules = {
  ...systemRules,
  ...mathRules,
  // length(null, 0).
  // length([_ | T], N) :- length(T, M), add(M, 1, N).
  length: [() => [head(null, 0)], (T, N, M) => [head({next: T}, N), term('length', T, M), term('add', M, 1, N)]]
};

const N = variable('N');
solve(rules, 'length', [{value: 'a', next: {value: 'b', next: {value: 'c', next: null}}}, N], env => {
  console.log(assemble(N, env)); // 3
});

This example shows the typical pattern:

1. Spread the library predicates you need (mathRules for add).
2. Define your rules in terms of both the library and your own helpers.
3. Use head for the head and term for recursive / library calls.
4. Run the rule through any solver and assemble the result.

Where to look next

• solve — the main callback solver and the rule shape it accepts.
• solvers-gen, solvers-async, solvers-asyncGen — alternative drivers.
• rules-system — every helper and predicate in the system module, with examples.
• rules-comp, rules-math, rules-bits, rules-logic — the built-in rule libraries.