技術memo

関数型ゴースト

関数型・オブジェクト指向なプログラミングパラダイムについて思うところ

  • 動機
    1. イメージ論でない言語パラダイムに関する技術ポエム*1を書きたかった。
    2. まともな意見をインターネット空間に1つでも多く残しておきたかった。
  • 要約
    1. オブジェクト指向プログラミングはデータを抽象化する。
    2. 関数型プログラミングでは関数による抽象化を特に重視する。
    3. 言語設計の問題と概念の問題は、混同すべきではない。

オブジェクト指向プログラミング 題材

Consというデータ構造を考えてみます。 Consは任意のデータのペアから成り、その片方をCar、もう片方をCdrと呼びます。

それはJava風に書けば次のようになるでしょう。

public final class Cons{
    private Object car;
    private Object cdr;
    public void setCar(Object x){
        this.car = x;
    }
    public void setCdr(Object x){
        this.cdr = x;
    }
    public Object getCar(){
        return this.car;
    }
    public Object getCdr(){
        return this.cdr;
    }
    public Cons(Object x, Object y){
        this.car = x;
        this.cdr = y;
    }
}

オブジェクト指向風の言い回しをするなら、「Consオブジェクトに、getCarまたはgetCdrというメッセージを送ると、それぞれに格納した値を取得できる」などと言えます。

あるいは、以下の様なインターフェースを実装していると考えても構いません。インターフェースを介してメソッドを呼び出せば、その実体が別の構造に差し替えられたとしても、外部から気づかれることはありません。*2

// Consインターフェース
public interface ICons{
    public void setCar(Object x);
    public void setCdr(Object x);
    public Object getCar();
    public Object getCdr();
}

public class ConsModule{
    // コンストラクタを関数として置いておく
    publis static ICons newCons(Object x, Object y){
        return new Cons(x, y);
    }
    private ConsModule(){
        // モジュール自体のインスタンスは生成させない
    }
}

// Cons実装
public final class Cons implements ICons{
    // 中身は上記と同様なので省略
}

関数オブジェクトで構成するCons

ところで、「無名(インライン)関数が、関数内部から使用された外部の変数への参照を保持し続けられる」ような言語機能のあるプログラミング言語があります。その多くは「ラムダ式」「無名関数」「匿名関数」等と呼ばれますが、ここではそのような言語機能によって生成された実体を指して、関数オブジェクトと単に呼びます。*3

ここで、関数オブジェクトにより、Consというデータ構造は表現できます。*4

それはSchemeで書けば以下のようになります。*5*6

(define (cons* x y)
  (lambda (m) (m x y)))

(define (car* c)
  (c (lambda (x y) x)))

(define (cdr* c)
  (c (lambda (x y) y)))

これを使って値をセットし、取り出してみます。

(define hoge (cons* 'a 'b))

(car* hoge); -> a
(cdr* hoge); -> b

*7

メッセージパッシングスタイルでのConsオブジェクトを実現する

ここで先ほどのJavaでの例が、言語組み込みでオブジェクト指向機能を持たない言語でも実現可能なことが、簡単に示されます。*8

