Editing Fixed-point combinator (section)

==Implementation in other languages==

The Y combinator is a particular implementation of a fixed-point combinator in lambda calculus. Its structure is determined by the limitations of lambda calculus. It is not necessary or helpful to use this structure in implementing the fixed-point combinator in other languages.

Simple examples of fixed-point combinators implemented in some [[programming paradigm]]s are given below.

=== Lazy functional implementation ===

In a language that supports [[lazy evaluation]], as in [[Haskell]], it is possible to define a fixed-point combinator using the defining equation of the fixed-point combinator which is conventionally named <code>fix</code>. Since Haskell has lazy [[data type]]s, this combinator can also be used to define fixed points of data constructors (and not only to implement recursive functions). The definition is given here, followed by some usage examples. In Hackage, the original sample is:<ref>[https://hackage.haskell.org/package/base-4.10.0.0/docs/src/Data.Function.html#fix The original definition in Data.Function].</ref>

<syntaxhighlight lang="haskell">
fix, fix' :: (a -> a) -> a
fix f = let x = f x in x         -- Lambda dropped. Sharing.
                                 -- Original definition in Data.Function.
-- alternative:
fix' f = f (fix' f)              -- Lambda lifted. Non-sharing.

fix (\x -> 9)                    -- this evaluates to 9

fix (\x -> 3:x)                  -- evaluates to the lazy infinite list [3,3,3,...]

fact = fix fac                   -- evaluates to the factorial function
  where fac f 0 = 1
        fac f x = x * f (x-1)

fact 5                           -- evaluates to 120
</syntaxhighlight>

=== Strict functional implementation ===

In a strict functional language, as illustrated below with [[OCaml]], the argument to ''f'' is expanded beforehand, yielding an infinite call sequence,
: <math>f\ (f ... (f\ (\mathsf{fix}\ f))... )\ x</math>.

This may be resolved by defining fix with an extra parameter.

<syntaxhighlight lang=ocaml>
let rec fix f x = f (fix f) x (* note the extra x; hence fix f = \x-> f (fix f) x *)

let factabs fact = function   (* factabs has extra level of lambda abstraction *)
   0 -> 1
 | x -> x * fact (x-1)

let _ = (fix factabs) 5       (* evaluates to "120" *)
</syntaxhighlight>

In a multi-paradigm functional language (one decorated with imperative features), such as [[Lisp (programming language)|Lisp]], [[Peter Landin]] suggested the use of a variable assignment to create a fixed-point combinator,<ref>{{cite journal
 |last1=Landin |first1=P. J. |author1-link=Peter Landin
 |date=January 1964
 |title=The mechanical evaluation of expressions
 |journal=The Computer Journal
 |volume=6
 |issue=4
 |pages=308–320
 |doi=10.1093/comjnl/6.4.308
}}</ref> as in the below example using [[Scheme (programming language)|Scheme]]:

