McCarthy 歧义运算符的 C# 实现
5.00/5 (6投票s)
McCarthy 歧义运算符在 C# 中的实现
引言
已故的 John McCarthy 发表了一篇题为“计算的数学理论基础”的论文，收录在 P. Braffort 和 D. Hirshberg 编辑、North-Holland 于 1963 年出版的《计算机程序设计与形式系统》一书中。在文中，McCarthy 讨论了计算的许多其他方面，包括模糊函数。
模糊函数
McCarthy 认为模糊函数实际上不是函数，因为对于其参数值的每种组合，模糊函数都会返回一个可能值的列表。他举了一个函数 less( n ) 为例，该函数针对所有正整数 n 定义。该函数是模糊的，因为小于 n 的每个非负整数都是 less( n ) 的可能值。为了定义此函数，McCarthy 定义了一个基本的模糊算子 amb( x, y )，其可能值为 x 和 y（当两者都定义时）；否则，则为已定义的那个。请注意，根据其基本定义，模糊算子会返回一个值列表。（这稍后会改变。）函数 less( n ) 可以根据 amb 算子定义如下：
由于其论文的性质，在此定义之后，McCarthy 没有提供任何实现细节。（谨告诫读者：以免读者得出 McCarthy 仅仅是一位纯数学家的结论，必须回顾他不仅设计和实现了 Lisp 编程语言的第一个版本，还发明了分时概念，这是任何现代操作系统实现的基础。）
amb 算子的实现
从现在开始，所有将要展示的 C# 代码都假定位于 Visual Studio 控制台应用程序的上下文中。
amb 算子的一个基本属性是它返回的值取决于其参数是否已定义。在 C# 中处理此属性的方法是使用可空类型，可空类型是标量类型，可以取 null 作为其值。（C# 中引入可空类型是为了使程序能够处理来自 SQL Server 数据库等的 NULL 值。）考虑到这一点，amb 算子可以按如下方式实现：
static List<int> amb( int? x, int? y )
{
List<int> values = new List<int>(); // A list containing no values.
if ( x != null && y != null )
{
values.Add( (int)x );
values.Add( (int)y );
}
else // x == null || y == null
{
if ( x != null )
{
values.Add( (int)x );
}
else if ( y != null )
{
values.Add( (int)y );
}
// else BOTH x and y are null. Do not add anything to values.
}
return values;
}// amb
在上面的代码中，int? 是一个整数可空类型。amb 函数返回一个整数列表，它直接实现了 amb 算子的语义。但是，有一个问题。
从 McCarthy 的模糊函数 less( n ) 的定义可以看出，一般来说，amb 算子的第二个参数可能是一个值列表（可能是 null），而不仅仅是一个标量可空类型。为了处理这种情况，可以如下重载 amb 函数：
static List<int> amb( int? x, List<int> y )
{
List<int> values = new List<int>(); // A list containing no values.
if ( x != null && y != null )
{
values.Add( (int)x );
values.AddRange( y );
}
else // x == null || y == null
{
if ( x != null )
{
values.Add( (int)x );
}
else if ( y != null )
{
values = y;
}
// else BOTH x and y are null. Do not add anything to values.
}
return values;
}// amb
与函数第一个版本相比，这里的更改在于处理第二个参数是列表的情况，即 values.AddRange( y ) 和 values = y。
模糊函数的实现
有了上面给出的 amb 算子的功能，模糊函数 less( n ) 可以如下实现：
static List<int> less( int n )
{
return n == 0
? null
: amb( n - 1, less( n - 1 ) );
}// less
另一个与 less( n ) 类似的模糊函数是处理 2 的幂的函数。给定一个作为 2 的指数的值 n，所有小于 2n 的正幂都可能是以下函数的可能值。
static List<int> ltPof2( int n )
{
return n == 0
? null
: amb( 1 << ( n - 1 ), ltPof2( n - 1 ) );
}// ltPof2
测试前面的代码
将所有代码放入 Visual Studio 控制台应用程序中，就可以在主程序中测试 amb 算子和两个模糊函数的功能，例如下面的示例：
static void Main( string[] args )
{
PrintList( " amb( 5, 7 )", amb( 5, 7 ) );
PrintList( " amb( null, 7 )", amb( null, 7 ) );
PrintList( " amb( 5, (int?)null )", amb( 5, (int?)null ) );
PrintList( "amb( (int?)null, (int?)null )", amb( (int?)null, (int?)null ) );
Console.WriteLine();
PrintList( "less( 10 )", less( 10 ) );
PrintList( " less( 2 )", less( 2 ) );
PrintList( " less( 0 )", less( 0 ) );
Console.WriteLine();
PrintList( "ltPof2( 10 )", ltPof2( 10 ) );
PrintList( " ltPof2( 2 )", ltPof2( 2 ) );
PrintList( " ltPof2( 0 )", ltPof2( 0 ) );
Console.WriteLine();
}// Main
其中函数 PrintList 只是在控制台上显示值列表。
static void PrintList( string operation, List<int> list )
{
Console.Write( "\n{0}: [", operation );
if ( list != null )
{
foreach ( int i in list )
{
Console.Write( " {0}", i );
}
}
Console.WriteLine( " ]" );
}// PrintList
执行示例主程序会产生如下图所示的结果：
函数值的解析
一旦模糊函数返回一个可能值的列表，出现的问题是哪个值将用作函数的值以供进一步处理。答案很简单：如果可能值列表包含多个元素，只需从列表中随机选择一个值。需要进行的更改可能如下：
static Random rnd;
static void Main( string[] args )
{
rnd = new Random();
PrintListAndResolve( "less( 10 )", less( 10 ) );
PrintListAndResolve( "less( 10 )", less( 10 ) );
PrintListAndResolve( " less( 2 )", less( 2 ) );
PrintListAndResolve( " less( 0 )", less( 0 ) );
Console.WriteLine();
}// Main
static void PrintListAndResolve( string operation, List<int> list )
{
Console.Write( "\n{0}: [", operation );
if ( list != null )
{
foreach ( int i in list )
{
Console.Write( " {0}", i );
}
}
Console.Write( " ] " );
int n = list == null ? 0 : list.Count;
if ( n == 0 )
{
Console.WriteLine( " no resolution" );
}
else
{
Console.Write( " resolved to: " );
if ( n == 1 )
{
Console.WriteLine( "{0}", list[ 0 ] );
}
else
{
int index = rnd.Next( 0, n - 1 );
Console.WriteLine( "{0}", list[ index ] );
}
}
}// PrintListAndResolve
修改后的 Main 函数的执行将产生如下结果。（由于使用了随机数生成器，结果会有所不同。）
less( 10 ): [ 9 8 7 6 5 4 3 2 1 0 ] resolved to: 4
less( 10 ): [ 9 8 7 6 5 4 3 2 1 0 ] resolved to: 1
less( 2 ): [ 1 0 ] resolved to: 1
less( 0 ): [ ] no resolution
Press any key to continue . . .
通过解析操作，amb 算子现在返回单个值。
可空 amb
amb 的可空版本接收多个参数并“模糊地”返回其中一个，即随机返回一个。该函数可以返回参数之一或 null，可以按如下方式实现：
public static IEnumerator<int?> amb( params int?[] args )
{
int n = args == null ? 0 : args.Length;
List<int> chosen = new List<int>();
//
// NOTE: The use of List {chosen} causes {amb} to return
// a distinct element from {args} every time it is
// called.
if ( n == 0 )
{
yield return null;
}
else
{
while ( chosen.Count < n )
{
int index = rnd.Next( 0, n );
if ( !chosen.Contains( index ) )
{
chosen.Add( index );
yield return args[ index ];
}
}
yield return null;
}
}// amb <int?>
然后可以使用以下两个函数来测试 amb 的可空版本。
static void TestNullableAmb( params int?[] args )
{
int n = args == null ? 0 : args.Length;
List<int?> arglist = args.ToList<int?>();
Console.WriteLine( "\nTestNullableAmb:\n" );
Console.Write( "amb( " );
if ( n > 0 )
{
for ( int i = 0; i < n; ++i )
{
Console.Write( "{0} ", NintToString( arglist[ i ] ) );
}
}
IEnumerator<int?> Amb = Fn.amb( args );
Amb.MoveNext();
Console.WriteLine( ") ==> {0}", NintToString( Amb.Current ) );
while ( Amb.MoveNext() )
{
Console.WriteLine( "amb() ==> {0}", NintToString( Amb.Current ) );
}
}// TestNullableAmb
static string NintToString( int? i ) // String representation of nullable {i}.
{
return i == null
? "null" : i.ToString();
}// NintToString
以下两张图显示了从多次调用函数 TestNullableAmb 获得的结果。同样，由于使用了随机数生成器，一般来说，结果会不同。
连续 amb
到目前为止实现的所有 amb 版本最终都会返回 null。为了准备讨论 amb 的一个非常有趣的应用，以下是两个永远不会返回 null 的连续 amb 版本：
/// <summary> Continuous version of {amb}.
///
/// This version of {amb} NEVER yields {null} if {n} is not zero.
///
/// </summary>
/// <param name="args">String parameters to be used.
/// </param>
/// <returns> A randomly-selected element of {args}.
/// </returns>
public static IEnumerator<string> amb2( params string[] args )
{
int n = args == null ? 0 : args.Length;
if ( n == 0 )
{
yield return null;
}
else
{
while ( true )
{
int index = rnd.Next( 0, n );
yield return args[ index ];
}
}
}// amb2 <string>
/// <summary> Refinement of {Fn.amb2}
///
/// This version of {amb} rotates the elements of its {args}
/// parameter after choosing one element at random to be
/// returned.
///
/// </summary>
/// <param name="args"> Array to operate upon.
/// </param>
/// <returns> A randomly-selected element of {args}.
/// </returns>
public static IEnumerator<string> amb3( params string[] args )
{
int n = args == null ? 0 : args.Length;
if ( n == 0 )
{
yield return null;
}
else
{
int index;
while ( true )
{
index = rnd.Next( 0, n );
RotateArgs( args, n );
yield return args[ index ];
}
}
}// amb3 <string>
/// <summary> Rotate left the elements of the {args} parameter.
/// </summary>
/// <param name="args"> The array to be operated upon.
/// </param>
/// <param name="n"> The length of the {args} parameter.
/// </param>
static void RotateArgs( string[] args, int n )
{
string _1stArg = args[ 0 ];
for ( int i = 0, j = 1; j < n; ++i, ++j )
{
args[ i ] = args[ j ];
}
args[ n - 1 ] = _1stArg;
}// RotateArgs
amb 在四色问题中的应用
至少在 1977 年，“四色问题（或猜想）一直是数学中最伟大的未解问题之一”（T.L. Saaty 和 P.C. Kainen，《四色问题：进攻与征服》，McGraw-Hill 1977，第 3 页）。该问题由 Francis Guthrie 大约在 167 年前提出，其陈述相当简单：给定任意地图，是否可以用最多四种颜色来着色，以便共享边界的国家（即邻国）不具有相同的颜色？1976 年，Wolfgang Haken 和 Kenneth Appel 找到了这个猜想的肯定答案，它花费了超过一千小时的计算机时间，也就是说，“证明”不是数学的。（参见 R. Wilson，《四色足够》，普林斯顿大学出版社 2014 年，第 3 页。）
以前的基于计算机的四色问题解决方案是用 Prolog（参见 L. Sterling 和 E Shapiro，《Prolog 的艺术》，MIT 出版社 1986 年，第 212-214 页、53 页和 114 页）和 Lisp 编程语言的 Scheme 方言（参见 D. Sitaram，“用 Fixnum 天自学 Scheme”，第 14.4.2 节）实现的。Prolog 程序是迭代的，而 Scheme 程序是递归的，并使用成功和失败的连续。两个程序都是非确定性的。回想一下，给定相同的输入，非确定性程序在不同运行中会产生不同的结果。结果可能在两次或多次运行中相同，但总的来说，预期结果应该不同。
在本节中，amb 算子将用于通过一个非确定性的 C# 函数来解决四色问题，该函数用于对西欧国家进行着色。该函数将不依赖于回溯。凭空想象，C# 代码将以自顶向下的方式开发。包含 Program.cs、Country.cs 和 Fn.cs 文件的完整代码在附带的 ZIP 文件中。
从现在开始，将展示的代码假定位于控制台应用程序的 AmbiguousFunctions 命名空间中。首先，必须有一种方法来表示国家及其相关信息。一个国家将拥有一个名称、一种颜色、一个关于四种颜色的颜色数组的 amb 算子实例、一组邻居以及一组邻居的颜色。请注意，amb 算子的使用使得颜色分配成为非确定性的。
static string[] colors = { "red", "yellow", "blue", "white" }; // In file Program.cs.
public class Country // In file Country.cs.
{
public string Name;
public string Color;
private IEnumerator<string> Amb; // {amb} generator.
private HashSet<Country> neighbors;
private HashSet<string> neighborsColors;
public Country( string name, params string[] colors )
{
Name = name;
Amb = Fn.amb3( colors ); // In file Fn.cs.
Amb.MoveNext();
Color = Amb.Current;
neighbors = new HashSet<Country>();
neighborsColors = new HashSet<string>();
}// Country (constructor)
}
country 的 string 表示形式由其 name 和 color 组成。
public override string ToString()
{
return String.Format( "{0,12}: {1} ",
Name,
Color == String.Empty ? "null" : Color );
}// ToString
一旦创建了所有国家（实例化），就可以填充它们的邻居数据成员。
public void SetNeighbors( params Country[] countries )
{
foreach ( Country country in countries )
{
neighbors.Add( country );
}
}// SetNeighbors
一个 country 第一次被分配 color（在 Country 类实例化时），或者在填充了其邻居的 color 组成的 neighborsColors 数据成员之后，它的 color 可以被重新分配。
public bool AddToNeighborsColors( params Country[] countries )
{
foreach ( Country country in countries )
{
neighborsColors.Add( country.Color );
}
// If necessary, attempt to change the color of {this} country.
return this.AssignColor();
}// AddToNeighborsColors
public bool AssignColor()
{
bool assigned = false;
int i = 0;
do
{
Amb.MoveNext();
++i;
if ( Amb.Current != Color )
{
Color = Amb.Current;
}
} while ( neighborsColors.Contains( Color ) && i < 4 );
if ( i < 4 ) // All the colors have not been attempted.
{
assigned = true;
}
return assigned;
}// AssignColor
Country 类的最后一个函数成员生成一个包含国家邻居的 name 和 color 的 string。
public string NeighborsColorsToString()
{
StringBuilder sb = new StringBuilder();
int i = 0;
sb.Append( "\n\t\t " );
foreach ( Country neighbor in neighbors )
{
sb.Append( String.Format( " [{0}: {1}]", neighbor.Name, neighbor.Color ) );
++i;
if ( i > 2 )
{
sb.Append( "\n\t\t " );
i = 0;
}
}
sb.Append( "\n" );
return sb.ToString();
}// NeighborsColorsToString
有了 Country 类的功能到位，Program.cs 中的代码现在可以开发了。Main 函数创建随机数生成器类的实例，并通过调用函数 ColorWesternEurope 来启动地图着色过程。
static Random rnd;
static void Main( string[] args )
{
rnd = new Random();
ColorWesternEurope();
Console.WriteLine();
}// Main
static void ColorWesternEurope()
{
Console.WriteLine( "\nColorWesternEurope:\n" );
CreateCountries();
SetNeighbors();
ShowColors();
FillNeighborsColors();
ShowCountriesAndNeighbors();
}// ColorWesternEurope
static void CreateCountries()
{
portugal = Countries[ (int)CountryEnum.Portugal ]
= new Country( "Portugal", colors );
spain = Countries[ (int)CountryEnum.Spain ]
= new Country( "Spain", colors );
france = Countries[ (int)CountryEnum.France ]
= new Country( "France", colors );
belgium = Countries[ (int)CountryEnum.Belgium ]
= new Country( "Belgium", colors );
holland = Countries[ (int)CountryEnum.Holland ]
= new Country( "Holland", colors );
germany = Countries[ (int)CountryEnum.Germany ]
= new Country( "Germany", colors );
luxembourg = Countries[ (int)CountryEnum.Luxembourg ]
= new Country( "Luxembourg", colors );
italy = Countries[ (int)CountryEnum.Italy ]
= new Country( "Italy", colors );
switzerland = Countries[ (int)CountryEnum.Switzerland ]
= new Country( "Switzerland", colors );
austria = Countries[ (int)CountryEnum.Austria ]
= new Country( "Austria", colors );
}// CreateCountries
一旦实例化了西欧国家，就填充了它们的邻居数据成员，并显示了初始颜色分配。
static void SetNeighbors()
{
portugal.SetNeighbors( spain );
spain.SetNeighbors( france, portugal );
france.SetNeighbors( spain, italy, switzerland,
belgium, germany, luxembourg );
belgium.SetNeighbors( france, holland, luxembourg, germany );
holland.SetNeighbors( belgium, germany );
germany.SetNeighbors( france, austria, switzerland, holland,
belgium, luxembourg );
luxembourg.SetNeighbors( france, belgium, germany );
italy.SetNeighbors( france, austria, switzerland );
switzerland.SetNeighbors( france, italy, austria, germany );
austria.SetNeighbors( italy, switzerland, germany );
}// SetNeighbors
static void ShowColors()
{
Console.WriteLine( "Initial colors:\n" );
foreach ( CountryEnum country in Enum.GetValues( typeof( CountryEnum ) ) )
{
Console.WriteLine( Countries[ (int)country ].ToString() );
}
Console.WriteLine();
}// ShowColors
接下来是填充每个 country 的 neighborsColors 数据成员的任务。完成后，如果需要，将重新分配每个 country 的 color。如果无法重新分配 country 的 color，则会显示失败消息。
static void FillNeighborsColors()
{
Console.WriteLine( "\nFillNeighborsColors:\n" );
if ( !portugal.AddToNeighborsColors( spain ) )
{
Failure( portugal );
}
if ( !spain.AddToNeighborsColors( france, portugal ) )
{
Failure( spain );
}
if ( !france.AddToNeighborsColors( spain, italy, switzerland,
belgium, germany, luxembourg ) )
{
Failure( france );
}
if ( !belgium.AddToNeighborsColors( france, holland, luxembourg, germany ) )
{
Failure( belgium );
}
if ( !holland.AddToNeighborsColors( belgium, germany ) )
{
Failure( holland );
}
if ( !germany.AddToNeighborsColors( france, austria, switzerland, holland,
belgium, luxembourg ) )
{
Failure( germany );
}
if ( !luxembourg.AddToNeighborsColors( france, belgium, germany ) )
{
Failure( luxembourg );
}
if ( !italy.AddToNeighborsColors( france, austria, switzerland ) )
{
Failure( italy );
}
if ( !switzerland.AddToNeighborsColors( france, italy, austria, germany ) )
{
Failure( switzerland );
}
if ( !austria.AddToNeighborsColors( italy, switzerland, germany ) )
{
Failure( austria );
}
}// FillNeighborsColors
static void Failure( Country country )
{
Console.WriteLine( "Failure: a color could not be re-assigned to {0}", country.Name );
}// Failure
最后一步是显示每个 country 的 name 和 color，以及用方括号括起来的邻居的 name 和 color。
static void ShowCountriesAndNeighbors()
{
Console.WriteLine( "\nReport colors:\n" );
foreach ( CountryEnum country in Enum.GetValues( typeof( CountryEnum ) ) )
{
int iCountry = (int)country;
Console.Write( Countries[ iCountry ].ToString() );
Console.WriteLine( Countries[ iCountry ].NeighborsColorsToString() );
}
}// ShowCountriesAndNeighbors
ColorWesterEurope 函数的示例执行
由于 ColorWesternEurope 函数不依赖于回溯或连续，它大多数时候都会在着色地图时失败。但是，在某些运行中，它确实成功地解决了四色问题。下面的示例输出显示了两次成功的着色（在附带的 ZIP 文件中为 _out 020 _success.txt 和 _out 028 success.txt）和一次失败的着色（文件 _out 027 failures.txt）。输出已编辑，仅用于删除多余的空行。
_out 020 success.txt
ColorWesternEurope:
Initial colors:
Portugal: white
Spain: blue
France: red
Belgium: blue
Holland: red
Germany: blue
Luxembourg: blue
Italy: blue
Switzerland: blue
Austria: blue
FillNeighborsColors:
Report colors:
Portugal: white
[Spain: yellow]
Spain: yellow
[France: red] [Portugal: white]
France: red
[Spain: yellow] [Italy: yellow] [Switzerland: white]
[Belgium: white] [Germany: yellow] [Luxembourg: blue]
Belgium: white
[France: red] [Holland: red] [Luxembourg: blue]
[Germany: yellow]
Holland: red
[Belgium: white] [Germany: yellow]
Germany: yellow
[France: red] [Austria: red] [Switzerland: white]
[Holland: red] [Belgium: white] [Luxembourg: blue]
Luxembourg: blue
[France: red] [Belgium: white] [Germany: yellow]
Italy: yellow
[France: red] [Austria: red] [Switzerland: white]
Switzerland: white
[France: red] [Italy: yellow] [Austria: red]
[Germany: yellow]
Austria: red
[Italy: yellow] [Switzerland: white] [Germany: yellow]
Press any key to continue . . .
_out 028 success.txt
ColorWesternEurope:
Initial colors:
Portugal: red
Spain: blue
France: red
Belgium: yellow
Holland: red
Germany: white
Luxembourg: white
Italy: blue
Switzerland: white
Austria: red
FillNeighborsColors:
Report colors:
Portugal: yellow
[Spain: blue]
Spain: blue
[France: red] [Portugal: yellow]
France: red
[Spain: blue] [Italy: blue] [Switzerland: yellow]
[Belgium: yellow] [Germany: blue] [Luxembourg: white]
Belgium: yellow
[France: red] [Holland: red] [Luxembourg: white]
[Germany: blue]
Holland: red
[Belgium: yellow] [Germany: blue]
Germany: blue
[France: red] [Austria: red] [Switzerland: yellow]
[Holland: red] [Belgium: yellow] [Luxembourg: white]
Luxembourg: white
[France: red] [Belgium: yellow] [Germany: blue]
Italy: blue
[France: red] [Austria: red] [Switzerland: yellow]
Switzerland: yellow
[France: red] [Italy: blue] [Austria: red]
[Germany: blue]
Austria: red
[Italy: blue] [Switzerland: yellow] [Germany: blue]
Press any key to continue . . .
_out 027 failures.txt
ColorWesternEurope:
Initial colors:
Portugal: red
Spain: red
France: yellow
Belgium: red
Holland: white
Germany: red
Luxembourg: yellow
Italy: white
Switzerland: red
Austria: white
FillNeighborsColors:
Failure: a color could not be re-assigned to Belgium
Failure: a color could not be re-assigned to Holland
Failure: a color could not be re-assigned to Germany
Report colors:
Portugal: blue
[Spain: white]
Spain: white
[France: blue] [Portugal: blue]
France: blue
[Spain: white] [Italy: yellow] [Switzerland: red]
[Belgium: white] [Germany: blue] [Luxembourg: yellow]
Belgium: white
[France: blue] [Holland: white] [Luxembourg: yellow]
[Germany: blue]
Holland: white
[Belgium: white] [Germany: blue]
Germany: blue
[France: blue] [Austria: white] [Switzerland: red]
[Holland: white] [Belgium: white] [Luxembourg: yellow]
Luxembourg: yellow
[France: blue] [Belgium: white] [Germany: blue]
Italy: yellow
[France: blue] [Austria: white] [Switzerland: red]
Switzerland: red
[France: blue] [Italy: yellow] [Austria: white]
[Germany: blue]
Austria: white
[Italy: yellow] [Switzerland: red] [Germany: blue]
Press any key to continue . . .
结论
本文介绍了 John McCarthy 的模糊（amb）算符的各种版本的实现，以及它在实现一个非确定性函数以解决西欧国家四色问题中的应用。正如所见，代码确实是非确定性的，因为成功的着色是不同的。
Using the Code
本文介绍的所有代码都在附带的 ZIP 文件中。有三个 C# 文件：Program.cs、Country.cs 和 Fn.cs，以及五个文本文件中的示例输出。创建一个名为 AmbiguousFunctions 的 Visual Studio 控制台应用程序。用 Program.cs 文件中的 Program 类替换它。右键单击项目名称，添加一个新项，一个名为 Country 的类。用文件 Country.cs 中的代码替换类定义。对另一个新项，一个名为 Fn 的类执行相同的操作，并用文件 Fn.cs 中的代码替换类定义。生成解决方案并开始调试。
历史
- 2021 年 2 月 3 日：初始版本