15,609,135 members
Articles / Artificial Intelligence
Article
Posted 6 Mar 2015

15.5K views
10 bookmarked

# Propagation of Constraints

Rate me:
Propagation of constraints

## Introduction

NOTE: This article is from sections of Chapter 15 “Special Computational Patterns” of my unpublished textbook Applied Algorithms and Data Structures, and is based on the following: Abelson, H., and G.J. Sussman, Structure and Interpretation of Computer Programs, The MIT Press, 1985, pp. 230-242; Sussman, G.J., and G.L. Steele, Jr. “CONSTRAINTS?A Language for Expressing Almost-Hierarchical Descriptions, Artificial Intelligence, Vol. 14, 1980, pp. 1-39; de Kleer, J., and G.J. Sussman. “Propagation of Constraints Applied to Circuit Synthesis,” International Journal of Circuit Theory and Applications, Vol. 8, 1980, pp. 127-144.

This article deals with the implementation of a constraint-propagation system. Computer programs are often organized in terms of one-directional computations, which perform operations on pre-specified arguments to produce desired outputs. On the other hand, systems are modeled in terms of relations among quantities. For example, a mathematical model for a resistor describing its resistance R (in Ohms) is given by the equation R = ρ(L/A), where ρ is the resistivity of the material (in Ohms-cm), L is its length (in cm) and A is its cross-sectional area (in cm squared).

The equation for the resistivity of a material is not one-directional. If any three of the quantities are known, they can be used to compute the fourth. However, translating the equation into a function in a traditional computer language would require choosing one of the quantities to be computed in terms of the other three. Therefore, a procedure for computing the area A could not be used to compute the resistivity ρ, even though both computations arise from the same equation.

## Constraint Networks

It is possible to use object-oriented programming to define a new programming language that would allow working in terms of relations. The elements of the new language are primitive constraints, which state that certain relations hold among quantities. For example, the constraint adder( a, b, c ) might specify that the quantities a, b, and c are related by the equation a + b = c. Similarly, the constraint multiplier( u, v, w ) would express the equation u * v = w. To specify constant values for variables, say x == 2.5, we could use a constraint such as constant( x, 2.5 ).

This kind of language provides a means of combining primitive constraints in order to express more complex relations. Constraints are combined by building constraint networks, in which constraints are joined by connectors. A connector is an object that holds a value that may participate in one or more constraints. For example, the relationship between Fahrenheit and Celsius temperatures is given by the equation 9C = 5(F – 32), and such a constraint equation can be thought of as a network of primitive adder, multiplier and constant constraints, as shown below:

On the left of the figure, there is a multiplier box (i.e., a constraint) with three terminals labeled m1, m2 and p. These connect the multiplier to the rest of the network in the following way. Terminal m1 is linked to a connector C which holds the Celsius temperature. Terminal m2 is linked via connector w to a constant box that holds number 9. Terminal p, which the multiplier box constraints to be the product of m1 and m2, is linked to the p terminal of another multiplier box, whose m2 terminal is connected to a constant box holding 5, while its m1 terminal is connected to the s terminal of an adder box. Terminal a1 of the adder is linked to connector F (holding the Fahrenheit temperature), and terminal a2 is linked to connector y, which in turn is linked to a constant box holding number –32.

The computation by such a network proceeds as follows. When a connector is given a value (either by a User constraint or by a constraint box to which it is linked), it awakens all of its associated constraints (except for the constraint that has been just awakened by the connector) to inform them that it has a value. Each awakened constraint box then polls its connectors to see if there is enough information to determine a value for one of its connectors. If so, the box sets the value of that connector, and the connector awakens all of its associated constraints, thus repeating the process. In the Celsius-Fahrenheit conversion example, connectors w, x and y are immediately set by the constant boxes to 9, 5 and -32, respectively. These connectors awaken the two multipliers and the adder, which determine that there is not enough information to proceed (because connectors C and F, and hence u and v, have no values). When the user constraint (or some other part of the network) sets C to a value, say 25, the leftmost multiplier is awakened and it sets u to the value 25 * 9 = 225. Then, connector u awakens the middle multiplier, which sets v to 45. Finally, connector v awakens the adder, which sets F to 77.

## Connectors and Abstract Constraints

The constraint-propagation system can be implemented in C#/C++ via classes, inheritance, and virtual functions. The following declarations constitute the bare minimum that can be used to implement such a system.

