1

我正在用 F# 构建一个解释器。我试图变得聪明并将原始运算符的解释概括为函数调用（在这种情况下，作为归约）。

这是这样的想法：

let reduce fx values =
    Array.reduce values fx

let primitivesEnv = 
    let r = Dictionary<string,'T -> 'T -> 'T>()
    r.["int_+"] <- reduce (fun(l:int, r:int) -> l + r)
    r.["int_-"] <- reduce (fun(l:int, r:int) -> l - r)
    r

所以我以后可以这样做：

env.["int_+"]([| 1, 2 |])

当然，类型检查器会拒绝这个

警告 FS0064：此构造导致代码的通用性低于类型注释所指示的通用性。类型变量 'T 已被限制为类型 ''a -> 'a -> 'a'。错误 FS0001：类型不匹配。期待 ('a -> 'a -> 'a) -> ('a -> 'a -> 'a) -> 'a -> 'a -> 'a 但给定一个 ('a -> 'a -> 'a) -> 'a 当统一 ''a' 和 '('a -> 'a -> 'a) -> 'a -> 'a -> 'a' 时，结果类型将是无限的

PD：作为一个简单的解释器，我知道如何做到这一点，但我试图构建一个解决方案，让我以通用的方式构建数十种方法，而无需为每个方法制作 MATCH。

4

1 回答 1

1

首先，您的代码存在一些问题。您已在您的字典中添加了类型注释，'T -> 'T -> 'T但在我看来，它应该返回一个类型的函数，'T[] -> 'T因为您试图给它一个数组并评估一个归约。

此外，[| 1, 2 |]是一个元组的数组，您需要一个包含多个值的数组，例如这个：[| 1; 2 |]

我像这样修复了您的代码：

let reduce values =
    Array.reduce values

let primitivesEnv = 
    let r = System.Collections.Generic.Dictionary<string,'T[] ->'T>()
    r.["int_+"] <- reduce ((+) : int -> int -> int)
    r.["int_-"] <- reduce ((-) : int -> int -> int)
    r

let result = primitivesEnv.["int_+"] [| 1; 2 |]

不幸的是，这并不是问题的终结。

我们可能会说字典是类型'T[] ->'T但不是，字典的唯一有效类型是int[] -> int，第一个int -> int -> int类型注释创建该约束。如果我们省略了该类型注释，'T那么int当我们将它与int[].

类型参数'T必须始终以某种方式解析为固定类型，它不是允许您使用任何东西的通配符。

这意味着字典方法很好，直到您想要添加float（或其他类型）除了int. 使用字典时，您唯一的选择是选择一种类型或丢弃一些类型安全性并在运行时解析特定类型。

最简单的更改是创建一些联合案例来描述不同的归约类型：

type Reduction =
    |IntReduction of (int[] -> int)
    |FloatReduction of (float[] -> float)

然后，您创建 aDictionary<string, Reduction>而不是 a Dictionary<string,'T[] ->'T>。

当谈到在 F# 中创建解释器的更一般的问题时，我将首先创建一组结构化的可区分联合来描述您希望解释的迷你语言的表达式和结构，这称为抽象语法树 ( AST）。

然后，您可以定义一个run遍历树并执行 AST 描述的所有计算的函数。

我还将使用解析器组合库（我推荐 FParsec）将任何结构化文本解析为您在上述步骤中定义的联合案例的抽象语法树。

Phillip Trelford 有一个在线示例，说明如何使用 FParsec 进行简单的 C# AST：http ://www.fssnip.net/lf 这可能比您需要的强大得多，但希望它能给您一个起点.

于 2015-12-30T18:16:15.837 回答