Pythonと有理数

isamさんがまた面白い事をやっている。

ちなみに、コップ本とは以下の本の事だ。

Scalaスケーラブルプログラミング第4版 impress top gearシリーズ

Martin Odersky

インプレス

表紙にコップ(グラス)が大々的に写ってるから通称「コップ本」と言う。

なお、Scalaとはプログラミング言語の一つで、現在、大々的な使用例としてはご存知、X(旧Twitter)を記述している。基本的な設計思想はオブジェクト指向言語と関数型言語のマリアージュで、そういう意味だとOCaml/F#に近い、極めて尖った言語(つまり、マニアックなプログラマが好む)だ。

Scalaの元々の見た目は「性的静的型付けRuby」ってなカンジだったんで、旧Twitter社のRuby使用 -> Scala使用もあまり問題が無く行われたような印象だ。また、Scalaは多分、3.xになった時点でPython的なオフサイドルール(インデントでブロック構造を表す)を導入して、多くの人が馴染み始めたPythonっぽいコードの見た目をも取り込んでいる。

また、Scalaの一つの特徴に、JVM言語だ、と言う事がある。つまり、ハードウェア上で直接動く言語ではなく、Java Virtual Machine(Java仮想マシン)上で動く前提で設計されている。

従って、

直接ハードウェア上で動かない以上、Webプログラミングを行う上では安全性が高い。 => サーバーサイドWebプログラミング向け
Javaの豊富なライブラリ資産を使い放題。

と言う性質がある。

結果、Javaの資産を使用したい、としつつ、でもJavaの言語仕様やら文法はイマイチ好きじゃない、って人にとっては、Javaの上で走るスクリプト言語として人気が高い。

また、X(旧Twitter)での大規模使用例がある事から、JVM言語としての信頼度が極めて高く、JavaScript実装Rhinoや、Lisp系言語Clojureを向こうに回して一番人気だと思う。

さて。

実用的な話をすると、Pythonでは分数が扱えるので、自分で有理数を実装する必要はない(そもそもPythonで分数を扱えると言う事を知らん人もいるらしいんで、こういうトンマな本を書くわけだが)。

ただし、現時点だと分数を扱えるプログラミング言語は数少ない。そんなワケで、その実装方法を曲がりなりにも学ぶ、ってぇのは悪い試みじゃないだろう。また、どうしてC言語のような低レベルなプログラミング言語では分数を扱わないのか、ってのも良く分かると思う・・・分数を扱う時点で、そのための計算量は他の数値型に比べると圧倒的に多い、んだ。よって高速な計算を要する低レベルレイヤーにはあまりふさわしくない数値型、なんだよな。それを学ぶ為にも自分で曲がりなりにも有理数を実装するのは悪い経験じゃない、と思う。

なお、Lispな人たちにはネタ的にはSICPのコレと同じだ、って事を言っておこう(※1)。

んでだ。

コップ本での有理数(Rational)実装のPythonへの移植だが、最後に至るちょっと前、まではPythonで書く事は可能だ。しかし残念ながらPythonには拡張メソッドがない、んで、最後までたどり着く事は出来ない。

オチから言うと、Pythonで自作Rationalクラスを作るとして、次のような分数と整数との計算は可能だ。

>>> r = Rational(2, 3)
>>> r * 2
4/3

一方、単純には整数と分数の計算は不可能だ。

>>> 2 * r
Traceback (most recent call last):
File "<pyshell#2>", line 1, in <module>
2 * r
TypeError: unsupported operand type(s) for *: 'int' and 'Rational'

これは何故か、と言うと、有理数クラスは型が違う数値型を引数に取って計算する事は可能だが(と言うかそういう風に設計するが)、整数のような「Python組み込みの」型自体は、引数には組み込みの数値型を取れる、と言う情報はあっても、今みたいに「新しく作った型(有理数クラス)」を計算相手として認識は出来ないから、だ。

だから有理数 * 整数は計算出来ても整数 * 有理数は計算出来ないわけだ。

ロジックとしてはScalaでも事情は同じ筈だが、Scalaには拡張メソッドがある。つまり、Scalaが元々持ってる「組み込みのデータ型の振る舞い」をプログラマ側が変更出来る。

言い換えると、Scalaの整数クラスは、「引数に新しく作った有理数型を手渡しても正常に計算出来る」ように拡張出来るわけだ。

それがPythonには出来ない(※2)。

