Editing Fixed-point combinator (section)

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