Python
math
数学
代数学
Python3.5

Pythonに型付けして代数拡大を実装する (1) 〜モノイド・群・環・整数環〜

はじめに

Python 3.5で型ヒント機能が導入され,型を意識できるようになりました。しかし,型ヒントの付いたコードを目にする機会は殆どありません。自分も当初は「Pythonに静的型付けは必要なのか?」と懐疑的でしたが,自分のコードに型ヒントを付けてみたところ,"oh my(py)!" と思ってしまい,広めたいと思ったのでこの記事を書くことにしました。

これから3回に分けて,型ヒントを活用して,Pythonで体の拡大を実装していきます。実装に際して,taketo1024さんの記事「Swiftで代数学入門」を大変参考にしました。

ちなみに筆者は代数拡大には疎いので(結城浩著「数学ガール/ガロア理論」を読んだ程度),誤りがあれば教えていただけますと幸いです。

代数拡大については,taketo1024さんの記事やその他のWebページに丁寧に書かれているので,この記事では数学的な話にはあまり触れず,Pythonでどうやるかをメインテーマにしようと思います。

想定する読者層

  • Pythonの型ヒントに興味がある人
  • 演算できるPythonクラスを作ってみたい人
  • Pythonで抽象基底クラスを作ってみたい人

目次

  1. モノイド・群・環・整数環
  2. 体・有理数体・ユークリッド環・剰余類環・有限体
  3. 多項式環・多項式の剰余環・体の拡大

Pythonの型ヒント機能

型ヒントがベースにしているものに,関数アノテーション(PEP 3107)というコードの書き方があります。これは,関数の引数や戻り値に説明付けを行う場合に用います。

以下はPEP 3107から引用したアノテーション例です。

def compile(source: "something compilable",
            filename: "where the compilable thing comes from",
            mode: "is this a single statement or a suite?"):

関数アノテーションの内容はプログラムの実行結果に影響を与えませんが,関数アノテーションを活用して,コードをオフラインで検査する試みがあります。

PEP 3107ではそのアノテーション内容については特に規程されていないため,検査ツールのためにさまざまなアノテーション流儀が乱立する可能性があります。しかし,それではプログラマーの受ける恩恵が半減してしまうため,Python 3.5からは型ヒント(PEP 484)という標準化された枠組みが導入され,関連して typing モジュールが提供されるようになりました。

以下はPEP 484から引用したアノテーション例です。変数や文字列に,説明文ではなくクラスや型の名称を指定します。

from typing import List
Vector = List[float]

def scale(scalar: float, vector: Vector) -> Vector:
    return [scalar * num for num in vector]

もう一度書きますが,アノテーション内容によってプログラムの挙動が変わったり,アノテーションの仕方が強制されることはありません。また,必ずしもこのアノテーション方法に従う必要はありません。しかし,標準化によってルールが統一され,プログラマー同士の協調が期待できます。

検査ツール

型ヒントの枠組みができたからといって,検査ツールがPythonの一部として提供されるわけではないので,ツールを選ぶ必要があります。本記事では,PEP 484が強く意識しており,現時点でデファクトスタンダードとなっているmypyを使うこととします。

mypyのインストールは,pipコマンドで以下のようにしてインストールできます(mypyではなくmypy-langなので注意)

$ sudo pip3 install mypy-lang

実際の使用はこの記事の最後の方で行います。

実装

では,さっそく「数」を作っていきましょう。

モノイド

まずはモノイドです。次の条件を満たす集合を「モノイド」といいます。

二項演算 $\star$ について閉じており,
1. 結合法則が成立する($x \star (y \star z) = (x \star y) \star z$ となる)
2. 単位元が存在する($x \star e = e \star x = x$ となる $e$ が存在)

例えば,自然数,実数,正方行列などは「積」についてモノイドです。
これをPythonで表現するために,まずはモノイドの抽象基底クラスを作ります。metaclass=ABCMeta を付ければ抽象基底クラスになります。

from abc import ABCMeta, abstractmethod

class Monoid(metaclass=ABCMeta):
    @abstractmethod
    def __mul__(self, x):
        pass

    @abstractmethod
    def identity(self):
        pass

    @abstractmethod
    def __eq__(self, x):
        pass

    def testAssociativity(self, a, b):
        return (self * a) * b == self * (a * b)

    def testIdentity(self):
        return self * self.identity() == self

