Для каких языков уже существует теория наблюдательной эквивалентности?

Для доказательства корректности я ищу пригодное для использования понятие эквивалентности программы для систем чистого типа (PTS) Барендрегта; не хватает этого, для достаточно специфических систем типов. Моя цель - просто использовать это понятие, а не исследовать его ради самого себя. $\cong$

Это понятие должно быть « экстенсиональным » - в частности, чтобы доказать, что , должно быть достаточно, чтобы доказать, что $t_1 \cong t_2$ для всех значений соответствующего типа. $t_1\; v \cong t_2\; v$ $v$

Денотационная эквивалентность

Денотационная эквивалентность легко удовлетворяет всем правильным леммам, но денотационная семантика для произвольной PTS кажется довольно сложной задачей - это уже казалось бы сложным для Системы F.

Контекстуальная / наблюдательная эквивалентность

Тогда очевидной альтернативой являются различные формы контекстуальной эквивалентности (два термина эквивалентны, если никакой основной контекст не может их различить), но его определение не может быть сразу использовано; различные леммы не тривиальны, чтобы доказать. Они были доказаны для PTS? В качестве альтернативы, будет ли теория «очевидным расширением», или есть основания полагать, что теория будет существенно отличаться?

РЕДАКТИРОВАТЬ: я не сказал, что сложно выше.

Легкая часть: определение

Определение эквивалентности не так уж сложно, и определение появляется во многих работах (начиная, по крайней мере, с исследования PCF Плоткина в 1975 году, если не раньше - источником может быть докторская диссертация Морриса в 1968 году). Мы если для всех основных контекстов , - то есть и дают одинаковый результат $t_1 \cong t_2$ $C$ $C[t_1] \simeq C[t_2]$ $C[t_1]$ $C[t_2]$ , У вас есть несколько вариантов здесь с множеством альтернатив: например, в сильно нормализующем языке, если у вас есть базовый тип натуралов, вы можете сказать, что базовые контексты - это те, которые возвращают натуралы, и тогда означает, что и оценить до того же числа. При отсутствии завершения для приемлемых языков достаточно использовать «X заканчивается» в качестве наблюдения, потому что, если две программы эквивалентны при наблюдении завершения, они также эквивалентны при наблюдении результата. $a \simeq b$ $a$ $b$

Трудная часть: доказательства

Тем не менее, эти документы часто не объясняют, насколько сложно на самом деле использовать это определение. Все ссылки ниже показывают, как справиться с этой проблемой, но нужная теория сложнее, чем кажется. Как доказать, что ? Делаем ли мы на самом деле анализ и введение в контекст? Ты не хочешь этого делать. $t_1 \cong t_2$

Как указывает Мартин Бергер, вместо этого вы хотите использовать либо бисимуляцию (как это сделал Питтс), либо отношение логической эквивалентности (которое Харпер просто называет «логической эквивалентностью»).

Наконец, как вы доказываете экстенсиональность, как определено выше?

Харпер решает эти вопросы на 10 страницах для System T, благодаря значительным умам и логическим связям. Питтс берет больше. Некоторые языки еще более сложны.

Как с этим бороться

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

Я знаю (хотя и не подробно) о следующих работах:

Эндрю Питтс (например, в ATTAPL для расширенной Системы F и в нескольких статьях, таких как 58-страничные «Оперативные теории эквивалентности программ»).
Практические основы языков программирования (главы 47-48), вдохновленные Питтом (но утверждающие, что имеют более простые доказательства).
Логическое исследование эквивалентности программы . Я не могу найти аннотацию на английском языке, но она, похоже, тратит много усилий на побочные эффекты (ссылки), что кажется ортогональным осложнением.

pl.programming-languages type-theory operational-semantics Blaisorblade
источник

⇓

$\Downarrow$

P ≅ Q

$P \cong Q$

C [\cdot]

$C[\cdot]$

C [P] ⇓

