LoginSignup
1

More than 1 year has passed since last update.

無名相互再帰の記述例(各言語まとめ)

Last updated at Posted at 2021-07-16

これやらこれと同じ趣旨のお遊び記事です.

相互再帰は,複数の関数の間で呼び出し合うことで再帰となっているものです.関数それぞれは自分自身を呼び出す自己再帰ではなく,気づかず無限ループとなってしまったということもある形式です.言語記述解析では,文章構造(構文)が相互再帰となっていることもあって,むしろ積極的に使われることが多い形式でもあります.

この相互再帰を,様々なプログラミング言語のラムダ式(無名関数,無名メソッド)のみでやってみようというのがこの記事の趣旨です.

相互再帰の例(偶数奇数判定)

Pythonでの記述例は次の通り.余りを求める演算なしに定義できる例でもあるのですが,1を引くたびに関数呼び出しをしているため,値が大きくなるとほとんどの言語処理系で再帰制限エラーとなります.

Python(3.7.3)
>>> def even(x): return True if x == 0 else odd(x - 1)
... 
>>> def odd(x): return False if x == 0 else even(x - 1)
... 
>>> even(100)
True
>>> odd(100)
False
>>> even(101)
False
>>> odd(101)
True
>>> even(998)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 1, in even
  File "<stdin>", line 1, in odd
  File "<stdin>", line 1, in even
  File "<stdin>", line 1, in odd
  ...
  File "<stdin>", line 1, in odd
  File "<stdin>", line 1, in even
RecursionError: maximum recursion depth exceeded in comparison
>>>

ラムダ式による相互再帰

ラムダ式による自己再帰は不動点コンビネータを用いることになりますが,今回は自己ではないので,他者(?)を呼び出す仕組みが必要となります.呼び出すための名前を大域環境で付けることができないのであれば,大域環境に相当するラムダ式を用意して名前束縛すれば良いことになります.ただし,ラムダ式は通常レキシカルスコープであるため,上位ラムダ式の引数として束縛した名前のラムダ式同士がお互いの名前を使用することは,そのままではできません原初LISP評価器や当初のEmacs Lispはダイナミックスコープのため可能です).ここでは,上位ラムダ式で束縛した名前をお互いの引数とすることで解決することを考えます.

上記の考え方に沿って相互再帰の例をPythonで書き直した記述例は次の通り.

Python(3.7.3)
>>> (lambda even,odd: even(100,even,odd))(
...  lambda x,even,odd: True  if x == 0 else  odd(x-1,even,odd),
...  lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
True
>>> (lambda even,odd: odd(100,even,odd))(
...  lambda x,even,odd: True  if x == 0 else  odd(x-1,even,odd),
...  lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
False
>>> (lambda even,odd: even(101,even,odd))(
...  lambda x,even,odd: True  if x == 0 else  odd(x-1,even,odd),
...  lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
False
>>> (lambda even,odd: odd(101,even,odd))(
...  lambda x,even,odd: True  if x == 0 else  odd(x-1,even,odd),
...  lambda x,even,odd: False if x == 0 else even(x-1,even,odd))
True
>>>

各言語での記述例

Python以外の記述例を次に示しますが,いずれの記述もリファレンス実装のPython版と同じ構造であるため,ラムダ式や三項演算子などの記述方法の違いの一覧程度の意味しかないかもしれません(ヒドス).

Scheme(Gauche0.9.10)
gosh> ((lambda (even odd) (even 100 even odd))
       (lambda (x even odd) (if (= x 0) #t (odd  (- x 1) even odd)))
       (lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#t
gosh> ((lambda (even odd) (odd 100 even odd))
       (lambda (x even odd) (if (= x 0) #t (odd  (- x 1) even odd)))
       (lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#f
gosh> ((lambda (even odd) (even 101 even odd))
       (lambda (x even odd) (if (= x 0) #t (odd  (- x 1) even odd)))
       (lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#f
gosh> ((lambda (even odd) (odd 101 even odd))
       (lambda (x even odd) (if (= x 0) #t (odd  (- x 1) even odd)))
       (lambda (x even odd) (if (= x 0) #f (even (- x 1) even odd))))
#t
gosh> 
Ruby(2.5.5/irb--simple-prompt)
>> ->even,odd{even[100,even,odd]}[
?>   ->x,even,odd{x==0 ? true  :  odd[x-1,even,odd]},
?>   ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> true
>> ->even,odd{odd[100,even,odd]}[
?>   ->x,even,odd{x==0 ? true  :  odd[x-1,even,odd]},
?>   ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> false
>> ->even,odd{even[101,even,odd]}[
?>   ->x,even,odd{x==0 ? true  :  odd[x-1,even,odd]},
?>   ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> false
>> ->even,odd{odd[101,even,odd]}[
?>   ->x,even,odd{x==0 ? true  :  odd[x-1,even,odd]},
?>   ->x,even,odd{x==0 ? false : even[x-1,even,odd]}]
=> true
>>
JavaScript(Node.js10.24.0)
> ((even,odd)=>even(100,even,odd))(
... (x,even,odd)=>x==0 ? true  :  odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
true
> ((even,odd)=>odd(100,even,odd))(
... (x,even,odd)=>x==0 ? true  :  odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
false
> ((even,odd)=>even(101,even,odd))(
... (x,even,odd)=>x==0 ? true  :  odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
false
> ((even,odd)=>odd(101,even,odd))(
... (x,even,odd)=>x==0 ? true  :  odd(x-1,even,odd),
... (x,even,odd)=>x==0 ? false : even(x-1,even,odd))
true
>

備考

更新履歴

  • 2021-07-16:初版公開

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
1