Типизированное лямбда-исчисление — это типизированный формализм , в котором лямбда-символ ( ) используется для обозначения абстракции анонимной функции. В этом контексте типы обычно представляют собой объекты синтаксической природы, которые присваиваются лямбда-термам; точная природа типа зависит от рассматриваемого исчисления (см. виды ниже). С определенной точки зрения типизированные лямбда-исчисления можно рассматривать как усовершенствования нетипизированного лямбда-исчисления , но с другой точки зрения их также можно считать более фундаментальной теорией, а нетипизированное лямбда-исчисление - особым случаем только с одним типом.
Типизированные лямбда-исчисления являются основополагающими языками программирования и основой типизированных функциональных языков программирования , таких как ML и Haskell , а также, косвенно, типизированных императивных языков программирования . Типизированные лямбда-исчисления играют важную роль в разработке систем типов для языков программирования; здесь типизация обычно отражает желаемые свойства программы (например, программа не вызывает нарушения доступа к памяти).
Типизированные лямбда-исчисления тесно связаны с математической логикой и теорией доказательств через изоморфизм Карри-Говарда , и их можно рассматривать как внутренний язык определенных классов категорий . Например, просто типизированное лямбда-исчисление является языком декартовых закрытых категорий (CCC) [1].
Были изучены различные типизированные лямбда-исчисления. Просто типизированное лямбда-исчисление имеет только один конструктор типа — стрелку , и его единственными типами являются базовые типы и типы функций . Система T расширяет просто типизированное лямбда-исчисление за счет натуральных чисел и примитивной рекурсии более высокого порядка; в этой системе определимы все функции, доказуемо рекурсивные в арифметике Пеано . Система F допускает полиморфизм за счет использования универсальной количественной оценки всех типов; с логической точки зрения он может описать все функции, которые являются доказуемо полными в логике второго порядка . Лямбда-исчисления с зависимыми типами — это основа интуиционистской теории типов , исчисления конструкций и логической структуры (LF), чистого лямбда-исчисления с зависимыми типами. Основываясь на работе Берарди по системам чистых типов , Хенк Барендрегт предложил лямбда-куб для систематизации отношений чисто типизированных лямбда-исчислений (включая просто типизированное лямбда-исчисление, систему F, LF и исчисление конструкций). [ нужна цитата ]
Некоторые типизированные лямбда-исчисления вводят понятие подтипирования , т. е. если является подтипом , то все термины типа также имеют тип . Типизированные лямбда-исчисления с подтипами — это просто типизированные лямбда-исчисления с конъюнктивными типами и системой F <: .
Все системы, упомянутые до сих пор, за исключением нетипизированного лямбда-исчисления, являются строго нормализующими : все вычисления завершаются. Следовательно, они не могут описать все функции , вычислимые по Тьюрингу . [2] Как еще одно следствие, они логически последовательны, т.е. существуют необитаемые типы. Однако существуют типизированные лямбда-исчисления, которые не являются строго нормализующими. Например, зависимо типизированное лямбда-исчисление с типом всех типов (Тип: Тип) не является нормализуемым из-за парадокса Жирара . Эта система также является простейшей системой чистого типа, формализмом, который обобщает лямбда-куб. Системы с явными комбинаторами рекурсии, такие как « Язык программирования для вычислимых функций » Плоткина (PCF), не являются нормализующими, но они не предназначены для интерпретации как логики. Действительно, PCF — это прототип типизированного функционального языка программирования, в котором типы используются для обеспечения правильного поведения программ, но не обязательно для их завершения.
В компьютерном программировании подпрограммы (функции, процедуры, методы) строго типизированных языков программирования близко соответствуют типизированным лямбда-выражениям.