(define (cons* x y)
  (let ((dispatch (lambda (m)
    (cond ((eq? m 'car) x)
          ((eq? m 'cdr) y)
          ((eq? m 'set-car!) (lambda (arg) (set! x arg)))
          ((eq? m 'set-cdr!) (lambda (arg) (set! y arg)))
          (else (error "Wrong Argument -- CONS" m))))))
    dispatch))

;; 以下、単に通常の関数として呼び出せるようにラッパーを用意します。
;; これは記述スタイルの問題で、特に必須というものではありません。
(define (car* c)
  (c 'car))
(define (cdr* c)
  (c 'cdr))
(define (set-car!* c arg)
  ((c 'set-car!) arg))
(define (set-cdr!* c arg)
  ((c 'set-cdr!) arg))

これを実際に使ってみます。

(define hoge (cons* 'a 'b))

(car* hoge); -> a
(cdr* hoge); -> b

(set-car!* hoge 'p)
(set-cdr!* hoge 'q)

(car* hoge); -> p
(cdr* hoge); -> q

確かに、cond式での分岐によりメソッドを定義するのは分かりづらく、若干非効率そうにも見えますが、Javaでやっていたようなオブジェクト指向プログラミングと同じように使えています。

ここで、オブジェクト指向プログラミングで何が重要だったか振り返ってみましょう。*9

  1. オブジェクトに、予め用意されたメッセージを送ると、対応する操作(データの取り出しや変更、あるいは諸々の計算)が行われる(メッセージパッシング)
  2. オブジェクトの内部は隠蔽され、利用する際に実際の構造を気にかけることはない。利用者が用意されたインターフェースに従っている限り、提供者は内部の構造を変更できる(カプセル化)

*10

関数型プログラミング

関数型プログラミングの特徴は、第一級関数による抽象化能力の高さにあることに、異論はないと思います。

イミュータブルだ、リアクティブだ、モナドだ、遅延評価だ、いやいや遅延ストリームだ、などとたびたび世間で騒がれていますが、どこまでを組み込みとするかは言語設計上の問題です。基本的に、関数型プログラミングをし易い言語が関数型プログラミング言語です。 *11 *12

例えば、リスト処理に対する抽象化として、FizzBuzzを考えましょう。

以前の記事*13でも一部扱いましたが、まずは汎用に使えそうな関数から。

;; 関数合成
;; 複数の関数(f1, f2, f3...)を引数にとり、それを順に適用するような新しい関数を生成します。
;; つまり、(>> f1 f2 f3) == (lambda (x) (f3 (f2 (f1 x)))) というようなイメージ。
;; 可変長引数対応で複雑になってます。
(define >>
  (lambda fs
    (letrec
        ((>>
          (lambda (fs)
            (cond
             ((null? (cdr fs)) (car fs))
             (else
              (lambda (x)
                ((>> (cdr fs)) ((car fs) x))))))))
      (>> fs))))

;; パイプライン演算子
;; 関数合成に加え、関数に最初に渡す値を指定します。
;; (*> x f1 f2 f3) == (f3 (f2 (f1 x))) というようなイメージ。
(define *>
  (lambda (x . fs)
    ((call-with-values
         (lambda () (apply values fs))
       >>) x)))

;; 2引数関数の引数の順番を入れ替えます。
(define (flip f)
  (lambda (x y) (f y x)))

;; listを先頭から走査し、順にアキュムレーター関数fを適用していき、その蓄積を返します。
;; カリー化形式を模倣するため、listだけは最後に別で与える形とします。
(define (fold f init)
  (letrec ((loop
            (lambda (acc lis)
            (cond
             ((null? lis) acc)
             (else (loop (f acc (car lis)) (cdr lis)))))))
    (lambda (lis) (loop init lis))))

;; listを逆順にします。
(define reverse
  (fold (flip cons) '()))

;; listを先頭から走査し、順に関数fを適用していき、その結果を同じ順のリストにして返します。
;; カリー化形式を模倣するため、listだけは最後に別で与える形とします。
(define (map f)
  (>>
   (fold (lambda (acc x) (cons (f x) acc)) '())
   reverse))

;; listを先頭から走査し、順に関数fを適用していき、その結果を破棄します。
;; カリー化形式を模倣するため、listだけは最後に別で与える形とします。
(define (iter act)
  (fold (lambda (acc x) (begin (act x) #f)) #f))

;; initからmaxまでの整数値を生成します。
;; Scheme標準ではiota関数が知られています。
(define (range init max)
  (cond
   ((< max init) '())
   (else (cons init (range (+ 1 init) max)))))

実際の関数型プログラミング言語では、この辺りの関数を自前で実装することはまず無く、基本的なライブラリとして提供されるでしょう。

そしてFizzBuzz本体。

;; 整数値からfizzbuzz結果の値に変換します。
(define (int->fizzbuzz x)
  (let ((is-fizz (= (modulo x 3) 0)); 3で割り切れたらFizz
        (is-buzz (= (modulo x 5) 0))); 5で割り切れたらBuzz
    (let ((is-fizzbuzz (and is-fizz is-buzz))); FizzかつBuzzならFizzBuzz
      (cond
       (is-fizzbuzz "FizzBuzz")
       (is-fizz "Fizz")
       (is-buzz "Buzz")
       (else x)))))

;; 指定された値までのfizzbuzzをコンソールに出力します。
(define (fizzbuzz max)
  (*> (range 1 max)
      (map int->fizzbuzz)
      (iter print)))

ほら、簡単でしょう?*14

「単純な」関数型プログラミングにないもの

そもそもデータ型の定義方法

オブジェクト指向プログラミング言語では、データ型の定義はつまりオブジェクトの定義であり、データ型はその概念の中枢にありますが、"関数型プログラミング言語"では、関数が主体というだけでは、扱うデータに関しては何も述べていません。

多くの"関数型プログラミング言語"、特にSMLやOCaml, HaskellなどのML由来の言語では、レコード型*15と代数的データ型*16が組み合わされて用いられます。それ以外だと、例えばScalaではJavaのオブジェクトシステムを基礎としていたり、言語により様々です。

パフォーマンス、コスト

「早すぎる最適化」という言葉にもあるように*17、ある程度は後回しにしてよい問題ではありますが、単純な実装では処理の時間・空間コストが大きくかかってしまいがち、という問題があります。

あまり詳しい話は存じないのですが、要するに、lambda生成が1回行われるたびに、関数オブジェクト、つまりJava等の言語のクラスのインスタンス生成が1回発生するため、コストの高いメモリアロケートが行われてしまう、ということでしょう。 これは例えば遅延リストによるストリームや、解釈系による関数のインライン展開等により、ある程度は改善されるでしょう。最悪、特にボトルネックとなる箇所について局所的に手続き的に記述するなど、現実的な方策はありえます。

多相性

例えば上記FizzBuzz関数では、「通常のlistをやめて遅延ストリームにしたい」といった場合に、cons/car/cdrの全てをストリーム版に差し替える必要があります。 *18 *19

こういった問題には、Common LispClojureのマルチメソッド(ジェネリックファンクション)のように、引数の実行時の型によって実際にディスパッチされる関数が決まる機構を用いたり*20Haskellの型クラス*21のように、型への制約と型同士の継承関係から、型検査の時点で適用可能な関数を割り当てておいたりするような、高度な手法が用いられます。*22

よく論じられる点について

オブジェクト指向プログラミング言語(仕事で使うあの言語)がつらい、どうしてこんなことに……やはりオブジェクト指向が悪い

それはきっと "あの言語" や "あの言語" のことだと思いますが、オブジェクト指向プログラミングを基本とする言語のアンチパターンがよく踏み抜かれがちということでしょう。

  • 1メソッド1000行、20個並んだ引数
  • 1クラス10000行、50個並んだフィールド変数
  • 新しいクラスを作るには申請書が必要
  • リファクタリングできない、している暇がない、そもそも手がつけられない

それらはきっとオブジェクト指向プログラミング言語が悪いのではなく、人員が、あるいは環境が悪いのです。そのような環境ではたとえHaskellを使ったとしても、メイン関数に10000行のIOが並ぶだけでしょう。

また、どうしても古くから普及している言語は、いまどきの言語に比べたら記述が冗長になりがちです。こればかりは、パラダイムに関係なく、新しい言語の普及が待たれると思います。

オブジェクト指向は全くダメだ、これからは関数型の時代だ

無茶な話です。確かに、例えばHaskellでは、レコード/代数的データ型を基本に、第一級関数や型クラス、遅延評価やモナドを駆使して、高度に抽象化されたプログラミングを実現しています。しかしそういった抽象的な構造を扱いやすいプログラミング言語では、代償として、処理コストを見積る難しさや、抽象的なコードのデバッグの難しさ、コンパイル処理時間の増大などを負っています。

またそれは、既存のオブジェクト指向言語の仕様の"筋の悪さ"を否定するものではあっても、オブジェクト指向の概念を否定するものでは無いでしょう。 高々オブジェクト指向を実現する機構など、最低限の機能なら、先に述べたようなメッセージパッシングの実装例や、レコードによるインターフェースの表現*23でも、単純に代用可能なものです。

また、オブジェクト指向プログラミングを型の継承関係と関数のディスパッチという方面から捉えるなら、上記の多相性の箇所で挙げたように、オブジェクト指向的な機構が必要になるでしょう。*24*25

さらに言うならば、言語機能として何を取り入れるかは、言語設計者による、言語動作環境へのコンパイルまでを含めた取捨選択であって、銀の弾丸はありません。言うなれば

  • 覚えることが最小限で済み
  • 簡潔に記述でき
  • 理解しやすく
  • 言語自体をスマートに拡張可能で
  • モジュール性が高く
  • 動作効率が素晴らしく高く、高速で省メモリで
  • あらゆるプラットフォームで動作し
  • ビルドや配布、リリースが容易で
  • IDEの開発が容易、または素晴らしいIDEが既に開発されていて
  • デバッグが容易で
  • 既存の様々なライブラリの移植が容易で
  • パッケージ管理システムとエコシステムが揃っていて、様々なライブラリが検索すれば簡単に導入できて
  • 言語仕様からライブラリを網羅したドキュメントが、英語でも自分の言語でも充実している
  • 多くの人に普及していてバグも出尽くしている、バージョンも安定している

そんなプログラミング言語がほしいと言うようなものです。夢を見るのもいいですが現実も見ましょう。

その他参考にしたい文献

長くなりましたが、今回はこの辺で。

*1:インターネットスラング的意味のポエム

*2:その差し替えによって思わぬ不具合が発生する事案は、世の中にはゴマンとあるわけですが、それはまた別の話です。

*3:実体とは一体何か、という話もありますが、「関数として利用可能な対象が、プログラムの実行時に操作可能な箇所にあるなにものか」というようなふわっとしたものがイメージできれば。

*4:これには非常に驚かされました。関数の返り値はひとつしか無いのに、どうして複数の値を保持できるのか。保持できるのは判るとしても、どうやって取り出すのか。なるほど(実際には効率のためプリミティブに実装するとしても)言われてみれば理解できる話です。

*5:例えば他のラムダ式のある言語、例えばC# で書いても構わないのですが、ここでその分かりやすさが改善するかといえば微妙です。

*6:参照: 計算機プログラムの構造と解釈 第二版

*7:本題とはズレますが、この方法で単に実装した場合、setCarやsetCdrは実装できないようです。(define (set-car!* c n) (c (lambda (x y) (set! x n)))) と書いたところで、元のconsにあるxまで変更が伝播するわけではありません。

*8:参照: 計算機プログラムの構造と解釈 第二版

*9:参照: オブジェクト指向プログラミング - Wikipedia この記事にはだいぶ独自研究の臭いがします

*10:継承や型検査、静的ディスパッチや多重ディスパッチの問題を考えるとまた話は複雑になりますが、一旦棚上げとします。

*11:参照: 120901fp key

*12:もちろん、オブジェクトのメソッドと関数がシームレスに扱えたり、イミュータブルなデータ型が簡単に定義できたり、扱いやすい不変コレクションがライブラリにあったり、クラス継承等を考えなくても代数的データ型を作ってパターンマッチできたら素晴らしいですし、モナド内包記法が汎用的に使えると最高ですね。

*13:SchemeでF# 風パイプライン演算子を書いてみた - 技術memo

*14:といいながら、型検査無しで型合わせゲームをやるのは、慣れないとつらい気もします。

*15:レコード - ウォークスルー Standard ML

*16:型の定義 - ウォークスルー Standard ML

*17:参照: 最適化 - Wikipedia

*18:参照: 計算機プログラムの構造と解釈 第二版

*19:具体的な言語だと、F# ではListとArrayとSeqのそれぞれでモジュールが分かれていて、使用しているデータ型に応じて個別に呼び分ける必要があるという問題があります

*20:参照: 多重ディスパッチ - Wikipedia

*21:参照: 型クラス - ウォークスルー Haskell

*22:厳密には、この例だとconsの引数にメソッドを特定できる型が無く、ジェネリックファンクションでは不可能そうな気もします。実際やってみたわけでは無いので怪しい。

*23:参照: GoF in OCaml for Advent Calendar 2012 #3 - まぁ、そんなもんでしょう。

*24:誤解を招きやすいところですが、型クラスもそういう意味ではオブジェクト指向のようなものですし……。

*25:参照: オブジェクト指向から理解する型クラス - think and error