Lurch Deductive Engine

Class

Problem

This class expresses a matching problem, that is, a set of matching Constraints, and includes an algorithm for solving them simultaneously, producing a list of Solutions (which may be empty). For more information on the concept of matching in general, see the documentation for the Matching module.

Constructor

new Problem(…args)

Construct a new matching problem with no constraints in it. Then, if any argument are provided, they are passed directly to the add() function. See its documentation for how they are processed.

Parameters

  • args any <repeatable>

    constraints to add to this problem after its construction, in a wide variety of forms, as documented in this class's add() function

See

Source

Classes

Problem

Members

length

The length of a problem is the number of constraints in it. Note that as a problem is solved, the algorithm successively removes constraints as it satisfies them (sometimes replacing them with one or more simpler ones), so this value may change over time, up or down.

See

Source

Methods

add(…args)

Add constraints to this problem. Arguments are accepted in any of the following forms.

  • p.add( p1, e1, p2, e2, ... ), where p1,p2,... are patterns and e1,e2,... are expressions, as defined in the Constraint class, so that we might construct Constraint instances from them
  • p.add( [ p1, e1, p2, e2, ... ] ), same as the previous, but in array form rather than separate arguments
  • p.add( [ [ p1, e1 ], [ p2, e2 ], ... ] ), same as the previous, but as an array of pairs rather than flattened
  • p.add( c1, c2, ... ), where each of c1,c2,... is a Constraint instance
  • p.add( [ c1, c2, ... ] ), same as the previous, but in array form rather than separate arguments
  • p.add( other ), where other is another instance of the Problem class, and we are to add all of its constraints to p

No Constraint is added if it is already present, in the sense of there being an equal Constraint already stored in this object.

Constraints are stored internally in increasing order of complexity(), and this function preserves that order when adding new constraints. This makes it easy for algorithms to find an easy constraint to process, by taking the first one off the internal list.

Parameters

  • args any <repeatable>

    constraints to add to this problem, in any of the forms given above

Source

copy() → {Problem}

Create a shallow copy of this object, which will include a shallow copy of its constraint set.

Returns

  • Problem

    a shallow copy of this object

Source

empty() → {boolean}

Is this problem empty? That is, does it have zero constraints? Return true if so, false otherwise

See

Returns

  • boolean

    whether this problem is empty (no constraints)

Source

equals(other) → {boolean}

Equality of two problems is determined solely by the content of their constraint sets. This function returns true if and only if the set of constraints is the same in both problems.

Parameters

  • other Problem

    another instance of the Problem class with which to compare this one

Returns

  • boolean

    whether the two instances are equal

Source

firstSolution() → {Solution}

Sometimes it is useful to just get one example solution for the problem, rather than computing all solutions. Although that can be done efficiently using the solutions() iterator, this function is a convenience to make it easier. It returns either the first solution, as an instance of the Solution class, or it returns undefined if the problem has no solutions.

Note that this function operate completely independently of the solutions() iterator, in that if you are partway through computing the list of solutions with that iterator, you can still ask for the first solution using this function, and it will give that first solution and will have no effect on the ongoing iterator.

Caching of solutions is not implemented for problems, so the work of finding and computing the first solution is done again when you call this function, even if it has been computed in the past. One could implement a cache, which would need to be invalidated by functions like add(), but that has not been done.

See

Returns

  • Solution

    the first solution to this matching problem, or undefined if the problem has no solutions

Source

isSolvable() → {boolean}

If you do not need to fetch any solutions, but rather just check to see whether any exist, this function is more efficient than running the full solutions() iterator, which computes all possible solutions. This function returns a boolean, whether any solutions exist. Calling P.isSolvable() is equivalent to computing !!P.firstSolution(), but is more readable, and more efficient than computing P.numSolutions() > 0.

See

Returns

  • boolean

    true if and only if there is at least one solution to this matching problem, and false otherwise

Source

numSolutions() → {integer}

If you do not need the solution set, but just need to know its size, call this function instead of the solutions() iterator. Note that the full iterator will be traversed to compute its size, which is thus the same amount of computational effort as finding and returning all the solutions, so no time is saved. This function is provided for those cases where P.numSolutions() is more readable than computing the full array of solutions and then asking for its length.

See

Returns

  • integer

    the number of solutions to this matching problem

Source

plus(…args) → {Problem}

Construct a new Problem just like this one, except with the given Constraints added. In other words, just call this instance's copy() function, and then call add() in the copy, then return the new object.

Parameters

  • args any <repeatable>

    the constraints to add to the problem, in any of the forms supported by the add() function

Returns

  • Problem

    a new problem instance equal to this one plus the new constraints specified as arguments

Source

remove(toRemove)

Most clients will not call this function; it is mostly for internal use. Various algorithms within this class occasionally need to remove a constraint, and this function is used to do so.

Parameters

  • toRemove integer | Constraint

    the caller can provide an integer between 0 and this problem's length minus 1, inclusive, to have this function remove the constraint at that index; or the caller can provide a Constraint instance, and this function will remove any constraint equal to that one, if this Problem contains such a copy

See

Source

substitute(…subs)

Alter this object by applying the given Substitutions to it, in-place. Constraints in this Problem whose patterns contain any of the metavariables on the LHS of any of the given Substitutions will be replaced with new Constraints whose patterns have been altered by those Substitutions.

Parameters

See

Source

toString() → {string}

The string representation of a Problem is simply the comma-separated list of string representations of its Constraints, surrounded by curly brackets to suggest a set. For example, it might be "{(A,(- x)),(B,(+ 1 t))}" or "{}".

See

Returns

  • string

    a string representation of the Problem, useful in debugging

Source

without(toRemove) → {Problem}

Construct a new Problem just like this one, except with the constraint at the given index removed. In other words, just call this instance's copy() function, and then call remove() in the copy, then return the new object.

Parameters

  • toRemove integer | Constraint

    the Constraint to remove, or a copy of it, or the index of it; this argument will be passed directly to remove(), so see the documentation there for details

Returns

  • Problem

    a new problem instance equal to this one minus the constraint at the given index

Source