代数的データ型とオブジェクト指向プログラミングと

タイトルは意味不明です。

関数型プログラミング (言語) について書かれたエッセイがあります。

• Why the next language you learn should be functional
• なぜ次に学ぶ言語は関数型であるべきか

素晴らしい翻訳記事があるので私はそちらを読みました。

このエッセイの中で OCaml で表現された 代数的データ型 とパターンマッチの例が紹介されています。

• OCamlでの表現型と評価器

type 'a expr = | True 
               | False 
               | And  of  'a expr * 'a  expr 
               | Or   of  'a expr * 'a  expr 
               | Not  of  'a expr 
               | Base of  'a  
 
let  rec eval eval_base expr  = 
   let  eval' x = eval eval_base x in 
   match expr with 
   | True  -> true 
   | False -> false 
   | Base base  -> eval_base base 
   | And  (x,y) -> eval' x && eval' y  
   | Or  (x,y)  -> eval' x || eval' y 
   | Not  x     -> not (eval' x) 

また、これと同等のことを Java で実装するとどうなるのかを比較として紹介されています。非関数型プログラミング言語では、代数的データ型 (直和型) を言語としてサポートしていないものが多いと思います。Python もそんな言語の1つです。記事の中で紹介されている Java のコードを Python に置き換えて考えてみます。

まず評価器の実装からです。元記事の Java のコードではインターフェースの定義のみで実装は紹介されていないので、ここでもインターフェース的に ABCMeta と abstractmethod を使い、実装は適当にしています。

3.4

from abc import ABCMeta, abstractmethod

class Evaluator(metaclass=ABCMeta):
    @abstractmethod
    def evaluate(self, value): pass

class MyEvaluator(Evaluator):
    def evaluate(self, value):
        return bool(value)

次に Boolean 式とそれらの式を評価する関数の定義へ移ります。先ほどの Evaluator と同様、Expr というインターフェースっぽいものを継承してそれぞれの式をオブジェクトとして定義します。

3.4

class Expr(metaclass=ABCMeta):
    @abstractmethod
    def eval(self, evaluator): pass

class True_(Expr):
    def eval(self, evaluator):
        return True

class False_(Expr):
    def eval(self, evaluator):
        return False

class Base(Expr):
    def __init__(self, value):
        self.value = value

    def eval(self, evaluator):
        return evaluator.evaluate(self.value)

class And(Expr):
    def __init__(self, expr1, expr2):
        self.expr1 = expr1
        self.expr2 = expr2

    def eval(self, evaluator):
        return self.expr1.eval(evaluator) and self.expr2.eval(evaluator)

class Or(Expr):
    def __init__(self, expr1, expr2):
        self.expr1 = expr1
        self.expr2 = expr2

    def eval(self, evaluator):
        return self.expr1.eval(evaluator) or self.expr2.eval(evaluator)

class Not(Expr):
    def __init__(self, expr):
        self.expr = expr

    def eval(self, evaluator):
        return not self.expr.eval(evaluator)

こんな感じかな。

細かいことは置いておいて実行して動くかどうかを試してみましょう。

True_ と False_ は Evaluator に関係なくブール値を返すため、シングルトンとして扱っても良いでしょう。

3.4

>>> from sample1 import *
>>> evaluator = MyEvaluator()
>>> true, false = True_(), False_()
>>> true.eval(evaluator)
True
>>> And(Base(3), false).eval(evaluator)
False

これよりも eval 関数風に呼び出す方がそれっぽくみえる気がします。

3.4

>>> from operator import methodcaller
>>> eval_ = methodcaller('eval', evaluator)
>>> eval_(Not(true))
False
>>> eval_(Or(And(Base(3), false), Not(false)))
True

・・・

おそらくは実行することはあまり重要ではないですね (実装のテストのためにやっているだけ) 。

代数的データ型の直和型に相当するものをインターフェース (っぽいもの) と継承を使って表現できました。ここで Ocaml の代数的データ型の定義をみてみます。

type 'a expr = | True 
               | False 
               | And  of  'a expr * 'a  expr 
               | Or   of  'a expr * 'a  expr 
               | Not  of  'a expr 
               | Base of  'a  

元記事 (翻訳) から引用すると、

直和型の式は異なる宣言部を分けているパイプで示されています。これらの宣言部の内、たとえばTrueやFalseは単一タグで、JavaやCの列挙型の要素と実質的には変わりません。他のもの、たとえばAndやNotは結びついているデータがあって、そのデータは場合によって変わります。この型はAndやOrの部分がタプルを含んでいるので、実際直和型と直積型の両方を含んでいます。積と和の重構造の組み合わせで成り立つ型はOCamlではよくあるもので、強力なイディオムです。

継承を使ってクラスで表現するより、| (パイプ) で記述する表現の方がずっと簡潔だというのに異論はないでしょう。

さらに直和型は列挙型 (enum) でも表現できるとあるのでそれも試してみましょう。Python 3.4 から標準ライブラリに enum モジュールが追加されています。標準の enum だと簡潔に表現できないので extenum という拡張を使っていますが、そこは本質的ではないので気にしないでください。

3.4

from extenum import ConstantSpecificEnum

class Expr(ConstantSpecificEnum):

    TRUE = 1
    FALSE = 2
    BASE = 3
    AND = 4
    OR = 5
    NOT = 6

    @overload(TRUE)
    def eval(self, evaluator, *args):
        return True

    @overload(FALSE)
    def eval(self, evaluator, *args):
        return False

    @overload(BASE)
    def eval(self, evaluator, *args):
        return evaluator.evaluate(args[0])

    @overload(AND)
    def eval(self, evaluator, *args):
        return evaluator.evaluate(args[0]) and evaluator.evaluate(args[1])

    @overload(OR)
    def eval(self, evaluator, *args):
        return evaluator.evaluate(args[0]) or evaluator.evaluate(args[1])

    @overload(NOT)
    def eval(self, evaluator, *args):
        return not evaluator.evaluate(args[0])

1つの enum クラス内に式に相当するオブジェクトを定義できたので、先ほどの継承の例よりはちょっとましかもしれません。

3.4

>>> from sample2 import *
>>> Expr.TRUE.eval(evaluator)
True
>>> Expr.AND.eval(evaluator,
...               Expr.BASE.eval(evaluator, 3),
...               Expr.FALSE.eval(evaluator))
...
False

見た目が冗長なので評価器を隠蔽すると、

3.4

>>> true = Expr.TRUE.eval(evaluator)
>>> false = Expr.FALSE.eval(evaluator)

>>> from functools import partial
>>> Base = partial(Expr.BASE.eval, evaluator)
>>> And = partial(Expr.AND.eval, evaluator)
>>> Or = partial(Expr.OR.eval, evaluator)
>>> Not = partial(Expr.NOT.eval, evaluator)

>>> Not(true)
False
>>> Or(And(Base(3), false), Not(false))
True

それっぽく見やすくなりました (ちゃんと動くかテストしやすくなりました) 。

はてブのコメントでは、関数型プログラミング言語の特徴的なところを手続き型プログラミング言語で表現して対比するのは公平じゃないといったコメントも見られました。それも一理あるとは思いますが、その対比をもって一方を賞賛する (侮蔑する) というよりも、同じ目的に対してプログラミング言語のパラダイムが違うとどういった表現方法になるのかを考えるきっかけとして、元記事は素晴らしいなと思いました。

例えば、私は関数型プログラミング言語に明るくないため、OCaml で説明されるよりも Java で説明された方がまだコードが意図することを理解しやすいからです。そして、同じ理屈から Python でも書いてみたという次第です。

表現方法は簡潔であるならば、それに越したことはないですし、プログラミング (言語) のパラダイムとそのコードの表現力は密接な関係があるということを実感するのに良い例だと思いました。