Значение и актуальность формулировки "без завершающей реализации" в теории типов

Question

В контексте обсуждения Haskell https://stackoverflow.com/questions/62509788/the-intuition-behind-the-definition-of-the-co-reader-monad, Мне сказали, что

Для полиморфного типа не существует завершающей реализации $(e \к a) \к a$

и что у нас не могло бы быть функции типа $((e \к a) \к a) \к e$ или функция типа $(r \к x) \к x$, поскольку они не были бы "реализуемыми".

Эти типы хорошо сформированы в STLC, в том смысле, что мы можем сконструировать их, используя правила формирования типов.И я не понимаю, почему мы не можем сформировать лямбда-термины такой формы, такие как $\лямбда c_{((a o t) o t)}.\, b_a$, или $\лямбда p_{e \к a}.\,b_a$.

В чем же, таким образом, проблема?В частности, что такое "завершающая реализация" в контексте STLC?Я полагаю, что это связано с тем фактом, что $(e o \bot) o \bot$ конструктивно не эквивалентен $e$, но я был бы признателен, если бы кто-нибудь объяснил мне это по буквам.

Answer 1

Ты можешь всегда заполнять тип свободной переменной:тип $\тау$ заполняется свободной переменной $x_\тау$.Когда люди говорят о "реализации" какого-либо типа, они имеют в виду закрытый срок, т.е. один без свободных переменных.Приведенные вами примеры содержат свободные переменные, а именно $b_a$.

В чистый просто набранный текст $\лямбда$-математический анализ все термины являются "завершающими" в том смысле, что математический анализ сильно нормализуется, поэтому какие бы сокращения вы ни предпринимали, они всегда приведут к (уникальной) нормальной форме.

В $\лямбда$-математический анализ, расширенный рекурсивными определениями (такими как Haskell), мы можем использовать для каждого типа $\тау$ с закрытым термином, например, в Haskell тип t населен a определяется как

a :: t
a = a

Как только у нас есть рекурсивные определения, легко написать закрытые термины, которые не заканчиваются (или не имеют нормальной формы).