Является ли eta-эквивалентность для функций совместимой с операцией seke в Haskell?

14

Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B.

Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду.

В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями:

seq :: a -> b -> b
seq ⊥ b = ⊥
seq ab = b, если a ≠ ⊥

Затем он заявляет: «Как следствие, ⊥ - это не то же самое, что \ x -> ⊥, поскольку для их различения можно использовать seq».

У меня вопрос, действительно ли это является следствием определения seq?

Кажется, что неявный аргумент был seqбы не вычислимым, если seq (\x -> ⊥) b = ⊥. Однако я не смог доказать, что такое seqбыло бы неисчислимо. Мне кажется, что такое seqявляется как монотонным, так и непрерывным, что ставит его в область вычислимости.

Алгоритм, реализующий такие как сл может работать, пытаясь найти для некоторых , xгде f x ≠ ⊥, перечисляя область fначиная с ⊥. Хотя такая реализация, даже если это вообще возможно, становится довольно волосатой, когда мы хотим сделать ее seqполиморфной.

Есть ли доказательство того, что нет вычислимого, seqкоторый идентифицирует себя (\x -> ⊥)с ⊥ :: A -> B? Кроме того , есть некоторые строительства , seqчто делает идентифицировать (\x -> ⊥)с ⊥ :: A -> B?

Рассел О'Коннор
источник

Ответы:

6

Во-первых, давайте подробно рассмотрим, как seqотличить от λ x . :λx.

bottom :: a
bottom = bottom

eta :: a -> b
eta x = bottom

-- This terminates
fortytwo = seq eta 42

-- This does not terminate
infinity = seq bottom 42

Поэтому экспериментальным фактом является то, что в Хаскеле и λ x . Operation функционально различимы. Это также факт, и вполне очевидный, который вычислим, потому что Хаскелл вычисляет его. Так много о Хаскеле. Вы спрашиваете об очень конкретной формулировке документации на Haskell. Я прочитал это как высказывание, которое должно удовлетворять двум данным уравнениям, но этих двух уравнений недостаточно для определения . И вот почему: я могу дать вам две модели (просто типизированного) λ- исчисления, в которых вычислимо и удовлетворяет заданным уравнениям, но в одной из моделей и λ x . λx.seqseqseqλseqλx. согласен, а в другом их нет.

В простой теоретико-доменной модели, где выражения интерпретируются в области непрерывных функций [ D E ], имеем = λ x . Obviously , очевидно. Возьмите эффективные домены Скотта или что-то подобное, чтобы все было вычислимо. Это легко определить в такой модели.λ[DE]=λx.seq

Мы также можем иметь модель исчисления, в которой различаются и λ x . , и тогда, конечно, η- правило не может быть выполнено. Например, мы можем сделать это путем интерпретации функций в области [ D E ] , т. Е. Области функциональных пространств с присоединенным дополнительным дном. Итак, - это дно [ D E ] , а λ x . это элемент чуть выше него. Их нельзя отличить по приложению, потому что они оба оцениваютλseqλx.η[DE][DE]λИкс, , независимо от того, к чему вы их применяете (они вравной степени равны). Но у нас естькарта между доменами, и она всегда отличает дно от всех других элементов.seq

Андрей Бауэр
источник
1
Это экспериментальный факт, что в GHC и / или Hugs ⊥ и λx.⊥. К счастью, Haskell не определяется реализацией. Мой вопрос предполагает, что Haskell недостаточно конкретизирован в отношении seq.
Рассел О'Коннор
Можете ли вы дать ссылку на то, что вы подразумеваете под "эффективными доменами Скотта" Предположительно, это не означает, что частичный порядок является разрешимым. Кроме того, STLC не является полиморфным, но Haskell является. Обычно Haskell интерпретируется в Системе F или одной из ее производных. Как это влияет на ваш аргумент?
Рассел О'Коннор
Раздел 1.1.4 моей кандидатской диссертации В диссертации на andrej.com/thesis/thesis.pdf приведено краткое определение эффективных доменов Скотта, и это фактически первый бесплатный доступ Google.
Андрей Бауэр
2
Если вы напишите доказательство для меня, вы получите реализацию Haskell 98, в котором выполняется правило eta, позволяющее оптимизировать (foldr (\ ab -> fab) z xs) до (foldr fz xs), вызывая асимптотическое повышение производительности с O (n ^ 2) - O (n) (см. ghc.haskell.org/trac/ghc/ticket/7436 ). Более убедительным он позволит оптимизировать NewTypeWrapper в (NewTypeWrapper. F) без необходимости расширения eta и предотвратить некоторые асимптотические потери производительности, которые в настоящее время накладываются newTypes в GHC (например, при использовании foldr).
Рассел О'Коннор
1
На самом деле, вы должны убедиться, что ваш компилятор всегда реализует как . То есть у вас может возникнуть соблазн не всегда сжиматься и поэтому в принципе λ x . и будут «иногда различимыми», очень опасная ситуация. Чтобы убедиться, что это не так, вам нужно реализовать умным способом, который включает в себя создание бесконечного числа процессов, каждый из которых применяет вашу функцию к базовому элементу. Если какой-либо из процессов завершается, то может продолжаться. Было бы интересно посмотреть, сможем ли мы сделать это последовательно. Хм. λИкс,λИкс,seqseq
Андрей Бауэр
2

