Kappa calculus
≈ 3 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematical logic, category theory, and computer science, kappa calculus is a formal system for defining first-order functions. Unlike lambda calculus, kappa calculus has no higher-order functions; its functions are not first class objects. Kappa-calculus can be regarded as "a reformulation of the first-order fragment of typed lambda calculus". Because its functions are not first-class objects, evaluation of kappa calculus expressions does not require closures.
In mathematical logic, category theory, and computer science, kappa calculus is a formal system for defining first-order functions. Unlike lambda calculus, kappa calculus has no higher-order functions; its functions are not first class objects. Kappa-calculus can be regarded as "a reformulation of the first-order fragment of typed lambda calculus".
Because its functions are not first-class objects, evaluation of kappa calculus expressions does not require closures. \tau = 1 \mid \tau\times\tau \mid \ldots e = x \mid id_\tau \mid !_\tau \mid \operatorname{lift}_\tau(e) \mid e \circ e \mid \kappa x:1{\to}\tau . e In other words, 1 is a type If \tau_1 and \tau_2 are types then \tau_1\times\tau_2 is a type.
Background
Every variable is an expression If is a type then id_\tau is an expression If is a type then !_\tau is an expression If is a type and e is an expression then \operatorname{lift}_\tau(e) is an expression If e_1 and e_2 are expressions then e_1\circ e_2 is an expression If x is a variable, is a type, and e is an expression, then \kappa x{:}1{\to}\tau\;.\;e is an expression The :1{\to}\tau and the subscripts of , , and \operatorname{lift} are sometimes omitted when they can be unambiguously determined from the context.
Juxtaposition is often used as an abbreviation for a combination of \operatorname{lift} and composition: e_1 e_2\ \overset\operatorname{def}{=}\ e_1 \circ \operatorname{lift}(e_2) Neutrality: If f:\tau_1{\to}\tau_2 then f{\circ}id_{\tau_1}=f and f=id_{\tau_2}{\circ}f Associativity: If f:\tau_1{\to}\tau_2 , g:\tau_2{\to}\tau_3 , and h:\tau_3{\to}\tau_4 , then (h{\circ}g){\circ}f = h{\circ}(g{\circ}f) .
Terminality: If f{:}\tau{\to}1 and g{:}\tau{\to}1 then f=g Lift-Reduction: (\kappa x.f)\circ \operatorname{lift}_\tau(c) = f[c/x] Kappa-Reduction: \kappa x. (h\circ \operatorname{lift}_\tau(x)) = h if x is not free in h The last two equalities are reduction rules for the calculus, rewriting from left to right.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1320783335 under CC BY-SA 4.0; modifications have been made.