Исчисление каппа - Kappa calculus

В математическая логика, теория категорий, иИнформатика, исчисление каппа этоформальная система для определения первый заказфункции.

В отличие от лямбда-исчисление, исчисление каппа не имеетфункции высшего порядка; его функции не объекты первого класса. Каппа-исчисление можно рассматривать как «переформулировку фрагмента первого порядка типизированного лямбда-исчисления».^[1]

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

Определение

Приведенное ниже определение было адаптировано из диаграмм на страницах 205 и 207 Hasegawa.^[1]

Грамматика

Исчисление Каппа состоит из типы и выражения дается приведенной ниже грамматикой:

${ Displaystyle тау = 1 мид тау раз тау мид ldots}$

${ displaystyle e = x mid id _ { tau} mid! _ { tau} mid operatorname {lift} _ { tau} (e) mid e circ e mid kappa x: 1 { to} tau .e}$

Другими словами,

• 1 - это тип
• Если ${ displaystyle tau _ {1}}$ и ${ displaystyle tau _ {2}}$ типы тогда ${ Displaystyle тау _ {1} раз тау _ {2}}$ это тип.
• Каждая переменная - это выражение
• Если τ это тип тогда ${ displaystyle id _ { tau}}$ это выражение
• Если τ это тип тогда ${ displaystyle! _ { tau}}$ это выражение
• Если τ - это тип, а e - выражение, тогда ${ displaystyle operatorname {лифт} _ { tau} (e)}$ это выражение
• Если ${ displaystyle e_ {1}}$ и ${ displaystyle e_ {2}}$ тогда выражения ${ displaystyle e_ {1} circ e_ {2}}$ это выражение
• Если x - переменная, τ - это тип, а e - выражение, тогда ${ Displaystyle каппа х {:} 1 { to} тау ;. ; е}$ это выражение

В ${ displaystyle: 1 { to} tau}$ и индексы я бы, !, и ${ displaystyle operatorname {лифт}}$ иногда опускаются, если их можно однозначно определить из контекста.

Сопоставление часто используется как сокращение для комбинации${ displaystyle operatorname {лифт}}$ и состав:

${ displaystyle e_ {1} e_ {2} { overset { operatorname {def}} {=}} e_ {1} circ operatorname {lift} (e_ {2})}$

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

В презентации здесь используются секвенции (${ displaystyle Gamma vdash e: tau}$), а не гипотетические суждения, чтобы облегчить сравнение с просто типизированным лямбда-исчислением. Для этого требуется дополнительное правило Var, которого нет в Hasegawa.^[1]

В исчислении каппа выражение бывает двух типов: тип его источник и тип его цель. Обозначение ${ Displaystyle е: тау _ {1} { то} тау _ {2}}$ используется, чтобы указать, что выражение e имеет исходный тип ${ displaystyle { tau _ {1}}}$ и тип цели ${ displaystyle { tau _ {2}}}$.

Выражениям в исчислении каппа присваиваются типы в соответствии со следующими правилами:

${ Displaystyle {х {:} 1 { to} tau ; in ; Gamma} over { Gamma vdash x: 1 { to} tau}}$	(Вар)
${ displaystyle {} over { vdash id _ { tau} ;: ; tau to tau}}$	(Идентификатор)
${ Displaystyle {} над { vdash! _ { tau} ;: ; tau to 1}}$	(Хлопнуть)
${ Displaystyle { Gamma vdash e_ {1} {:} tau _ {1} { to} tau _ {2} ; ; ; ; ; ; Gamma vdash e_ {2 } {:} tau _ {2} { to} tau _ {3}} over { Gamma vdash e_ {2} circ e_ {1}: tau _ {1} { to} тау _ {3}}}$	(Comp)
${ displaystyle { Gamma vdash e {:} 1 { to} tau _ {1}} over { Gamma vdash operatorname {lift} _ { tau _ {2}} (e) ; : ; tau _ {2} to ( tau _ {1} times tau _ {2})}}$	(Поднимать)
${ Displaystyle { Gamma, ; х {:} 1 { to} tau _ {1} ; vdash ; e: tau _ {2} { to} tau _ {3}} над { Gamma vdash kappa x {:} 1 { to} tau _ {1} ,. , e ;: ; tau _ {1} times tau _ {2} to tau _ {3}}}$	(Каппа)

Другими словами,

• Вар: предполагая ${ displaystyle x: 1 { to} tau}$ позволяет сделать вывод, что ${ displaystyle x: 1 { to} tau}$
• Идентификатор: для любого типа τ, ${ displaystyle id _ { tau}: tau { to} tau}$
• Хлопнуть: для любого типа τ, ${ displaystyle! _ { tau}: tau { to} 1}$
• Комп: если целевой тип ${ displaystyle e_ {1}}$ соответствует типу источника ${ displaystyle e_ {2}}$ они могут быть составлены, чтобы сформировать выражение ${ displaystyle e_ {2} circ e_ {1}}$ с источником типа ${ displaystyle e_ {1}}$ и целевой тип ${ displaystyle e_ {2}}$
• Поднимать: если ${ displaystyle e: 1 { to} tau _ {1}}$, тогда ${ displaystyle operatorname {lift} _ { tau _ {2}} (e): tau _ {2} { to} ( tau _ {1} times tau _ {2})}$
• Каппа: если мы можем сделать вывод, что ${ Displaystyle е: тау _ {2} к тау _ {3}}$ в предположении, что ${ displaystyle x: 1 { to} tau _ {1}}$, то можно сделать вывод без этого предположения который ${ displaystyle kappa x {:} 1 { to} tau _ {1} ,. , e ;: ; tau _ {1} times tau _ {2} to tau _ {3}}$