じゃあ、Pythonのfractionsモジュールは何をどうやってんのか、と言うと、Pythonではnumbersモジュールの中に既にRationalと言う抽象クラスがあって、加減乗算等の数値計算用特殊メソッドには数学的に考えうる全ての型同士の計算が予め定義されている(※3)。

>>> from fractions import Fraction
>>> r = Fraction(2, 3)
>>> r * 2
Fraction(4, 3)
>>> 2 * r
Fraction(4, 3)

言い換えると、ここでnumbers.Rationalを用いて有理数を実装してみれば上記のような問題は起こらないわけだが、そうするとRationalは単にFractionの再実装、って事になってしまう。

興味のある人は、Pythonで分数型(fractions.Fraction)がどうやって実装されているのか、ソースコードを覗いてみて欲しい。

なお、Scalaはインタプリタも兼ね備えていて、コップ本では、前回見たように徹底してリスナー(REPL)を活用するように読者を誘導している(※4)。

結果、やはり余計な出力をカマしていない(※5)。関数型言語にも準じてるだけあって、C言語脳が書いたPython本のような出力塗れ、と言うコードがなく、非常にキレイなコードを提供している。

さすが、だ。

さて、ではコップ本に従って有理数を作成していこう。言い換えると、有理数クラスを作る。

もう一度基礎を確認する。以前にも言ったが、クラス作成の本質、ってのは「ユーザー定義型」作成だ。ここを外して「オブジェクト指向とはデータと関数を一体化して・・・」なんて説明になるからワケが分からなくなる。そうじゃなくって、「関数がユーザーが作れるように、型もユーザーが作れて構わない」と言うのがクラスの背景にあるアイディアだ。

従って、「有理数と言う数値型を作りたい」のなら速攻「有理数と言うクラスを作りたい」のと同義になる。

class Rational(object):
　def __init__(self, n, d):
　　self.numer, self.denom = n, d

これで新しく有理数(Rational)型が定義された(※6)。

しかしこのままだと、例えば二分の一を定義しようとすると、

>>> Rational(1, 2)
<__main__.Rational object at 0x7fbfafbe0290>

とワケの分からない表示が返ってくる。

「データ」は作成されてはいるが、それがどういう中身なのか、一見では分からなくなってしまう。

何度もPythonによるREPLベースのソフトウェアの作り方、で書いたが、ここでも改めて書いておく。

REPLベースのソフトウェアでは評価器(Eval)が操作するデータ対象としてクラスで環境データを定義してたが、この時、デバッグ目的で__repr__と言う特殊メソッドを定義していた。これはクラスが実行された時に「何を表示として返すか」決定する為の特殊メソッドだ。

isamさんは、Scalaのコードを実直にtoStringと言うメソッドをオーバーライドするつもりで書いてたが、そもそもPythonのクラスに(作らなければ)toStringと言うメソッドはない。従って、出力用の文字列を弄りたいのなら、__repr__を作成すべきだ。

class Rational(object):
　def __init__(self, n, d):
　　self.numer, self.denom = n, d
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'

これで、分数と言うカタチで「表示」は可能となる。

>>> Rational(1, 2)
1/2
>>> x = Rational(1, 3)
>>> x
1/3
>>> y = Rational(5, 7)
>>> y
5/7

次に、分母が0の場合を考えよう。単純に言うと、分母部分のdが0であった場合、ValueErrorかあるいはZeroDivisionErrorを起こせばいい。

ここではZeroDivisionErrorを起こす前提とする。

class Rational(object):
　def __init__(self, n, d):
　　if d != 0:
　　　self.numer, self.denom = n, d
　　else:
　　　raise ZeroDivisionError
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'

次に有理数型(分数)同士の加算を考えよう。

Pythonでは特殊メソッド__add__をオーバーライド(書き換え)する事により、加算演算子(+)の挙動を変える事が出来る。

そして、分数同士の加算方法は小学生の時習ったまんまだ・・・通分して加算を実行する。

class Rational(object):
　def __init__(self, n, d):
　　if d != 0:
　　　self.numer, self.denom = n, d
　　else:
　　　raise ZeroDivisionError
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'
　def __add__(self, that):
　　return Rational(self.numer * that.denom + that.numer * self.denom,\
　　　　　　　　　self.denom * that.denom)

ここまでで、次のような実行結果を得る。

>>> oneHalf = Rational(1, 2)
>>> twoThirds = Rational(2, 3)
>>> oneHalf.__add__(twoThirds) # 本体の特殊メソッド(__add__)の実行結果
7/6
>>> oneHalf + twoThirds # + による加算は本体(__add__)に置き換えられてる
7/6

