Python とマクロ、代数的データ型

前回はマクロの概要と Python でマクロを実装するための仕組みについて説明しました。

Python とマクロ、インポートフックと抽象構文木 - forest book

動作原理を理解した上で実際にマクロでどういったことができるのか、MacroPy というライブラリで提供されている機能をみながら考察してみます。

MacroPy の概要

Python でのマクロ実装の1つです。インポートフックでモジュール内のマクロ機能を AST 変換することで動作します。MacroPy で提供されているマクロ機能は以下のデコレーターを使って実装されています。

  • @macros.expr
  • @macros.block
  • @macros.decorator
  • @macros.expose_unhygienic

これらの仕組みを使って自分でマクロを実装することもできます。それにより Python の意味論 (semantics) の拡張を簡単にします。

リポジトリには python3 ブランチがあり、Python 3 対応が試みられているようですが、正常に動作しない機能もあるため、Python 2.7 を使う方が無難だと思います。

MacroPy が提供するマクロや機能は多岐に渡ります。またドキュメントもしっかりしているので学習にはとても良さそうです。ただ、全てを README に記載しているので目を通すだけでもなかなか大変です。以下は MacroPy の README から目次を抜き出したものです。

機能

マクロ

ユーザー定義マクロ

リファレンス

項目がたくさんあるので興味のあるところから読み進めると良いと思います。

今回は README の前半部によく登場する Case クラスという機能を提供するマクロとその背景について解説します。

Case クラス

Scala から Case クラスという機能を提供するマクロです。Case クラス について MacroPy のドキュメントで以下が引用されています。

Case Classes Are Cool - Code Commit

私が Scala をよく知らないため、この記事を読んでもよく分からなくて最初からつまづきました。Case クラスについて調べていると Effetive Scala に Case クラスについて説明があるのを見つけました。

代数的データ型としてのケースクラス

ケースクラス (case class) は、代数的データ型 (algebraic data type) をエンコードする: ケースクラスは数多くのデータ構造をモデリングするのに役に立ち、強力な不変式を簡潔なコードとして提供する。ケースクラスは、パターンマッチと共に利用すると特に有用だ。パターンマッチの解析器は、さらに強力な静的保証を提供する包括的解析 (exhaustivity analysis) を実装している。

Effective Scala 関数型プログラミング-代数的データ型としてのケースクラス

( ゜Д゜)

説明が簡潔過ぎてもっと分からなくなってしまいました。

代数的データ型 (Algebraic data type)

wikipedia:代数的データ型 という用語が新たに出てきました。Case クラスを理解する前にこの型が何なのかを調べることにしましょう。

余談ですが、以前、Python と型ヒント について調べていたときに Alex Gaynor 氏が Python の型システムについての懸念を表明し、その中で代数的データ型がないといったことも挙げられていました。

Python's type system isn't very good. It lacks many features of more powerful systems such as algebraic data types, interfaces, and parametric polymorphism. Despite this, it works pretty well because of Python's dynamic typing. I strongly believe that attempting to enforce the existing type system would be a real shame.

[Python-ideas] Proposal: Use mypy syntax for function annotations

そういったやり取りも記憶に残っていて代数的データ型に興味がありました。大雑把にいまの自分の理解で要約しますが、厳密な定義は原典を参照してください。

代数的データ型とは、一般的に関数型言語にみられるデータ型で、具体的には直積型、直和型、列挙型や再帰型といったデータ型を指します。関数型言語では、これらのデータ型を使ったプログラミングが一般的であり、パターンマッチングと共にそのデータ型の表現や操作について簡潔、且つ強力に扱えます。

代数的データ型と簡潔な表現

例えば、なぜ次に学ぶ言語は関数型であるべきか - YAMAGUCHI::weblog の記事で紹介されている Boolean 式を表す型と、それらの式を評価する関数の定義が以下になります。

  • 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) 

これと同等のことを Python で実装してみたのが以下の記事になります。

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

代数的データ型の直和型 (後述) に相当するものは、オブジェクト指向言語においてもクラスの継承や列挙型 (Enum) で表現できます。以下は列挙型を使って表現したコードです。

# -*- coding: utf-8 -*-
from abc import ABCMeta, abstractmethod

from extenum import ConstantSpecificEnum

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

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

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つとして語られているように思います。

余談ですが、直和型を簡潔に表現するために Python 標準の enum モジュールだと機能不足だったので extenum というパッケージを作りました。extenum の機能と用途について簡単にまとめた記事が以下になります。

enum を拡張する extenum パッケージを作りました

標準の enum モジュールにはない以下の機能を提供しています。

  • 定数固定メソッド実装
  • 暗黙の列挙型メンバー
  • EnumSet

代数的データ型とパターンマッチング

代数的データ型の文脈で使われるデータ型がいくつかあります。Python におけるそれらを考察したのが以下の記事になります。

