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

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