RubyでClojure風loop-recur (末尾再帰) - c4se記：さっちゃんですよ☆

Clojureのloop-recurを、Rubyでやった。Elixirの古いversionにも有ったらしい。
末尾再帰の最適化 (TCO, tail call optimization) が出来ないsystemだと、助かるみたい。Ruby 2.0.0とかClojureみたいな。

def factorial n
  cloop n, 1 do |n, acc|
    if n == 0
      acc
    else
      recur n - 1, acc * n
    end
  end
end

みたいに使ふ。
instance_evalしか知らなくて、instance_execを見附け出すのに一番時間が掛った。アホだ。

Rubyだと、末尾再帰をloopに変換するmethod実装例とかも、検索すれば見附かるけど。
cf. Rubyで末尾再帰最適化をする。 - athosの日記 http://d.hatena.ne.jp/athos/20110119/p1
cf. Rubyの末尾再帰最適化を理解する http://melborne.github.io/2011/01/20/Ruby/
因みに多分、次のversionには入るんじゃないかな。
cf. CRubyで末尾最適化を使った再帰 - yarbの日記 http://d.hatena.ne.jp/yarb/20121029/p1
cf. 10 Things You Didn't Know Ruby Could do - SSSSLIDE http://sssslide.com/speakerdeck.com/jeg2/10-things-you-didnt-know-ruby-could-do#43
個人的にはTCOが無くても、殆どの場合はEnumerableを使へば困ってない。偶に欲しい事が有る。

実装

# coding=utf-8
# license: Public Domain

$DEBUG = true

# {{{ util

# Rubyで、D言語風にassertionを直書きする簡易unit test - c4se記：さっちゃんですよ☆
# http://c4se.hatenablog.com/entry/2013/08/15/022137
#
# @param test_name [String]
def unittest test_name, &proc
  if $DEBUG
    include Test::Unit::Assertions
    proc.call
    puts "#{test_name} ok."
  end
end
if $DEBUG
  require 'test/unit/assertions'
end
# }}}

# loop-recur like Clojure special form
# http://clojure.org/special_forms#Special%20Forms--(recur%20exprs*)
class LoopRecur
  def initialize proc
    @proc = proc
    @params = []
  end

  def eval params = []
    @params = params
    v = self
    while v == self
      v = instance_exec *@params, &@proc
    end
    v
  end

  private
  def recur *params
    @params = params
    self
  end
end

module Kernel
  def cloop *params, &proc
    LoopRecur.new(proc).eval params
  end
end

unittest 'loop-recur works' do
  v = cloop 5, 0 do |n, acc|
    if n <= 0
      acc
    else
      recur n - 1, acc + n
    end
  end
  assert_equal 15, v
end

unittest 'loop-recur can make tail recurusion' do
  v = cloop 1 do |n|
    if n == 10000
      n
    else
      recur n + 1
    end
  end
  assert_equal 10000, v
end
# vim:set et sw=2 sts=2 ff=unix foldmethod=marker:

clojure loop-recur

http://clojure.org/special_forms#Special%20Forms--(recur%20exprs*)
(loop [bindings* ] exprs*)

loop is exactly like let, except that it establishes a recursion point at the top of the loop, with arity equal to the number of bindings. See recur.

(recur exprs*)

Evaluates the exprs in order, then, in parallel, rebinds the bindings of the recursion point to the values of the exprs. If the recursion point was a fn method, then it rebinds the params. If the recursion point was a loop, then it rebinds the loop bindings. Execution then jumps back to the recursion point. The recur expression must match the arity of the recursion point exactly. In particular, if the recursion point was the top of a variadic fn method, there is no gathering of rest args - a single seq (or null) should be passed. recur in other than a tail position is an error.

Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler.
(def factorial
  (fn [n]
    (loop [cnt n acc 1]
       (if (zero? cnt)
            acc
          (recur (dec cnt) (* acc cnt))))))

發想の素

巧みな誘導によりClojureを書かずしてClojure力が向上されるももんが pic.twitter.com/n1LUdtgkI5
— mo (@supermomonga) August 28, 2013