Kappa calculus

Uses your system voice; voice and rate in settings.

Snapshot

≈ 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.

Provenance

snapshot enwiki-001320783335 · captured 1762453062.0 · version history

Cite this page as: encyclopegia.org, “Kappa calculus”, snapshot enwiki-001320783335. https://encyclopegia.org/a/kappa-calculus

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.