Церковное кодирование логического и STLC

Question

Часто говорят, что

tru t f = t
fls t f = f

представляют True и False в том смысле, что "мы можем использовать эти термины для выполнения операции по проверке истинности логического значения".

Но это скрывает важное предостережение в том, что оно кажется верным только в нетипизированном лямбда-исчислении. Если я просто вставлю эти значения в haskell, я могу написать функцию:

tryMeOnFalse ∷  (∀ t f. t → f → t) → String
tryMeOnFalse tr = "Hi"
a' = tryMeOnFalse tru
b' = tryMeOnFalse fls  -- type error !

который различает Tru и FLS на уровне типа. Насколько неправильно / верно было бы сказать, что:

• в STLC tru а также fls являются свидетельством уровня ценности некоторых повышен 'Boolean вид, который имеет типы 'True а также 'False
• в STLC (приведенные) типизированные значения (tru :: ∀ t . t → t → t) а также (fls :: ∀ t . t → t → t) представлять True и False (и нетипизированный, вполне обычный)

Редактировать: теперь я понимаю, благодаря ответу @Daniel Wagner, я думал о лямбда-исчислении второго порядка, а не STLC в моем вопросе.

Answer 1

Это относится не только к нетипизированному лямбда-исчислению; но в печатных исчислениях, как обычно, нужно быть немного осторожнее с печатанием. Мы должны определить:

type Boolean = forall r. r -> r -> r

У нас конечно есть tru, fls :: Booleanи должен аннотировать их как таковые. Но у нас нет tryMeOnFalse :: Boolean -> String! Так что здесь нет реального противоречия.

Ваши комментарии о STLC немного странные, поскольку в STLC совсем другая система набора текста. Нам нужны отдельные логические типы для каждого типа результата, так как полиморфизма нет.

В Haskell, безусловно, можно определить типы, которые населены только tru или только fls (ну, каждый тип также заселен undefined, конечно); но это вообще не очень полезно.