C#
```public abstract class Constraint              // Abstract constraint
{
public abstract void ProcessNewValue();    // All processing must be done
public abstract void ProcessForgetValue(); // by specific (derived) constraints
}

// Constants for message-passing
public enum message { GotValue, LostValue }

// Constants for signaling the type of value held by connectors
public enum valueType { _int, _float }

// Constants to control the output from probes
public enum behavior { normal, quiet }

public class Connector               // A connector
{
protected string name;            // has a name,
protected valueType type;         // and holds a certain type of value,
protected float fvalue;           // either a floating-point value,
protected int ivalue;             // or an integer value, assigned to it
protected Constraint informant;   // by an informant (constraint),

// Define and initialize a connector
public Connector( string str, valueType t )
{
name = str;                     // Set the connector's name
type = t;                       // and its type.
fvalue = 0F;                    // Clear the value
ivalue = 0;                     // fields.
informant = null;               // No constraint has set the connector's value
}

// Link the connector to a new constraint
public void Connect( Constraint _newConstraint )
{
if ( HasValue() )
{
try
{
_newConstraint.ProcessNewValue();
}
catch ( System.Exception e )
{
Console.WriteLine( "-- " + e.Message );
}
}
}

// Tell whether the connector has a value
public bool HasValue()
{
return informant != null;
}

// Show the name of the connector
public void ShowName()
{
Console.Write( Name );
}

// Properties of the connector

public string Name    // 'name' property of the connector
{
get { return name; }
set { name = value; }
}

public int Ivalue     // 'ivalue' property of the connector
{
get { return ivalue; }
}

public float Fvalue   // 'fvalue' property of the connector
{
get { return fvalue; }
}

public valueType Type // 'type' property of the connector
{
get { return type; }
}

// Special functions to set the ivalue and fvalue fields
// (too bad the 'setter' of properties cannot take optional
//  arguments in addition to the implicit 'value' argument)

// A 'setter' constraint requests the connector to set
// either its ivalue or its fvalue to a new value

public void SetValue( int _newValue, Constraint setter )
{
if ( !HasValue() )
{
ivalue = _newValue;
informant = setter;
ForEachExcept( setter, message.GotValue );
}
else // HasValue()
if ( ivalue != _newValue )
{
Console.Write( "Connector " );
ShowName();
Console.WriteLine( " *** contradiction {0} != {1}",
ivalue, _newValue );
}
}

public void SetValue( float _newValue, Constraint setter )
{
if ( !HasValue() )
{
fvalue = _newValue;
informant = setter;
ForEachExcept( setter, message.GotValue );
}
else // HasValue()
if ( fvalue != _newValue )
{
Console.Write( "connector " );
ShowName();
Console.WriteLine( " *** contradiction {0} != {1}",
fvalue, _newValue );
}
}

// A 'retractor' constraint requests the connector
// to forget its value (either ivalue or fvalue)

public void ForgetValue( Constraint retractor )
{
if ( retractor == informant )
{
informant = null;
ForEachExcept( retractor, message.LostValue );
}
}

// Function to propagate a message among the constraints
// linked to the connector, except for the constraint
// that issued the message.

protected void ForEachExcept( Constraint exception, message m )
{
foreach ( Constraint c in links )
{
if ( c != exception )
{
if ( m == message.GotValue )
{
try
{
c.ProcessNewValue();
}
catch ( System.Exception e )
{
Console.WriteLine( e.Message );
}
}
else // m == message.LostValue
{
c.ProcessForgetValue();
}
}
}
}
}// Connector (class)
```

Observe that the class `Connector `can handle floating-point as well as fixed-point quantities, but not both at the same time. It also has functions to set and retrieve either the `int `or the `float `value.

## Test of the Constraints Class

The following is a simple test of the `ConstraintsLib `class:

C#
```using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

using ConstraintsLib;

namespace TestConstraintsLib
{
class Program
{
static void Main( string[] args )
{
GenSym sym = new GenSym( "c" );
Connector c0 = new Connector( sym.next(), valueType._int ),
c1 = new Connector( sym.next(), valueType._float );
Probe p0 = new Probe( c0 ),
p1 = new Probe( c1 );
User jlo = new User();

c0.SetValue( 5, jlo );
c1.SetValue( 7.3F, jlo );

c0.SetValue( 8, jlo );     // Should generate a contradiction
c1.SetValue( 45.4F, jlo ); // Should generate a contradiction

Console.WriteLine();
c0.ForgetValue( jlo );
c1.ForgetValue( jlo );

Console.WriteLine();
c0.SetValue( 8, jlo );
c1.SetValue( 45.4F, jlo );
}
}
}```