Равенство

Исчисление Каппа подчиняется следующим равенствам:

• Нейтралитет: Если ${ displaystyle f: tau _ {1} { to} tau _ {2}}$ тогда ${ displaystyle f { circ} id _ { tau _ {1}} = f}$ и ${ displaystyle f = id _ { tau _ {2}} { circ} f}$
• Ассоциативность: Если ${ displaystyle f: tau _ {1} { to} tau _ {2}}$, ${ displaystyle g: tau _ {2} { to} tau _ {3}}$, и ${ displaystyle h: tau _ {3} { to} tau _ {4}}$, тогда ${ Displaystyle (ч { circ} г) { circ} е = ч { circ} (г { circ} f)}$.
• Терминальность: Если ${ displaystyle f {:} tau { to} 1}$ и ${ displaystyle g {:} tau { to} 1}$ тогда ${ displaystyle f = g}$
• Подъем-снижение: ${ displaystyle ( kappa x.f) circ operatorname {лифт} _ { tau} (c) = f [c / x]}$
• Каппа-редукция: ${ Displaystyle каппа х. (ч circ OperatorName {лифт} _ { тау} (х)) = ч}$ если x не свободен в h

Последние два равенства - это правила редукции для исчисления, переписываемые слева направо.

Характеристики

Тип 1 можно рассматривать как тип единицы. По этой причине любые две функции с одинаковым типом аргумента и типом результата 1 должно быть равно - поскольку существует только одно значение типа 1 обе функции должны возвращать это значение для каждого аргумента (Терминальность).

Выражения с типом ${ displaystyle 1 { to} tau}$ могут рассматриваться как «константы» или значения «типа земли»; это потому что 1 - это тип единицы, поэтому функция этого типа обязательно является постоянной функцией. Обратите внимание, что правило каппа допускает абстракции только тогда, когда абстрагируемая переменная имеет тип ${ displaystyle 1 { to} tau}$ для некоторых τ. Это основной механизм, обеспечивающий первоочередность всех функций.

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

Исчисление Каппа предназначено быть внутренним языкомконтекстно полный категории.

Примеры

Выражения с несколькими аргументами имеют исходные типы, которые являются двоичными деревьями с "несбалансированным вправо". Например, функция f с тремя аргументами типов A, B и C и типом результата D будет иметь тип

${ Displaystyle е: А раз (В раз (С раз 1)) к D}$

Если мы определим левоассоциативное сопоставление ${ displaystyle f ; c}$ как сокращение для ${ Displaystyle (е circ OperatorName {лифт} (с))}$, то - предполагая, что${ displaystyle a: 1 { to} A}$, ${ displaystyle b: 1 { to} B}$, и${ displaystyle c: 1 { to} C}$ - мы можем применить эту функцию:

${ Displaystyle е ; а ; б ; с ;: ; 1 к D}$

Поскольку выражение ${ Displaystyle е ; а ; б ; с}$ имеет тип источника 1, это «основное значение», которое может быть передано в качестве аргумента другой функции. Если ${ displaystyle g: (D times E) { to} F}$, тогда

${ Displaystyle г ; (е ; а ; б ; с) ;: ; от E до F}$

Очень похоже на каррированную функцию типа${ displaystyle A { to} (B { to} (C { to} D))}$ в лямбда-исчислении возможно частичное применение:

${ Displaystyle е ; а ;: ; В раз (С раз 1) к D}$

Однако нет более высоких типов (т.е. ${ Displaystyle ( тау { то} тау) { то} тау}$) вовлечены. Обратите внимание: поскольку исходный тип е а не является 1, следующее выражение не может быть хорошо типизировано при упомянутых выше предположениях:

${ Displaystyle ч ; (е ; а)}$

Поскольку для нескольких аргументов используется последовательное приложение, нет необходимости знать арность функции для определения ее типизации; например, если мы знаем, что${ displaystyle c: 1 { to} C}$ тогда выражение

j c

хорошо напечатан, пока j имеет тип

${ Displaystyle (С раз альфа) { то} бета}$ для некоторых α

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

История

Первоначально представил Барендрегт^[2] термин «функциональная полнота» в контексте комбинаторной алгебры. Исчисление Каппа возникло благодаря усилиям Ламбека^[3] сформулировать подходящий аналог функциональной полноты для произвольных категорий (см. Hermida, Jacobs,^[4] секция 1). Позже Хасегава разработал каппакалькулус в удобный (хотя и простой) язык программирования, включающий арифметику над натуральными числами и примитивную рекурсию.^[1] Подключения к стрелки позже были исследованы^[5] от Power, Thielecke и др.

Варианты

Можно исследовать версии исчисления каппа ссубструктурные типы Такие как линейный, аффинный,и упорядоченный типы. Эти расширения требуют устранения или ограничения ${ displaystyle! _ { tau}}$ выражение. В таких обстоятельствах × Оператор типа не является настоящим декартовым произведением и обычно записывается ⊗ чтобы прояснить это.

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