递归调用的函数类型推断

Question

我正在尝试实现一种自定义语言,允许从最后一个语句推断出函数返回类型.但是,当发现直接或间接递归函数调用时,类型推断系统显然会失败.

func factorial(a:int) -> 
    if a == 0
        1
    else
        a * factorial(a - 1)

例如,即使参数类型未指定,F#也会这样做:

let rec fact i =
    if i = 0 then 1 else i * fact (i-1)

这个系统如何运作？

Answer 1

F#类型检查器使用Damas-Hindley-Milner类型推断算法.阶乘的例子大致可以解释如下:

• 从申报fact,我们在同类形式tx -> ty和tx = t(i)在那里t(i)是一个值的类型i.

• 从平等检查,因为val (=): 'T -> 'T -> bool我们也有t(i) = t(0) = int.

• 从then分支,我们得到另一个约束ty = t(1) = int.
• 从else分支机构来看,普通的(*)运营商是'T -> 'T -> 'T如此t(i) = ty.

基于约束集:

tx = t(i)
t(i) = t(0) = int
ty = t(1) = int
t(i) = ty

使用统一,我们到达tx = ty = int和推断的类型fact作为int -> int.这也意味着如果你改变子句的顺序if/then/else(通过反转条件),类型推断仍然可以正常工作.

也就是说,这是类型推断算法的一个非常简单的例子.您可以按照上面的维基百科链接阅读更多相关信息.

为了将算法应用于您的自定义语言,您可以在各种函数式编程书籍中找到实现.有关更多详细信息,请参阅此线程Damas-Hindley-Milner类型推断算法实现.