“表达式问题”在F#中是否可解决？

Question

“表达式问题”在F#中是否可解决？

f#

8

我一直在观看一段有趣的视频，其中使用Haskell中的类型类来解决所谓的“表达式问题”。大约15分钟后，它展示了如何使用类型类来“打开”基于鉴别联合的数据类型以进行扩展 - 可以单独添加其他鉴别器而无需修改/重建原始定义。

我知道F#中没有可用的类型类，但是否有其他语言特性可以实现这种可扩展性？如果没有，我们能否在F#中接近解决表达式问题？

澄清：我假设该问题的定义如先前视频系列中所述 - 数据类型和对数据类型的操作的可扩展性具有代码级模块化和分离编译的特征（扩展可以作为单独的模块部署，而不需要修改或重新编译原始代码），以及静态类型安全性。

- Mike K

3

您可能需要澄清“表达式问题”究竟是什么。关于Wadler问题陈述中哪些部分是“表达式问题”的正常部分，哪些是在“表达式问题”之上的进一步限制，存在不同意见。例如，在他的论文中，Martin Odersky认为模块化类型检查是“表达式问题”的一部分，这实际上意味着Haskell并没有解决它。请注意，本翻译尽力遵循原意，但也许不能完全传达作者的每一个微妙之处。 - Jörg W Mittag

3个回答

3

请查看Vesa Karvonen在此处的评论，其中提供了一个SML解决方案（虽然有点繁琐），但可以轻松地转换为F#。

- kvb

不那么容易：这需要递归类型，而 F# 不支持。而且我也不清楚它是如何解决表达式问题的，例如如何在不重写所有内容的情况下添加 Pow 到示例中？ - J D

@JonHarrop - 不确定你所说的“它需要递归类型，而F#不支持”是什么意思(?!) - 直接翻译SML代码可以正常工作。关于如何添加Pow - 要么向num类型添加一个新案例并在numEval和numToString函数中处理它（其他所有内容都不变），要么直接向t类型添加一个新案例并在eval和toString函数中处理它（同样保持其他所有内容不变）。 - kvb

直接的SML代码音译按预期工作。我收到了“统一'a和'a lam时，结果类型将是无限的”错误。或者添加一个新的情况到num类型中。表达式问题的整个重点在于，你不被允许编辑原始代码。你必须在外部扩展它。因此，我认为这段代码根本没有解决表达式问题。我认为他只是硬编码了Garrigue论文中的一个特定版本，并错过了练习的要点。 - J D

@JonHarrop - 对我来说 type 'e lam = ABS of string * 'e | APP of 'e * 'e | VAR of string 是行得通的。Vesa 的方法允许将 lam、num 和 cons 类型分别编译，然后用少量样板代码将它们绑定到类型 t 上。在我看来，这似乎很明显地解决了表达式问题。 - kvb

我在lamEval函数的代码eval ((s, x)::e) b处遇到了类型错误。这段SML代码是否可以编译通过？表达式问题是关于如何扩展现有类型A以创建一个新类型B，使您可以直接使用类型B的值重用A上的现有函数。Garrigue的OCaml使用多态变体来实现这一点，例如var是'a lambda的子类型。Karvonen的SML没有做到这一点，在我看来。每次添加新的类型构造器时，都必须包装每个函数，即编写渐近更多的代码。 - J D

请注意，Garrigue的论文中的eval1具有类型(string * ('a lambda as 'a)) list -> 'a -> 'a。这是一个递归类型（又称为rectype）。OCaml支持这些类型。据我所知，Standard ML和F#不支持。我从F#得到的类型错误告诉我它正在尝试创建一个递归类型（将'a与'a lam统一）。 - J D

2

我知道F#中没有类型类，但是有没有其他语言特性可以实现这种扩展性呢？

我认为不可能。

如果不是的话，在F#中我们能实现多接口问题吗？

多接口问题指的是允许用户在不重新编译库的情况下添加新函数和新类型到你的库代码中。在F#中，联合类型使添加新函数变得容易（但无法向现有联合类型添加新联合情况），而类类型使派生新类类型变得容易（但无法向现有类层次结构添加新方法）。这些是实践中所需的两种扩展性形式。同时在不损失静态类型安全的前提下扩展两个方向的能力只是学术上的好奇心。

顺便说一句，我见过的提供这种可扩展性最优雅的方法是牺牲类型安全并使用所谓的“基于规则的编程”。 Mathematica就是这样做的。例如，一个计算整数文字、变量或加法表达式的符号导数的函数可以在Mathematica中如下编写：

D[_Integer, _] := 0
D[x_Symbol, x_] := 1
D[_Symbol, _] := 0
D[f_ + g_, x_] := D[f, x] + D[g, x]

我们可以这样为乘法添加支持：

D[f_ g_, x_] := f D[g, x] + g D[f, x]

我们可以添加一个新的函数来评估这样的表达式：

E[n_Integer] := n
E[f_ + g_] = E[f] + E[g]

对我来说，这比使用OCaml、Haskell和Scala等语言编写的任何解决方案都更加优雅，但是它当然不是类型安全的。

- J D

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Tomas Petricek · Accepted Answer

正如Jörg在评论中指出的那样，这取决于你所说的“解决”的含义。如果你的意思是包括某种类型检查来确保你没有漏掉某些情况下的某个函数的实现，那么F#不会给你任何优雅的方式（我不确定Haskell的解决方案是否优雅）。你可能能够使用kvb提到的SML解决方案进行编码，或者使用其中一个基于OO的解决方案。

实际上，如果我正在开发需要解决问题的真实系统，我会选择一种不提供完整检查但更容易使用的解决方案。

一个草图是使用obj作为类型的表示，并使用反射来定位为单个情况提供实现的函数。我可能会标记所有部分，以使检查更容易。添加表达式应用程序的模块可能看起来像这样：

[<Extends("Expr")>]  // Specifies that this type should be treated as a case of 'Expr'
type App = App of obj * obj

module AppModule = 
  [<Implements("format")>] // Specifies that this extends function 'format'
  let format (App(e1, e2)) =
    // We don't make recursive calls directly, but instead use `invoke` function
    // and some representation of the function named `formatFunc`. Alternatively
    // you could support 'e1?format' using dynamic invoke.
    sprintfn "(%s %s)" (invoke formatFunc e1) (invoke formatFunc e2)

这并没有给你任何类型检查，但它提供了一个相当优雅的解决方案，易于使用且不难实现（使用反射）。检查是否缺少某个情况并没有在编译时完成，但你可以轻松地编写单元测试来进行检查。