When I touched Haskell after writing "Basic representation of lambda calculus using Python lambda expressions" for various reasons, it executed an anonymous recursive function. Since the fixed-point combinator fix was ridiculously easy to write, I tried to see if it could be done in other programming languages in the same way, but it was also easy, so I wrote a new article as a summary memo.
I know that Qiita, books, and the Internet have more stars than the number of stars, but Y Combinator accounts for a large proportion of this kind of story (in fact, the original article). However, I hope that it will be regarded as one of the many reference materials of people who are interested. Tsukkomi, editing requests are welcome.
A fixed point combinator is a function $ g $ that holds $ f (g (f)) = g (f) $. In this article, Haskell's name fix is used as the function name of the fixed point combinator.
Haskell（GHC）
The fixed point combinator is defined according to the equation.
python
Prelude> fix f = f (fix f)
The results of operation confirmation using an anonymous function that calculates the Fibonacci number are as follows. Anonymous functions are intentionally curried.
python
Prelude> fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1 40
102334155
Prelude> map (fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1) [0..10]
[0,1,1,2,3,5,8,13,21,34,55]
Prelude> map (fix (\fib -> \f1 -> \f2 -> \n -> if n == 0 then f1 else fib f2 (f1+f2) (n-1)) 0 1) [0,10..50]
[0,55,6765,832040,102334155,12586269025]
Scheme（Gauche）
The fixed point combinator is defined according to the equation.
python
gosh> (define (fix f) (f (fix f)))
fix
The results of operation confirmation using an anonymous function that calculates the Fibonacci number are as follows. ** * Caution: Dangerous depending on the execution environment! ** **
python
gosh> ((((fix (lambda (fib) (lambda (n) (lambda (f1) (lambda (f2) (if (= n 0) f1 (((fib (- n 1)) f2) (+ f1 f2)))))))) 40) 0) 1)
;Not displayed forever → Forced termination
[Perform argument evaluation first](https://ja.wikipedia.org/wiki/%E8%A9%95%E4%BE%A1%E6%88%A6%E7%95%A5#%E5%80 Due to the specification of% A4% E5% 91% BC% E3% 81% B3), for (f (fix f)), (fix f) is executed before f and it falls into an infinite loop. , It seems that the memory was consumed.
Since the same phenomenon occurs in the Y combinator, it is a lambda expression that has the second argument x as an argument, which is the original argument of the anonymous recursive function, as in the conversion to the Z combinator that actually operates. By enclosing and making (lambda (x) ((fix f) x)), the execution is deferred until (fix f) is actually needed. Note that Haskell arguments are not evaluated until they are actually needed (one of the lazy evaluation functions), so this problem does not occur.
python
gosh> (define (fix f) (f (lambda (x) ((fix f) x))))
fix
The results of checking the operation of the rewritten fixed point combinator using an anonymous function that calculates the Fibonacci number are as follows.
python
gosh> ((((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155
gosh> (map (((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) (iota 11))
(0 1 1 2 3 5 8 13 21 34 55)
gosh> (map (((fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (((fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) (iota 6 0 10))
(0 55 6765 832040 102334155 12586269025)
Python（Python3，Python2） Since it is known that the argument evaluation is performed first, the fixed point combinator is defined with the same contents as the rewritten Scheme definition. Note that assigning a lambda expression directly to a variable is not recommended for PEP8, and the general description method is to return a function defined internally (with closure) ** return a function **, so we followed it. Make a definition.
python
>>> def fix(f):
... def ret(x):
... return fix(f)(x)
... return f(ret)
...
>>>
The results of operation confirmation using an anonymous function that calculates the Fibonacci number are as follows.
python
>>> fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1)(40)
102334155
>>> list(map(fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1), range(11)))
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> list(map(fix(lambda fib: lambda f1: lambda f2: lambda n: f1 if n == 0 else fib(f2)(f1+f2)(n-1))(0)(1), range(0,51,10)))
[0, 55, 6765, 832040, 102334155, 12586269025]
Ruby（CRuby，JRuby） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition.
python
fix = -> f { f.( -> x { fix.(f).(x) }) }
p fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(40)
# => 102334155
p (0..10).map { |x| fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(x) }
# => [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
p (0..50).step(10).map { |x| fix.(-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib.(f2).(f1+f2).(n-1) } } } }).(0).(1).(x) }
# => [0, 55, 6765, 832040, 102334155, 12586269025]
JavaScript（Node.js） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition.
fix = f => f(x => fix(f)(x))
console.log(fix(fib => f1 => f2 => n => n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)(40))
// => 102334155
console.log([...Array(11).keys()].map(fix(fib => f1 => f2 => n=> n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)))
// => [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ]
console.log([...Array(6)].map((v,k)=>k*10).map(fix(fib => f1 => f2 => n=> n == 0 ? f1 : fib(f2)(f1+f2)(n-1))(0)(1)))
// => [ 0, 55, 6765, 832040, 102334155, 12586269025 ]
Scala（Scala 2.11 + Java VM 12） In Scala, function arguments (although the mechanism is different from Haskell) are not evaluated until they are actually needed, so you should just write the definition of the immobility combinator as it is, but it is also a strongly typed language, and the arguments and return values The type of must be specified in advance. Here, the definition with the same contents as the rewritten Scheme definition is performed, including typing. The type is specified at the time of actual call.
python
scala> def fix[T1, T2](f:(T1=>T2)=>(T1=>T2))(x:T1):T2=f(fix(f))(x)
fix: [T1, T2](f:(T1=>T2)=>(T1=>T2))(x:T1)T2
The results of operation confirmation using an anonymous function that calculates the Fibonacci number are as follows.
scala> fix[BigInt,(BigInt => (BigInt => BigInt))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1)(40)
res0: BigInt = 102334155
scala> (0 to 10).map(fix[Int,(Int => (Int => Int))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1))
res1: scala.collection.immutable.IndexedSeq[Int] = Vector(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55)
scala> (0 to 50 by 10).map(fix[BigInt,(BigInt => (Int => BigInt))](fib=>f1=>f2=>n=>if(n==0)f1elsefib(f2)(f1+f2)(n-1))(0)(1))
res2: scala.collection.immutable.IndexedSeq[BigInt] = Vector(0, 55, 6765, 832040, 102334155, 12586269025)
Perl（perl 5） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition.
python
sub fix {
my $f = shift;
return $f->( sub { my $x = shift; return fix($f)->($x); })
};
print fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->(40), "\n";
# => 102334155
@r = map { fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->($_) } (0..10);
print "@r ", "\n"; # => 0 1 1 2 3 5 8 13 21 34 55
@r = map { fix( sub { my $fib = shift; return sub { my $o = shift; return sub { my $p = shift; return sub { my $n = shift; return $n == 0 ? $o : $fib->($p)->($o + $p)->($n - 1); }; }; }; })->(0)->(1)->($_) } (0,10,20,30,40,50);
print "@r ", "\n"; # => 0 55 6765 832040 102334155 12586269025
PHP（PHP 7.3，PHP 7.4） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition. Since 7.4, a simpler anonymous function definition has become possible, so it is shown together with the notation up to 7.3.
<?php
// for PHP 7.3
function fix73($f) {
return $f(function($x) use ($f) { return fix73($f)($x); });
};
echo fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1)(40) . PHP_EOL;
// => 102334155
foreach(array_map(
fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1), range(0,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 1 1 2 3 5 8 13 21 34 55
foreach(array_map(
fix73(
function($g) {
return function($f1) use ($g) {
return function($f2) use ($f1,$g) {
return function($n) use ($f2,$f1,$g) {
return $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1);
};
};
};
}
)(0)(1), range(0,50,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 55 6765 832040 102334155 12586269025
// for PHP 7.4
function fix74($f) { return $f( fn($x) => fix74($f)($x)); }
echo fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1)(40) . PHP_EOL;
// => 102334155
foreach(array_map(fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1), range(0,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 1 1 2 3 5 8 13 21 34 55
foreach(array_map(fix74(fn($g) => fn($f1) => fn($f2) => fn($n) => $n == 0 ? $f1 : $g($f2)($f1+$f2)($n-1))(0)(1), range(0,50,10)) as $v) { print($v); echo ' '; } echo "\n";
// => 0 55 6765 832040 102334155 12586269025
Julia（Version 1.0.5） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition.
julia> fix(f) = f(x -> fix(f)(x))
fix (generic function with 1 method)
julia> fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1)(40)
102334155
julia> map(fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1), 0:10)
11-element Array{Int64,1}:
0
1
1
2
3
5
8
13
21
34
55
julia> map(fix(g -> f1 -> f2 -> n -> n == 0 ? f1 : g(f2)(f1+f2)(n-1))(0)(1), 0:10:50)
6-element Array{Int64,1}:
0
55
6765
832040
102334155
12586269025
Common Lisp（SBCL 2.0.0） The following is the result of checking the operation using an anonymous function that calculates the Fibonacci number and the definition of a fixed point combinator that has the same contents as the rewritten Scheme definition.
* (defun fix (f) (funcall f (lambda (x) (funcall (fix f) x))))
FIX
* (funcall (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155
* (mapcar (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 1 2 3 4 5 6 7 8 9 10))
(0 1 1 2 3 5 8 13 21 34 55)
* (mapcar (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 10 20 30 40 50))
(0 55 6765 832040 102334155 12586269025)
Since it needs to be statically scoped, enable lexical-binding. Other than that, it is the same as Common Lisp.
*** Welcome to IELM *** Type (describe-mode) for help.
ELISP> (setq lexical-binding t)
t
ELISP> (defun fix (f) (funcall f (lambda (x) (funcall (fix f) x))))
fix
ELISP> (funcall (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) 40)
102334155 (#o606277313, #x6197ecb)
ELISP> (defun map (f l)
(if (null l) '()
(cons (funcall f (car l)) (map f (cdr l)))))
map
ELISP> (map (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 1 2 3 4 5 6 7 8 9 10))
(0 1 1 2 3 5 8 13 21 34 55)
ELISP> (map (funcall (funcall (fix (lambda (fib) (lambda (f1) (lambda (f2) (lambda (n) (if (= n 0) f1 (funcall (funcall (funcall fib f2) (+ f1 f2)) (- n 1)))))))) 0) 1) '(0 10 20 30 40 50))
(0 55 6765 832040 102334155 12586269025)
In R language, function arguments are not evaluated until they are actually needed (lazy evaluation), so the definition of the fixed point combinator can be described as it is.
> fix <- function(f) { f(fix(f)) }
The results of operation confirmation using an anonymous function that calculates the Fibonacci number are as follows.
> fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1)(40)
[1] 102334155
> Map(fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1), list(0,1,2,3,4,5,6,7,8,9,10))
[[1]]
[1] 0
[[2]]
[1] 1
[[3]]
[1] 1
[[4]]
[1] 2
[[5]]
[1] 3
[[6]]
[1] 5
[[7]]
[1] 8
[[8]]
[1] 13
[[9]]
[1] 21
[[10]]
[1] 34
[[11]]
[1] 55
> Map(fix(function(fib) { function(f1) { function(f2) { function(n) { if (n == 0) f1 else fib(f2)(f1+f2)(n-1) } } } })(0)(1), list(0,10,20,30,40,50))
[[1]]
[1] 0
[[2]]
[1] 55
[[3]]
[1] 6765
[[4]]
[1] 832040
[[5]]
[1] 102334155
[[6]]
[1] 12586269025
"Anonymous function" in programming is a function. Refers to a function definition that has only arguments without a name. Since it is not necessary to use the function definition syntax, you can receive the function definition as an argument "[Higher-order function](https://ja.wikipedia.org/wiki/%E9%AB%98%E9%9A%8E%E9%96] It is often used to add a small arbitrary process to "% A2% E6% 95% B0)". Higher-order functions include those that can return the function definition as a return value.
The biggest drawback of anonymous functions is that they define a "recursive function" because there is no function name. Both to do and to do so require a special method. As a method, you can prepare a separate higher-order function that allows you to call yourself with the name of your argument, or allow the execution environment to automatically remember the location of the anonymous function and call itself with a special name. There is something (Wikipedia "Anonymous recursion" reference).
In this article, as a higher-order function for anonymous recursion, "[Fixed Point Combinator](https://ja.wikipedia.org/wiki/%E4%B8%8D%E5%8B%95%E7%82%B9%" It focuses on how to define E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF). There are various functions in fixed point combinators, and the most famous one is Y combinator, which is often shown as an anonymous function. % E5% 8B% 95% E7% 82% B9% E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF # Y % E3% 82% B3% E3% 83% B3% E3% 83% 93% E3% 83% 8D% E3% 83% BC% E3% 82% BF). This article describes a fixed point combinator that can be defined without being particularly conscious of the Y combinator. The following is an example of describing the Z combinator in Python, which makes the Y combinator available in the language of argument pre-evaluation.
print(
(lambda f:
(lambda x: f(lambda y: x(x)(y)))
(lambda x: f(lambda y: x(x)(y)))
)
(lambda fib: lambda f1: lambda f2: lambda n:
f1 if n == 0 else fib(f2)(f1+f2)(n-1)
)(0)(1)(40)
)
# => 102334155
Regarding the execution of an anonymous function by a fixed-point combinator, the first argument of the anonymous function is the name for the anonymous function itself to call the anonymous function itself, and the second argument is the original argument required by the anonymous function. Since only one original argument is assumed, in this execution example, the anonymous function is manually "curryed" (https://ja.wikipedia.org/wiki/%) using the function of the higher-order function. E3% 82% AB% E3% 83% AA% E3% 83% BC% E5% 8C% 96) ”, and after making it possible to call multiple arguments with only one argument specification, adjust the order of argument application. And a simpler description is made. * Reference: "Cheat sheet"
fix