When run as a console application, the output is as follows:

## Primitive Constraints

The class `Constraint `is truly `abstract`, because it cannot be instantiated. It is not possible to define variables of type `Constraint`, but other classes can be defined as derived from it. As a simple illustration, an `Adder `can be defined as a kind of `Constraint `as follows:

C#
```public class Adder : Constraint // An adder is a kind of constraint
{
// and a sum (s) by means of its constructor,
protected Connector a1, a2, s;
protected Report report = new Report();

public Adder( Connector _1, Connector _2, Connector _3 )
{
a1 = _1;            // Maintain a reference to each of
a2 = _2;            // the connectors associated to
s = _3;             // the constraint.
a1.Connect( this ); // Link (i.e., connect) each of the
a2.Connect( this ); // connectors to this constraint
s.Connect( this );  // (instance of adder).

report._3argConstraint( "Adder", _1, _2, _3 );
}

// Provide specific implementations of the
// virtual functions of the base abstract class

public override void ProcessNewValue()
{
// If any two connectors have a value, set the value of the third

bool a1Hv = a1.HasValue(), a2Hv = a2.HasValue(), sHv = s.HasValue();

if ( s.Type == valueType._float )
{
float sV = s.Fvalue, a1v = a1.Fvalue, a2v = a2.Fvalue;

if ( a1Hv && a2Hv ) s.SetValue( a1v + a2v, this );
else
if ( a1Hv && sHv ) a2.SetValue( sV - a1v, this );
else
if ( a2Hv && sHv ) a1.SetValue( sV - a2v, this );
}
else // s.Type == valueType._int
{
int sV = s.Ivalue, a1v = a1.Ivalue, a2v = a2.Ivalue;

if ( a1Hv && a2Hv ) s.SetValue( a1v + a2v, this );
else
if ( a1Hv && sHv ) a2.SetValue( sV - a1v, this );
else
if ( a2Hv && sHv ) a1.SetValue( sV - a2v, this );
}
}

public override void ProcessForgetValue()
{
s.ForgetValue( this );  // Inform the three connectors
a1.ForgetValue( this ); // that this constraint requests
a2.ForgetValue( this ); // them to forget their values.
ProcessNewValue();      // Try to process a new value
}                          // not originally set by adder.
```

The definition of the `Adder `constraint provides specific implementations of the virtual functions of the `abstract `base class. Function `ProcessNewValue `is called when the `adder `is informed that one of its connectors has a value. For simplicity, the function assumes that the connectors linked to the `adder `hold the same type of value. By inspecting the type of value held by connector `s`, the appropriate functions can be called to get and set connector values.

Function `ProcessForgetValue `is called when the `adder `is informed that one of its connectors has lost its value. The function requests all the connectors linked to the adder to forget their values. (Only the values originally set by this `adder `are actually lost). Then it calls `ProcessNewValue `because one or more of the connectors may still have a value (not originally set by the `adder`) that must be propagated through other constraints.

A Multiplier constraint can be defined in a way similar to that of an `adder`, with the provision that the multiplier will set its product to zero if either of the factors is zero, even if the value of the other factor is not known (undefined). The definition of the class `Multiplier `is a similar class. In the case of division by zero, function `ProcessNewValue `for the `Multiplier `constraint must abort the execution of the program that makes use of the multiplier constraint.

A `Constant `constraint simply sets the value of its associated connector. The two constructors allow defining floating-point and fixed-point constants. Its member functions `ProcessNewValue `and `ProcessForgetValue `do not perform any action (because constants do not change).

C#
```public class Constant : Constraint // A constant is a kind of constraint,
{
protected Connector conn;       // linked to a connector by its constructors,

public Constant( float f, Connector c )
{
conn = c;                 // Set reference to the connector.
conn.Connect( this );     // Link (i.e., connect) the connector.
conn.SetValue( f, this ); // Set the fvalue field.
}

public Constant( int i, Connector c )
{
conn = c;                 // Set reference to the connector.
conn.Connect( this );     // Link (i.e., connect) the connector.
conn.SetValue( i, this ); // Set the ivalue field.
}

public override void ProcessNewValue() { }    // No actions are performed
public override void ProcessForgetValue() { } // because constants do not change
}// Constant (class)
```

