Зависимый тип

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

Очень упрощённо зависимый тип можно представить как тип индексированного семейства множеств. Более формально, для типа ${\displaystyle A:{\mathcal {U}}}$ (где ${\displaystyle {\mathcal {U}}}$ — вселенная типов), можно определить семейство типов ${\displaystyle B}$, сопоставляющее каждому терму ${\displaystyle a:A}$ тип ${\displaystyle B(a):{\mathcal {U}}}$, что записывается как ${\displaystyle B:A\to {\mathcal {U}}}$. Функция, чья область значений варьируется в зависимости от её аргумента, называется зависимой функцией. Тип этой функции называется зависимым произведением типов, пи-типом или просто зависимым типом. Зависимый тип записывается для данного случая как

${\displaystyle \Pi _{(x:A)}B(x)}$

или

${\displaystyle \Pi (x:A),B(x)}$

Если ${\displaystyle B}$ является константой, то зависимый тип упрощается до обычной функции ${\displaystyle A\to B}$. Иначе говоря, ${\displaystyle \Pi _{(x:A)}B}$ равнозначен функциональному типу ${\displaystyle A\to B}$. Название «пи-тип» подчёркивает, что такой тип является декартовым произведением типов. Пи-типы также могут быть представлены как модели кванторов всеобщности.

Например, если ${\displaystyle {\mbox{Vec}}({\mathbb {R} },n)}$ — кортеж из ${\displaystyle n}$ вещественных чисел, то ${\displaystyle \Pi _{(n:{\mathbb {N} })}{\mbox{Vec}}({\mathbb {R} },n)}$ — тип функций, которые для всякого натурального ${\displaystyle n}$ возвращают кортеж вещественных чисел размера ${\displaystyle n}$. Обычное Функциональное пространство является тем частным случаем, когда область значений не зависит от входного параметра: например, ${\displaystyle \Pi _{(n:{\mathbb {N} })}\;{\mathbb {R} }}$ — тип функций из натуральных в вещественные, обозначаемых ${\displaystyle {\mathbb {N} }\to {\mathbb {R} }}$ в просто типизированном лямбда-исчислении.

Полиморфные функции являются важным примером зависимых функций, то есть функций, имеющих зависимый тип. Для некоторого заданного типа такие функции обрабатывают значения этого типа, или значения типа, построенного на основе этого типа. Полиморфная функция, возвращающая значения типа ${\displaystyle C}$, будет иметь полиморфный тип, записываемый как

${\displaystyle \Pi _{(A:{\mathcal {U}})}A\to C}$

• Chlipala, A. Certified Programming with Dependent Types: A Pragmatic Introduction to the Coq Proof Assistant. — MIT Press, 2013. — 440 p. — ISBN 9780262026659. (текст с сайта автора (англ.))
• Jeremy Paul Condit. Dependent Types for Safe Systems Software. — PhD dissertation. — University of California at Berkeley, 2007.