hp12c
29 January 2009

SchemeとRubyで高階関数を学ぼう

「計算機プログラムの構造と解釈」という本を図書館で借りた プログラマー必読の名著で Amazonによればこれ1冊でコンピュータのすべてがわかるらしい 主著者はLISPの一方言であるSchemeという言語を作った人で 本書もSchemeで書かれている Ruby以外知らない自分には新鮮で大変勉強になる

最初の方に高階手続きによる抽象という章がある 高階手続きというのは手続きを扱う手続き つまり手続きの引数として手続きを取ったり 手続きを値として返す手続きのことだ

Rubyにもそういう表現力があるので 同じことをRubyでもできるか試してみよう

高階手続き

最初に以下の似たような3つの手続きを考える

  1. aからbまでの整数の和を計算する(sum_integers)
  2. 与えられた範囲の整数の三乗の和を計算する(sum_cubes)
  3. 級数の項の並びの和を計算する(pi_sum)

これらをSchemeで表現すると通常次のようになる

(define (sum_integers a b)
	(if (> a b)
	     0
	     (+ a (sum_integers (+ a 1) b))))
		
 (define (sum_cubes a b)
	(if (> a b)
	     0
	     (+ (sum_cubes (+ a 1) b))))
		
 (define (pi_sum a b)
	(if (> a b)
	     0
	     (+ (/ 1.0 (* a (+ a 2))) (pi_sum (+ a 4) b))))

defineの後に手続き名と引数をカッコで括って置き 続けて手続きの実体を置く

Rubyでは以下のように表現される

def sum_integers(a, b)
   if a > b
     0
   else
     a + sum_integers(a+1, b)
   end
 end
 def sum_cubes(a, b)
   if a > b
     0
   else
     cube(a) + sum_cubes(a+1, b)
   end
 end
 def pi_sum(a, b)
   if a > b
     0
   else
     1.0/(a*(a+2)) + pi_sum(a+4, b)
   end
 end

見ての通り3つの手続きの実体は共通のパターンを持っている 加算するaの関数とaの次の値を計算する関数が違うだけだ これらをterm, nextと記号化し 3つの手続きで共通する総和sumという概念を表現する Schemeでは以下のようになる

(define (sum term a next b)
	(if (> a b)
	     0
	     (+ (term a)
		   (sum term (next a) next b))))

手続きsumにはtermとnextがその引数として加わる その取り扱いに特別なものはない Schemeではこのような手続きを引数として取る手続きが 自然な形で書ける

sum手続きを使って先の3つの手続きを完成させるには 以下のように手続きを加える

(define (inc n) (+ n 1))					
 (define (sum_cubes a b)
	(sum cube a inc b))
 (sum_cubes 1 10)
 3025
 (define (identity x) x)
 (define (sum_integers a b)
	(sum identity a inc b))
	
 (sum_integers 1 10)
 55
 (define (pi_sum a b)
	(define (pi_term x)
		(/ 1.0 (* x (+ x 2))))
	(define (pi_next x)
		(+ x 4))
	(sum pi_term a pi_next b))
	
 (* 8 (pi_sum 1 1000))
 3.139592655589783

sum_cubesとsum_integersのためにincを定義し pi_sumのためにpi_termとpi_nextを定義している pi_term,pi_nextは汎用性が低いからpi_sumの中で定義している それぞれに固有の手続きをsumのtermとnextに渡すことで 共通のsum手続きを用いて3つの異なる演算が実現できる

これをRubyで表現してみよう まずはsumメソッドから

def sum(term, a, _next, b)
   if a > b
     0
   else
     term.call(a) + sum(term, _next.call(a), _next, b)
   end
 end

Schemeと異なりRubyでは手続きはオブジェクトではない だけど手続きをオブジェクトにすることはできる この手続きオブジェクトの起動にはcallが必要だ

このsumメソッドを使って先の3つの手続きを完成させよう

def cube(n)
   n**3
 end
 def inc(n)
   n + 1
 end
 def sum_cubes(a, b)
   sum(method(:cube), a, method(:inc), b)
 end
 sum_cubes(1, 10) # => 3025
 def identity(n)
   n
 end
 def sum_integers(a, b)
   sum(method(:identity), a, method(:inc), b)
 end
 sum_integers(1, 10) # => 55
 def pi_sum(a, b)
   def pi_term(x)
     1.0/(x*(x+2))
   end
   def pi_next(x)
     x + 4
   end
   sum(method(:pi_term), a, method(:pi_next), b)
 end
 8 * pi_sum(1, 1000) # => 3.13959265558978