## Creation and Linkage of Connectors

The constructor of the `Connector `class must initialize the name of a connector, set its informant to zero (to indicate that the connector has no value), and initialize the list of links to constraints. When function `Connector.Connect `is called by a constraint, the reference to the constraint must be added to the list of links of the connector. Then, if the connector has a value, the constraint must process such a value.

## Message-Passing Among Connectors and Constraints

Connectors communicate with constraints by passing messages to them via the enumerated type message, defined as follows:

C#
```// Constants for message-passing
public enum message { GotValue, LostValue }
```

A connector uses the message `GotValue `to signal to a constraint that it has acquired a new value, and the message `LostValue `to signal that it has lost its value. A connector’s `SetFvalue `or `SetIvalue `function is called to request the setting of its value. If the connector does not have a value, it sets the value and remembers as the informant the constraint that requested the setting of the value. Then, the connector sends a message about the new value to all the constraints linked to it except the constraint that requested the value to be set. These actions for the case of floating-point values are implemented by the following code:

C#
```public void SetValue( float _newValue, Constraint setter )
{
if ( !HasValue() )
{
fvalue = _newValue;
informant = setter;
ForEachExcept( setter, message.GotValue );
}
else // HasValue()
if ( fvalue != _newValue )
{
Console.Write( "connector " );
ShowName();
Console.WriteLine( " *** contradiction {0} != {1}",
fvalue, _newValue );
}
}
```

The definition of function `SetIvalue `is similar.

Function `ForEachExcept `is defined as follows:

C#
```// Function to propagate a message among the constraints
// linked to the connector, except for the constraint
// that issued the message.

protected void ForEachExcept( Constraint exception, message m )
{
foreach ( Constraint c in links )
{
if ( c != exception )
{
if ( m == message.GotValue )
{
try
{
c.ProcessNewValue();
}
catch ( System.Exception e )
{
Console.WriteLine( e.Message );
}
}
else // m == message.LostValue
{
c.ProcessForgetValue();
}
}
}
}
```

If a retractor constraint calls function `Connector::ForgetValue `to request a connector to forget its value, the connector first makes sure that the request comes from the same constraint that set the value originally. If that is not the case, the connector ignores the request. Otherwise, the connector clears the informant reference, and informs its associated constraints (except the retractor) about the loss of its value. The definition of function `Connector::ForgetValue `is as follows:

C#
```// A 'retractor' constraint requests the connector
// to forget its value (either ivalue or fvalue)

public void ForgetValue( Constraint retractor )
{
if ( retractor == informant )
{
informant = null;
ForEachExcept( retractor, message.LostValue );
}
}
```

## Probes and Users

In order to watch a constraint network in action, probes can be attached to connectors. A Probe constraint prints an appropriate message (via `ProcessNewValue` and `ProcessForgetValue`, respectively) about the setting or unsetting of the value of the associated connector. Additionally, the user of the constraint-propagation system may want to set/unset the values on one or more connectors. For this purpose, it is convenient to define a dummy constraint User (whose constructor, `ProcessNewValue `and `ProcessForgetValue `functions do nothing) that could be passed as either the setter or the retractor argument to the `SetFvalue`, `SetIvalue`, and `ForgetValue `functions of connectors. The definition of the constraints `Probe `and `User `are as follows:

C#
```public class Probe : Constraint // A probe is a kind of constraint,
{
protected Connector conn;         // linked to a connector by its constructor.
protected behavior onForgetValue; // output normal or quiet

public Probe( Connector c, behavior ofg = behavior.normal )
{
conn = c;             // Maintain a reference to the connector.
conn.Connect( this ); // Link (i.e., connect) the connector.
onForgetValue = ofg;
}

public override void ProcessNewValue()    // Print the new value assigned
{                                         // to a connector
Console.Write( "probe: " );
conn.ShowName();
if ( conn.Type == valueType._float )
{
Console.WriteLine( "(f) = {0}", conn.Fvalue );
}
else // conn.Type == valueType._int
{
Console.WriteLine( "(i) = {0}", conn.Ivalue );
}
}

public override void ProcessForgetValue()  // Print a '?' to signal that
{ //                                       // a connector has lost its value
if ( onForgetValue == behavior.normal )
{
Console.Write( "\tprobe: " );
conn.ShowName();
Console.WriteLine( " = ?" );
}
}
}// Probe (class)

public class User : Constraint // A user is a kind of constraint
{
public User() { }                             // Associated to nothing,
public override void ProcessNewValue() { }    // and performing
public override void ProcessForgetValue() { } // no actions
}// User (class)
```

