Line 1: Error: Invalid Blog('by Esehara' )

または私は如何にして心配するのを止めてバグを愛するようになったか

>> Zanmemo

あと何かあれは 「esehara あっと じーめーる」 か @esehara まで

問題の定義よりも、それを実現するプロセスに注目してみる

はじめに

 『計算機プログラムの構造と解釈』(以下、SICP)を読んでいたらとてもいいことが書いてあった。

関数と手続きの対照は、もののあり様の記述と、ことのなし方の記述の違いの反映である。あるいは、よくいわれるように、平叙文的知識と命令文的知識の違いである。われわれは数学では通常平叙文的(何である)記述に関心を持つが、一方、計算機科学では命令文的(どうする)記述に関心を持つ。(p.12)

 既に「文系」と「理系」という区分も恥ずかしいのだけれども、ほぼ数学とかそういう素養がない人間にとって、上のような記述は目から落ちた。SICPにおいてなんて「手続き」という言葉を使うのか、といえば、プログラミングというのは、詰まるところ「データ」を如何に加工するかという流れをコードで表している話なのだろうと思う。その加工の過程のことを「手続き」と呼んでいる、という話になるのだろう。

 こんな話をなぜ思い出したのかというと、つい最近、身内の中で、SICPの勉強会をやったばっかりで、そのあたりのことを考えていたからだ。自分はScheme(Lispの一つの方言)はやったことはなかったけれども、関数型言語だったら少しくらいは触っていたし、どういうものか、というのは何となくわかっているつもりであった。

問題

三つの数を引数としてとり、大きい二つの数の和を返す手続きを定義せよ。

 ……実は、元は二つの数の二乗の和だったのだけれども、上の問題と勘違いしていたので、コードも下のようなかたちになっている。申し訳ない。

 これ自体は余りにも簡単のように見える。実際に、Schemeに慣れていた人は、Listを使ってSortするということをやっていたのだけれども、ここは一つ、あえて関数定義と分岐だけで表現できるか、ということから考えてみる。しかも、関数自体は一つの値しか返せない、ということにしてみよう。

 一番簡単な方法は、三つの引数を大きい順に調べていくことだろう。condは、とりあえずはifみたいなもの、と説明する。

(define (plus-big-two-number x y z)
    (cond 
        ((and (> x y) (> x z))
            (+ x (cond
                    ((> y z) y)
                    ((> z y) z))))
        ((and (> y x) (> y z))
            (+ y (cond
                    ((> x z) x)
            ((> z x) z))))
        ((and (> z y) (> z x))
            (+ z (cond
                    ((> x y) x)
                    ((> y x) y))))))

 確かに、これは不格好ではあるものの、ある流れを示している。つまり、この関数は、次のように疑似コードに書き換えられる。

  • 関数の宣言: plus-big-two-number x y z
    • x が y や z よりも大きいならば、x + ? とする
      • ?には、y と zの大きいほうが入る
    • y が x や z よりも大きいならば、y + ? とする
      • ?には、x か zの大きいほうが入る
    • z が x や y よりも大きいならば、z + ? とする
      • ?には、x や yの大きいほうが入る

 このようなデータの比較を通じて、三値のうちの大きい二値の和を出すことが可能になる。このような流れこそが、たぶん手続きなんだろうなという気がする。とはいえ、これでは冗長すぎる。

 二層目のcondに注目してみると、「二値のうちの大きなほうを一つ返す」というようにとれる。従って、次のような関数を定義する。

(define (if-big x y)
    (cond
        ((> x y) x)
        ((> y x) y)))

 すると、下のように書ける。だいぶ見通しが良くなった。

(define (plus-big-two-number x y z)
    (cond 
        ((and (> x y) (> x z))
            (+ x (if-big y z)))
        ((and (> y x) (> y z))
            (+ y (if-big x z)))
        ((and (> z y) (> z x))
            (+ z (if-big x y)))))

 一つの手続きを「同じもの」として抽象化することにより、同じようなプロセスを書かなくてすむようになる。しかし、これでもまだ冗長すぎる。最初のcondの比較を無くせないものか。

 ここで少し立ち止まって考えてみよう。今回要求されているものは、あくまでも値であって、その大きさをソートする必要はない。和の組み合わせは、実際のところ、下の三つしかない。

  • x + y
  • x + z
  • y + z

 とするならば、先ほど定義したif-bigを使って、次のように定義しなおすことが可能になる。

(define (plus-big-two-number x y z
    (if-big (+ x y)
        (if-big (+ x z) (+ y z))))

 つまり、一番大きな数の組み合わせこそが、一番大きな和の数になるはずである。なので、このような形で、抽象化することができる。このプロセスは、下のように書き直すことができる。

  • 関数を定義する: plus-big-two-number x y z
    • xとyの和を足したものと、?を比較し、大きいほうを返す
      • ?はxとzの和と、yとzの和、どちらか大きいものが入る

 これは冗長ではあるものの、確かに大きな数の二つの和として抽象化されている、と考えられる。

 なるほど、確かに上記で良さそうに見える。実は勉強会のときはそう思って、こうやってブログに記事にしてみると、あることに気がついた。

  • a + b というのは、実は (a + b + c) - c として置き換えることができる。

 このような、恐らく数式的に無意味な言い換えは、今回にとっては重要な役割を果たす。というのも、下のような形で抽象化できるからだ。

  • 関数を定義する: plus-big-two-number x y z
    • x, y, zの和から?を引け
      • ?はx, y, zから一番小さいものである

 さて、いままで考えて来たことを組み合わせるならば、次のような形のパーツとして実現できるだろう。

(define (if-min x y)
    (cond
        ((> x y) y)
        ((> y x) x)))

(define (my-three-min x y z)
    (if-min x (if-min y z)))

(define (plus-big-two-number x y z)
    (- (+ x y z) (my-three-min x y z)))

 これであるならば、二乗の和にも、簡単に対応できるだろう。

まとめ

 元々数学というのがそれほど好きではない自分が、プログラムのことになるとそれなりに楽しめてしまうのは、恐らくは「それを導き出すための過程をどのように道筋として付けてあげるのか」という部分にあるのだろう。そういう風に、何かを入力することによって、何かを出力し、その連鎖が一つの大きなシステムになっているということが好きなのだろう。もちろん、数学もそういう側面があるとは思うけれども。

 あともう一つとして、上記のような簡単なコードですら、ある程度制限された中ではいろいろなアプローチがあり、さらに言うならば、そのアプローチすらも、よりよい形でまとめていくことが可能なのだ、ということも、一つの発見だった。やっぱりプログラミングは奥が深いな、と思う。

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

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

  • 作者: ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン,Gerald Jay Sussman,Julie Sussman,Harold Abelson,和田英一
  • 出版社/メーカー: ピアソンエデュケーション
  • 発売日: 2000/02
  • メディア: 単行本
  • 購入: 35人 クリック: 1,149回
  • この商品を含むブログ (489件) を見る