Rubyではメソッドをオブジェクト化するのに Object#methodメソッドを使いメソッド名をシンボルで渡す pi_sumメソッドのように メソッド定義の中にメソッド定義をした場合 Rubyでは外側のメソッドの呼び出し時に 内側のメソッドが定義される

lambda

Schemeに戻ろう 先の高階手続きにおいてその引数として使うためだけに pi_termやpi_nextの手続きを定義するのは煩わしい このような場合lambdaが使える lambdaを使ったpi_sum手続きは以下のようになる

(define (pi_sum a b)
	(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
	a
	(lambda (x) (+ x 4))
	b))
;元のpi_sum手続き
 (define (pi_sum a b)
	(define (pi_term x)
		(/ 1.0 (* x (+ x 2))))
	(define (pi_next x)
		(+ x 4))
	(sum pi_term a pi_next b))

元のpi_sum手続きにおける sumの引数pi_term, pi_nextに直接 手続きを埋め込んでいるのがわかる

Rubyもlambdaを持っているので 同様のことができる

def pi_sum(a, b)
   sum(lambda { |x| 1.0/(x*(x+2)) }, a, lambda { |x| x + 4 }, b)
 end
 #元のpi_sumメソッド
 def pi_sum(a, b)
   def pi_term(x)
     1.0/(x*(x+2))
   end
   def pi_next(x)
     x + 4
   end
   sum(method(:pi_term), a, method(:pi_next), b)
 end

Rubyでは手続きはブロックで表現する

メソッドに渡す手続きが一つなら Rubyではブロックが使える ブロックの起動はyieldを呼ぶ

def sum(a, _next, b)
   if a > b
     0
   else
     yield(a) + sum(_next.call(a), _next, b){ |a| yield a }
   end
 end
 inc = lambda { |i| i + 1 }
 pi_next = lambda { |i| i + 4 }
 sum(1, inc, 10){ |i| i } # => 55
 sum(1, inc, 10){ |i| i**3 } # => 3025
 8 * sum(1, pi_next, 1000){ |i| 1.0/(i*(i+2)) } # => 3.13959265558978

let

Schemeではlambdaは局所変数を作り出すためにも使われる

という関数を計算したい場合 これは以下のように書ける

手続きfにおいてこの途中のa,bも束縛しておきたい そのようなときは補助手続きを定義する

(define (f x y)
	(define (f_helper a b)
		(+ (* x (square a))
		     (* y b)
		     (* a b)))
	(f_helper (+ 1 (* x y))
			 (- 1 y)))

もちろんlambdaが使える

(define (f x y)
	((lambda (a b)
		(+ (* x (square a))
		     (* y b)
		     (* a b)))
	 (+ 1 (* x y))
	 (- 1 y)))

更にletというものが使える letを使えば最初にa,bを定義できる

(define (f x y)
	(let ((a (+ 1 (* x y)))
		(b (- 1 y)))
	  (+ (* x (square a))
	       (* y b)
	       (* a b))))

これら3つのRubyの等価コードは以下のようになる

def f(x, y)
   def f_helper(a, b, x, y)
     x*a**2 + y*b + a*b
   end
   f_helper(1+(x*y), 1-y, x, y)
 end
 def f(x, y)
   f_helper = lambda do |a,b|
     x*a**2 + y*b + a*b
   end
   a = 1+(x*y)
   b = 1-y
   f_helper.call(a, b)
 end
 def f(x, y)
   a = 1+(x*y)
   b = 1-y
   x*a**2 + y*b + a*b
 end

一番上のコードにおいて Rubyではローカル変数はメソッドを透過できないので 明示的に引数で受け渡す必要がある

関連記事：Rubyのブロックはメソッドに対するメソッドのMix-inだ！

計算機プログラムの構造と解釈

ジェラルド・ジェイ サスマン, ジュリー サスマン, and ハロルド エイブルソン (追記:2009/2/1）タイトルを「RubyでSchemeの高階関数を学ぼう」から「SchemeでRubyの高階関数を学ぼう」に変えました (追記:2009/2/5)　タイトルを「SchemeでRubyの高階関数を学ぼう」から「SchemeとRubyで高階関数を学ぼう」に変えました

blog comments powered by Disqus
ruby_pack8

100円〜で好評発売中！
M'ELBORNE BOOKS