## Generic Primitive Logic Gates

A simple application of connectors that hold integer values is the implementation of generic primitive logic gates. The following figure illustrates the symbols for the primitive logic functions `NOT`, `AND`, and `OR`, respectively.

An inverter is a logic gate with one input and one output (the connector emerging from the small circle). The `NOT `function prescribes that the (logic) value on the output connector is the complement of the value on the input connector, that is, if the input is `0(1)` the output is `1(0)`.

The two-input, one-output `AND `gate produces a `1` on its output connector only when both input connectors hold a `1`, while the output is `0` whenever one (or both) of the inputs is (are) `0`. The output of an `OR `gate is `0` only when both of its inputs are `0`, while the output is `1` whenever one (or both) of the inputs is (are) `1`. These operational descriptions can be easily implemented by constraints. However, suppose that it is desired to implement N-input, `1`-output `AND `and `OR `logic gates, with the additional requirement that the number of inputs is to be determined at run time. In combination with the inverter, such gates are extremely useful as building blocks to implement logic circuits of arbitrary complexity.

Instead of plunging into a straightforward implementation of these gates as two different kinds of constraints, some thought reveals that they share common features. In both cases, it is necessary to (a) keep track of the actual number of connectors, (b) allocate references to the connectors, (c) initialize the references, and (d) link the connectors to the constraint. Further thought reveals that, no matter what kind of logic function is performed, in both cases function `ProcessForgetValue `must do the same, namely tell all the connectors associated with the constraint to forget their values. By exploiting the inheritance mechanism of C# the `AND `and `OR `gates can be implemented as specializations of a generic N-input, `1`-output logic gate (`NinGate`) defined as follows:

C#
```public class NinGate : Constraint // An N-input, 1-output gate
{                                 // is a kind of constraint
protected int M;               // with a number (M) of external connectors
// which is determined at run time.
// Connectors 0 .. M-2 are the N inputs
// and connector M-1 is the output.
protected Connector[] conn;
protected Report report = new Report();

public NinGate( params Connector[] _c )
{
M = _c.Length;
conn = new Connector[ M ];
for ( int i = 0; i < M; ++i )
{
conn[ i ] = new Connector( "_", valueType._int ); // Anonymous instance
// of a connector
conn[ i ] = _c[ i ]; // Maintain a reference to each connector.
}
for ( int i = 0; i < M; ++i )
{
conn[ i ].Connect( this ); // Link (i.e., connect) each connector to
}                             // this constraint (instance of NinGate).
}

public override void ProcessForgetValue() // Can be implemented at this level
{
for ( int i = 0; i < M; ++i )     // Inform each connector that this
{                                 // constraint requests them to forget
conn[ i ].ForgetValue( this ); // their values.
}
ProcessNewValue();                // Try to process a new value not
}                                    // originally set by NinGate.

public override void ProcessNewValue() // No processing can be performed
{                                      // without further specialization
}                                      // (i.e., kind of gate implemented)
}// NinGate (class)
```

Observe that the class `NinGate `provides an implementation of `ProcessForgetValue`, but maintains as pure virtual the function `ProcessNewValue`.

The specializations of an `NinGate `into `AND `and `OR `gates involve the implementation of function `ProcessNewValue `for each gate. Thus, an `N`-input, `1`-output `AND `gate (`NinAnd`) can be defined as a kind of `NinGate `as follows:

C#
```public class NinAnd : NinGate // An NinAnd gate is a kind of NinGate
{
public NinAnd( params Connector[] _c )
:
base( _c ) { report.NargConstraint( "And", _c ); }

public override void ProcessNewValue() // that processes new values according
{                                      // to the logic of the AND function.
int i, withValue, M1 = M - 1;

for ( i = 0, withValue = 0; i < M1; ++i )
{
if ( conn[ i ].HasValue() )
{
++withValue;
if ( conn[ i ].Ivalue == 0 )
{
conn[ M1 ].SetValue( 0, this ); // when any input is 0
return;                         // the output must be 0
}
}
}
if ( withValue == M1 ) // when all inputs are 1
{
conn[ M1 ].SetValue( 1, this ); // the output must be 1
}
else
if ( conn[ M1 ].HasValue() && conn[ M1 ].Ivalue == 1 ) // when the output is 1
{
for ( i = 0; i < M1; ++i )
{
conn[ i ].SetValue( 1, this ); // all inputs must be 1
}
}
}
}// NinAnd (class)
```