すべてのモノイドには最低限「二項演算 $\star$」「単位元」および「イコール」が実装されていてほしいので,抽象基底クラスでは @abstractmethod デコレーターをつけた空のメソッドを宣言します。これにより,Group を継承したクラスにこれら3つのメソッドが定義されていないと,インスタンス化の際にエラーとなります

演算 $\star$ はPythonの演算子 * を代用します。クラスに対して演算子 * を定義するには,__mul__ メソッドを定義します。この演算子が定義されたクラスのインスタンスは,* 演算子で他のオブジェクトをつないで式を作ることができます。例えば次のとおりです。

class A(object):
    def __init__(self, data):
        self.data

    def __mul__(self, x):
        return self.data * x.data

a = A(5)
b = A(10)
print((a * b).data) # -> 50

式を評価する際には,つなげられたオブジェクトが __mul__x に代入されて計算され,戻り値がその式の評価結果となります。__eq__ は演算 == に対応しています。

ただしこれだけでは,モノイドが演算 $\star$ について閉じていることを表現できていません。そこで登場するのが型ヒントです。型ヒントでは,関数の引数や戻り値の型を表現できます。型ヒントを加えた例を見てみましょう。

from typing import TypeVar

MonoidType = TypeVar("MonoidType", bound="Monoid")

