LoginSignup
10
11

More than 3 years have passed since last update.

@ytaki0801(Yozo TAKIZAWA)

不動点コンビネータを用いた無名再帰関数の実行まとめ

Last updated at Posted at 2020-07-29

諸般の理由で『Pythonのlambda式を用いたラムダ計算の基礎表現』を書いた後にHaskellに触れたところ，無名再帰関数を実行する不動点コンビネータfixがとんでもなく簡単に書けたため，同じ方法で他のプログラミング言語でもできないか試したところ，これまたあっさりできたので，まとめメモ的に新しく記事にした．

このような内容がQiitaや書籍，ネット上に星の数の更に星の数乗ほどあることは承知しているが，この手の話はYコンビネータが大きな割合を占めており（実際，元記事でも取り上げている），関心のある人々の数多ある参考資料のひとつ程度に捉えてもらえると幸いである．ツッコミ，編集リクエスト歓迎．

不動点コンビネータの定義

不動点コンビネータとは，$f(g(f))=g(f)$が成り立つ関数$g$を指す．この記事では，Haskellの呼称であるfixを不動点コンビネータの関数名とする．

Haskell（GHC）

式に従い，不動点コンビネータを定義する．

Prelude> fix f = f (fix f)

フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．なお，無名関数はあえてカリー化表記としている．

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）

式に従い，不動点コンビネータを定義する．

gosh> (define (fix f) (f (fix f)))
fix

フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．※注意：実行環境によっては危険！

gosh> ((((fix (lambda (fib) (lambda (n) (lambda (f1) (lambda (f2) (if (= n 0) f1 (((fib (- n 1)) f2) (+ f1 f2)))))))) 40) 0) 1)
; いつまでも表示されず → 強制終了

引数評価を先に行うという仕様上，(f (fix f))について，(fix f)がfより先に実行されて無限ループに陥り，メモリを食い潰していった模様．

同様の現象はYコンビネータでも起こるため，実際に稼働するZコンビネータへの変換と同じく，無名再帰関数の本来の引数である第二引数xを引数にもつlambda式で(fix f)をくくって(lambda (x) ((fix f) x))とすることで，実際に(fix f)が必要とされるまで実行を据え置くようにする．なお，Haskellの引数は実際に必要となるまで評価されない（遅延評価機能のひとつ）ため，このような問題が起こらない．

gosh> (define (fix f) (f (lambda (x) ((fix f) x))))
fix

書き直した不動点コンビネータについて，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

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）

引数評価を先に行うことがわかっているので，書き直したSchemeの定義と同じ内容で不動点コンビネータを定義する．なお，lambda式を直接変数に代入するのはPEP8非推奨であり，内部で（クロージャで）定義した関数を返す関数を返す，という記述方法が一般的であるため，それに従った定義を行う．

>>> def fix(f):
...     def ret(x):
...         return fix(f)(x)
...     return f(ret)
...
>>>

フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

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

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

irb(main):001:0> fix = -> f { f[-> x { fix[f][x] }] }
=> #<Proc:0x00e9a3c0@(irb):1 (lambda)>
irb(main):002:0> fix[-> fib { -> f1 { -> f2 { -> n { n == 0 ? f1 : fib[f2][f1+f2][n-1] } } }}][0][1][40]
=> 102334155
irb(main):003:0> (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]
irb(main):004:0> (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）

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

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）

Scalaでは，（Haskellとは仕組みは違うものの）関数の引数は実際に必要となるまで評価されないため，不動点コンビネータの定義そのままを記述すれば良いはずだが，強い型付け言語でもあり，引数や戻り値の型をあらかじめ指定しなければならない．ここでは，書き直したSchemeの定義と同じ内容の定義を，型付けを含めて行う．なお，どのような型とするかは，実際の呼び出し時に指定するようにしている．

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

フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

scala> fix[BigInt,(BigInt => (BigInt => BigInt))](fib => f1 => f2 => n => if (n == 0) f1 else fib(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) f1 else fib(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) f1 else fib(f2)(f1+f2)(n-1))(0)(1))
res2: scala.collection.immutable.IndexedSeq[BigInt] = Vector(0, 55, 6765, 832040, 102334155, 12586269025)

