进行类型推断的代码 [英] Code that exercises type inference

问题描述

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

I'm working on an experimental programming language that has global polymorphic type inference.

最近，我使算法运行得很好，可以正确键入要抛出的示例代码的位.我现在正在寻找可以解决极端情况的更复杂的东西.

I recently got the algorithm working sufficiently well to correctly type the bits of sample code I'm throwing at it. I'm now looking for something more complex that will exercise the edge cases.

任何人都可以指出我可用于此目的的粗糙和可怕的代码片段的来源吗?我确信函数式编程世界有很多.我特别在寻找使用函数递归进行恶意操作的示例，因为我需要检查以确保函数扩展正确终止，但是一切都很好---我需要构建一个测试套件.有什么建议吗?

Can anyone point me at a source of really gnarly and horrible code fragments that I can use for this? I'm sure the functional programming world has plenty. I'm particularly looking for examples that do evil things with function recursion, as I need to check to make sure that function expansion terminates correctly, but anything's good --- I need to build a test suite. Any suggestions?

我的语言在很大程度上是必须的，但是任何ML风格的代码都应该易于转换.

My language is largely imperative, but any ML-style code ought to be easy to convert.

推荐答案

我的总体策略实际上是从相反的方向进行处理-确保它拒绝不正确的事情！

My general strategy is actually to approach it from the opposite direction -- ensure that it rejects incorrect things!

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

That said, here are some standard "confirmation" tests I usually use:

急切的定点组合器(从此处被盗):

The eager fix point combinator (unashamedly stolen from 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表达式:

Check out those deeply nested let expressions too:

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

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

I don't know if you have to have the value restriction in order to incorporate mutable references. If so, see what happens:

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

You might need to implement map and rev in the standard way :)

然后附上实际参考文献(从此处窃取) ):

Then with actual references lying around (stolen from here):

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

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

Hope these help in some way. Make sure to try to build a set of regression tests you can re-run in some automatic fashion to ensure that all of your type inference behaves correctly through all changes you make :)

这篇关于进行类型推断的代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！