Like logic programming, narrowing of algebraic value sets gives a method of reasoning about the values in unsolved or partially solved equations. Where logic programming relies on resolution, the algebra of value sets relies on narrowing rules. Narrowing rules allow the elimination of values from a solution set which are inconsistent with the equations being solved.
Unlike logic programming, narrowing of algebraic value sets makes no use of backtracking. Instead all values are contained in value sets, and are considered in parallel.
The approach is also similar to the use of constraints in constraint logic programming, but without the logic processing basis.
Probabilistic value sets is a natural extension of value sets to deductive probability. The value set construct holds the information required to calculate probabilities of calculated values based on probabilities of initial values.
History
Early programming languages were imperative. These implement functionality by allowing change to be represented. The assignment statement allows a variable to change its value.
In mathematics a variable's value may not change. This is fundamental to the mathematical approach. Functional languages based on lambda calculus allow this mathematical approach to programming. Functional languages developed by implementing lazy evaluation, and allowing functions to be passed as parameters.
Lazy evaluation is an essential feature of modern functional programming languages such as Haskell. Haskell is the latest in a series of languages based on lambda calculus and let expressions. These languages provide rich functionality through lazy evaluation, and a polymorphic type system using type inference. Functional programming languages also naturally support higher-order functions.
Logic programming based on Resolution developed alongside functional programming. Logic programming is a form of relational programming that makes deductions about values. Constraint logic programming extends logic programming, by supporting constraints. Constraint logic programming languages such as ECLiPSe provide the ability to solve complex logic problems. However ECLiPSe is not lazy.
Logic programming languages, although they have greater deduction abilities, never gained the power and flexibility of functional languages.
Narrowing is a technique that allows logical deduction, with the flexibility of functional languages.
Introduction
In mathematics an expression represents a single value. A function maps one or more values to one unique value.
Inverses of functions are not always well defined as functions. Sometimes extra conditions are required to make an inverse of a function fit the definition of a function.
Some Boolean operations, in particular do not have inverses that may be defined as functions. In particular the disjunction "or" has inverses that allow two values. In natural language "or" represents alternate possibilities.
Narrowing is based on value sets that allow multiple values to be packaged and considered as a single value. This allows the inverses of functions to always be considered as functions.
To achieve this value sets must record the context to which a value belongs. A variable may only take on a single value in each possible world. The value sets tag each value in the value set with the world to which it belongs.
Possible worlds belong to world sets. A world set is a set of all mutually exclusive worlds. Combining values from different possible worlds is impossible, because that would mean combining mutually exclusive possible worlds.
The application of functions to value sets creates combinations of value sets from different worlds. Narrowing reduces those worlds by eliminating combinations of different worlds from the same world set. Narrowing rules also detect situations where some combinations of worlds are shown to be impossible.
No back tracking is required in the use of narrowing. By packaging the possible values in a value set all combinations of values may be considered at the same time. Evaluation proceeds as for a functional language, combining combinations of values in value sets, with narrowing rules eliminating impossible values from the sets.
Introduction to value sets
A value set is an object, which represents the set of values a variable may have. The value set behaves mathematically as a single value, while internally representing multiple values. To achieve this the value set tracks the value along with the context, or world, in which they occurred.
Multiple solutions to an equation
In mathematics, an expression must represent a single value. For example consider the equation,
which implies,
But this is a bit long winded, and it does not allow us to work with multiple values at the same time. If further conditions or constraints are added to x we would like to consider each value to see if it matches the constraint. So naively we would like to write,
Naively then,
but this is wrong. Each x must represent a single value in the expression. Either x is 2 or x = −2. This can be resolved by keeping track of the two values so that we make sure that the values are used consistently, and this is what a value set does.
Representation
The value set for 'x' is written as,
It is container V which has a set of tag, value pairs,
The value 2 is associated with the possible world . The value −2 is associated with the possible world . This means that the value cannot be both 2 and −2 at the same time. In the world the value of the value set must be 2. In the world the value of the value set must be −2.
The solution of the equation,
is,
Possible worlds
A possible world is used here as an informal term. Formally a possible world is defined by a Boolean condition. A possible world may be considered the set of possibilities for the world that match the condition.
The term "possible world" is used to make the description of value sets easier to follow.
World sets
A world set is a set of possible worlds that represent all possibilities. So is a world set as either x = 2 (in world ) or x= −2 (in world ). There are no other possibilities.
Worlds from the same world set are mutually exclusive, so it is not possible that the propositions for both worlds and are true at the same time.
Application of functions
The rule for the application of functions to value sets is,
For example,
is,
The intersection of the possible world with itself is the possible world,
The intersection of the possible world with another possible world from the same world set is empty,
So,
The empty worlds rule allows tagged values from empty worlds to be dropped
giving,
Giving the result that is either −4 or 4, as expected.
Application to Booleans
Is a relationship between a, b and true that implies that both a and b must be true.
Allows multiple values for a and b. If a is,
then for b
This means that if a is false then b must be true.
Now consider,
gives,
and
unifying these two value sets gives,
The pair is dropped because of the "assert equal" rule,
Its value did not match with .
Dependent worlds
Consider the problem,
Firstly calculate the value set for ,
As this statement is asserted true, all the false values are dropped giving,
The worlds,
are impossible. The worlds are empty.
If a world set is included in a calculation then every world from the world set must be included in the result. If a world is not found, it is called a dependent world, and must be empty. The world is not represented in this value, and so must be empty. The value set for is now smaller,
The second condition is now simpler, because of the smaller value set.
Then the value sets are,
And the calculation is,
But is empty. So,
So and are empty,
Now and are not represented, and are removed as dependent worlds. So,
Every calculation made may reduce the size of value sets by removing dependent worlds, but add a new value set whose size is the product of the sizes of the input value sets. Then calculations should proceed first where the product of the sizes of the input value sets is smallest.
Pizza, beer, whiskey
After a hard day's work attempting to meet some crazy deadline with the project from hell, there comes that desperate time at 10 PM when we all need pizza, beer, and whiskey. Pizza shops are open at,
Beer you can get at,
Whiskey,
The cops are about and we are not getting any younger. Where to go?
If the constraints are applied in the order left to right,
Then we need to unify this with,
This will create 24 combinations from which the matching ones are,
Finally we need to unify with whiskey.
Which gives 6 combinations. The matching one is,
A total of 30 combinations were generated.
If the constraints are applied in the order right to left,
Then we need to unify this with,
This will create 8 combinations from which the matching one is,
Finally we need to unify with pizza.
Which gives 6 combinations. The matching one is,
The result is the same but only 14 combinations were generated to arrive at the conclusion.
Every calculation combines value sets to create a value set which is the product of the sizes of the input value sets. The value set will then be trimmed down. And every calculation has an equal chance of narrowing the calculation. So by controlling the order and proceeding with calculations with the smallest product of sizes, there will be less calculation and less combinatorial explosion.
Let expressions and multiple values
A general solution to the problem of inverses of functions that are not functions is needed. What is required is a representation of a value that is constrained to be a member of a set of values. A let expression may be used to represent a value that is a member of a set,
In this expression is a constraint. A constraint is a Boolean expression that a variable must satisfy. The let expression allows the constraint be represented in an expression. If there was a general rule for function application of constraint expressions, then a constraint could be treated like a value.
Under function application, of one let expression to another,
But a different rule applies for applying the let expression to itself. The let expression does not restrict the scope of the variable x, so x is the same variable in the two let expressions.
There appears no simple rule for combining let expressions. What is required is a general form of expression that represents a variable whose value is a member of a set of values. The expression should be based on the variable and the set.
Function application applied to this form should give another expression in the same form. In this way any expression on functions of multiple values may be treated as if it had one value.
It is not sufficient for the form to represent only the set of values. Each value must have a condition that determines when the expression takes the value. The resulting construct is a set of pairs of conditions and values, called a "value set".
Theory of value sets
A "value set" K is defined as a set of pairs, each pair consisting of a value and a set of dependent conditions. The set of dependent conditions is used by the "condition function", to determine if the value set takes that value.
The condition function is defined by 3 axioms, Each pair means that the value of the value set is v if the condition function applied to the list, , is true. One of the conditions is true. Only one of the conditions is true.
The condition is represented as a function applied to a set of dependent conditions, to allow the structure of the condition to be controlled. Also the set of conditions is used in narrowing by exclusion of dependent values. However for most purposes the value set may be thought of as a set of value, condition pairs. The condition function translates the set into the condition.
Formally,