Programming Language Theory: Difference between revisions
| Line 16: | Line 16: | ||
<pre>C-term ::= C-app | C-prim | var | <pre>C-term ::= C-app | C-prim | var | ||
C-app ::= C-term C-term</pre> | C-app ::= C-term C-term</pre> | ||
====Divergent Combinators==== | |||
The ''omega'' combinator is divergent (a non-terminating redux): | |||
* <tt>omega </tt> | |||
====Fixed-Point Combinators==== | ====Fixed-Point Combinators==== | ||
For a function F, its set of ''fixed points'' are those inputs which map to themselves. Provided algebraic functions, for instance, fixed points of a function F(x) would be found by setting <i>F(x) = x</i> and solving for the roots. Provided an ordered, finite domain, looping through the domain will find all solutions. For an infinite ordered domain, looping is a semi-decision: if there is a least fixed point, it will be found, but the loop never terminates otherwise. The ''fixed-point combinators'' compute the fixed points of their functional inputs. Curry's ''Y-combinator'' was the first: | For a function F, its set of ''fixed points'' are those inputs which map to themselves. Provided algebraic functions, for instance, fixed points of a function F(x) would be found by setting <i>F(x) = x</i> and solving for the roots. Provided an ordered, finite domain, looping through the domain will find all solutions. For an infinite ordered domain, looping is a semi-decision: if there is a least fixed point, it will be found, but the loop never terminates otherwise. The ''fixed-point combinators'' compute the fixed points of their functional inputs. Curry's ''Y-combinator'' was the first: | ||