class Monoid(metaclass=ABCMeta):
    @abstractmethod
    def __mul__(self: MonoidType, x: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def identity(self: MonoidType) -> MonoidType:
        pass

    @abstractmethod
    def __eq__(self, x): 
        pass

    def testAssociativity(self: MonoidType, a: MonoidType, b: MonoidType) -> bool:
        return (self * a) * b == self * (a * b)

    def testIdentity(self: MonoidType) -> bool:
        return self * self.identity() == self

関数の各引数の後ろに : と型を表すシグネチャーがくっついています。また,def 文の最後にも -> に続いてシグネチャーがあります。これが型ヒントです。

型ヒントでは,関数の引数や戻り値,その他の変数に型情報を与えることができます。これらは実際にプログラムを動かす際にはコメントと同じように扱われますが,型チェッカーを使う際に有効な情報となります。

各箇所では,MonoidType という変数を宣言して使っています。これは型変数といい,同じ型変数でアノテーションされた変数は,同じ型でなければなりません。

MonoidType の宣言の箇所では,bound="Monoid" としています。このようにすると,MonoidType が指定された変数を Monoid のサブクラスのインスタンスに限定することができます。

ここで,__eq__ には型ヒントを与えていません。__eq__ は全クラスの基底である object に定義されており,それと異なる型ヒントを与えるとエラーとなってしまいます。

「群」はモノイドに逆元の条件を加えたものです。

二項演算 $\star$ について閉じており,
1. 結合法則が成立する($x \star (y \star z) = (x \star y) \star z$ となる)
2. 単位元が存在する($x \star e = e \star x = x$ となる $e$ が存在)
3. 逆元が存在する($x \star x^{-1} = x^{-1} \star x = e$ となる $x^{-1}$ が存在)

群の抽象基底クラスはモノイドを継承し,逆元はメソッド inverse で定義します。逆元を定義するついでに,除算の定義 __truediv__ もここで行ってしまうのがいいでしょう。

GroupType = TypeVar("GroupType", bound="Group")

class Group(Monoid, metaclass=ABCMeta):
    @abstractmethod
    def inverse(self: GroupType) -> GroupType:
        pass

    def __truediv__(self: GroupType, x: GroupType) -> GroupType:
        return self * x.inverse()

    def testInverse(self: GroupType) -> bool:
        return self * self.inverse() == self.identity()

加法群

特に「加法」と呼ばれる演算について群をなす集合を「加法群」と呼びます。加法群では可換性を仮定するので,以下のように条件を4つとします。

演算 $\oplus$ について閉じており,
1. 結合法則が成立する($x \oplus (y \oplus z) = (x \oplus y) \oplus z$ となる)
2. 単位元が存在する($x \oplus 0 = 0 \oplus x = x$ となる $0$ が存在,零元)
3. 逆元が存在する($x \oplus (-x) = (-x) \oplus x = 0$ となる $-x$ が存在,マイナス元)
4. 可換である($x \oplus y = y \oplus x$ となる)

群の場合と同様ですが,コード例は以下のようになります。群で除算を定義した代わりに,減算を定義します。

AdditiveGroupType = TypeVar("AdditiveGroupType", bound="AdditiveGroup")

class AdditiveGroup(metaclass=ABCMeta):

    @abstractmethod
    def __add__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def zero(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    @abstractmethod
    def __neg__(self: AdditiveGroupType) -> AdditiveGroupType:
        pass

    def __sub__(self: AdditiveGroupType, x: AdditiveGroupType) -> AdditiveGroupType:
        return self + (-x)

    @abstractmethod
    def __eq__(self, x):
        pass

    def testAdditiveAssociativity(self: AdditiveGroupType, a: AdditiveGroupType, b: AdditiveGroupType) -> bool:
        return (self + a) + b == self + (a + b)

    def testZero(self: AdditiveGroupType) -> bool:
        return self + self.zero() == self

    def testNegative(self: AdditiveGroupType) -> bool:
        return self + (-self) == self.zero()

    def testAbelian(self: AdditiveGroupType, a: AdditiveGroupType) -> bool:
        return self + a == a + self

self + (-x) を見ると,改めて「演算を定義しているんだ」ということを実感します。

群とモノイドは,ひとつの演算のみについて条件を定めていました。「環」は,2つの演算について条件を定めます。

乗法と呼ばれる演算 $\star$ と加法と呼ばれる演算 $\oplus$ について閉じており,
1. 乗法 $\star$ についてモノイドである
2. 加法 $\oplus$ についてアーベル群である
3. 乗法と加法の間で分配法則が成り立つ($x \star (y \oplus z) = x \star y \oplus x \star z$ となる)

環のクラスを定義する際は,単純にモノイドと加法群のクラスを継承して,分配法則のテストコードを実装するだけです。

RingType = TypeVar("RingType", bound="Ring")

class Ring(Monoid, AdditiveGroup):
    def testDistributive(self: RingType, a: RingType, b: RingType) -> bool:
        return self * (a + b) == self * a + self * b

整数環

いよいよ整数環を実装できます。環の抽象基底クラス Ring を継承して,@abstractmethod で宣言したメソッドをオーバーライドしていきます。また,Pythonのコンソール上で Integer クラスの内容を表示できるように,__repr__ メソッドを定義しておきます。

本当であれば identityzero だけ書いて int を拡張できればいいのですが,残念ながらPythonではそのようなことはできないので,各メソッドを地道に定義していきます。

class Integer(Ring):
    def __init__(self: "Integer", v: int) -> None:
        self.v = v

    def __repr__(self: "Integer") -> str:
        return str(self.v)

    def __mul__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v * x.v)

    def __add__(self: "Integer", x: "Integer") -> "Integer":
        return Integer(self.v + x.v)

    def __neg__(self: "Integer") -> "Integer":
        return Integer(-self.v)

    def __eq__(self, x):
        if not isinstance(x, Integer):
            return NotImplemented
        return self.v == x.v

    def identity(self: "Integer") -> "Integer":
        return Integer(1)

    def zero(self: "Integer") -> "Integer":
        return Integer(0)

Z = Integer

ここで,Integer の別名として Z を使えるようにしておきます。

各メソッドで Integer 型を文字列で指定しています。メソッド定義の時点で Integer クラスの定義は終わっていないため,これは前方参照となります。型ヒントで前方参照をする際は,シンボルではなく文字列リテラルを使用します。

mypyによる解析

整数を実装したら,mypyでコードをチェックしてみましょう。チェックするには,単純にmypyコマンドにファイル名を指定して実行します。

$ mypy ./field_extension.py

問題がなければエラーは表示されません。
では,試しに Integer クラスから __mul__ メソッドを削除してチェックしてみます。

$ mypy ./field_extension.py
field_extension.py:174: error: Cannot instantiate abstract class 'Integer' with abstract attribute '__mul__'
...

乗算が定義されていない環はエラーとなります。このエラーはmypyを使わなくても,Integer クラスのインスタンスを生成した段階でエラーとなります。

では次に,__mul__ メソッドの引数の型を Integer から int に変更してみます。

def __mul__(self: "Integer", x: int) -> "Integer":
    return Integer(self.v * x)

この状態でmypyを実行すると,型が合わないというエラーが出ます。

$ mypy ./field_extension.py
field_extension.py: note: In class "Integer":
field_extension.py:91: error: Argument 1 of "__mul__" incompatible with supertype "Monoid"

ここまでで,モノイド,群,環を抽象化し,無事に整数環を実装できました。

次回の予定

次回は体について触れてから,有理数体,剰余類環,有限体を作る予定です。