约束传播
4.58/5 (6投票s)
约束传播
引言
注意：本文摘录自我尚未出版的教科书《应用算法与数据结构》第15章“特殊计算模式”中的部分内容，并基于以下文献：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。
本文讨论约束传播系统的实现。计算机程序通常组织成单向计算，对预先指定的参数执行操作以产生期望的输出。另一方面，系统则以量之间的关系进行建模。例如，描述电阻 R（欧姆）的电阻器数学模型由方程 R = ρ(L/A) 给出，其中 ρ 是材料的电阻率（欧姆-厘米），L 是其长度（厘米），A 是其横截面积（平方厘米）。
材料电阻率的方程不是单向的。如果已知其中任何三个量，都可以用来计算第四个量。然而，将该方程转换为传统计算机语言中的函数需要选择一个量来表示其他三个量。因此，用于计算面积 A 的过程不能用于计算电阻率 ρ，即使这两种计算都源于同一个方程。
约束网络
可以使用面向对象编程定义一种新的编程语言，允许我们基于关系进行工作。新语言的元素是基本约束，它们声明某些关系在量之间成立。例如，约束 adder( a, b, c ) 可能指定量 a、b 和 c 之间满足方程 a + b = c。类似地，约束 multiplier( u, v, w ) 将表示方程 u * v = w。要指定变量的常量值，例如 x == 2.5，我们可以使用诸如 constant( x, 2.5 ) 这样的约束。
这种语言提供了一种组合基本约束以表达更复杂关系的方法。约束通过构建约束网络进行组合，在约束网络中，约束由连接器连接。连接器是一个对象，它持有一个可能参与一个或多个约束的值。例如，摄氏度和华氏度温度之间的关系由方程 9C = 5(F – 32) 给出，这种约束方程可以被视为由基本加法器、乘法器和常数约束组成的网络，如下所示。
在图的左侧，有一个乘法器框（即约束），带有三个标有 m1、m2 和 p 的终端。它们通过以下方式将乘法器连接到网络的其余部分。终端 m1 连接到一个持有摄氏温度的连接器 C。终端 m2 通过连接器 w 连接到一个持有数字 9 的常数框。终端 p，乘法器框限制其为 m1 和 m2 的乘积，连接到另一个乘法器框的 p 终端，该乘法器框的 m2 终端连接到一个持有 5 的常数框，而其 m1 终端连接到一个加法器框的 s 终端。加法器终端 a1 连接到连接器 F（持有华氏温度），终端 a2 连接到连接器 y，该连接器又连接到一个持有数字 –32 的常数框。
这种网络的计算过程如下。当连接器获得值时（由用户约束或其连接的约束框设置），它会唤醒所有与之关联的约束（除了刚刚被连接器唤醒的约束），通知它们它有一个值。每个被唤醒的约束框然后轮询其连接器，看看是否有足够的信息来确定其中一个连接器的值。如果有，该框将设置该连接器的值，连接器唤醒所有与之关联的约束，从而重复此过程。在摄氏-华氏度转换示例中，连接器 w、x 和 y 分别立即由常数框设置为 9、5 和 -32。这些连接器唤醒两个乘法器和加法器，它们确定没有足够的信息可以继续（因为连接器 C 和 F，因此 u 和 v，没有值）。当用户约束（或其他网络部分）将 C 设置为某个值，例如 25 时，最左边的乘法器被唤醒，它将 u 设置为值 25 * 9 = 225。然后，连接器 u 唤醒中间的乘法器，它将 v 设置为 45。最后，连接器 v 唤醒加法器，它将 F 设置为 77。
连接器和抽象约束
约束传播系统可以通过类、继承和虚函数在 C#/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),
protected List<Constraint> links; // and is linked to other constraints
// 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
links = new List<Constraint>(); // Initialize the list of links
}
// Link the connector to a new constraint
public void Connect( Constraint _newConstraint )
{
links.Add( _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)
请注意，类 `Connector` 可以同时处理浮点数和定点数，但不能同时处理两者。它还具有设置和检索 `int` 或 `float` 值的函数。
约束类的测试
以下是对 `ConstraintsLib` 类的简单测试。
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 );
}
}
}
当作为控制台应用程序运行时，输出如下：
基本约束
类 `Constraint` 是真正的 `abstract` 类，因为它不能被实例化。不能定义 `Constraint` 类型的变量，但其他类可以定义为从它派生。作为简单的说明，`Adder` 可以定义为一种 `Constraint`，如下所示：
public class Adder : Constraint // An adder is a kind of constraint
{
// that links to three connectors, two addends (a1, a2)
// 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.
}// Adder (class)
`Adder` 约束的定义提供了 `abstract` 基类虚函数的具体实现。当 `adder` 被告知其连接器之一具有值时，会调用 `ProcessNewValue` 函数。为简单起见，该函数假定连接到 `adder` 的连接器持有相同类型的值。通过检查连接器 `s` 持有的值类型，可以调用适当的函数来获取和设置连接器值。
`ProcessForgetValue` 函数在 `adder` 被告知其连接器之一丢失值时被调用。该函数请求连接到加法器的所有连接器忘记它们的值。（实际上只会丢失由该 `adder` 最初设置的值）。然后它调用 `ProcessNewValue`，因为一个或多个连接器可能仍然有一个值（不是由 `adder` 最初设置的），该值必须通过其他约束进行传播。
`Multiplier` 约束的定义方式与 `adder` 类似，其中规定，如果任一因子为零，乘法器会将乘积设置为零，即使另一个因子的值未知（未定义）。`Multiplier` 类的定义是一个类似的类。在除以零的情况下，`Multiplier` 约束的 `ProcessNewValue` 函数必须中止使用该乘法器约束的程序的执行。
`Constant` 约束只是设置其关联连接器的值。两个构造函数允许定义浮点和定点常量。其成员函数 `ProcessNewValue` 和 `ProcessForgetValue` 不执行任何操作（因为常量不会改变）。
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)
连接器的创建和链接
`Connector` 类的构造函数必须初始化连接器的名称，将其通知者设置为零（表示连接器没有值），并初始化链接到约束的列表。当约束调用 `Connector.Connect` 函数时，约束的引用必须添加到连接器的链接列表中。然后，如果连接器有值，则该约束必须处理该值。
连接器和约束之间的消息传递
连接器通过传递消息与约束通信，消息通过枚举类型 `message` 定义，如下所示：
// Constants for message-passing
public enum message { GotValue, LostValue }
连接器使用 `GotValue` 消息向约束发出信号，表示它已获得新值，并使用 `LostValue` 消息发出信号表示它已丢失值。调用连接器的 `SetFvalue` 或 `SetIvalue` 函数来请求设置其值。如果连接器没有值，它会设置该值，并将请求设置值的约束作为通知者记住。然后，连接器会将关于新值和旧值的信息发送给所有与之链接的约束，除了请求设置值的那个约束。以下代码实现了浮点值情况下的这些操作：
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 );
}
}
`SetIvalue` 函数的定义类似。
`ForEachExcept` 函数定义如下：
// 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::ForgetValue` 函数请求连接器忘记其值，连接器首先确保该请求来自最初设置该值的约束。如果不是这种情况，连接器将忽略该请求。否则，连接器清除通知者引用，并将其关联的约束（撤销者除外）通知有关其值丢失的信息。 `Connector::ForgetValue` 函数的定义如下：
// 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 );
}
}
探测器和用户
为了观察约束网络的工作情况，可以将探测器附加到连接器上。探测器约束通过 `ProcessNewValue` 和 `ProcessForgetValue` 分别打印一条适当的消息，关于关联连接器值的设置或取消设置。此外，约束传播系统的用户可能希望设置/取消设置一个或多个连接器的值。为此，定义一个虚拟约束 `User`（其构造函数、`ProcessNewValue` 和 `ProcessForgetValue` 函数不执行任何操作）会很方便，它可以作为设置者或撤销者参数传递给连接器的 `SetFvalue`、`SetIvalue` 和 `ForgetValue` 函数。 `Probe` 和 `User` 约束的定义如下：
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)
通用基本逻辑门
连接器持有整数值的简单应用是实现通用基本逻辑门。下图分别说明了基本逻辑函数 `NOT`、`AND` 和 `OR` 的符号。
反相器是一种只有一个输入和一个输出（从小圆圈引出的连接器）的逻辑门。 `NOT` 函数规定，输出连接器上的（逻辑）值是输入连接器值的补码，即，如果输入是 `0(1)`，输出是 `1(0)`。
两个输入、一个输出的 `AND` 门仅当两个输入连接器都持有 `1` 时，其输出连接器才产生 `1`，而当输入（或两个输入）是 `0` 时，输出为 `0`。 `OR` 门的输出仅当两个输入都是 `0` 时才为 `0`，而当一个（或两个）输入是 `1` 时，输出为 `1`。这些操作描述可以很容易地通过约束来实现。但是，假设我们希望实现 N 输入、1 输出的 `AND` 和 `OR` 逻辑门，并且附加要求在运行时确定输入的数量。与反相器结合，这类门是实现任意复杂度的逻辑电路的极其有用的构建块。
与其直接实现这两种不同类型的约束门，不如仔细考虑它们共享的公共特征。在这两种情况下，都有必要 (a) 跟踪连接器的实际数量，(b) 分配连接器的引用，(c) 初始化引用，以及 (d) 将连接器链接到约束。进一步思考发现，无论执行何种逻辑函数，在两种情况下 `ProcessForgetValue` 函数都必须执行相同的操作，即告诉与约束关联的所有连接器忘记它们的值。通过利用 C# 的继承机制，`AND` 和 `OR` 门可以实现为通用 N 输入、1 输出逻辑门（`NinGate`）的特化，该门定义如下：
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)
请注意，`NinGate` 类提供了 `ProcessForgetValue` 的实现，但将 `ProcessNewValue` 函数保持为纯虚函数。
将 `NinGate` 特化为 `AND` 和 `OR` 门涉及为每个门实现 `ProcessNewValue` 函数。因此，N 输入、1 输出的 `AND` 门（`NinAnd`）可以定义为 `NinGate` 的一种，如下所示：
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)
N 输入、1 输出的 `OR` 门（`NinOr`）以类似的方式定义。
保守逻辑 Fredkin 门
本节和下一节将讨论约束传播系统的进一步扩展，以实现保守逻辑电路。（参考 Fredkin, E., and T. Toffoli “Conservative Logic,” International Journal of Theoretical Physics, Vol. 21, No. 3, 1982, pp. 227-230。在以下书籍中可以找到更易于理解的 Fredkin 门描述：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。）
Fredkin 门是一种允许可逆计算的计算单元，并且因其在量子计算中的应用而受到广泛关注。该门（下图所示）根据控制信号的值执行两个数据信号的条件交叉。
当控制信号 (u) 为 `1` 时，两个数据信号沿平行路径传输；当控制信号为 `0` 时，两个数据信号交叉。请注意，此门是非线性的。当将其视为一个函数时，该门与其自身的逆函数重合，即，两个级联的 Fredkin 门产生恒等函数。
下图说明了我使用传输门和基本反相器（用于生成控制信号 u 的补码）在 CMOS 中实现 Fredkin 门。这表明该门不仅仅是一个数学玩具。
| CMOS Fredkin 门 | 基本 CMOS 反相器 |
 |
 |