なお、isamさんが、

演算子のオーバーロード定義のときは、__add__と書いて、使うときは"+"。チョット何故？

と書いていたが、単純には+は__add__の構文糖衣(Syntactic Sugar)だから、だ。+を使った中置記法構文は内部的に__add__を使った特殊メソッドによる計算に置き換えられる。

もう一つの理由は、Pythonは実は結構古めかしい言語で、ユーザーに開放された識別子は大小のアルファベット、アンダースコア(_)、先頭に来ない数値、の基本三種類しかない。

つまり、単純に「関数/メソッド名に加算記号が使えない」辺りが理由だ。C言語と同じだ。Lispなんかに比べると圧倒的に「命名に不自由さがある」言語なんだ。

次に、分母dが1だった時、特に明示入力しなくても良いようにしておこう。要はdをデフォルト引数にしておけばいい。

class Rational(object):
　def __init__(self, n, d = 1):
　　if d != 0:
　　　self.numer, self.denom = n, d
　　else:
　　　raise ZeroDivisionError
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'
　def __add__(self, that):
　　return Rational(self.numer * that.denom + that.numer * self.denom,\
　　　　　　　　　self.denom * that.denom)

これにより、分母が1だった場合に入力を省略出来る。

>>> y = Rational(3)
>>> y
3/1

3/1って表示がみっともない、って思う向きもあるかもしれない。

が、取り敢えずこれでいい。表示はいつでもいじれるから、だ。

もう一つ重要なのは、確かに数学的には3と表示したい。したいんだが、このプログラム上、仮に3と表示されてもその3は整数じゃないんだ。依然として、型は有理数型になってて、整数として表示するにはちと危険なわけだな。誤認を促してしまう。

だから現時点はこのままにしてほおっておこう。

なお、現時点では、例えば、

>>> Rational(66, 42)
66/42

となるが、約分されない。

そう、C言語のような低レベルレイヤーの言語で分数が実装されないのは、分数と言うのは約分と言う手間がかかる処理があるから、なんだ。これが計算量を増やす。

一方、Pythonは(真の)高級言語なんで、便利であれば、負荷はそれほど気にするようなデメリットでもない。

約分するには最大公約数(G.C.D.)を利用すればいいが、Pythonにはmathモジュールにgcdがあるんで約分自体は大した手間でもない。

from math import gcd

class Rational(object):
　def __init__(self, n, d = 1):
　　if d != 0:
　　　g = gcd(abs(n), abs(d))
　　　self.numer, self.denom = n // g, d // g
　　else:
　　　raise ZeroDivisionError
　def __add__(self, that):
　　return Rational(
　　　　self.numer * that.denom + that.numer * self.denom,\
　　　　self.denom * that.denom
　　　　)
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'

分子や分母が負の数の場合も考慮して、絶対値を取ってからgcdを使う。あとは最大公約数で分子と分母を割ればいい。

なお、isamさんが、

割り算すると浮動小数点の
データに解釈されますので、intで整数の計算にしないとダメみたい！

と言ってたが、単に商を求める場合、/(除算: division)ではなくて//(切り捨て除算: floor division) を使う。

また、gcdを利用した変数gにselfが付いてない事を不思議に思う人もいるかもしんない。「self.gにしなくていいの?」と。

クラス内では、selfが付いた変数はまるで大域変数のように振る舞う。一方、この場合のgは__init__メソッド内だけ、で有効でそれで事足りる。他のメソッドから使われる事は無いわけだ。

すなわち、クラスのあるメソッド内に存在するselfを付けない変数は、メソッドが形成するスコープに縛られる。一方、繰り返すが、クラスのあるメソッド内に存在するselfを付けた変数はメソッドのスコープに縛られず大域変数的に振る舞う。

オブジェクト指向が意外と、クラス作成上古典的な「命令形プログラミング」(つまり往年のBASIC的なプログラミング)になりやすいのは、このselfを付けた変数の大域変数的な振る舞いに拠るんだ。

いずれにせよ、これで有理数型は自然と約分をしてくれるようになる。

Rational(66, 42)
11/7

次は掛け算を実装する。掛け算用の特殊メソッドは__mul__で、こいつをオーバーライドする。

from math import gcd