Perl（perl 5）

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

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）

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．なお，7.4から，よりシンプルな無名関数定義が可能となったため，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）

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

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）

書き直したSchemeの定義と同じ内容の不動点コンビネータの定義，および，フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

* (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)

Emacs Lisp（GNU Emacs 24.1以降）

静的スコープとする必要があるため，lexical-bindingを有効にする．それ以外は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)

R言語

R言語では，関数の引数は実際に必要となるまで評価されないため（遅延評価），不動点コンビネータの定義そのままを記述すれば良い．

> fix <- function(f) { f(fix(f)) }

フィボナッチ数計算を行う無名関数を用いた動作確認を行った結果は次の通り．

> 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

補足説明

無名関数，高階関数

プログラミングにおける『無名関数』とは，関数名を持たずに引数のみを持つ関数定義のことを指す．関数定義構文を用いる必要がないため，関数定義を引数として受け取れる『高階関数』への小さな任意処理の埋め込み追加などによく用いられる．なお，高階関数は，関数定義を戻り値として返すことができるものも含まれる．

再帰関数，無名再帰

無名関数の最大の欠点は，関数名がないために，『再帰関数』を定義するのも実行するのも，特別な方法が必要となることである．その方法としては，自身の引数の名前で自身を呼び出せるようにしてくれる高階関数を別途用意したり，実行環境が無名関数の場所を自動的に覚えて特別な名前で自身を呼び出せるようにしたりといったものがある（Wikipedia『無名再帰』を参照）．

不動点コンビネータ

この記事では，無名再帰のための高階関数として『不動点コンビネータ』を定義する方法に焦点を当てている．不動点コンビネータには様々な関数があり，その中でも有名なのが，自身も無名関数として示されることが多いYコンビネータである．この記事では，Yコンビネータを特に意識しなくとも定義できる不動点コンビネータについて述べている．なお，Yコンビネータを引数先行評価の言語でも利用できるようにしたZコンビネータのPythonでの記述例は次の通り．

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

カリー化

不動点コンビネータによる無名関数の実行については，無名関数の第一引数を無名関数自身が無名関数自身を呼び出すための名前とし，第二引数を無名関数が必要とする本来の引数としている．想定されている本来の引数はひとつのみなので，今回の実行例では，高階関数の機能を利用して無名関数を手動で『カリー化』し，複数の引数をひとつの引数指定のみで呼び出せるようにした上で，引数の適用順番を調整してよりシンプルな記述を行っている．※参考：『カリー化チートシート』

備考

記事に関する補足

  • 概説に留めたいため，この記事では正確な定義や位置付けは述べていない．
  • 各言語の例は，高階関数記述のチートシート代わりになるかもしれない．
  • PythonのPEP8非推奨は高階関数大好き人間にはやっぱりつらたん．
  • タグは最大5つなので，フォロワーが多い順にて言語名を付けている．不本意ながら．

変更履歴

  • 2020-08-12：R言語の例を追加
  • 2020-08-12：Common Lisp，Emacs Lispの例を追加
  • 2020-08-10：補足説明にPythonのZコンビネータの例を追記
  • 2020-08-06：Juliaの例を追加
  • 2020-08-03：PHPの例を追加（別記事コメントより）
  • 2020-08-01：不動点コンビネータの関数名をfixに統一
  • 2020-08-01：補足説明にカリー化を追加
  • 2020-08-01：引数先行評価対策の記述を整理
  • 2020-08-01：Perlの例を追加
  • 2020-07-31：Scalaの例を追加
  • 2020-07-31：JavaScriptの例を追加
  • 2020-07-31：無名関数の例をフィボナッチ数計算＋mapに変更
  • 2020-07-30：Rubyの例を追加
  • 2020-07-30：無名関数の例をカリー化末尾再帰のフィボナッチ数計算に変更
  • 2020-07-29：初版公開（Haskell，Scheme，Python）
10
11
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
10
11