Supercombinator: Difference between revisions

Revision as of 03:35, 22 April 2005

Latest revision as of 11:09, 22 March 2022

(28 intermediate revisions by 22 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]]

:i) $S has no free variables.

:ii) any lambda abstraction in E is a supercombinator.

:iii) n >= 0, that is there need be no lambdas at all.

==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]]

{{mathcomp-sci-theory-stub}}

[[Category:Formal languages]]