Supercombinator: Difference between revisions

Revision as of 12:34, 13 July 2010

Latest revision as of 11:09, 22 March 2022

(16 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|Bound and self-contained mathematical expression}}

A '''supercombinator''' is a [[mathematical expression]] which is [[Free variables and bound variables|fully-bound]] and [[self-contained]]. It may either be a [[constant]] or a [[combinator]] where all the subexpressions are supercombinators.

{{disputed|date=November 2015}}

{{cleanup-rewrite|date=November 2015}}

A '''supercombinator''' is a [[mathematical expression]] which is [[Free variables and bound variables|fully- bound]] and [[self-contained]]. It may either be either a [[constant (mathematics)|constant]] or a [[combinator]] where all the subexpressions are supercombinators. Supercombinators are used in the implementation of functional languages.

In mathematical terms, a [[lambda expression]] ''S'' is a supercombinator of [[arity]] ''n'' if it has no free variables and is of the form λx₁.λx₂...λx_n.''E'' (with ''n'' ≥ 0, so that lambdas are not required) such that ''E'' itself is not a [[lambda abstraction]] and any lambda abstraction in ''E'' is again a supercombinator.

In mathematical terms, a [[Lambda calculus|lambda expression]] ''S'' is a supercombinator of [[arity]] ''n'' if it has no free variables and is of the form λxλx₁.λxλx₂...λxλx_n.''E'' (with ''n'' ≥ 0, so that lambdas are not required) such that ''E'' itself is not a [[lambda abstraction]] and any lambda abstraction in ''E'' is again a supercombinator.

==References==

*S. L. Peyton Jones, ''The Implementation of Functional Programming Languages''. Prentice Hall, 1987.

== See also ==

{{comp-sci-theory-stub}}

* [[Lambda lifting]]

==References==

*S. L. Peyton Jones, ''[https://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/ The Implementation of Functional Programming Languages]''. Prentice Hall, 1987.

[[Category:Functional programming]]

[[Category:Implementation of functional programming languages]]

[[Category:Lambda calculus]]

[[hr:Superkombinator]]

{{comp-sci-theory-stub}}

[[ru:Суперкомбинаторы]]