Posted at

RubyでClojure風loop-recur (末尾再帰)

More than 5 years have passed since last update.

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の日記

cf. Rubyの末尾再帰最適化を理解する

因みに多分、次のversionには入るんじゃないかな。

cf. CRubyで末尾最適化を使った再帰 - yarbの日記

cf. 10 Things You Didn't Know Ruby Could do - SSSSLIDE

個人的にはTCOが無くても、殆どの場合はEnumerableを使へば困ってない。偶に欲しい事が有る。


実装

# 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
start
end

private
def start
v = self
while v == self
v = instance_exec *@params, &@proc
end
v
end

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:

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