Обратите внимание , что спецификация для seqкоторых вы цитируете это не его определение. Процитируем отчет Haskell «Функция seq определяется уравнениями : [а затем уравнениями, которые вы даете]».

Предполагаемый аргумент состоит в том, что seq будет невычислимым, если seq (\ x -> ⊥) b = ⊥.

Такое поведение будет нарушать спецификацию seq.

Важно отметить, что, поскольку он seqявляется полиморфным, seqего нельзя определить в терминах деконструкторов (проекции / сопоставление с образцом и т. Д.) Ни по одному из двух параметров.

Есть ли доказательство того, что не существует вычислимой последовательности, идентифицирующей (\ x -> ⊥) с ⊥ :: A -> B?

Если seq' (\x -> ⊥) bкто-то может подумать, что мы могли бы применить первый параметр (который является функцией) к некоторому значению, а затем выйти. Но, seqникогда не может отождествить первый параметр со значением функции (даже если это один для некоторого использования seq) из-за его параметрического полиморфного типа. Параметричность означает, что мы ничего не знаем о параметрах. Кроме того, seqникогда не может взять выражение и решить "это this?" (см. проблему Остановки), seqможно только попытаться оценить ее, а сама расходиться до ⊥.

Что seqнужно сделать, это оценить первый параметр (не полностью, а как «слабую головную нормальную форму» [1], то есть для самого верхнего конструктора), а затем вернуть второй параметр. Если первый параметр оказывается (то есть, не завершающее вычисление), то его оценка приводит seqк тому, что он не завершается, и, таким образом seq ⊥ a = ⊥.

[1] Бесплатные теоремы в присутствии seq - Johann, Voigtlander http://www.iai.uni-bonn.de/~jv/p76-voigtlaender.pdf

dorchard
источник
Спецификация, которую я даю для seq, является определением seq, потому что это именно то, что говорится в отчете Haskell 2010 в разделе 6.2. Ваше определение операции seq не поддерживается в отчете Haskell 2010: слова «нормальная форма головы» встречаются в отчете только один раз в совершенно ином контексте. Это также не согласуется с моим пониманием того, что GHC будет часто сокращать второй аргумент до seq перед первым аргументом, или первый аргумент не будет сокращен вообще, потому что анализатор строгости доказал, что он статически не является нижним.
Рассел О'Коннор
Параметричность прямо не говорит о том, что мы не можем применять какие-либо деконструкторы, и при этом не говорит, что мы никогда не можем отождествить первый параметр со значением функции. Все параметричность говорит, что для полиморфного лямбда-исчисления с фиксированными точками является то, что seq может поглощать строгие функции, или, в более общем случае, определенные строгие отношения, выполняемые для членов, содержат seq. Я допускаю, что вполне вероятно, что параметричность может быть использована для доказательства (\ x -> ⊥) & ne; ⊥, но я хотел бы увидеть строгое доказательство.
Рассел О'Коннор
В случае функции f : forall a . a -> T(где Tесть некоторый другой тип), тогда fне может применить никакие деконструкторы к своему первому аргументу, так как она не знает, какие деконструкторы применить. Мы не можем сделать "случай" на типах. Я попытался улучшить ответ выше (в том числе цитируя информацию о том, как seqоценивать нормальную форму головы).
Дорчард
Я могу попытаться сделать строгие доказательства позже, если найду время (использование отношений в стиле Рейнольдса может быть хорошим подходом).
Дорчард
@ RussellO'Connor: описание seq не «несовместимо» с этим поведением, это просто операционная спецификация (а поведение - это оптимизация, которая не меняет конечный результат).
Blaisorblade
2

