Narrowing of algebraic value sets
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 formula_8. The value −2 is associated with the possible world formula_9. This means that the value cannot be both 2 and −2 at the same time. In the world formula_8 the value of the value set must be 2. In the world formula_9 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 formula_14 is a world set as either x = 2 (in world formula_8) or x= −2 (in world formula_9). 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 formula_8 and formula_9 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 formula_31 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 formula_40 is dropped because of the "assert equal" rule, Its value formula_40 did not match with formula_43. Dependent worlds. Consider the problem, Firstly calculate the value set for formula_46, 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 formula_56 is not represented in this value, and so must be empty. The value set for formula_57 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 formula_54 is empty. So, So formula_65 and formula_66 are empty , Now formula_68 and formula_69 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 formula_87 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, 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, Value function. Using the  value condition and complete set axioms, As a let expression this becomes, Single value. The value set to represent a single value is, The derivation is, Element of a set. The value set to represent an element of a set is, This rather strange definition adds the value set in as part of the dependent condition. This is used in narrowing by exclusion of dependent values. The value of the expression is Both "R" and "x" must be included in the dependent condition, because "R" identifies the value set to which the dependent condition belongs, and "x" provides the variable  used to carry the value in the let expression. If the addition of "R" to the dependent condition is ignored, the expression takes on a simpler and more understandable form, The derivation is, Application of functions. Function application of value sets is given by, Derivation, Then using, get, Exclusion. The exclusion is a rule that determines when conditions must be false, This may be derived from, Simplification. The simplification rule allows values whose condition is false to be dropped. Derivation A value sets identity. By defining the application of functions to value sets the definition of equality of value sets  has also been redefined. The old definition of equality still exists, because value sets are constructed as a set of pairs. Two sets are equal if they contain the same elements. This definition of equality for value sets is at best misleading. What is needed is to use the name, or identity of the variable from which the value set is constructed as part of the structure of the value set. This would make value sets distinct, unless they are based on the same variable. In mathematics, quantification is over values, not formulas. To proceed further with the exact definition  of value sets, quantification over formulas is needed, in a way that allows the comparison of the identity of formulas. The distinction between the formula representing a value and the identity of the formula is the use–mention distinction. The notation, is introduced to mean quantification over formula "x" where "x" refers to the value, as a use, and "u" refers to the identity of the formula as represented or mentioned. Using this notation the element of a set definition would be, Every reference to a value set would then need to be changed to take account of the extra  level of structure in the value set, which would make the description harder to read. For the sake of readability this extra level of structure has been omitted from the definition of value sets. Narrowing. "Narrowing" is determining when conditions for values must be "false". Narrowing starts when the value of two value sets is asserted equal. Narrowing by asserting equal. Assertion that two value sets are equal gives the narrowing rule, For the derivation, start with, The value condition gives, Narrowing by conjunction. If any base condition is false, all the conditions obtained from it are false. This comes  from the definition of the Condition function, The base condition for (r, z, u) is, So if this is false formula_95 is false. Narrowing by crossed conditions. If a dependent condition list has two different base conditions from the same value set it must be false. To derive this, start with the exclusion rule which is, Then for any set of dependent conditions "l", So if a dependent condition list is based on two conditions from the same value set, the condition value of that dependent condition list is false. Narrowing by exclusion of dependent values. Each value set puts  a constraint on the base value set from which it is constructed. If a base values set includes values that are not present as dependent values in the value set, the conditions for these values must be false. To derive this, start with the complete set rule, The condition function is, A particular dependent condition may be chosen, as being implied by the whole condition, So Here formula_155. The expression may be rearranged to define the set of values that formula_156 might take, and so, Then using the exclusion rule, gives, This is the narrowing exclusion rule. formula_161 is the  set of values in the base value "L" set which are represented in the value set "K". Conditions for other values must be false. Probabilistic value sets. The value set records the dependent conditions that the condition function may be applied to in order to deduce the truth of the proposition that the value set has a particular value. The same structure may be used to give the probability of a value set being equal to a particular value. The condition function is, The probability function is, This is the probability of each base case holding the particular value, if  the events are independent. The probability function is defined by 3 axioms, The probability function gives probabilities for results based on initial probabilities given by Boolean inductive inference. Formally, Probabilities for each value in a value set may be calculated from probabilities in base value sets using the probability function and the value condition. Base value sets are either for a single value, or multiple value value set. Probability for a single value. The value set to represent a single value is, The complete set rule is, Which is consistent with the axiom. Probabilities for multiple values. The value set  to represent multiple values is, The probability is given by the allowed values rule, which simplifies to, If prior estimates of probabilities for values are given then they will be proportional to the posterior probabilities, if the value is in the value set. If the value is not in the value set the probabilities will be zero, So, If the prior probabilities are all the same the probabilities are, Probabilities of general value sets. A general value set is created out of the application of base value sets. The value condition rule and the probability function may be combined to  give, Accessing the value set. Narrowing allows the elimination of values that do not satisfy a variable's constraints. Considered as the basis for an algorithm for solving equations, this narrowing gives a set of values consistent with the constraints on a variable. However in mathematics there is no way to access this set of values. If formula_183 is an expression constraining a variable "x" then the set of values that the variable may take is, Define the "gset" of "x" to be the set of values that satisfy the constraints on "x". Consider defining "gset" as, This definition depends  on knowing the expression "E", which is the condition giving all the constraints on "x". Within mathematics "E" may not be obtained from "x". So there is no mathematical function that may be applied to a variable to request the set of values. So may the "gset" function be added to mathematics? Meta math definition. A meta-mathematical definition of "gset" may be possible. Imagine that what we know of as mathematics is actually implemented by a meta function called "math". "math" takes an abstract syntax tree and gives meaning to the variables and mathematical structures and adds existential quantifiers  for variables not explicitly quantified. "math" would be an expression in a meta mathematical environment with its own variables. To distinguish these meta-variables from math variables represent them by capital letters and the mathematical variables by lower case letters. Now suppose there is an extended implementation of mathematics implemented by the "xmath" function, defined as, Using "xmath", "gset" may be defined by, Here again the notation, is used to mean quantification over variables "x" where "x" refers to the value, and "u" refers to the unique identity of the variable. Example. For example take the constraint expression formula_1. Then , Then the "xmath" expression is, Then where u is the unique identity of the variable x, represented here as the number 1 (for the first variable used in a call to "gset"), Here formula_199 invokes "T" with M as N.