Programming Language Theory: Difference between revisions
No edit summary |
|||
| Line 21: | Line 21: | ||
====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 | 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 fixed points of their functional inputs. Curry's ''Y-combinator'' was the first (it always computes the least fixed point): | ||
* <tt>Y ≡ λf. (λx. f (x x)) (λx. f (x x))</tt> (untyped λ-calculus) | * <tt>Y ≡ λf. (λx. f (x x)) (λx. f (x x))</tt> (untyped λ-calculus) | ||
* <tt>Y ≡ S (K (S I I)) (S (S (K S) K) (K (S I I)))</tt> (SKI calculus) | * <tt>Y ≡ S (K (S I I)) (S (S (K S) K) (K (S I I)))</tt> (SKI calculus) | ||
| Line 106: | Line 106: | ||
==Concurrency== | ==Concurrency== | ||
* '''FIXME''' π-calculus, CSS, CSP, petri nets... | * '''FIXME''' π-calculus, CSS, CSP, petri nets... | ||
==Typing== | |||
==Objects== | ==Objects== | ||