执行类型推断的代码

Question

我正在研究一种具有全局多态类型推断的实验性编程语言。

我最近让该算法运行得足够好，可以正确输入我扔给它的示例代码。我现在正在寻找更复杂的东西来练习边缘情况。

谁能指出我可以用于此目的的非常粗糙和可怕的代码片段的来源？我确信函数式编程世界里有很多这样的东西。我特别寻找用函数递归做坏事的例子，因为我需要检查以确保函数扩展正确终止，但一切都很好——我需要构建一个测试套件。有什么建议吗？

我的语言很大程度上是命令式的，但任何 ML 风格的代码都应该很容易转换。

Answer 1

我的总体策略实际上是从相反的方向接近它——确保它拒绝不正确的东西！

也就是说，这里是我通常使用的一些标准“确认”测试：

急切的固定点组合器（无耻地从 此处）：

datatype 'a t = T of 'a t -> 'a

val y = fn f => (fn (T x) => (f (fn a => x (T x) a)))
               (T (fn (T x) => (f (fn a => x (T x) a))))

明显的相互递归：

fun f x = g (f x)
and g x = f (g x)

也请检查那些深度嵌套的 let 表达式：

val a = let
   val b = let 
      val c = let
         val d = let
            val e = let
               val f = let
                  val g = let
                     val h = fn x => x + 1
                  in h end
               in g end
            in f end
         in e end
      in d end
   in c end
in b end

深度嵌套的高阶函数！

fun f g h i j k l m n = 
   fn x => fn y => fn z => x o g o h o i o j o k o l o m o n o x o y o z

我不知道是否必须有值限制才能合并可变引用。如果是这样，看看会发生什么：

fun map' f [] = []
  | map' f (h::t) = f h :: map' f t

fun rev' [] = []
  | rev' (h::t) = rev' t @ [h]

val x = map' rev'

您可能需要以标准方式实现 map 和 rev :)

然后使用实际引用（从 此处）：

val stack =
let val stk = ref [] in
  {push = fn x => stk := x :: !stk,
   pop  = fn () => stk := tl (!stk),
   top  = fn () => hd (!stk)}
end

希望这些能在某种程度上有所帮助。确保尝试构建一组可以以某种自动方式重新运行的回归测试，以确保所有类型推断在您所做的所有更改中都能正确运行:)