class Rational(object):
　def __init__(self, n, d = 1):
　　if d != 0:
　　　g = gcd(abs(n), abs(d))
　　　self.numer, self.denom = n // g, d // g
　　else:
　　　raise ZeroDivisionError
　def __add__(self, that):
　　return Rational(
　　　　self.numer * that.denom + that.numer * self.denom,\
　　　　self.denom * that.denom
　　　　)
　def __mul__(self, that):
　　return Rational(self.numer * that.numer, self.denom * that.denom)
　def __repr__(self):
　　return f'{self.numer}/{self.denom}'

これで有理数同士の掛け算も可能となった。

>>> x = Rational(1, 2)
>>> y = Rational(2, 3)
>>> x + y
7/6
>>> x.__add__(y)
7/6
>>> x + x * y
5/6
>>> (x + x) * y
2/3
>>> x + (x * y)
5/6

ここまではあくまで有理数(と言うより実際は分数だが)同士の演算に付いてプログラムしてきた。

ここからは分数と整数、と言う順番での計算に手をつける。

とは言ってもここからちとややこしい。何故なら「型判定」の問題が出てくるから、だ。

そしてPythonは型判定が弱い。型オブジェクト、ってのが存在してるかしてないか分からん、って辺りがとても中途半端なんだ。

まずはオーソドックスな手ではisinstanceを使う事が考えられる。

　def __mul__(self, that):
　　if isinstance(that, Rational):
　　　return Rational(self.numer * that.numer, self.denom * that.denom)
　　elif isinstance(that, int):
　　　return Rational(self.numer * that, self.denom)
　　else:
　　　return NotImplemented

これはPythonのfractions.Fractionでも見られる実装方法だ。Pythonではオーソドックスな手順となる。

しかしながら、今回は特殊メソッドの第二引数が有理数型と整数「だけ」だからこれでいいけど、今後演算可能な型を追加していく事を考えるとisinstanceを書きまくらないといけないんであまり嬉しくない。

Lisp辺りをやってきて、matchがある前提だと本当はこんな風に書きたいトコだ。

　def __mul__(self, that):
　　match type(that):
　　　case Rational:
　　　　return Rational(self.numer * that.numer, self.denom * that.denom)
　　　case int:
　　　　return Rational(self.numer * that, self.denom)
　　　case _:
　　　　return NotImplemented

これなら演算対象の型の追加がラクだ。

ところが、これは現時点では許されてないらしい。

そもそも、上で書いたが、Pythonの型判定の機能は弱い。関数typeは型情報を返すが、

>>> type(2)
<class 'int'>

上で書いた通り、ここで返される<class 'int'>はint型そのものを指し示すモノではなく、特殊メソッド__repr__で定義された単なる文字列だ。

すなわち、

>>> int
<class 'int'>

と字面が同じでも、中身、あるいはパターンが「全く同一だ」と言う保証がない。

加えると、PythonのmatchはRacketやOCaml/F#のmatchと違ってユーザー定義型そのものの中身まで入り込めない。非常に中途半端なパターンマッチしか出来ない、と言う事もある(※7)。

結果、ANSI Common Lispのtypecaseみたいな事をやりたい場合、もうちょっととっ散らかった書き方をしないといけない(※8)。

　def __mul__(self, that):
　　match type(that).__name__: # 型から名前を引きずり出す
　　　# 文字列と比較する
　　　case 'Rational':
　　　　return Rational(self.numer * that.numer, self.denom * that.denom)
　　　case 'int':
　　　　return Rational(self.numer * that, self.denom)
　　　case _:
　　　　return NotImplemented

これで受け取る型により演算方針を変更する事が出来る。

>>> r = Rational(2, 3)
>>> r * r
4/9
>>> r * 2
4/3

そしてここで打ち止め、だ。最初に書いた通り、有理数、整数の順での演算は可能だが、整数がここで作った有理数を判別する仕組みがないんで、整数、有理数の順だと計算が出来ない。

いずれにせよ、コップ本からPythonへと翻訳した有理数型のコードはこのようになる。

Python上では単純にfractions.Fractionを使えばいいので、ここで紹介したコードには実用性はない。

しかし、分数を持たないプログラミング言語の方が多いんで、「分数型なんてどうやって実装するんだ?」と言う人の役に立てば幸いだ。

以上。

※1: SICPではそこで「関数」と「データ」に差異が無いことを嫌と言うほど痛感出来る。

※2: 拡張メソッドをエミュレートするforbiddenfruitと言う外部ライブラリがある事はある。

ただし、どうやら__mul__のような組み込みの特殊メソッドを「拡張」する事は不可能っぽい。

