function - 如何对没有显式返回类型的递归函数进行类型检查？

Question

我正在编写一种不输入函数的语言。这意味着我需要推断函数调用的返回类型才能进行类型检查。但是，当有人编写递归函数时，类型检查器会进入无限递归，试图推断函数体内的函数调用类型。

类型检查器执行以下操作：

1. 推断函数调用实际参数的类型。
2. 创建实际参数类型到形式参数的映射。
3. 使用映射来注释函数体内使用的参数的类型。
4. 推断并返回函数体的返回类型。

第 4 步尝试在函数体内推断函数调用的类型，它再次调用相同的类型检查器函数，导致无限递归。

给我这个问题的递归函数的一个例子：

function factorial(n) = n<1 ? 1 : n*factorial(n-1); // Function definition.
...
assert 24 == factorial(4); // Function call expression usage example.

如何在不进入无限递归循环的情况下解决这个问题？有没有办法推断递归函数调用的类型而不必再次进入正文？或者一些从上下文推断类型的干净方法？

我知道简单的解决方案可能是向函数添加类型注释，这样问题就很简单了，但在这样做之前，我想知道是否有办法解决这个问题而无需求助。

我也希望解决方案能够相互递归。

标签： functionrecursioncompiler-constructiontypecheckingfunction-call

Answer 1