各言語による無名再帰処理の実行例まとめ

先に作成した拙作記事『Rubyのアロー演算子を用いたラムダ計算の基礎表現』の最後に記載した，関数処理本体に自己適用パターンを埋め込んだ無名再帰処理について，他のプログラミング言語でも実行してみた結果をあらためて記事にしました．実用性の薄い技術記事ですが，関数型プログラミングに関する教養程度に捉えていただけますと幸いです．

この記事の無名再帰処理は，40番目のフィボナッチ数 を求める定義としています．再帰処理として定義通りに実装すると関数呼び出しが指数的に増加して膨大な時間がかかるため，末尾再帰による事実上の繰り返し処理に変更しています．この処理を無名関数化し，ラムダ式$(\lambda g . g g)(\lambda g . g g)$で示される無名ループ処理を更に埋め込んでいます．

各言語による実行例

記述が長くなることから，字句解析できる程度に空白等を詰めた記述を行っています．

Python

>>> (lambda g:g(g))(lambda g:lambda a,b,n:a if n==0 else g(g)(b,a+b,n-1))(0,1,40)
102334155

Ruby

>> ->g{g[g]}[->g{->(a,b,n){n==0?a:g[g][b,a+b,n-1]}}][0,1,40]
=> 102334155

JavaScript (Node.js)

> (g=>g(g))(g=>(a,b,n)=>n==0?a:g(g)(b,a+b,n-1))(0,1,40)
102334155

Julia

julia> (g->g(g))(g->(a,b,n)->n==0 ? a : g(g)(b,a+b,n-1))(0,1,40)
102334155

Scheme

> (((lambda(g)(g g))(lambda(g)(lambda(a b n)(if(= n 0)a((g g)b(+ a b)(- n 1))))))0 1 40)
102334155

Common Lisp (Emacs Lisp)

Emacs Lispでは(setq lexical-binding t)でレキシカルスコープ対応にして実行．

(funcall(funcall(lambda(g)(funcall g g))(lambda(g)(lambda(a b n)(if(= n 0)a(funcall(funcall g g)b (+ a b) (- n 1))))))0 1 40)
102334155

R言語

> (function(g){g(g)})(function(g){function(a,b,n){if(n==0)a else g(g)(b,a+b,n-1)}})(0,1,40)
[1] 102334155

Lua

> (function(g)return g(g)end)(function(g)return function(a,b,n)return n==0 and a or g(g)(b,a+b,n-1)end end)(0,1,40)
102334155

Clojure

user=> ((#(% %)#(fn[a b n](if(= n 0)a((% %)b(+ a b)(- n 1)))))0 1 40)
102334155

おまけ：LINE Botにしてみた

Google Apps Script（JavaScript）＋LINE Message APIでお手軽実装．整数は符号付き64ビットなので，78番目まで正確な値が返ってきます．

ソースコードは次の通り．メインはuserMessageとして受け取った受信メッセージを処理するif文です．

var ACCESS_TOKEN = '（アクセストークン）';
var REPLY_URL = 'https://api.line.me/v2/bot/message/reply';

function doPost(e) {
  var replyToken = JSON.parse(e.postData.contents).events[0].replyToken;
  var userMessage = JSON.parse(e.postData.contents).events[0].message.text;
  var headers = {
    'Content-Type': 'application/json; charset=UTF-8',
    'Authorization': 'Bearer ' + ACCESS_TOKEN
  };

  if (userMessage.toLowerCase() == 'help') {
    rMes = '0以上の整数値xを送信するとx番目のフィボナッチ数を返信します．';
  } else {
    if (isNaN(x = Number(userMessage)) || x < 0)
      rMes = '0以上の整数値を送信して下さい．';
    else
      rMes = String((g=>g(g))(g=>(a,b,n)=>n==0?a:g(g)(b,a+b,n-1))(0,1,x))
  }

  var payload = JSON.stringify({
    'replyToken' : replyToken,
    'messages': [{
      'type' : 'text',
      'text' : rMes
    }]
  })

  var options = {
    'headers' : headers,
    'method' : 'post',
    'payload' : payload
  };

  UrlFetchApp.fetch(REPLY_URL, options);
}

備考

記事に関する補足

• Pythonの例がなんとか80文字以内に収まった…！（lambda使いまくってる時点でPEP8的にアウトっぽいけど）

更新履歴

• 2020-12-09：Clojureの例を追加
• 2020-11-20：LINE Botの例を追加
• 2020-11-19：初版公開（Python，Ruby，JavaScript，Julia，Scheme，Common Lisp，R，Lua）