programming-languages - 执行类型推断的代码

Question

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

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

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

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

Answer 1

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

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

急切的固定点组合器(无耻地从 here 窃取):

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 :)

然后使用周围的实际引用文献(从 here 窃取):

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

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