また、これを考えると、ANSI Common LispのCLOS(Common Lisp Object System)のような「メソッドがクラスに属さない」実装方法の優位性が良く分かる。CLOSでは新しくメソッドを定義・追加するのは至極簡単で、それはメソッドがクラスに属してないから、だ。

また、オブジェクト指向じゃなくても、総称関数、と言う関数設計法の方が色々と融通が利く事が分かる。

※3: 理論的な話をすると、「数」と言うのはヒエラルキーを形成している。

このヒエラルキーを見ると、有理数は整数と分数を含んでいて、結果、加減乗算等の基礎的計算が有理数で定義されてたら、「その性質を受け継いだ」整数や分数は当然互いに四則演算的な計算が可能だ、と言う事になる。

もっと言うと、複素数をルートとして、そこで計算が定義されていたら、「その性質を受け継いだ」全ての「数値型」では互いに計算が成り立つ、と言う事になる。

平たく言うと、この「性質を受け継ぐ」のがオブジェクト指向に於ける「継承」で、これを見ても、ユーザーに対してより、言語設計者の方に「オブジェクト指向」がより有用な「データ型の設計方針」だと言う事が分かるだろう。

ここでの有理数実装に於ける整数と有理数の間の計算の不整合は、本質的な意味では、「ポッと出の有理数」になってる事で、このヒエラルキーに属していない、ってのが問題なんだ(完全に独立している)。そう、実はPythonに「拡張メソッド」と言う飛び道具がない、ってのが問題なのではない。

もちろん、本来のPythonの数値データ型のヒエラルキーは上のような「数学的整合性」を持つようにデザインされている。

※4: ちなみに、こっちで試した限りだと、Scalaのインタプリタはやたら重い(笑)。「こんなに重くてエエの?」ってくらい反応が悪くてビックリした。

Scalaはどっちかっつーと、コンパイル目的の処理系なんだろう。恐らくJVMで動かす最適化したバイトコードを吐き出す事を重要視したプログラミング言語なんじゃないか。

※5: これに付いてのisamさんの記事があるが、技術的には全くその通りで、単にPython端末を走らせ、書いたプログラムを端末側でimportすれば要件は満たせるだろう。

その通り、だ。

ただし、IDEでのインタプリタ開発、ってのは機能的な意味では、「何かキーを叩くだけ」で書いたプログラムが自然とPythonインタプリタにimportされる事が必要なわけで、結果、やっぱりVisual Studio Codeには「それが欠けてる」と言う事を繰り返し指摘しよう。要は「import書くのが面倒くさいじゃん」って事だ(笑)。

GNU Emacs(Spacemacs)だと、Space、m、s、b、の順でキーを叩くと、エディタ内のプログラムが下部のリスナーにすぐさまimportされ、明示的にファイルをロードする必要がない。そのままリスナーで定義したプログラムをテスト出来る。
繰り返すが、IDEによるインタプリタでの開発では、「プログラムファイル」とターミナルではなくってインタプリタ(REPL)との接続が重要で、Visual Studio Codeに欠けてるのはそれ、なんだ。

※6: 有名な話だが、「有理数」と言うのは明治維新後、海外の「技術用語」を素早く日本語化する際の「造語」に於いて、忙しい中で起きた一種の誤訳だ。

確かにrationalには「理がある事」と言う意味もあるが、数学的にはこれは単に「分割可能」の意を表す。そして分割不可の数をirrationalと呼ぶ。日本語では「有理」に対して「無理」と言う訳語を与えたが、お陰様で意味の分からん単語になってしまった。

なお、根底的にはrationには「グルーピング」と言う意味があり、「分割可能」にはこの「グループ化可能」と言う意味が背景としてある。

※7: 結果、Pythonのmatchは定義したクラスを分解出来ず、matchにクラスをかける際には、クラス定義に次のようなブツを追加して、「matchにその中身を教える」アドホックな方策を取らないとならない。

class Point:
　__match_args__ = ('x', 'y') # こういう補助定義が必要
　def __init__(self, x, y):
　　self.x = x
　　self.y = y

Pythonのmatchは甚だ不完全なんだ。

※8: しかしながら実のことを言うと、「型判定」で完璧な機能を備えてるのはANSI Common Lispくらいしか無いかもしんない。C言語にはそんな機能はないし、Schemeでさえ仕様上はデータ型のヒエラルキーを持っていない(つまりあるデータ型が「どこの下部に属してるか」分からん以上、汎用的に「このデータの型はこれ」と言うのが難しい)。

意外と「型判定」は難しいんだ。