An `N`-input, `1`-output `OR `gate (`NinOr`) is defined in a similar way.

## Conservative-Logic Fredkin Gates

This section and the next deal with further extensions to the constraint-propagation system to implement conservative-logic circuits. (After Fredkin, E., and T. Toffoli “Conservative Logic,” International Journal of Theoretical Physics, Vol. 21, No. 3, 1982, pp. 227-230. More accessible descriptions of Fredkin gates can be found in the following books: Hey, T., and R.W. Allen (Eds.) Feynman Lectures on Computation, Westview, 1999, pp. 34-39. Feynman, R.P. The Pleasure of finding things out, Cambridge, Massachusetts: Perseus Books, pp. 40-41. Milburn, G.J. The Feynman Processor: Quantum Entanglement and the Computing Revolution, Australia: Perseus Books, 1998, pp. 125-131.)

The Fredkin gate is a computing element that allows reversible computation, and has received much attention for quantum computation. This gate (illustrated below) performs conditional crossover of two data signals according to the value of a control signal.

When the control signal (u) is `1`, the two data signals follow parallel paths; when the control signal is `0`, the two data signals cross over. Observe that this gate is nonlinear. When considered as a function, the gate coincides with its own inverse, that is, two Fredkin gates connected in cascade yield the identity function:

The following figures illustrate my CMOS implementation of the Fredkin gate in terms of both transmission gates and a basic inverter (which is used to generate the complement of the control signal u). This is to show that this gate is not just a mathematical toy.

 CMOS Fredkin gate Basic CMOS inverter

The implementation of a Fredkin gate in terms of a constraint-propagation system is as follows:

C#
```using ConstraintsLib;

namespace FredkinGate
{
public class FredkinGate : Constraint // A Fredkin gate is a kind of constraint
{
protected Connector[] conn; // that links to several connectors by means of its constructor

public FredkinGate( Connector[] _c ) // elements of array _c: u, v, x1, x2, y1, y2
{
conn = new Connector[ Constants.FGn2 ]; // elements of array conn: u, v, x1, x2, y1, y2

Console.Write( "FredkinGate( " );
for ( int i = 0; i < Constants.FGn2; ++i )
{
conn[ i ] = _c[ i ];
conn[ i ].Connect( this );
conn[ i ].ShowName();
Console.Write( " " );
}
Console.WriteLine( " )" );
}

protected void TrySetSignals( int uv )
{
for ( int i = 2; i < Constants.FGn2; ++i )
{
if ( conn[ i ].HasValue() )
{
conn[ (int)Constants.FGlut[ uv, i ] ].SetValue( conn[ i ].Ivalue, this );
}
}
}

public override void ProcessNewValue()
{
int u, v;

if ( conn[ (int)SI._u ].HasValue() )
{
u = conn[ (int)SI._u ].Ivalue;
conn[ (int)SI._v ].SetValue( u, this );
TrySetSignals( u );
}
else // !conn[ (int)SI._u ].HasValue()
{
if ( conn[ (int)SI._v ].HasValue() )
{
v = conn[ (int)SI._v ].Ivalue;
conn[ (int)SI._u ].SetValue( v, this );
TrySetSignals( v );
}
}
}

public override void ProcessForgetValue()
{
for ( int i = 0; i < Constants.FGn2; ++i )
{
conn[ i ].ForgetValue( this );
}
ProcessNewValue();
}
}
}```

## Conservative-Logic Primitive Functions

The Fredkin gate can be used to implement (as constraints) the primitive logic functions `NOT`, `AND`, and `OR `illustrated below:

 NOT AND OR

As an example, the following code implements a conservative-logic `AND `function in terms of a Fredkin gate:

