Просто типизированное лямбда-исчисление - Simply typed lambda calculus

В просто типизированное лямбда-исчисление (${\displaystyle \lambda ^{\to }}$), форма теория типов, это печатная интерпретация из лямбда-исчисление только с одним конструктор типов (${\displaystyle \to }$), который строит типы функций. Это канонический и простейший пример типизированного лямбда-исчисления. Просто типизированное лямбда-исчисление было первоначально введено Церковь Алонсо в 1940 году как попытка избежать парадоксального использования нетипизированное лямбда-исчисление, и он демонстрирует много желанных и интересных свойств.

Период, термин простой тип также используется для обозначения расширений просто типизированного лямбда-исчисления, таких как товары, побочные продукты или же натуральные числа (Система T ) или даже полный рекурсия (подобно PCF ). Напротив, системы, которые вводят полиморфные типы (например, Система F ) или же зависимые типы (словно Логическая структура ) не считаются просто набрал. Первые, кроме полной рекурсии, до сих пор считаются просто поскольку Церковные кодировки таких конструкций можно сделать только ${\displaystyle \to }$ и подходящие переменные типа, а полиморфизм и зависимость - нет.

Синтаксис

В этой статье мы используем ${\displaystyle \sigma }$ и ${\displaystyle \tau }$ варьироваться по типам. Неофициально тип функции ${\displaystyle \sigma \to \tau }$ относится к типу функций, которые при вводе типа ${\displaystyle \sigma }$, произвести вывод типа ${\displaystyle \tau }$.Условно, ${\displaystyle \to }$ сподвижники справа: читаем ${\displaystyle \sigma \to \tau \to \rho }$ в качестве ${\displaystyle \sigma \to (\tau \to \rho )}$.

Чтобы определить типы, мы начнем с фиксации набора базовые типы, ${\displaystyle B}$. Иногда их называют атомные типы или же константы типа. С этим исправленным синтаксисом типов будет:

${\displaystyle \tau ::=\tau \to \tau \mid T\quad \mathrm {where} \quad T\in B}$.

Например, ${\displaystyle B=\{a,b\}}$, генерирует бесконечный набор типов, начиная с ${\displaystyle a,b,}$${\displaystyle a\to a,}$${\displaystyle a\to b,b\to b,}$${\displaystyle b\to a,}$${\displaystyle a\to (a\to a),\ldots ,}$${\displaystyle (b\to a)\to (a\to b),\ldots }$

Также фиксируем набор константы для базовых типов. Например, мы можем предположить, что базовый тип нац, а термин «константы» может быть натуральным числом. В исходной презентации Черч использовал только два базовых типа: ${\displaystyle o}$ для "типа предложений" и ${\displaystyle \iota }$ для «типа лиц». Тип ${\displaystyle o}$ не имеет констант, тогда как ${\displaystyle \iota }$ имеет одну постоянную члена. Часто исчисление только с одним базовым типом, обычно ${\displaystyle o}$, Считается.

Синтаксис просто типизированного лямбда-исчисления по сути аналогичен самому лямбда-исчислению. Мы пишем ${\displaystyle x{\mathbin {:}}\tau }$ чтобы обозначить, что переменная ${\displaystyle x}$ относится к типу ${\displaystyle \tau }$. Таким образом, синтаксис термина в BNF:

${\displaystyle e::=x\mid \lambda x{\mathbin {:}}\tau .e\mid e\,e\mid c}$

куда ${\displaystyle c}$ - термальная постоянная.

То есть, ссылка на переменную, абстракции, заявление, и постоянный. Ссылка на переменную ${\displaystyle x}$ является граница если он находится внутри привязки абстракции ${\displaystyle x}$. Срок закрыто если нет несвязанных переменных.

Сравните это с синтаксисом нетипизированного лямбда-исчисления:

${\displaystyle e::=x\mid \lambda x.e\mid e\,e}$

Мы видим, что в типизированном лямбда-исчислении каждая функция (абстракция) должен указывать тип своего аргумента.

Правила набора

Чтобы определить набор хорошо типизированных лямбда-терминов данного типа, мы определим типизирующее отношение между терминами и типами. Сначала введем контексты ввода или же окружающая среда для набора текста ${\displaystyle \Gamma ,\Delta ,\dots }$, которые представляют собой наборы предположений о типизации. А допущение набора имеет форму ${\displaystyle x{\mathbin {:}}\sigma }$, смысл ${\displaystyle x}$ имеет тип ${\displaystyle \sigma }$.

