Типизированное лямбда-исчисление

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

Типовые $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-исчисления являются фундаментальными примитивными языками программирования, которые обеспечивают основу типовым языкам функционального программирования — аппликативным языкам, — среди которых ML и Haskell, а также типовым императивным языкам программирования.

$\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-исчисление с типами является языком декартово-замкнутой категории, что устанавливает прямую связь с такой моделью вычислений, как категориальная абстрактная машина. С одной точки зрения типовые $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-исчисления могут рассматриваться как специализации бестиповых $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-исчислений, а с другой — наоборот, типовые языки могут считаться более фундаментальными, из которых бестиповые получаются как частные случаи. Анализ этого явления дает теория вычислений Д. Скотта.

$\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-исчисление с типами служит основой для разработки новых систем типизации для языков программирования, поскольку именно средствами типов и зависимостей между ними выражаются желаемые свойства программ.

В программировании самостоятельные вычислительные блоки (функции, процедуры, методы) языков программирования с сильной типизацией соответствуют типовым $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$-выражениям.

См. такжеПравить

• Лямбда-куб
• Каррирование
• Просто типизированное лямбда-исчисление
• Полиморфное лямбда-исчисление

ЛитератураПравить

• Friedman H. Equality between functionals. LogicColl. '73, pages 22-37, LNM 453, 1975.
• Barendregt H. Lambda Calculi with Types, Handbook of Logic in Computer Science, Volume II, Oxford University Press.