在约束传播系统中实现 Fredkin 门如下：
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();
}
}
}
保守逻辑基本函数
Fredkin 门可用于（作为约束）实现下图所示的基本逻辑函数 `NOT`、`AND` 和 `OR`。
| NOT | AND | 或者 |
 |
 |
 |
例如，以下代码使用 Fredkin 门实现了一个保守逻辑 `AND` 函数：
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
{
// Link the input/output connectors
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
}
}
作为控制台应用程序执行时，输出如下：
复杂逻辑构建块
已作为约束实现的逻辑基本函数可以进一步组合以创建更复杂的构建块。作为一个简单有趣的例子，约束传播系统可用于实现一个 4 对 1 线多路复用器，类似于晶体管-晶体管逻辑 (TTL) SN74153 4 对 1 多路复用器，其内部逻辑和框图如下所示。（参考 Texas Instruments Inc. The TTL Data Book for Design Engineers, Dallas, Texas, 1976。）
 |
 |
使用 N 输入、1 输出的 `AND`/`OR` 门，SN74153 多路复用器的一半实现如下：
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)
}
4 对 1 多路复用器可用作 4 位、左移、桶形移位器的构建块，其实现如下所示。移位器有两个控制输入 (A 和 B)，四个并行输入 (I0 到 I3)，一个“填充”输入 (F)，以及四个并行输出 (Y0 到 Y3)。最重要的数据位是 I3 和 Y3，而 B 是最重要的控制位。
作为对桶形移位器的测试，可以通过生成控制输入和填充输入的各种组合，将并行输入中的位 1001 传输到输出，并向左移位。
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 );
}
}
}
}
作为控制台应用程序运行时，输出节选如下：
 |
 |
 |
运行代码
要运行代码，请将 `Projects` 文件解压到您的 Visual Studio Projects 目录中。