В типизация отношения ${\displaystyle \Gamma \vdash e{\mathbin {:}}\sigma }$ указывает, что ${\displaystyle e}$ это термин типа ${\displaystyle \sigma }$ в контексте ${\displaystyle \Gamma }$. В этом случае ${\displaystyle e}$ как говорят хорошо напечатанный (имеющий тип ${\displaystyle \sigma }$). Экземпляры отношения типизации называются печатать суждения. Обоснованность заключения о типировании демонстрируется предоставлением печатание вывода, построенный с использованием правила набора текста (при этом посылки над линией позволяют сделать вывод под линией). Лямбда-исчисление с простой типизацией использует следующие правила:

${\displaystyle {\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x{\mathbin {:}}\sigma }}}$ (1)	${\displaystyle {\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c{\mathbin {:}}T}}}$ (2)
${\displaystyle {\frac {\Gamma ,x{\mathbin {:}}\sigma \vdash e{\mathbin {:}}\tau }{\Gamma \vdash (\lambda x{\mathbin {:}}\sigma .~e){\mathbin {:}}(\sigma \to \tau )}}}$ (3)	${\displaystyle {\frac {\Gamma \vdash e_{1}{\mathbin {:}}\sigma \to \tau \quad \Gamma \vdash e_{2}{\mathbin {:}}\sigma }{\Gamma \vdash e_{1}~e_{2}{\mathbin {:}}\tau }}}$ (4)

Прописью,

1. Если ${\displaystyle x}$ имеет тип ${\displaystyle \sigma }$ в контексте мы знаем, что ${\displaystyle x}$ имеет тип ${\displaystyle \sigma }$.
2. Терминные константы имеют соответствующие базовые типы.
3. Если в определенном контексте с ${\displaystyle x}$ имеющий тип ${\displaystyle \sigma }$, ${\displaystyle e}$ имеет тип ${\displaystyle \tau }$, то в том же контексте без ${\displaystyle x}$, ${\displaystyle \lambda x{\mathbin {:}}\sigma .~e}$ имеет тип ${\displaystyle \sigma \to \tau }$.
4. Если в определенном контексте ${\displaystyle e_{1}}$ имеет тип ${\displaystyle \sigma \to \tau }$, и ${\displaystyle e_{2}}$ имеет тип ${\displaystyle \sigma }$, тогда ${\displaystyle e_{1}~e_{2}}$ имеет тип ${\displaystyle \tau }$.

Примеры закрытых условий, т.е. термины, вводимые в пустом контексте, следующие:

