Supercombinator: Difference between revisions

Revision as of 03:00, 25 June 2007

Latest revision as of 11:09, 22 March 2022

(21 intermediate revisions by 18 users not shown)

Line 1:

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

A '''supercombinator''' is a [[mathematical]] [[mathematical expression|expression]] which is [[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]] [[mathematical expression|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.

It may be defined, in mathematical terms, as the following:

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

:A supercombinator, ''S'' of arity ''n'' is a [[lambda]] expression of the form

:λx₁.λx₂...λx_n.''E''

== See also ==

:where ''E'' is not a lambda abstraction, such that:

* [[Lambda lifting]]

:# ''S'' has no free variables.

:# any lambda abstraction in ''E'' is a supercombinator.

:# ''n'' ≥ 0, so that lambdas are not required.

==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:FormalLambda languagescalculus]]

{{math-stub}}

[[Category:Formal languages]]

{{comp-sci-theory-stub}}

[[hr:Superkombinator]]