<syntaxhighlight lang="scheme">
(define Y!
  (lambda (f)
    ((lambda (g)                       
       (set! g (f (lambda (x) (g x)))) ;; (set! g expr) assigns g the value of expr,
       g)                              ;; replacing g's initial value of #f, creating 
     #f)))                             ;; thus the truly self-referential value in g
</syntaxhighlight>

Using a lambda calculus with axioms for assignment statements, it can be shown that <code>Y!</code> satisfies the same fixed-point law as the call-by-value Y combinator:<ref>{{cite book |last1=Felleisen |first1=Matthias |author1-link=Matthias Felleisen |year=1987 |title=The Lambda-v-CS Calculus |publisher=Indiana University |url=https://www2.ccs.neu.edu/racket/pubs/#felleisen87}}</ref><ref>{{cite book |last1=Talcott |first1=Carolyn |author1-link=Carolyn Talcott |year=1985 |title=The Essence of Rum: A theory of the intensional and extensional aspects of Lisp-type computation |type=Ph.D. thesis |publisher=Stanford University}}</ref>
: <math>(Y_!\ \lambda x.e) e' = (\lambda x.e)\ (Y_!\ \lambda x.e) e'</math>

In more idiomatic modern Scheme usage, this would typically be handled via a <code>letrec</code> expression, as [[lexical scope]] was introduced to Lisp in the 1970s:

<syntaxhighlight lang="scheme">
(define Y*
  (lambda (f)
    (letrec                           ;; (letrec ((g expr)) ...) locally defines g 
         ((g                          ;; as expr recursively: g in expr refers to 
            (f (lambda (x) (g x)))))  ;; that same g being defined, g = f (λx. g x)
	   g)))                           ;; ((Y* f) ...) = (g ...) = ((f (λx. g x)) ...)
</syntaxhighlight>

Or without the internal label:

<syntaxhighlight lang="scheme">
(define Y
  (lambda (f)
    ((lambda (i) (i i))
     (lambda (i)
       (f (lambda (x)
	        (apply (i i) x)))))))
</syntaxhighlight>

===Imperative language implementation===

This example is a slightly interpretive implementation of a fixed-point combinator.  A class is used to contain the ''fix'' function, called ''fixer''.  The function to be fixed is contained in a class that inherits from fixer.  The ''fix'' function accesses the function to be fixed as a virtual function.  As for the strict functional definition, ''fix'' is explicitly given an extra parameter ''x'', which means that lazy evaluation is not needed.

<syntaxhighlight lang="cpp">
template <typename R, typename D>
class fixer
{
public:
    R fix(D x)
    {
        return f(x);
    }
private:
    virtual R f(D) = 0;
};

class fact : public fixer<long, long>
{
    virtual long f(long x)
    {
        if (x == 0)
        {
            return 1;
        }
        return x * fix(x-1);
    }
};

long result = fact().fix(5);
</syntaxhighlight>

Another example can be shown to demonstrate [[SKI combinator calculus]] (with given bird name from [[combinatory logic]]) being used to build up Z combinator to achieve [[tail call]]-like behavior through trampolining:

<syntaxhighlight lang="js">
var K = a => b => a; // Kestrel
var S = a => b => c => a(c)(b(c)); // Starling
var I = S(K)(K); // Identity
var B = S(K(S))(K); // Bluebird
var C = S(B(B)(S))(K(K)); // Cardinal
var W = C(S)(I); // Warbler
var T = C(I); // Thrush
var V = B(C)(T); // Vireo
var I_ = C(C(I)); // Identity Bird Once Removed; same as C(B(B)(I))(I)
var C_ = B(C); // Cardinal Once Removed
var R_ = C_(C_); // Robin Once Removed
var V_ = B(R_)(C_); // Vireo Once Removed
var I__ = R_(V); // Identity Bird Twice Removed
var Z = B(W(I_))(V_(B)(W(I__)));

var Z2 = S(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))(K(S(S(K))))))(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S))(K))))(K(S(S(K(S(S(K)(K))(S(K)(K))))(S(K(S(K(S))(K)))(S(K(S(S(K)(K))))(K))))(K(S(K(S(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K(S(K(S))(K)))(S))(K(K))))(S(K(S(S(K)(K))))(K))))))(K))))));
	// Alternative fully expanded form.

var Z3 = S(S(K(S(S)(K(S(S(K)(K))(S(K)(K))))))(K))(S(S(K(S))(K))(K(S(S(K(S))(S(K(S(K(S(K(S(K(S(S)(K(K))))(K)))(S)))(S(S(K)(K)))))(K)))(K(K(S(S(K)(K))(S(K)(K))))))));
	// Another shorter version.

var trampoline = fn => {
	let ctx = fn;
	while (ctx instanceof Function)
		ctx = ctx();
	return ctx;
};

var count_fn = self => n =>
	(console.log(n), n === 0)
		? n
		: () => self(n - 1); // Return thunk "() => self(n - 1)" instead.

trampoline(Z(count_fn)(10));
trampoline(Z2(count_fn)(10));
trampoline(Z3(count_fn)(10));
</syntaxhighlight>