编译器如何确定sml中的类型

Question

我得到了以下代码，并被要求确定类型。

exception Break;
fn f => fn a => fn b =>
    (f(raise Break)
       handle Break => if (f a) then a else raise Break)
          handle Break => if not(f a) then a else b;

我知道这个函数在所有情况下都接受 f、a 和 b 并输出 a，所以它必须等同于：

fn f => fn a => fn b => a

其类型为：

'a -> 'b -> 'c -> 'b

因为 'if( f a)' 我们可以推导出 'a 必须是一个接受类型 'b 并输出布尔值的函数，否则它不会工作。

('b->bool) -> 'b -> 'c -> 'b

完成了 'a 是开始:

('a->bool) -> 'a -> 'b -> 'a

是我从中得到的最终答案。但是，当我在命令提示符下键入它时，我得到以下类型：

(bool->bool) -> bool -> bool -> bool

我错过了什么？ 'a 和 'b（根据我的最终类型评估）在什么时候专用于 bool？

Answer 1

How does the compiler determine types in sml

标准 ML 使用 Damas-Hindley-Milner type inference, but there are several algorithms for resolving the most general type，特别是算法 W。

A Generalized Let-Polymorphic Type Inference Algorithm [PS]，其实主要是提出了一个更高效的替代算法G，但是介绍非常通俗易懂，给出了推断a类型的完整例子小表情
So you still don't understand Hindley-Milner?, which introduces just enough type theory to explain the Whosebug question "What part of Milner-Hindley do you not understand?".

At what point does 'a and 'b specialize to bool?

'a 和 'b 专用于 bool 的确切点取决于所使用的算法。我将跳到前面并跳过一些步骤，其中表达式被赋予类型并且这些类型是统一的。

当它说 if (f a) then a else raise Break 时，然后

a : t₁
f : t₁ → bool
if ... : t₁

同样地，当它说 if not (f a) then a else b 时，我们还有

b : t₁

最后，f (raise Break) handle Break => if ... then a else ... 告诉我们

f (raise Break) : 布尔值
t₁ = bool，因为 f (raise Break) 和 if ... then a else ... 必须具有相同的类型。

您遗漏的部分可能是意识到 x handle ... => y、x 和 y 必须具有相同的类型。否则，您将拥有一个根据是否抛出异常而改变类型的表达式。当在编译期间解析类型并且在运行时抛出异常时，这是不可能的。与此相关的一个实际示例是负面测试，其中 handle ... 左侧的类型被强制为右侧的类型：

val factorial_robust_test = (factorial -1; false)
                            handle Domain => true
                                 | Overflow => false
                                 | _ => false

编译器如何确定sml中的类型

How does the compiler determine types in sml

types

sml

smlnj