λИкс,λИкс,

Самсон Абрамский давно обдумал этот вопрос и написал статью под названием « Ленивое лямбда-исчисление ». Итак, если вы хотите формальные определения, это то, где вы можете посмотреть.

Удай Редди
источник
1
По-видимому, эти детали определяются только путем десагерации в «ядро Haskell». Где это определено? В докладе говорится, в гл. 1.2 : «Хотя ядро ​​формально не указано, это, по сути, слегка подсахаренный вариант лямбда-исчисления с простой денотационной семантикой. Перевод каждой синтаксической структуры в ядро ​​дается после введения синтаксиса».
Blaisorblade
В отчете Haskell 2010 говорится то же самое , удивительно.
Blaisorblade
Спасибо за ссылку на Абрамского! Я просмотрел его, чтобы посмотреть, как он отвечает на вопрос, и пришел к следующему ответу: cstheory.stackexchange.com/a/21732/989
Blaisorblade
2

Доказательство того, что λ x. Ω ‌ ≠ Ω в является одной из целей, которые Абрамский ставит перед своей теорией ленивого лямбда-исчисления (страница 2 своей статьи , уже цитируемой Удаем Редди), потому что они оба находятся в нормальной форме со слабой головой. Что касается определения 2.7, он явно обсуждает, что эта-редукция λ x. M x → M, как правило, недопустимо, но это возможно, если M заканчивается в каждой среде. Это не означает, что M должна быть полной функцией - только то, что вычисление M должно завершиться (например, путем сокращения до лямбды).

Ваш вопрос, кажется, мотивирован практическими проблемами (производительность). Однако, хотя отчет по Хаскеллу может быть не совсем ясен, я сомневаюсь, что приравнивать λ x. ‌ ‌with produce создаст полезную реализацию Haskell; реализует ли он Haskell '98 или нет, остается спорным, но, учитывая замечание, ясно, что авторы предполагали, что это так.

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

Обновлено : мне не удалось закодировать это право (потому что я не очень бегло говорю на Хаскеле), и для исправления этого требуются вложенные runSTобласти. Я попытался использовать одну ячейку ссылки (в монаде ST), чтобы сохранить такие произвольные элементы, прочитать их позже и сделать их общедоступными. Параметричность доказывает, что break_parametricityниже не может быть определено (за исключением возврата bottom, например, ошибки), в то время как он может восстановить элементы, которые сгенерирует ваш предложенный seq.

import Control.Monad.ST
import Data.STRef
import Data.Maybe

produce_maybe_a :: Maybe a
produce_maybe_a = runST $ do { cell <- newSTRef Nothing; (\x -> writeSTRef cell (Just x) >> return x) `seq` (readSTRef cell) }

break_parametricity :: a
break_parametricity = fromJust produce_maybe_a

Я должен признать, что я немного нечетко формализирую доказательство параметричности, необходимое здесь, но это неформальное использование параметричности является стандартным в Haskell; но из работ Дерека Дрейера я узнал, что необходимая теория быстро разрабатывается в последние годы.

правок:

  • Я даже не уверен, нужны ли вам те расширения, которые изучаются для ML-подобных, императивных и нетипизированных языков, или же классические теории параметричности охватывают Haskell.
  • Кроме того, я упомянул Дерека Дрейера просто потому, что только позже я наткнулся на работу Удея Редди - я узнал об этом только недавно из «Сущности Рейнольдса». (Я только начал действительно читать литературу по параметричности в прошлом месяце или около того).
Blaisorblade
источник
Оценка (\x -> writeSTRef cell (Just x) >> return x)на случайных входах не выполняет запись в ячейку. Выполняются только те команды ST, которые превращают его в последовательность, переданную в runST. Точно так же, бег main = (putStrLn "Hello") `seq` (return ())не печатает ничего на дисплее.
Рассел О'Коннор
@ RussellO'Коннор, конечно, ты прав - тестирование сложно, так как у seq нет поведения, которое мы обсуждаем. Но я все еще думаю, что генерация элементов нарушает параметричность как таковую. Я попытаюсь исправить ответ, чтобы проиллюстрировать это.
Blaisorblade
Хм, очевидное исправление ответа требует вложения областей runST и использования ячейки из внешней области во внутренней, но это недопустимо.
Blaisorblade