C#
```using ConstraintsLib;

namespace FredkinGate
{
public class ConsLogic_AND : Constraint
{
protected Connector[] conn;       // ConsLogic_AND gate I/O connectors (a, b, ab)
protected Connector[] FG_IO_Conn; // Fredkin gate I/O connectors (u, v, x1, x2, y1, y2)
protected Constant zero;          // Constant 0 fed to Fredkin gate input x2
protected FredkinGate fg;         // Fredkin gate

public ConsLogic_AND( Connector[] _c ) // elements of array _c: a, b, ab
{

conn = new Connector[ 3 ]; // elements of array conn: a, b, ab
Console.Write( "ConsLogic_ANDgate( " );
for ( int i = 0; i < 3; ++i )
{
conn[ i ] = _c[ i ];
conn[ i ].Connect( this );
conn[ i ].ShowName();
Console.Write( " " );
}
Console.WriteLine( " )" );

// Implement the conservative-logic AND gate

FG_IO_Conn = new Connector[ Constants.FGn2 ];

FG_IO_Conn[ 0 ] = conn[ 0 ]; // a <--> u
FG_IO_Conn[ 1 ] = conn[ 0 ]; // a <--> v
FG_IO_Conn[ 2 ] = conn[ 1 ]; // b <--> x1

FG_IO_Conn[ 3 ] = new Connector( "0", valueType._int );
zero = new Constant( 0, FG_IO_Conn[ 3 ] );              // 0 <--> x2

FG_IO_Conn[ 4 ] = conn[ 2 ]; // ab <--> y1
FG_IO_Conn[ 5 ] = new Connector( "_ab", valueType._int );

fg = new FredkinGate( FG_IO_Conn );
}

public override void ProcessNewValue() { }    // all the work is done by the Fredkin gate

public override void ProcessForgetValue() { } // all the work is done by the Fredkin gate
}
}```

Upon execution as a Console application, the output is as follows:

## Complex Logic Building Blocks

The primitive logic functions that have been implemented as constraints can be further combined to create more complex building blocks. As a simple and interesting example, the constraint-propagation system can be used to implement a 4-to-1-line multiplexer similar to the Transistor-Transistor Logic (TTL) SN74153 4-to-1 multiplexer, whose internal logic and block diagram are shown below. (After Texas Instruments Inc. The TTL Data Book for Design Engineers, Dallas, Texas, 1976.)

One half of the TTL SN74153 4-to-1 multiplexer and its block diagram

Using N-input, 1-output `AND`/`OR `gates, one-half of the SN74153 multiplexer is implemented as follows:

C#
```using ConstraintsLib;
using NinGatesLib;

namespace HalfSN74153
{
// Input/Ouput signals for the multiplexer

public enum h74153signal { G, C0, C1, C2, C3, B, A, Y };

public class H_SN74153 : Constraint // One half of an SN74153 is a kind
{                                   // of constraint, implemented with
protected Connector[] w,         // five level-1, level-2 internal connectors,
x;         // four level-3 internal connectors,
protected Inverter[] inv;        // five inverters,
protected NinAnd[] and;          // four 4-input AND gates,
protected NinOr or;              // and one 4-input OR gate

protected Report report = new Report();

public H_SN74153( params Connector[] extC )
{
// extC.Length == 8
// Array extC contains the external I/O connectors to interface
// with the multiplexer, indexed by the h74153signal enumeration.

GenSym wSym = new GenSym( "w" ), // symbol-generator for level-1 and level-2 connectors
xSym = new GenSym( "x" ); // symbol-generator for level-3 connectors
int i;

// Create the internal connectors
w = new Connector[ 5 ];
x = new Connector[ 4 ];
for ( i = 0; i < 4; ++i )
{
w[ i ] = new Connector( wSym.next(), valueType._int );
x[ i ] = new Connector( xSym.next(), valueType._int );
}
w[ 4 ] = new Connector( wSym.next(), valueType._int );

// Create the inverters
inv = new Inverter[ 5 ];
inv[ 0 ] = new Inverter( extC[ (int)h74153signal.G ], w[ 0 ] );
inv[ 1 ] = new Inverter( extC[ (int)h74153signal.B ], w[ 1 ] );
inv[ 2 ] = new Inverter( w[ 1 ], w[ 3 ] );
inv[ 3 ] = new Inverter( extC[ (int)h74153signal.A ], w[ 2 ] );
inv[ 4 ] = new Inverter( w[ 2 ], w[ 4 ] );

// Create AND gates
and = new NinAnd[ 4 ];
and[ 0 ] = new NinAnd( w[ 0 ], w[ 1 ], w[ 2 ], extC[ (int)h74153signal.C0 ], x[ 0 ] );
and[ 1 ] = new NinAnd( w[ 0 ], w[ 1 ], w[ 4 ], extC[ (int)h74153signal.C1 ], x[ 1 ] );
and[ 2 ] = new NinAnd( w[ 0 ], w[ 3 ], w[ 2 ], extC[ (int)h74153signal.C2 ], x[ 2 ] );
and[ 3 ] = new NinAnd( w[ 0 ], w[ 3 ], w[ 4 ], extC[ (int)h74153signal.C3 ], x[ 3 ] );

// create OR gate
or = new NinOr( x[ 0 ], x[ 1 ], x[ 2 ], x[ 3 ], extC[ (int)h74153signal.Y ] );

report.NargConstraint( "Half SN74153", extC );
}

public override void ProcessNewValue() { }    // All the processing is done
public override void ProcessForgetValue() { } // by the internal gates

}// H_SN74153 (class)
}```

