Почему этот код с использованием UndecidableInstances компилируется, а затем генерирует бесконечный цикл времени выполнения?

При написании кода с использованием UndecidableInstances раньше я столкнулся с чем-то очень странным. Мне удалось непреднамеренно создать некоторый код, который проверяет типы, когда я полагал, что это не должно:

{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE MultiParamTypeClasses #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}

data Foo = Foo

class ConvertFoo a b where
  convertFoo :: a -> b

instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
  convertFoo = convertFoo . (convertFoo :: a -> Foo)

evil :: Int -> String
evil = convertFoo

В частности, convertFoo Проверка типов функций при наличии любого ввода для получения любого вывода, как показано evil функция. Сначала я подумал, что, возможно, мне удалось случайно осуществить unsafeCoerce, но это не совсем так: на самом деле пытается позвонить convertFoo функция (делая что-то вроде evil 3 например) просто заходит в бесконечный цикл.

Я в некотором смысле понимаю, что происходит. Мое понимание проблемы примерно так:

  • Пример ConvertFoo что я определил работает на любом входе и выходе, a а также b ограничивается только двумя дополнительными ограничениями, из которых должны существовать функции преобразования a -> Foo а также Foo -> b,
  • Каким-то образом это определение может соответствовать любым типам ввода и вывода, поэтому может показаться, что вызов convertFoo :: a -> Foo выбирает само определение convertFoo сам, так как это единственный доступный, в любом случае.
  • поскольку convertFoo вызывая себя бесконечно, функция входит в бесконечный цикл, который никогда не заканчивается.
  • поскольку convertFoo никогда не завершается, тип этого определения является нижним, так что технически ни один из типов никогда не нарушается, и типы программ проверяются.

Теперь, даже если вышеприведенное понимание верно, я все еще не понимаю, почему все типы программ проверяются. В частности, я бы ожидал ConvertFoo a Foo а также ConvertFoo Foo b ограничения на неудачу, учитывая, что таких экземпляров не существует.

Я понимаю (по крайней мере, нечетко), что ограничения не имеют значения при выборе экземпляра - экземпляр выбирается только на основе заголовка экземпляра, затем ограничения проверяются, поэтому я мог видеть, что эти ограничения могут разрешиться очень хорошо из-за моего ConvertFoo a b экземпляр, который примерно настолько разрешительный, насколько это возможно. Однако для этого потребуется разрешить тот же набор ограничений, который, я думаю, поместит проверку типов в бесконечный цикл, в результате чего GHC либо зависнет при компиляции, либо выдаст мне ошибку переполнения стека (последнее из которых я видел до).

Тем не менее, очевидно, что средство проверки типов не зацикливается, потому что оно успешно работает на дне и скомпилирует мой код. Зачем? Как контекст экземпляра удовлетворяется в этом конкретном примере? Почему это не приводит к ошибке типа или к циклу проверки типов?

Источник

2 ответа

Решение

Я искренне согласен с тем, что это отличный вопрос. Это говорит о том, как наши представления о классах типов отличаются от реальности.

Типкласс сюрприз

Чтобы увидеть, что здесь происходит, собираемся поднять ставки на подпись типа для evil:

data X

class Convert a b where
  convert :: a -> b

instance (Convert a X, Convert X b) => Convert a b where
  convert = convert . (convert :: a -> X)

evil :: a -> b
evil = convert

Очевидно, что Covert a b экземпляр выбирается, так как существует только один экземпляр этого класса. Типограф проверяет что-то вроде этого:

  • Convert a X верно, если...
    • Convert a X верно [верно по предположению]
    • а также Convert X X правда
      • Convert X X верно, если...
        • Convert X X верно [верно по предположению]
        • Convert X X верно [верно по предположению]
  • Convert X b верно, если...
    • Convert X X верно [верно сверху]
    • а также Convert X b верно [верно по предположению]

Типепекер нас удивил. Мы не ожидаем Convert X X быть правдой, поскольку мы не определили ничего подобного. Но (Convert X X, Convert X X) => Convert X X это своего рода тавтология: она автоматически верна и верна независимо от того, какие методы определены в классе.

Это может не соответствовать нашей ментальной модели классов типов. Мы ожидаем, что на этом этапе компилятор будет поглазеть и пожаловаться на Convert X Xне может быть правдой, потому что мы не определили экземпляр для него. Мы ожидаем, что компилятор будет стоять на Convert X X, чтобы найти другое место, чтобы идти туда, где Convert X X это правда, и сдаться, потому что нет другого места, где это правда. Но компилятор умеет рекурсировать! Рекурсировать, зациклить и быть завершенным по Тьюрингу.

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

(Это еще более убедительно продемонстрировано в комментарии Даниила:

class Loop a where
  loop :: a

instance Loop a => Loop a where
  loop = loop

.)

Опасности неразрешимости

Это именно та ситуация, UndecidableInstancesпозволяет. Если мы выключим это расширение и включим FlexibleContexts (безобидное расширение, которое по своей природе является просто синтаксическим), мы получаем предупреждение о нарушении одного из условий Патерсона:

...
Constraint is no smaller than the instance head
  in the constraint: Convert a X
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’

...
Constraint is no smaller than the instance head
  in the constraint: Convert X b
(Use UndecidableInstances to permit this)
In the instance declaration for ‘Convert a b’

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

Вниз

Что касается того, почему программа во время выполнения бесконечных циклов: есть скучный ответ, где evil :: a -> b не может не вызывать бесконечный цикл или выбрасывать исключение или вообще снизу, потому что мы доверяем проверке типов в Haskell, и нет значения, которое может населять a -> b кроме дна.

Более интересный ответ заключается в том, что, так как Convert X X тавтологически верно, его определение экземпляра является этот бесконечный цикл

convertXX :: X -> X
convertXX = convertXX . convertXX

Мы можем аналогичным образом расширить Convert A B определение экземпляра

convertAB :: A -> B
convertAB =
  convertXB . convertAX
  where
    convertAX = convertXX . convertAX
    convertXX = convertXX . convertXX
    convertXB = convertXB . convertXX

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

Источник

Вот как я мысленно обрабатываю эти случаи:

class ConvertFoo a b where convertFoo :: a -> b
instance (ConvertFoo a Foo, ConvertFoo Foo b) => ConvertFoo a b where
  convertFoo = ...

evil :: Int -> String
evil = convertFoo

Сначала мы начнем с вычисления набора необходимых экземпляров.

  • evil прямо требует ConvertFoo Int String (1).
  • Тогда (1) требует ConvertFoo Int Foo (2) и ConvertFoo Foo String (3).
  • Тогда (2) требует ConvertFoo Int Foo (мы уже это посчитали) и ConvertFoo Foo Foo (4).
  • Тогда (3) требует ConvertFoo Foo Foo (посчитано) и ConvertFoo Foo String (Счет).
  • Тогда (4) требует ConvertFoo Foo Foo (посчитано) и ConvertFoo Foo Foo (Счет).

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

Затем мы приступаем к предоставлению кода для этих экземпляров. Вот.

convertFoo_1 :: Int -> String
convertFoo_1 = convertFoo_3 . convertFoo_2
convertFoo_2 :: Int -> Foo
convertFoo_2 = convertFoo_4 . convertFoo_2
convertFoo_3 :: Foo -> String
convertFoo_3 = convertFoo_3 . convertFoo_4
convertFoo_4 :: Foo -> Foo
convertFoo_4 = convertFoo_4 . convertFoo_4

Мы получаем кучу взаимно рекурсивных определений экземпляров. В этом случае они будут зациклены во время выполнения, но нет причин отклонять их во время компиляции.

Источник
Другие вопросы по тегам