C# 和 F# 中的计算类型
4.91/5 (17投票s)
探索 C# 和 F# 中的计算类型概念。
介绍
在本文中，我将探讨“计算类型”的概念——与计算相关联的类型，并且可以通过反射来确定其计算，从而基于类型进行自我文档化和自动化值计算。我将演示如何在 C# 和 F# 语言中处理计算类型。
类型系统
类型系统将一个类型与每个计算值相关联。通过检查这些值的流，类型系统试图确保或证明不会发生类型错误。具体的类型系统决定了什么构成类型错误，但总的来说，其目的是防止将预期某种类型值的操作用于不适合该操作的值（逻辑错误）；内存错误也将被防止。类型系统通常作为编程语言的一部分来指定，并内置于它们的解释器和编译器中；尽管它们也可以作为可选工具来实现。1
上述引用的关键部分是第一句话：“类型系统将一个类型与每个计算值相关联。” 在本文中，我将探讨这样一个概念，即不仅类型与计算值相关联，而且该值的计算本身也由类型决定，我将在 C# 和 F# 代码中演示这一概念。
基本类型
基本类型（int、double、bool 等）提供的规范不足以推导出最基本的计算/验证之外的任何内容。例如，在数据库中，大多数验证都需要额外的字段，如外键关系、长度、模式匹配和触发器，这些字段进一步定义了要在基本类型上执行的验证。数据库中的计算由 SQL 表达式、PL/SQL 代码或客户端/服务器端自定义代码处理，所有这些都求值为基本类型或基本类型集合（表）。
高阶类型：类和结构
虽然我们几乎总是以面向对象的范例进行工作，但我们很少为类中的离散字段创建独立的（非基本）类型。这会降低程序的类型安全性。与基本类型过于紧密地工作带来的另一个问题是，负责类型计算/验证的代码难以查找、扩展和测试。稍后将对此主题进行更详细的讨论。
此外，由于类和结构通常用于封装“对象”的整个概念，因此它们通常不被视为提供精确类型规范的机制。例如，您可能会看到如下内容：
public class FullName
{
public string FirstName {get; set;}
public string LastName {get; set;}
}
但很少会看到这样：
public class FullName
{
public TFirstName FirstName {get; set;}
public TLastName LastName {get; set;}
}
其中 TFirstName 和 TLastName 是包装字符串值的简单特定于类型的实现。显然，后一种方法增加了复杂性，牺牲了类型安全性和可计算性以换取更简单的语法。
丘奇类型论
类型论也被称为高阶逻辑，因为它们不仅允许对个体变量进行量化（如在一阶逻辑中），还允许对函数、谓词甚至高阶变量进行量化。类型论特征性地为实体分配类型，例如区分数字、数字集合、从数字到数字集合的函数以及此类函数的集合……这些区分允许人们讨论集合和函数的概念上丰富的世界，而不会遇到朴素集合论的悖论。2
通过使用唯一的类型区分值（数字、字符串等），程序可以更轻松地以完全类型安全的方式表达对这些唯一类型进行操作的函数。此外，程序检查（通过反射自动化）可以构建一个操作离散类型的函数的字典。例如，这个函数（有意模糊化）
string X(string s1, string s2);
除了告诉程序员方法 X 接受两个字符串并返回一个字符串外，别无其他信息。反之：
TFullname X(TFirstName s1, TLastName s2);
告诉程序员方法 X 接受两种类型 TFirstName 和 TLastName，并返回一个 TFullName 类型。即使方法名和变量名被模糊化，这仍然更具描述性。此外，通过反射，程序员可以询问：
- 所有使用类型 T 的函数有哪些？
- 所有计算类型 Q 的函数有哪些？
这开始接近上面引用的内容，即允许“人们讨论集合和函数的概念上丰富的世界”。
计算类型论
计算类型论的一个显著特点是它已被公开实现并用于完成艰巨的工作，尤其是在计算机科学领域。这是什么意思？要说一个逻辑理论已被公开实现，意味着已经完成了以下工作：(1) 该理论的每个细节都被编程，创建了一个软件系统（被称为各种名称，如：定理证明器、证明器、证明助手、证明检查器、证明开发系统、逻辑编程环境、逻辑引擎）。(2) 许多人使用该系统查找、检查和发布了数百个证明。(3) 关于形式理论、其系统以及如何使用它的文章和书籍被发表。这种极端的理论形式化仅在 20 世纪才成为可能，并且随着这些理论的推进计算机辅助思维，在 21 世纪将变得普遍。
使用已实现的计算类型论（CTT）完成的科学工作包括寻找新算法、构建“正确构造”的软件系统、解决数学和计算理论中的开放问题、为现代编程语言（包括模块、依赖记录和对象）和自然语言提供形式语义、自动化验证和解释协议、算法和系统所需的许多任务，以及创建基于完全形式化和计算机检查的关键计算概念的课程。3
考虑一下这段引文的含义——计算类型论的形式化“在 21 世纪将变得普遍”。虽然有关于类型论、形式方法、定理证明器等的丰富信息，但到目前为止，这些主要属于数学家和晦涩的函数式编程环境（如 Coq10）的领域。甚至微软也在研究可验证的安全程序构建和证明（使用 F*11）。目前，这项工作主要应用于提高安全性并创建可证明正确的算法。我个人认为，计算类型是改进代码质量、准确性和可维护性的一个丰富领域（即使这些流行语在过去 30 年里已经变得陈旧）。本文的目的是以一种希望简单易懂的方式介绍这些概念。
依赖类型
在计算机科学和逻辑学中，依赖类型是一种依赖于值的类型。依赖类型在直觉类型论和 ATS、Agda 和 Epigram 等函数式编程语言的设计中起着核心作用。
一个例子是实数 n 元组的类型。这是一个依赖类型，因为类型取决于值 n。
在程序中判断依赖类型的相等性可能需要计算。如果允许在依赖类型中使用任意值，那么判断类型相等性可能需要判断两个任意程序是否产生相同的结果；因此，类型检查可能变得不可判定。
Curry–Howard 对应关系意味着可以构造表达任意复杂数学属性的类型。如果用户可以提供一个构造性证明，证明一个类型是“可居住的”（即，该类型的值存在），那么编译器可以检查证明，并将其转换为可执行的计算机代码，通过执行构造来计算该值。证明检查功能使依赖类型语言与证明助手密切相关。代码生成方面为形式程序验证和证明携带代码提供了一种强大的方法，因为代码直接源自经过机械验证的数学证明。12
依赖类型的概念超出了本文的范围，但我在此提及它是因为它为计算类型的概念增加了一个特殊的细微差别——类型本身依赖于值。然而，考虑一个简单的情况，我们有一个地址表和一个指示地址是邮政信箱、住宅街道还是商业地址的查找字段。实例化的类型取决于查找字段的值。或者，一个更简单的例子，考虑一个具有可能值 2、.33333 或 3.1415 的字段。在这里，我们可能会根据值分别实例化“整数”、“有理数”或“无理数”类型。
定义问题：类型与实例
另一种陈述类型与实例问题的方法是“类与对象”。类当然是类型，对象是类的实例。但是，无论术语如何，问题是：我们如何执行基于类型的计算？显然，计算必须在值上执行，但计算的规范是由类型决定的吗？可以说算。虽然这看起来像是一个直接的“带成员函数的类型”解决方案，但让我们更仔细地看看。
一个简单的例子：计算全名
假设我们有这三种类型：
- FirstName，实例为“Marc”
- LastName，实例为“Clifton”
- FullName，一个计算类型，其结果为“Clifton, Marc”
更抽象地表述：
- 我们有一个计算类型规范，它操作于另外两种类型的实例。计算的结果应该是计算类型的实例。
具体来说：
- 给定 FirstName 和 LastName 类型的实例，计算类型 FullName 应该是 LastName 和 FirstName 的连接，中间用“ , ”分隔。（当然，这只适用于某些社会。）
起初这似乎很简单：
public class FullName
{
public string Compute(string firstName, string lastName)
{ return lastName + ", " + firstName; }
}
这里的问题是，我们必须首先实例化 FullName 才能执行计算：
FullName fn = new FullName();
string fullName = fn.Compute("Marc", "Clifton");
使用静态方法可以稍微改善问题：
public static class FullName
{
static string Compute(string firstName, string lastName)
{ return lastName + ", " + firstName; }
}
string fullName = FullName.Compute("Marc", "Clifton");
但我们仍然面临几个问题：
- 计算返回的是基本类型，而不是所需的 FullName 类型。
- 计算的参数是字符串，而不是 FirstName 和 LastName 类型。
由于这些是基本类型，因此我们没有类型检查来确保程序员不会弄错名字的顺序（姓和名）。
string fullName = FullName.Compute("Clifton", "Marc");
类型与实例：问题总结
上述讨论可归结为四个问题：
- 我们有一个计算类型，并且该类型的计算应返回该类型的一个实例。
- 我们希望精确指定计算操作的参数类型，以避免不正确的计算。
- 我们需要某种方式将计算类型与其计算函数关联起来。
- 我们需要以某种方式关联这样一个事实：给定 LastName 和 FirstName 的实例，我们实际上可以计算 FullName。
我们将着手解决这些问题，首先是如何精确地定义类型。
精确定义类型
我们精确定义 FirstName、LastName 和 FullName 类型的第一个想法可能是尝试在 C# 中这样做：
public class FirstName : String {}
这当然会因“无法从密封类型 'string' 派生”而失败。
在 F# 中，我们可能会尝试这样做：
type FirstName = string
这是无用的，因为“类型缩写在 .NET Framework MSIL 代码中不保留。因此，当您从其他 .NET Framework 语言使用 F# 程序集时，必须使用类型缩写的底层类型名称。”4 因此，它实际上没有提供可用的类型规范。
C# 示例
这使我们在 C# 中得到以下形式：
public class FirstName
{
public string Value { get; set; }
}
public class LastName
{
public string Value { get; set; }
}
public class FullName
{
public string Value { get; set; }
}
static FullName ComputeFullName(FirstName fn, LastName ln)
{
return new FullName() { Value = ln.Value + ", " + fn.Value };
}
F# 示例
在 F# 中，可以使用记录来实现这些类型：
type typeFirstName =
{
FirstName : string;
}
type typeLastName =
{
LastName : string;
}
type typeFullName =
{
FullName : string;
}
let ComputeFullName fn ls =
{FullName = ls.LastName + ", " + fn.FirstName}
请注意区别——在 C# 代码中，我们可以使用每个类中的“Value”属性。在 F# 代码中，由于类型是推断的，记录的标签必须是唯一的。
关于函数式编程语言中类型推断的说明
未能使用唯一的标签会导致类型推断混乱，并浪费了大量时间，至少是这个开发人员的时间！而且，考虑到在 F#（以及 OCaml 等其他函数式编程语言）中，类型推断不会查看整个记录实例来确定类型，因此第一个标签与其他记录中的所有标签不同非常重要。否则，类型推断很可能会导致错误的类型。
在 F# Interactive (fsi) 中，我们可以检查 ComputeFullName 的类型，观察到该函数接受 FirstName 和 LastName 类型作为输入并返回 FullName 类型。
val ComputeFullName : typeFirstName -> typeLastName -> typeFullName
在 C# 方法中，这是“通过检查显而易见”的：
static FullName Compute(FirstName fn, LastName ln)
调用计算
在 C# 中，我们可以通过类似这样的方式调用我们的计算：
static void Main(string[] args)
{
FirstName fn = new FirstName() { Value = "Marc" };
LastName ln = new LastName() { Value = "Clifton" };
FullName name = ComputeFullName(fn, ln);
Console.WriteLine(name.Value);
}
以及在 F# 中：
let fn = {FirstName = "Marc"}
let ln = {LastName = "Clifton"}
let result = ComputeFullName fn ln
printfn "%s" result.FullName
关于柯里化
柯里化是函数式编程语言的一项功能，它允许您定义偏函数。例如：
let fn = {FirstName = "Marc"}
let ln = {LastName = "Clifton"}
let partialResult = ComputeFullName fn
let fullResult = partialResult ln
printfn "%s" fullResult.FullName
考虑柯里化的重要性是因为，虽然可以指定函数参数类型，但应尽可能避免这样做。指定函数参数类型会导致编译器将参数列表视为一个元组，从而禁用柯里化。5
例如：
let ComputeFullName(fn : typeFirstName, ls : typeLastName) =
{FullName = ls.LastName + ", " + fn.FirstName}
let fn = {FirstName = "Marc"}
let ln = {LastName = "Clifton"}
let result = ComputeFullName(fn, ln)
let partialResult = ComputeFullName(fn)
在最后一个语句中会导致编译器错误：
This expression was expected to have type typeFirstName * typeLastName but here has type typeFirstName
请注意，编译器现在期望一个元组 typeFirstName * typeLastName 作为参数列表，这会禁用柯里化。这是不可取的，因为柯里化是函数式编程的重要组成部分。
正如 Matt Newport 在本文的评论中指出的那样，这种语法允许指定参数类型并仍然保留柯里化能力：
let Add (a:float) (b:float) = a + b let AddPartial = Add 1.0 printfn "%f" (AddPartial 2.0)
因此，我们避免使用元组参数，但仍然支持柯里化。个人而言，我发现我没有在任何搜索中找到指定参数类型的示例，这有点奇怪。
关于柯里化的说明
在数学和计算机科学中，柯里化是一种将接受多个参数（或 n 元组参数）的函数转换为可以作为一系列每个参数只有一个参数的函数（偏应用）进行调用的技术。它由 Moses Schönfinkel[1] 发现，后来被 Haskell Curry 重新发现。7
诚然，维基百科不应被视为该主题的权威，但我对“发现”一词感到不安，因为它暗示这并非有意为之的功能，而是“发现”的副产品。因此，既然不是故意的，也许对柯里化的强调有点过头了。Patrick Hurst 在评论 Haskell 时写道，“此外，没有柯里化，您将无法获得可变参数函数。”8 可变参数函数是可以接受可变数量参数的函数，这在命令式编程语言中很容易支持，例如 C# 的 params 关键字。
在 Haskell 中，每个函数接受一个参数。一个多参数函数（例如 map，它将一个函数应用于列表中的每个元素）实际上只有一个参数；例如，map 可以被解释为接受一个函数和一个列表并返回一个列表，或者接受一个函数并返回一个函数，该函数接受一个列表并返回一个列表……这个将多参数函数转换为一系列单参数函数的过程称为柯里化……以这种方式对函数进行部分应用参数的过程称为“偏应用”，但也称为柯里化。8
关于重载函数/方法
允许程序员以任何顺序指定名字和姓氏将非常有用。在 C# 中，我们可以轻松实现这一点：
static FullName Compute(FirstName fn, LastName ln)
{
return new FullName() { Value = ln.Value + ", " + fn.Value };
}
static FullName Compute(LastName ln, FirstName fn)
{
return new FullName() { Value = ln.Value + ", " + fn.Value };
}
不幸的是，在 F# 中，我们不能。这个：
let ComputeFullName fn ls =
{FullName = ls.LastName + ", " + fn.FirstName}
let ComputeFullName ls fn =
{FullName = ls.LastName + ", " + fn.FirstName}
会导致编译器错误：值“ComputeFullName”的重复定义。Don Syme 写道：
非正式重载未限定函数名在 F# 的设计中被考虑过。然而，我们基于软件工程的理由拒绝了它。
正如您所理解的，非正式重载可能是优点也是缺点。在 C# 和 .NET 中，重载相对“驯服”，主要是因为所有对重载集的引用都通过类型名称（例如 C.M，而不是仅仅 M）来限定（除了在 C 的主体中，这有点不同）。在 F# 中，我们选择遵循类似的方法：允许方法重载，但确保对重载项的引用由（类型）名称限定。我们预计这种限制将继续下去。6
然而，此实现作为成员函数会失败：
type typeFullName =
{
FullName : string;
}
static member Compute fn ls =
{FullName = ls.LastName + ", " + fn.FirstName}
static member Compute ls fn =
{FullName = ls.LastName + ", " + fn.FirstName}
导致错误该方法“Compute”具有柯里化参数，但名称与其他方法在此类型中相同。具有柯里化参数的方法不能重载。请考虑使用接受元组参数的方法。
关于函数重载的说明
因此，我们面临同样的问题——重载函数。
- 必须实现为成员函数。
- 必须为参数使用元组形式。
因此会禁用柯里化，而柯里化被认为是函数式编程的一个有用特性。这似乎会限制 F# 的可用性。如果“重载通常是类型推断语言的弊端（至少当类型系统不如 F# 强大到可以包含类型类时）”9，并且特别是，如果重载函数必须使用元组参数实现，从而禁用柯里化，那么这就施加了一个限制，降低了语言的可用性。相反，F# 中存在元组参数（和成员函数）的整个原因是为了与其他 .NET 语言兼容。就其本身而言，拥有唯一命名的函数而不是依赖函数重载可以被视为一件好事，可以提高代码的可读性。
到目前为止我们取得了什么成就？
至此，我们基本上解决了前面确定的四个问题。
- 我们使用 C# 类或 F# 记录精确地指定了我们的类型。
- 这允许我们在这些精确类型上创建方法/函数（计算），从而极大地提高了类型安全性。
- 返回类型是对导致所需类型的计算的精确规范。
- 如果我们使用反射来检查返回类型，我们可以确定导致特定类型的*所有*可能的计算。因此，我们可以创建一个“类型计算”字典。
现在我们需要一些“胶水”来将这些部分组合在一起，即确定给定一组实例和所需的输出类型可以执行哪些计算。这让我想起我为 Code Project 写的的第一篇文章，“有机编程环境”，我在其中写道：
处理函数将自己注册到 D-Pool Manager (DPM)，指示它们操作的数据以及它们产生的数据。
更好的说法是：
创建一个计算字典，它定义输入类型和结果输出类型。给定一组实例化的类型，我们可以确定导致所需输出类型的计算。
接下来我们将看看如何将这些部分组合在一起。
一个更有趣的例子：邮政编码上的计算
为了演示到目前为止所描述的概念，让我们看一个常见的数据类型，即邮政编码。我们将使用几个 Web 服务来指定邮政编码上的以下计算：
- 根据邮政编码查找城市和州
- 根据邮政编码查找预期的最低和最高温度
定义类型
首先，我们需要一些具体类型。
C#
public class TZipCode
{
public string ZipCode { get; set; }
public override string ToString() { return ZipCode; }
}
public class TMinTemp
{
public double MinTemp { get; set; }
public override string ToString() { return MinTemp.ToString(); }
}
public class TMaxTemp
{
public double MaxTemp { get; set; }
public override string ToString() { return MaxTemp.ToString(); }
}
public class TMinMaxTemp
{
public TMinTemp MinTemp { get; set; }
public TMaxTemp MaxTemp { get; set; }
public override string ToString() { return "(" + MinTemp.ToString() + ", " + MaxTemp.ToString() + ")"; }
}
public class TCity
{
public string City { get; set; }
public override string ToString() { return City; }
}
public class TState
{
public string State { get; set; }
public override string ToString() { return State; }
}
public class Location
{
public TCity City { get; set; }
public TState State { get; set; }
public override string ToString() { return "(" + City.ToString() + ", " + State.ToString() + ")"; }
}
在上面的代码中，请注意我还为 City 和 State 创建了显式类型。我们将在下一步看到原因。F#
type TZipCode =
{
ZipCode : string;
}
override this.ToString() = this.ZipCode
type TMinTemp =
{
MinTemp : double;
}
override this.ToString() = this.MinTemp.ToString()
type TMaxTemp =
{
MaxTemp : double;
}
override this.ToString() = this.MaxTemp.ToString()
type TMinMaxTemp =
{
// note the unique label, which helps type inference.
AMinTemp : TMinTemp;
AMaxTemp : TMaxTemp;
}
override this.ToString() = "(" + this.AMinTemp.MinTemp.ToString() + ", " + this.AMaxTemp.MaxTemp.ToString() + ")"
type TCity =
{
City : string;
}
override this.ToString() = this.City
type TState =
{
State : string;
}
override this.ToString() = this.State
type Location =
{
// note the unique label, which helps type inference.
ACity : TCity;
AState : TState;
}
override this.ToString() = "(" + this.ACity.City + ", " + this.AState.State + ")"
定义计算
接下来，我们定义计算。
C#
public static TMinMaxTemp ComputeMinMaxTemp(TZipCode zipCode)
{
double minTemp;
double maxTemp;
AcquireMinMaxTemp(zipCode.ZipCode, out minTemp, out maxTemp);
return new TMinMaxTemp()
{
MinTemp = new TMinTemp() { MinTemp = minTemp },
MaxTemp = new TMaxTemp() { MaxTemp = maxTemp }
};
}
public static TMinTemp ComputeMinTemp(TMinMaxTemp temp)
{
return temp.MinTemp;
}
public static TMaxTemp ComputeMaxTemp(TMinMaxTemp temp)
{
return temp.MaxTemp;
}
public static TLocation ComputeLocation(TZipCode zipCode)
{
string city;
string state;
AcquireLocation(zipCode.ZipCode, out city, out state);
return new TLocation()
{
City = new TCity() { City = city },
State = new TState() { State = state }
};
}
public static TCity ComputeCity(TLocation location)
{
return location.City;
}
public static TState ComputeState(TLocation location)
{
return location.State;
}
private static void AcquireMinMaxTemp(string zipCode, out double minTemp, out double maxTemp)
{
ndfdXML weather = new ndfdXML();
string latLonXml = weather.LatLonListZipCode(zipCode);
XDocument xdoc = XDocument.Parse(latLonXml);
string[] latLon = xdoc.Element("dwml").Element("latLonList").Value.Split(',');
decimal lat = Convert.ToDecimal(latLon[0]);
decimal lon = Convert.ToDecimal(latLon[1]);
string weatherXml = weather.NDFDgenByDay(lat, lon, DateTime.Now, "1", "e", "24 hourly");
xdoc = XDocument.Parse(weatherXml);
minTemp = Convert.ToDouble(xdoc.Element("dwml").Element("data").Element("parameters").Elements("temperature").
Where(el => el.Attribute("type").Value == "minimum").
Single().Element("value").Value.Trim());
maxTemp = Convert.ToDouble(xdoc.Element("dwml").Element("data").Element("parameters").Elements("temperature").
Where(el => el.Attribute("type").Value == "maximum").
Single().Element("value").Value.Trim());
}
private static void AcquireLocation(string zipCode, out string city, out string state)
{
USZip zip = new USZip();
XmlNode node = zip.GetInfoByZIP(zipCode);
XDocument xdoc = XDocument.Parse(node.InnerXml);
city = xdoc.Element("Table").Element("CITY").Value;
state = xdoc.Element("Table").Element("STATE").Value;
}
在上面的代码中，ComputeMinMaxTemp 和 ComputeLocation 中的基本类型在内部用于与 Web 服务交互。同样，在“Acquire...”方法中使用（目前只是存根）的基本类型严格用于与 Web 服务交互，并不打算被定义计算的库的消费者直接调用。这由静态方法的 public 和 private 访问限定符强制执行。
F#
// Refer to http://codebetter.com/matthewpodwysocki/2009/06/11/f-duck-typing-and-structural-typing/
let inline implicit arg =
( ^a : (static member op_Implicit : ^b -> ^a) arg)
let (!!) : string -> XName = implicit
// Webservice Support:
let AcquireMinMaxTemp zipCode =
let weather = new ndfdXML();
let latLonXml = weather.LatLonListZipCode(zipCode)
let xdoc = XDocument.Parse(latLonXml)
let latLon = xdoc.Element(!!"dwml").Element(!!"latLonList").Value.Split(',');
let lat = Convert.ToDecimal(latLon.[0]);
let lon = Convert.ToDecimal(latLon.[1]);
let weatherXml = weather.NDFDgenByDay(lat, lon, DateTime.Now, "1", "e", "24 hourly");
let xdoc = XDocument.Parse(weatherXml);
let minTemp = Convert.ToDouble(xdoc.Element(!!"dwml").Element(!!"data").Element(!!"parameters").Elements(!!"temperature").Where(fun el -> (el : XElement).Attribute(!!"type").Value = "minimum").Single().Element(!!"value").Value.Trim())
let maxTemp = Convert.ToDouble(xdoc.Element(!!"dwml").Element(!!"data").Element(!!"parameters").Elements(!!"temperature").Where(fun el -> (el : XElement).Attribute(!!"type").Value = "maximum").Single().Element(!!"value").Value.Trim())
(minTemp, maxTemp)
let AcquireLocation zipCode =
let zip = new USZip()
let node = zip.GetInfoByZIP(zipCode)
let xdoc = XDocument.Parse(node.InnerXml)
let city = xdoc.Element(!!"Table").Element(!!"CITY").Value
let state = xdoc.Element(!!"Table").Element(!!"STATE").Value
(city, state)
// Computations:
let ComputeMinMaxTemp zipCode =
let minMaxTemp = AcquireMinMaxTemp zipCode.ZipCode
{
AMinTemp = {MinTemp = fst(minMaxTemp) }
AMaxTemp = {MaxTemp = snd(minMaxTemp) }
}
let ComputeMinTemp minMaxTemp = {MinTemp = minMaxTemp.AMinTemp.MinTemp}
let ComputeMaxTemp minMaxTemp = {MaxTemp = minMaxTemp.AMaxTemp.MaxTemp}
let ComputeCity location = {City = location.ACity.City}
let ComputeState location = {State = location.AState.State}
let ComputeLocation zipCode =
let location = AcquireLocation zipCode.ZipCode
{
ACity = {City = fst(location) }
AState = {State = snd(location) }
}
依赖项
请注意计算依赖关系：
- 给定 TZipCode，可以计算 TLocation
- 给定 TZipCode，可以计算 TMinMaxTemp
- 给定 TLocation，可以计算 TCity 和 TState
- 给定 TMinMaxTemp，可以计算 TMinTemp 和 TMaxTemp
计算依赖关系确保类型仅在其实例可用时才进行计算。计算类型及其输入类型的简单映射足以满足本文的目的。
C#
public struct ComputedType
{
public Type Type { get; set; }
public MethodInfo Method { get; set; }
}
static Dictionary<ComputedType, List<Type>> computedTypes;
F#
type ComputedType =
{
Type : Type
Method : MethodInfo
}
let computedTypes = new Dictionary<ComputedType, List<Type>>()
let typeInstances = new Dictionary<Type, Object>()
然后我们可以使用反射来填充此字典：
C#
static void CreateComputationalTypeDictionary()
{
computedTypes = new Dictionary<ComputedType, List<Type>>();
AddToComputedTypesDictionary(typeof(TMinMaxTemp));
AddToComputedTypesDictionary(typeof(TMinTemp));
AddToComputedTypesDictionary(typeof(TMaxTemp));
AddToComputedTypesDictionary(typeof(TLocation));
AddToComputedTypesDictionary(typeof(TCity));
AddToComputedTypesDictionary(typeof(TState));
}
static void AddToComputedTypesDictionary(Type t)
{
GetComputationsFor(t).ForEach(mi =>
computedTypes.Add(
new ComputedType()
{
Type = mi.ReturnType,
Method = mi
},
new List<Type>(mi.GetParameters().ToList().Select(p => p.ParameterType))));
}
static IEnumerable<MethodInfo> GetComputationsFor(Type t)
{
return
from type in Assembly.GetExecutingAssembly().GetTypes()
from mi in type.GetMethods(BindingFlags.Public | BindingFlags.Static)
where
mi.ReturnType == t
select mi;
}
F#
let GetComputationsFor t =
seq {
for typ in Assembly.GetExecutingAssembly().GetTypes() do
for mi in typ.GetMethods(BindingFlags.Public ||| BindingFlags.Static) do
match mi with
| rt when rt.ReturnType = t ->
yield mi
| _ -> ()
}
let AddToComputedTypesDictionary t =
GetComputationsFor(t).ForEach(fun mi ->
computedTypes.Add(
{
Type = mi.ReturnType
Method = mi
},
new List<Type>(mi.GetParameters().ToList().Select(fun p -> (p : ParameterInfo).ParameterType))))
|> ignore
let CreateComputationalTypeDictionary =
AddToComputedTypesDictionary typeof<TMinMaxTemp>
AddToComputedTypesDictionary typeof<TMinTemp>
AddToComputedTypesDictionary typeof<TMaxTemp>
AddToComputedTypesDictionary typeof<TLocation>
AddToComputedTypesDictionary typeof<TCity>
AddToComputedTypesDictionary typeof<TState>
|> ignore
然后我们可以遍历字典，对“已居住”（使用“依赖类型”中的措辞）的类型执行计算，也就是说，有值的类型。
C#
static Dictionary<Type, object> typeInstances;
static void ComputeAll()
{
bool more;
do
{
more = Compute();
} while (more);
}
static bool Compute()
{
bool more = false;
foreach (KeyValuePair<ComputedType, List<Type>> kvpComputation in computedTypes)
{
if (!IsTypeComputed(kvpComputation.Key.Type))
{
List<object> parms = GetParameterValues(kvpComputation.Value);
// If we have all the required parameters to perform the computation...
if (parms.Count == kvpComputation.Value.Count)
{
object ret = kvpComputation.Key.Method.Invoke(null, parms.ToArray());
typeInstances[kvpComputation.Key.Type] = ret;
more = true;
}
}
}
return more;
}
/// <summary>
/// Returns true if the type has been computed and a value is associated with the type.
/// </summary>
static bool IsTypeComputed(Type t)
{
return typeInstances.ContainsKey(t);
}
/// <summary>
/// Returns the computed value for the given type.
/// </summary>
static object GetComputedValue(Type t)
{
return typeInstances[t];
}
static List<object> GetParameterValues(List<Type> paramTypes)
{
List<object> ret = new List<object>();
paramTypes.Where(t => IsTypeComputed(t)).ForEach(t => ret.Add(GetComputedValue(t)));
return ret;
}
F#
let IsTypeComputed t = typeInstances.ContainsKey(t)
let GetComputedValue t = typeInstances.[t]
let GetParameterValues(paramTypes : List<Type>) =
let ret = new List<Object>()
paramTypes.Where(fun t -> IsTypeComputed(t)).ForEach(fun t -> ret.Add(GetComputedValue(t)))
ret
let Compute computedTypes =
let mutable more = false
for kvpComputation in (computedTypes : Dictionary<ComputedType, List<Type>>) do
match IsTypeComputed kvpComputation.Key.Type with
| false ->
let parms = GetParameterValues(kvpComputation.Value)
match parms.Count with
| cnt when cnt = kvpComputation.Value.Count ->
let ret = kvpComputation.Key.Method.Invoke(null, parms.ToArray())
typeInstances.[kvpComputation.Key.Type] <- ret
more <- true
| _ -> () // ignore
| true -> () // ignore
more
let ComputeAll computedTypes =
let mutable more = true
while more do
more <- Compute computedTypes
typeInstances
结果
我们可以转储字典，显示计算：
并且，通过“居住” TZipCode 类型，我们可以执行所有必要的计算来计算预期的最低/最高温度，并获取与邮政编码相关的城市和州：
C#
typeInstances = new Dictionary<Type, object>();
TZipCode zipCode = new TZipCode() { ZipCode = "12565" };
typeInstances.Add(zipCode.GetType(), zipCode);
ComputeAll();
DumpTypeInstances();
F#
在 F# 中，我们定义了一个可以从 C# 调用的方法：
let RunFSharpExample strZipCode =
typeInstances.Add(typeof<TZipCode>, { ZipCode = strZipCode })
ComputeAll computedTypes
并从 C# 轻松调用该方法：
Dictionary<Type, object> fsTypeInstances = ComputationalTypeExample.RunFSharpExample("12565");
DumpTypeInstances(fsTypeInstances);
结果是
后续步骤
显而易见，这是演示代码。有几件事需要完善：
- 消除 Method.Invoke 反射调用。
- 缓存 Web 服务。
- 创建真正的依赖关系树。
- F# 代码，特别是 Compute 方法，过于命令式，带有“for”循环。
- F# 代码应修改为使用原生集合而不是 .NET 集合类。
- 如果我们改进 F# 代码以处理不可变数据结构，我们可以轻松地利用并行执行计算的优势。
此外，上面的代码更像是“推送”实现——给定一个已居住的类型，它会遍历所有可能的计算，直到无法执行进一步的计算。实际上，我们想要的是一个更像“拉取”的实现：我们有一些已居住的类型，我们想计算其他类型的*值*。此实现将需要遍历一棵树来确定到达所需计算所需的中间计算。
F# 最佳实践
从这个练习中，我们可以得出几个 F# 语言的最佳实践：
- 在记录中使用唯一的标签以确保正确的类型推断。
- #1 帮助我们避免使用类型化参数，以便可以使用柯里化功能。
- 不要使用函数重载，而是为函数提供唯一且特定的名称。
- F# 中不带参数的函数会立即求值，基本上就像静态初始化器一样。函数通常期望接受参数。在本文的 F# 代码中，我使用了一些静态定义的字典，为了防止某些 F# 函数在字典初始化之前执行，我必须将字典传递给函数。需要小心处理 F# 中的无参数函数，要认识到这些函数将在您的 F# 调用执行之前被调用，并且可能产生意外的后果。
结论
希望本文以一种脚踏实地、易于理解的方式阐释了计算类型的一些基本概念。编写具有上述表达方式的程序，虽然比典型的实现更冗长，但会产生一个更具自文档性、类型安全且可维护的代码库。当然，使用方法调用存在显著的性能损失，这必须得到解决才能使此方法可用。本文还演示了 C# 调用 F# 函数以及 C# 和 F# 都使用的两个 Web 服务的用法。
参考文献
1 - http://en.wikipedia.org/wiki/Type_system
2 - http://plato.stanford.edu/entries/type-theory-church/
3 - http://www.scholarpedia.org/article/Computational_type_theory
4 - http://msdn.microsoft.com/en-us/library/dd233246
5 - http://msdn.microsoft.com/en-us/library/dd233200.aspx
6 - http://cs.hubfs.net/topic/None/57487
7 - http://en.wikipedia.org/wiki/Currying
8 - http://www.amateurtopologist.com/blog/2010/02/12/why-i-love-currying/
9 - http://stackoverflow.com/questions/501069/f-functions-with-generic-parameter-types
10 - http://coq.inria.fr/
11 - http://research.microsoft.com/en-us/projects/fstar/
12 - http://en.wikipedia.org/wiki/Dependent_type
延伸阅读
邮政编码 Web 服务： http://www.webservicex.net/uszip.asmx?WSDL