Код, который осуществляет вывод типа

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

Надеюсь, это поможет каким-то образом. Обязательно постарайтесь создать набор регрессионных тестов, которые вы можете повторно запускать в автоматическом режиме, чтобы гарантировать, что все выводы вашего типа работают правильно во всех внесенных вами изменениях:)