代数的データ型とパターンマッチングと

  • 直積型
  • 直和型
    • 前節の Ocaml のコードのように関数型言語では簡潔に表現できる
    • Python ではサポートしていない、継承や enum で代替できるが簡潔ではない
  • 列挙型
    • Python 3.4 から標準ライブラリとして提供されている
  • 再帰
    • データ型を定義するときに再帰的に扱う、前方参照 (forward reference) が必要

さらに代数的データ型とパターンマッチングは表裏一体な機能と言っても良さそうなので、一緒に考察することでその利点がより分かりやすくなります。

上記の記事で直積型は namedtuple に相当すると説明しています。

ここでようやく元の話に戻ってきましたが、この直積型に相当するものが Case クラスです。MacroPy では以下のように定義します。

@case
class Point(x, y): pass

MacroPy では Case クラスは以下の機能をもつと説明されています。Case クラスは @macros.decorator で実装されています。

ざっくり言うと、様々な特殊メソッド (機能) をもつクラスを自動生成してくれます。こういった何かの機能を自動生成するものをボイラープレート (boilerplate) と呼んだりするようです。詳細は README にあるサンプルコードを参照してください。

先の記事を書いた後で id:podhmoPythonのnamedtupleについて見過ごしてきたこと で namedtuple はタプルであって型ではないと言及しているのに気付きました。

これは結局、namedtupleは名前の通りtupleでしかないせいです。tupleなので型名を持っていません。したがって、同じ順序で同じ値が渡されていたものは比較でTrueになるというわけです。

先の記事で namedtuple が直積型に相当すると書いたのは厳密には間違っていて、Case クラスの __eq__ ではクラスのチェックも実装されているため、Case クラスが直積型に相当すると言った方が適切でしょう。

    def __eq__(self, other):
        try:
            return self.__class__ == other.__class__ \
                and all(getattr(self, x) == getattr(other, x) for x in self.__class__._fields)
        except AttributeError:
            return False

さて、前述した OCamlでの表現型と評価器を、MacroPy の Case クラスとパターンマッチングを使って実装してみます。

# -*- coding: utf-8 -*-
from macropy.case_classes import macros, case
from macropy.experimental.pattern import macros, ClassMatcher, _matching, switch

@case
class Expr:  # Algebraic data type
    class True_: pass
    class False_: pass
    class Base(value): pass
    class And(expr1, expr2): pass
    class Or(expr1, expr2): pass
    class Not(expr): pass

def eval_(expr):  # Pattern Matching
    with switch(expr):
        if Expr.True_():
            return True
        elif Expr.False_():
            return False
        elif Expr.Base(value):
            return bool(value)
        elif Expr.And(expr1, expr2):
            return eval_(expr1) and eval_(expr2)
        elif Expr.Or(expr1, expr2):
            return eval_(expr1) or eval_(expr2)
        elif Expr.Not(expr):
            return not eval_(expr)

def test():
    True_, False_ = Expr.True_, Expr.False_
    Base, And, Or, Not = Expr.Base, Expr.And, Expr.Or, Expr.Not
    assert eval_(Not(True_())) is False
    assert eval_(Or(And(Base(3), False_()), Not(False_()))) is True

列挙型で実装したコードよりも随分とすっきりしましたね。

Case クラスの継承 によると、@case で生成したクラスでは、継承関係をネストした内部クラスとして表現できるようです。この例では、Expr の内部クラスは Case クラスを継承することになります。

そして eval_() 関数が MacroPy の パターンマッチング のマクロで実装されています。こういった with 文と一緒に使うマクロは @macros.block で実装されています。

もはや Python の意味論ではないので何ともコメントが難しいですが、OCaml のコードによく似た表現になっていることが伺えます。そして、それでもまだ冗長であるのも否めない気はします。

感覚的なものですが、構文を変えずに意味論だけの拡張で他言語の概念を取り入れるというものの限界というのか境界というのか、そういったものが見え隠れしている気がします。

代数的データ型の補足

Python のようなオブジェクト指向言語ではほぼ馴染みがないため、最初から関数型言語で学習する方が良いとは思いますが、PyAlgebraicDataTypes というライブラリが代数的データ型とパターンマッチングの学習向けに分かりやすいと思います。以下に簡単なチュートリアルを書きました。

代数的データ型と FizzBuzz と

他にも代数的データ型そのものの概要やそれに関するデータ構造について以下の記事が参考になりました。

The Algebra of Data, and the Calculus of Mutation

代数表現とデータ型の表現の概念から始まり、直積型と直和型、再帰型の説明、後半に wikipedia:en:Zipper_(data_structure) や One-Hole Contexts といった話題も出てきます。

まとめ

MacroPy のマクロ機能と関数型言語における代数的データ型の概念について紹介しました。

  • MacroPy
    • Case クラス
    • パターンマッチング
  • 代数的データ型
    • 直積型
    • 直和型
    • 列挙型
    • 再帰

MacroPy を使って代数的データ型を表現してみました。

ボイラープレートとしての Case クラス、Case クラスを型とみなしたパターンマッチングにより、関数型言語のそれに近い表現で実装することはできました。マクロを使うことで Python の意味論を拡張できるというのを実感するには分かりやすい例でした。