Edited at

PythonでミニマルなLispを作る(蛇足編)

More than 1 year has passed since last update.


はじめに

以下の記事の続編というか蛇足です.

前回までで純Lispの実装は済んだのですが流石に足し算もできない言語というのもいかがなものかと思うので簡単に拡張したいと思います.

Githubのレポジトリを見てもらうとわかりますが最終的には以下のような構成になっています.

src

├── builtin.py
├── eval.py
├── extensions
│ ├── _import.py
│ ├── __init__.py
│ ├── list.py
│ └── number.py
├── __main__.py
├── pprint.py
├── read.py
└── repl.py

実はrepl.pyも前回の記事を書いた時点から様変わりしていますがこの記事では扱いません.また全体的にあまり行儀の良くないことをちょこちょこしていますがあまり真似はしないようにお願いします.

src/extensions以下が今回のメインターゲットです.


方針

まず拡張機能を実装するにあたって大きな方針は以下です.


  1. 元の実装を壊さないように拡張する.

  2. どの拡張機能を有効にするかは任意で選択できるようにする.

これらを達成するためにimportをフル活用します.

単体で実行されるPythonのスクリプトには以下のようなイディオムがよく見られます.


test.py

if __name__ == "__main__":

print("hoge")

このtest.pyを単体で実行するとhogeと表示されます.一方モジュールとしてimportされた場合にはprint("hoge")は実行されません.


test.py

print("hoge")


上記の場合単体で実行してもモジュールとしてimportしてもhogeと表示されます.Pythonのimportモジュールのトップレベルに現れた式をすべて実行するからです.if __name__ ...はこの仕組みで望まないコードがインポート時に実行されるのを防ぐ仕組みだったわけです.

逆に言えばあるモジュールがインポートされたときに環境をいじくり回したい場合にはモジュールのトップレベルにその処理を書いておけばいいわけです.

従って例えば以下のように組み込み関数を増設することができます.


hoge.py

import builtin

builtin.functions.update(hoge=lambda: print(hoge))

この拡張を仮にhoge拡張としますが,hoge拡張を有効にしたいときだけhoge.pyをインポートする形にすれば元の実装を触らずに拡張機能を追加することができます.

今回はこのやり方で数値とリスト操作の2つの拡張を実装しました.以下よりそれぞれの詳細です.


拡張その1:数値

かなり手抜きですがまずシンボル(実体は文字列)をfloatに変換する特殊形式を実装します.


number.py(continue)

import builtin

special_forms = {
"number": lambda number, env, hook: float(number),
}

builtin.special_forms.update(special_forms)


なんてことはないですね.ただ毎回(number 100)とかやってられないので以下のリーダマクロを定義します.


number.py(continue)

import read

from string import digits

def value_error(stream):
"Wrong number literal in file {name} at file position {position} (row: {row}, col: {col})"
raise ValueError(value_error.__doc__.format(**read.describe_stream(stream)))

def read_number(stream):
num_string = ""
stream.seek(stream.tell() -1)
char = read.peek_char(stream)
while char in digits + ".":
num_string += read.read_char(stream)
char = read.peek_char(stream)
return ["number", num_string]

read.readtable.update({key: read_number for key in digits})


これで例えば100(number 100)に展開されます.

四則演算の関数群をちゃちゃっと実装します.単にfloatの演算子メソッドを呼ぶだけです.


number.py(end)

functions = {

"+": float.__add__,
"-": float.__sub__,
"*": float.__mul__,
"/": float.__truediv__,
}

builtin.functions.update(functions)


出来上がりは以下です.


number.py

from . import _import

import read
import builtin

special_forms = {
"number": lambda number, env, hook: float(number),
}

functions = {
"+": float.__add__,
"-": float.__sub__,
"*": float.__mul__,
"/": float.__truediv__,
}

builtin.special_forms.update(special_forms)
builtin.functions.update(functions)

from string import digits

def value_error(stream):
"Wrong number literal in file {name} at file position {position} (row: {row}, col: {col})"
raise ValueError(value_error.__doc__.format(**read.describe_stream(stream)))

def read_number(stream):
num_string = ""
stream.seek(stream.tell() -1)
char = read.peek_char(stream)
while char in digits + ".":
num_string += read.read_char(stream)
char = read.peek_char(stream)
return ["number", num_string]

read.readtable.update({key: read_number for key in digits})


なお頭にあるfrom . import _importですがこれは上位ディレクトリにあるモジュールをインポートするための小技です.真似はしない方向でお願いします


_import.py

from sys import path

path.append("../")

詳しくはgithubのREADMEを見ていただければ幸いですが以下のようにしてnumber拡張を有効にできます.

$ ./lisp --ext number

LISP on Python 3.6.0 (default, Jul 28 2017, 08:43:21)
[GCC 4.9.4] on linux
Type :help, :copyright for more information.
[Enabled extensions: ['number']]

> (+ 0 10)
10.0
>


拡張その2:リスト操作

続いてリスト操作です.listやいわゆるcxxxrを追加します.ここもサボりですがリストはまんまPythonのリストです.まず最初に簡単なところから.


list.py(continue)

functions = {

"list": lambda *args: list(args),
"car": lambda lst: lst[0],
"cdr": lambda lst: lst[1:],
"length": len,
}

carcdrが重複してますがここはスルーでお願いします.

次にcxxxrですがこれはcarcdrの合成関数群のことです.例えば(caadr x)(car (car (cdr x)))のエイリアスとなります.

まずxxxの部分が"aad"のような文字列で与えられた場合に適切な関数を作る補助関数を定義します.


list.py(continue)

from functools import reduce

def xxx_to_function(xxx):
funcs = [functions[f"c{x}r"] for x in xxx]
return reduce(lambda f, g: lambda x: f(g(x)), funcs, lambda x: x)

すこし難解ですが文字列からcarcdrのリストを作成し,2つの関数を合成する関数とともにitertools.reduceに渡しています.

あとはこれを利用して辞書内包で片付けます.


list.py(end)

cxxxr = {

f"c{xxx}r": xxx_to_function(xxx) for n in range(2, 5) for xxx in set(map("".join, permutations("ad" * n, n)))
}

builtin.functions.update(functions, **cxxxr)


これまた難解に見えるかもしれませんが単に数を増やしながらadの順列を取って重複を削除,先の関数に渡しているだけです.重複を除きたいときにはsetが便利で良いです.全体的にもう少し良いやり方がありそうですがひとまずできているので良しとします.これで計28のcxxxrが生成されているはずです.

先程と同様にして試してみます.

$ ./lisp --ext list

LISP on Python 3.6.0 (default, Jul 28 2017, 08:43:21)
[GCC 4.9.4] on linux
Type :help, :copyright for more information.
[Enabled extensions: ['list']]

> (list 'a 'b 'c)
(a b c)
> (cadr (list 'a 'b 'c))
b
>

良いですね.


まとめ

一体誰が興味があるのか謎な話題ですが自分で実装したLispを自分で拡張してみました.個人的にはリードテーブルをいじくれるようにしておいたのが結構クールだと思うのですがどうでしょうか.

もし興味を持たれた方はぜひ触ってみてください.src/extensions以下に独自の拡張を追加してビルドし直せば同じように使えるはずです.最後までお読みいただきありがとうございました.