• Для любого типа ${\displaystyle \tau }$, термин ${\displaystyle \lambda x{\mathbin {:}}\tau .x{\mathbin {:}}\tau \to \tau }$ (тождественная функция / I-комбинатор),
• Для типов ${\displaystyle \sigma ,\tau }$, термин ${\displaystyle \lambda x{\mathbin {:}}\sigma .\lambda y{\mathbin {:}}\tau .x{\mathbin {:}}\sigma \to \tau \to \sigma }$ (K-комбинатор) и
• Для типов ${\displaystyle \tau ,\tau ',\tau ''}$, термин ${\displaystyle \lambda x{\mathbin {:}}\tau \to \tau '\to \tau ''.\lambda y{\mathbin {:}}\tau \to \tau '.\lambda z{\mathbin {:}}\tau .xz(yz):(\tau \to \tau '\to \tau '')\to (\tau \to \tau ')\to \tau \to \tau ''}$ (S-комбинатор).

Это типизированные представления лямбда-исчисления основных комбинаторов комбинаторная логика.

Каждый тип ${\displaystyle \tau }$ присваивается заказ, номер ${\displaystyle o(\tau )}$. Для базовых типов ${\displaystyle o(T)=0}$; для типов функций, ${\displaystyle o(\sigma \to \tau )={\mbox{max}}(o(\sigma )+1,o(\tau ))}$. То есть порядок типа измеряет глубину самой левой стрелки. Следовательно:

${\displaystyle o(\iota \to \iota \to \iota )=1}$

${\displaystyle o((\iota \to \iota )\to \iota )=2}$

Семантика

Внутренние и внешние интерпретации

Вообще говоря, есть два разных способа присвоения значения просто типизированному лямбда-исчислению, как и типизированным языкам в более общем смысле, иногда называемым внутренний против. внешний, или же Церковь -стиль против. Карри -стиль.^[1]Внутренняя семантика / семантика в стиле Чёрча присваивает значение только хорошо типизированным терминам или, точнее, придает значение непосредственно типизированным производным. Это приводит к тому, что термины, различающиеся только аннотациями типов, тем не менее, могут иметь разные значения. Например, термин идентичности ${\displaystyle \lambda x{\mathbin {:}}{\mathtt {int}}.~x}$ на целых числах и тождественном члене ${\displaystyle \lambda x{\mathbin {:}}{\mathtt {bool}}.~x}$ на логических значениях может означать разные вещи. (Классические предполагаемые интерпретации - это функция идентичности для целых чисел и функция идентичности для логических значений.) Напротив, внешняя семантика / стиль Карри присваивает значение терминам независимо от набора текста, поскольку они будут интерпретироваться на нетипизированном языке. С этой точки зрения ${\displaystyle \lambda x{\mathbin {:}}{\mathtt {int}}.~x}$ и ${\displaystyle \lambda x{\mathbin {:}}{\mathtt {bool}}.~x}$ означают то же самое (т.е., то же самое, что и ${\displaystyle \lambda x.~x}$).

Различие между внутренней и внешней семантикой иногда связано с наличием или отсутствием аннотаций в лямбда-абстракциях, но, строго говоря, такое использование неточно. Можно определить семантику в стиле Карри для аннотированных терминов, просто игнорируя типы (т.е., через стирание типа ), поскольку можно дать семантику в стиле Чёрча на неаннотированных терминах, когда типы могут быть выведены из контекста (т.е., через вывод типа ). Существенное различие между внутренним и внешним подходами состоит только в том, рассматриваются ли правила типизации как определение языка или как формализм для проверки свойств более примитивного базового языка. Большинство различных семантических интерпретаций, обсуждаемых ниже, можно рассматривать либо с точки зрения Черча, либо с точки зрения Карри.

Теория уравнений

Просто типизированное лямбда-исчисление имеет то же эквациональная теория βη-эквивалентности при нетипизированное лямбда-исчисление, но с учетом ограничений типа. Уравнение для бета-уменьшение

${\displaystyle (\lambda x{\mathbin {:}}\sigma .~t)\,u=_{\beta }t[x:=u]}$

в контексте ${\displaystyle \Gamma }$ в любое время ${\displaystyle \Gamma ,x{\mathbin {:}}\sigma \vdash t{\mathbin {:}}\tau }$ и ${\displaystyle \Gamma \vdash u{\mathbin {:}}\sigma }$, а уравнение для эта редукция

${\displaystyle \lambda x{\mathbin {:}}\sigma .~t\,x=_{\eta }t}$

держится всякий раз, когда ${\displaystyle \Gamma \vdash t\!:\sigma \to \tau }$ и ${\displaystyle x}$ не кажется свободным в ${\displaystyle t}$.

Операционная семантика

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

Категориальная семантика

Просто типизированное лямбда-исчисление (с ${\displaystyle \beta \eta }$-эквивалентность) - внутренний язык из Декартовы закрытые категории (CCCs), как впервые заметил Ламбек. Для любого конкретного CCC основными типами соответствующего лямбда-исчисления являются просто объекты, а условия морфизмы. И наоборот, каждое просто типизированное лямбда-исчисление дает CCC, объектами которого являются типы, а морфизмы - классы эквивалентности терминов.

Чтобы прояснить соответствие, конструктор типов для Декартово произведение обычно добавляется к вышеуказанному. Чтобы сохранить категоричность декартова произведения, добавляют правила типа за спаривание, проекция, а единичный член. Учитывая два условия ${\displaystyle s{\mathbin {:}}\sigma }$ и ${\displaystyle t{\mathbin {:}}\tau }$, период, термин ${\displaystyle (s,t)}$ имеет тип ${\displaystyle \sigma \times \tau }$. Точно так же, если у кого-то есть срок ${\displaystyle u{\mathbin {:}}\tau _{1}\times \tau _{2}}$, то есть термины ${\displaystyle \pi _{1}(u){\mathbin {:}}\tau _{1}}$ и ${\displaystyle \pi _{2}(u){\mathbin {:}}\tau _{2}}$ где ${\displaystyle \pi _{i}}$ соответствуют проекциям декартова произведения. В единичный член, типа 1, записывается как ${\displaystyle ()}$ и звучит как "ноль", это последний объект. Аналогичным образом расширяется эквациональная теория, так что

${\displaystyle \pi _{1}(s{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )=s{\mathbin {:}}\sigma }$

${\displaystyle \pi _{2}(s{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )=t{\mathbin {:}}\tau }$

${\displaystyle (\pi _{1}(u{\mathbin {:}}\sigma \times \tau ),\pi _{2}(u{\mathbin {:}}\sigma \times \tau ))=u{\mathbin {:}}\sigma \times \tau }$

${\displaystyle t{\mathbin {:}}1=()}$

Последнее читается как "если t имеет тип 1, то он сводится к нулю".

Вышеупомянутое затем можно превратить в категорию, взяв типы в качестве объекты. В морфизмы ${\displaystyle \sigma \to \tau }$ находятся классы эквивалентности пар ${\displaystyle (x{\mathbin {:}}\sigma ,t{\mathbin {:}}\tau )}$ куда Икс переменная (типа ${\displaystyle \sigma }$) и т это термин (типа ${\displaystyle \tau }$), не имеющий в себе свободных переменных, кроме (опционально) Икс. Закрытие получается из карри и заявление, как обычно.

Точнее, существуют функторы между категорией декартовых замкнутых категорий и категорией просто типизированных лямбда-теорий.

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

Теоретико-доказательная семантика

Просто типизированное лямбда-исчисление тесно связано с импликационным фрагментом пропозиционального интуиционистская логика, т.е. минимальная логика, через Изоморфизм Карри – Ховарда: термины точно соответствуют доказательствам в естественный вычет, и жилые типы точно тавтологии минимальной логики.

Альтернативные синтаксисы

Представленное выше представление - не единственный способ определить синтаксис просто типизированного лямбда-исчисления. Одна из альтернатив - полностью удалить аннотации типов (чтобы синтаксис был идентичен нетипизированному лямбда-исчислению), при этом обеспечивая правильную типизацию терминов с помощью Вывод типа Хиндли-Милнера. Алгоритм вывода является завершающим, надежным и завершенным: всякий раз, когда термин является типизированным, алгоритм вычисляет его тип. Точнее, он вычисляет термин основной тип, так как часто неаннотированный термин (например, ${\displaystyle \lambda x.~x}$) может иметь более одного типа (${\displaystyle {\mathtt {int}}\to {\mathtt {int}}}$, ${\displaystyle {\mathtt {bool}}\to {\mathtt {bool}}}$и т. д., которые все являются экземплярами основного типа ${\displaystyle \alpha \to \alpha }$).

Другое альтернативное представление просто типизированного лямбда-исчисления основано на двунаправленная проверка типов, который требует большего количества аннотаций типов, чем вывод Хиндли – Милнера, но его легче описать. В система типов делится на два приговора, представляющих оба проверка и синтез, написано ${\displaystyle \Gamma \vdash e\Leftarrow \tau }$ и ${\displaystyle \Gamma \vdash e\Rightarrow \tau }$ соответственно. В функциональном отношении три компонента ${\displaystyle \Gamma }$, ${\displaystyle e}$, и ${\displaystyle \tau }$ все входы на контрольное решение ${\displaystyle \Gamma \vdash e\Leftarrow \tau }$, тогда как обобщающее суждение ${\displaystyle \Gamma \vdash e\Rightarrow \tau }$ только берет ${\displaystyle \Gamma }$ и ${\displaystyle e}$ в качестве входных данных, производя тип ${\displaystyle \tau }$ как выход. Эти суждения основаны на следующих правилах:

${\displaystyle {\frac {x{\mathbin {:}}\sigma \in \Gamma }{\Gamma \vdash x\Rightarrow \sigma }}}$ [1]	${\displaystyle {\frac {c{\text{ is a constant of type }}T}{\Gamma \vdash c\Rightarrow T}}}$ [2]
${\displaystyle {\frac {\Gamma ,x{\mathbin {:}}\sigma \vdash e\Leftarrow \tau }{\Gamma \vdash \lambda x.~e\Leftarrow \sigma \to \tau }}}$ [3]	${\displaystyle {\frac {\Gamma \vdash e_{1}\Rightarrow \sigma \to \tau \quad \Gamma \vdash e_{2}\Leftarrow \sigma }{\Gamma \vdash e_{1}~e_{2}\Rightarrow \tau }}}$ [4]
${\displaystyle {\frac {\Gamma \vdash e\Rightarrow \tau }{\Gamma \vdash e\Leftarrow \tau }}}$ [5]	${\displaystyle {\frac {\Gamma \vdash e\Leftarrow \tau }{\Gamma \vdash (e{\mathbin {:}}\tau )\Rightarrow \tau }}}$ [6]

Обратите внимание, что правила [1] - [4] почти идентичны правилам (1) - (4) выше, за исключением тщательного выбора проверочных или обобщающих суждений. Этот выбор можно объяснить так:

1. Если ${\displaystyle x{\mathbin {:}}\sigma }$ находится в контексте, мы можем синтезировать тип ${\displaystyle \sigma }$ за ${\displaystyle x}$.
2. Типы термических констант фиксированы и могут быть синтезированы.
3. Чтобы проверить это ${\displaystyle \lambda x.~e}$ имеет тип ${\displaystyle \sigma \to \tau }$ в некотором контексте мы расширяем контекст с помощью ${\displaystyle x{\mathbin {:}}\sigma }$ и проверьте это ${\displaystyle e}$ имеет тип ${\displaystyle \tau }$.
4. Если ${\displaystyle e_{1}}$ синтезирует тип ${\displaystyle \sigma \to \tau }$ (в некотором контексте), и ${\displaystyle e_{2}}$ проверяет тип ${\displaystyle \sigma }$ (в том же контексте), то ${\displaystyle e_{1}~e_{2}}$ синтезирует тип ${\displaystyle \tau }$.

Обратите внимание, что правила синтеза читаются сверху вниз, а правила проверки - снизу вверх. Обратите внимание, в частности, что мы делаем нет нужны какие-либо аннотации к лямбда-абстракции в правиле [3], потому что тип связанной переменной может быть выведен из типа, по которому мы проверяем функцию. Наконец, мы объясняем правила [5] и [6] следующим образом:

5. Чтобы проверить это ${\displaystyle e}$ имеет тип ${\displaystyle \tau }$, достаточно синтезировать тип ${\displaystyle \tau }$.
6. Если ${\displaystyle e}$ проверяет тип ${\displaystyle \tau }$, то явно аннотированный член ${\displaystyle (e{\mathbin {:}}\tau )}$ синтезирует ${\displaystyle \tau }$.

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

Общие наблюдения

Учитывая стандартную семантику, просто типизированное лямбда-исчисление сильно нормализующий: то есть хорошо типизированные термины всегда сводятся к значению, т. е. ${\displaystyle \lambda }$ абстракция. Это связано с тем, что рекурсия не разрешена правилами типизации: невозможно найти типы для комбинаторы с фиксированной точкой и член цикла ${\displaystyle \Omega =(\lambda x.~x~x)(\lambda x.~x~x)}$. Рекурсию можно добавить в язык, используя специальный оператор ${\displaystyle {\mathtt {fix}}_{\alpha }}$типа ${\displaystyle (\alpha \to \alpha )\to \alpha }$ или добавив общие рекурсивные типы, хотя оба исключают сильную нормализацию.

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

Важные результаты

• В 1967 году Тейт показал, что ${\displaystyle \beta }$-восстановление сильно нормализующий. Как следствие ${\displaystyle \beta \eta }$-эквивалентность разрешимый. Статман показал в 1977 году, что проблема нормализации не элементарный рекурсивный, доказательство, которое позже было упрощено Майерсоном (1992). Доказательство чисто семантической нормализации (см. нормализация оценкой ) был дан Бергером и Швихтенбергом в 1991 году.
• В объединение проблема для ${\displaystyle \beta \eta }$-эквивалентность неразрешима. В 1973 году Хуэ показал, что объединение третьего порядка неразрешимо, и это было улучшено Бакстером в 1978 году, а затем Гольдфарбом в 1981 году, показав, что объединение второго порядка уже неразрешимо.Доказательство того, что сопоставление более высокого порядка (унификация, где только один член содержит экзистенциальные переменные) разрешимо, было объявлено Колином Стирлингом в 2006 году, а полное доказательство было опубликовано в 2009 году.^[2]
• Мы можем кодировать натуральные числа по типу ${\displaystyle (o\to o)\to (o\to o)}$ (Церковные цифры ). Швихтенберг показал в 1976 г., что в ${\displaystyle \lambda ^{\to }}$ точно расширенный многочлены могут быть представлены как функции над числами Чёрча; это примерно полиномы, замкнутые под условным оператором.
• А полная модель из ${\displaystyle \lambda ^{\to }}$ задается путем интерпретации базовых типов как наборы и типы функций по теоретико-множественной функциональное пространство. Фридман показал в 1975 году, что эта интерпретация полный за ${\displaystyle \beta \eta }$-эквивалентность, если базовые типы интерпретируются бесконечными множествами. Статман показал в 1983 году, что ${\displaystyle \beta \eta }$-эквивалентность - это максимальная эквивалентность, которая типично двусмысленный, т.е. замкнутые относительно подстановок типов (Типичная теорема Статмана о неоднозначности). Следствием этого является то, что конечное свойство модели , т.е. конечных наборов достаточно, чтобы различать термины, не идентифицируемые ${\displaystyle \beta \eta }$-эквивалентность.
• Плоткин ввел логические отношения в 1973 году для характеристики элементов модели, которые можно определить с помощью лямбда-терминов. В 1993 году Юнг и Тюрин показали, что общая форма логического отношения (логические отношения Крипке с разной степенью достоверности) в точности характеризует лямбда-определимость. Плоткин и Статман предположили, что разрешимо ли определимость данного элемента модели, порожденной из конечных множеств, с помощью лямбда-члена (Гипотеза Плоткина – Статмана). В 1993 году Лоадер показал, что это предположение неверно.

Примечания

1. Рейнольдс, Джон (1998). Теории языков программирования. Кембридж, Англия: Издательство Кембриджского университета.
2. Стирлинг, Колин (22 июля 2009 г.). «Разрешимость согласования высшего порядка». Логические методы в информатике. 5 (3): 1–52. arXiv:0907.3804. Дои:10.2168 / LMCS-5 (3: 2) 2009 г..

Рекомендации

• Церковь: Формулировка простой теории типов, JSL 5, 1940
• W.W. Тейт: Интенсиональные интерпретации функционалов конечного типа I, JSL 32 (2), 1967
• Г.Д.Плоткин: Лямбда-определимость и логические отношения, Технический отчет, 1973
• Г.П. Huet: Неразрешимость объединения в логике третьего порядка Информация и контроль 22 (3): 257-267 (1973).
• Х. Фридман: Равенство функционалов. LogicColl. '73, страницы 22-37, LNM 453, 1975.
• Х. Швихтенберг: Функции, определяемые в простом типизированном лямбда-исчислении, Arch. Математическая логика 17 (1976) 113-114.
• Р. Статман: Типизированное лямбда-исчисление не является элементарным рекурсивным методом FOCS 1977: 90-94
• В. Д. Гольдфарб: Неразрешимость проблемы объединения 2-го порядка, TCS (1981), no. 13, 225–230.
• Р. Статман. ${\displaystyle \lambda }$-определяемые функционалы и ${\displaystyle \beta \eta }$ конверсия. Arch. Математика. Логик, 23: 21–26, 1983.
• Я. Ламбек: Декартовы замкнутые категории и типизированные лямбда-исчисления. Комбинаторы и языки функционального программирования 1985: 136-175
• У. Бергер, Х. Швихтенберг: Инверсия оценочного функционала для типизированного лямбда-исчисления LICS 1991: 203-211
• Х. Майерсон: Простое доказательство теоремы Статмана, TCS 103 (2): 387-394, 1992.
• Юнг А., Тюрин Дж .:Новая характеризация лямбда-определимости, TLCA 1993
• Р. Погрузчик: Неразрешимость λ-определимости, появилась в Церковном фестивале, 2001 г.
• Х. Барендрегт, Лямбда-исчисления с типами, Справочник по логике в компьютерных науках, том II, Oxford University Press, 1993. ISBN  0-19-853761-1.
• Л. Бакстер: Неразрешимость проблемы диадического объединения третьего порядка, Информация и контроль 38 (2), 170-178 (1978)

внешняя ссылка

• Погрузчик, Ральф (февраль 1998 г.). «Заметки о простом типизированном лямбда-исчислении».
• "Теория церковных типов" запись в Стэнфордская энциклопедия философии