The 4-to-1 multiplexer can be used as a building block for a 4-bit, left-shift, barrel shifter whose implementation is shown below. The shifter has two control inputs (A and B), four parallel inputs (I0 to I3), a “fill” input (F), and four parallel outputs (Y0 to Y3). The most significant data bits are I3 and Y3, while B is the most significant control bit.

As a test of the barrel shifter, the input bits 1001 from the parallel inputs can be transferred to the outputs, and shifted to the left by generating all the possible combinations of the control inputs and of the fill input.

C#
```namespace FourBitBarrelShifter
{
class Program
{
static void Main( string[] args )
{
GenSym iSym = new GenSym( "I" ),                    // symbol-generator for input (I) connectors
ySym = new GenSym( "Y" );                    // symbol-generator for output (Y) connectors
Connector[] i = new Connector[ 4 ],                 // connectors for input signals
y = new Connector[ 4 ];                 // connectors for output signals
Connector f = new Connector( "F", valueType._int ), // connector for fill signal
g = new Connector( "G", valueType._int ), // connector for gate control
a = new Connector( "A", valueType._int ), // connector for address signal A
b = new Connector( "B", valueType._int ); // connector for address signal B
Constant gnd = new Constant( 0, g );                // gate control connected to ground
Probe[] pr = new Probe[ 7 ];                        // probes for the F, and A-B and Y connectors
H_SN74153[] mux = new H_SN74153[ 4 ];               // 4 half SN74153 multiplexers
User jlo = new User();                              // user constraint to set/clear signals
int j, k;

// Create the input-output connectors
for ( j = 0; j < 4; ++j )
{
i[ j ] = new Connector( iSym.next(), valueType._int );
y[ j ] = new Connector( ySym.next(), valueType._int );
}

// Create the probes
j = k = 0;
while ( j < 4 ) // for the output connectors
{
pr[ j++ ] = new Probe( y[ k++ ], behavior.quiet );
}
pr[ j++ ] = new Probe( f );
pr[ j++ ] = new Probe( a, behavior.quiet );
pr[ j++ ] = new Probe( b, behavior.quiet );

// Sample input signals
i[ 3 ].SetValue( 1, jlo );
i[ 2 ].SetValue( 0, jlo );
i[ 1 ].SetValue( 0, jlo );
i[ 0 ].SetValue( 1, jlo );

// Create the multiplexers
//
// Mux signals: G, C0, C1, C2, C3, B, A, Y

mux[ 3 ] = new H_SN74153( g, i[ 3 ], i[ 2 ], i[ 1 ], i[ 0 ], b, a, y[ 3 ] );
mux[ 2 ] = new H_SN74153( g, i[ 2 ], i[ 1 ], i[ 0 ], f,      b, a, y[ 2 ] );
mux[ 1 ] = new H_SN74153( g, i[ 1 ], i[ 0 ], f,      f,      b, a, y[ 1 ] );
mux[ 0 ] = new H_SN74153( g, i[ 0 ], f,      f,      f,      b, a, y[ 0 ] );

for ( int _f = 0; _f < 2; ++_f )
{
f.SetValue( _f, jlo );
for ( int _a = 0; _a < 2; ++_a )
{
a.SetValue( _a, jlo );
for ( int _b = 0; _b < 2; ++_b )
{
Console.WriteLine( String.Format( "\nF = {0}, A = {1}, B = {2}\n", _f, _a, _b ) );
b.SetValue( _b, jlo );
b.ForgetValue( jlo );
}
a.ForgetValue( jlo );
}
f.ForgetValue( jlo );
}
}
}
}```

When run as a console application, excerpts of the output are as follows:

## Running the Code

To run the code, unzip the Projects file into your Visual Studio Projects directory.

Written By
United States
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.