$C[P] \Downarrow$

C [Q] ⇓

$C[Q] \Downarrow$

@MartinBerger: это идея, на которую я намекаю, но доказать ее прямо удивительно сложно, потому что вам нужно сделать доказательства для всех C (я объясню это лучше в этом вопросе). Кроме того, если все программы завершаются, используемое вами определение определяет все программы.

Blaisorblade

β η

$\beta\eta$

C [P] ⇓ t r u e

$C[P] \Downarrow true$

C [Q] ⇓ t r u e

$C[Q] \Downarrow true$

≅

$\cong$ и (2) прост в обращении, например, некоторые понятия о сходстве или логические отношения. Зависит от приложения.

Мартин Бергер

@Blaisorblade Вероятно. Теоретики параллелизма делают это интенсивно в течение длительного времени, потому что с параллельными процессами намного менее ясно, какое понятие эквивалентности использовать. Это привело к разделению труда: используйте основанную на сокращении семантику с количественной оценкой по контекстам, чтобы определить понятие эквивалентности, а затем используйте бисимуляции или трассы над помеченными переходами, чтобы доказать эквивалентность (или ее отсутствие). Большой открытый вопрос исследования в теории параллелизма заключается в том, как алгоритмически перейти от первого к последнему.

Мартин Бергер

Ответы:

$[\![ {-} ]\!]$

[[t_{1}]] = [[t_{2}]] ⟹ t_{1} ≅ t_{2} .

$[\![ t_1 ]\!] = [\![ t_2 ]\!] \implies t_1 \cong t_2.$

Андрей Бауэр
источник

≅

$\cong$

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

Blaisorblade

@MartinBerger, я не понимаю вашу критику. ОП запрашивает методы демонстрации эквивалентности наблюдений, я упоминаю общую, а затем вы возражаете, что существуют другие способы, которые избегают метода?

Андрей Бауэр

@Blaisorblade, тогда вам просто придётся изобрести денотационную семантику для систем чистого типа, не так ли? :-) Но если серьезно, я спрошу Алекса Симпсона, он бы лучше знал о денотационной семантике для таких вещей.

Андрей Бауэр

@AndrejBauer Это не должно было быть критикой, скорее как приложение.

Мартин Бергер

$\eta$

Коди
источник

Я не думаю, что доктор философии Штрайхера о ПТС. Речь идет о семантике исчисления конструкций и результатах независимости через семантику надежности. Смотрите здесь .

Мартин Бергер

Благодарю за разъяснение! Я боюсь, что ссылка не работает, хотя (и трудно исправить с помощью минимизированной ссылки).

Коди

Ссылка была на оглавление книги здесь . Я надеюсь, что этот работает лучше.

Мартин Бергер

λ^{*}

$\lambda^*$

@MartinBerger: вы имеете в виду семантику реализуемости?

Доминик Деврисе

Этот ответ предлагает подход к проблеме. (Обратная связь приветствуется).

В главе 49 PFPL сразу обсуждаются эквивалентные понятия наблюдательной эквивалентности и логической эквивалентности. Логическая эквивалентность - это то же отношение, которое используется для определения параметричности, поэтому ядро главы является доказательством параметричности для системы F.

Работа по параметризации для PTS, AFAICT, не обсуждает связь с наблюдательной эквивалентностью. Фактически, чтобы даже определить эквивалентность наблюдений, если у вас нет нетерминации, вам нужен некоторый положительный тип основания (натуральные значения, логические значения), чтобы использовать его для наблюдений.

Тем не менее, ключевая теорема (PFPL 47.6, 48.3, 49.2) для связи двух отношений доказывается независимо от конкретного языка:

Наблюдательная эквивалентность является наиболее грубой последовательной конгруэнцией выражений.

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

n + 1 = 1 + nVecN nnVecNVecN $n + 1 = 1 + n$ Vec (n + 1)Vec (1 + n)n + 11 + n

Blaisorblade
источник