Python, web, Algorithm 技術的なメモ

技術的なメモを書いていきます．pythonistaを目指しています．

（Pythonによる簡単なLispインタープリタ実装方法（四則演算編））

lisp Python Algorithm

この記事はPython Advent Calendar 2014 11日目の記事です

Pythonによる簡単なLispインタープリタ実装方法

lispのインタープリタの実装を行う事により，プログラミング，コンピュータへの知識を 深める事を目的としています．今回は，以下のように2部に分けてLispインタープリタ実装方法を紹介します． （ただ，lispで四則演算ができるインタープリタを作成できれば，インタープリタの概念は理解出来ると思います．また，今回はpython3以降を想定しています．）

  1. 四則演算編
  2. 関数編 (一週間後くらいに書きます．すみません．すこし落ち着いたら書きます．)

なお，今回のLispインタープリタ実装を紹介するきっかけとなったのが，「ギークエンジニア必見！Lispインタープリター」勉強会 with すごい広島 - すごい広島 | Doorkeeperに参加した事でした．これを機にPythonでも実装してみようと思いました．幸い，Peterさんがブログ(How to Write a (Lisp) Interpreter (in Python))で既にPythonでの実装を紹介しております．今回はこのブログを参考にし，lispインタープリタ実装を紹介したいと思います．

先に，彼らに敬意と感謝の気持ちを記しておきたいと思います． さて，前置きが長くなりましたが，まずは四則演算編を紹介していきたいと思います．

インタープリタ概要

さて，今回はインタープリタを作りたいわけですが，インタープリタってどう動作するのでしょうか． 簡単に図示すると以下の通りになります．

プログラム（文字列）⇒　構文解析器　⇒　構文木（list） ⇒　評価（eval） ⇒　結果

となります．つまり，文字列であるプログラムを構文解析器に入れます．そうすると，構文木（今回はpythonで扱える構造なのでlist）が 出来上がります．構文木はインタープリタ内で処理出来る形です．最後に構文木を評価しプログラムが意図している結果を出力します．

実際に作成したインタープリタでは，以下のようなステップを踏んでプログラムを評価（実行）します．

>>> program = "(* 1 3)" # このようなプログラムがあります
# プログラムをparser（構文解析器）に入れます．
>>> ast = parse(program) # 構文木を生成します．astはabstract syntax tree(抽象構文木の略)
>>> ast
['*', 1, 3]　#このようにPythonで扱えるようなlist構造に変換します（つまり，インタープリタで扱える構文木になっている）
>>> eval(ast) # astを評価
4 # 1 * 3の結果

行っている事は凄い単純です．文字列をインタープリタ（python）が扱える形に変換して，それをlispの構文に沿って解釈するだけです． 以上が，概要となります．次は，四則演算を早速作っていきましょう．

四則演算作成に当たって，以下の事を順に説明していきます．

  1. 文字列からトークンを生成する（字句解析（Lexical Analysis））⇒　tokenize
  2. 1の結果を用いて構文解析をする（Syntactic Analysis）⇒ parse
  3. 四則演算等の手続きを参照可能とする環境(Enviornment)の構築（メモリの構築） ⇒ starndard_env
  4. 2の結果を評価(eval)する

1. 字句解析(Lexical Analysis)

構文解析は字句解析と構文解析部に分けられます．字句解析では，意味のあるトークンに分けます． 本来ならば，正規表現を使うべきですが，インタープリタの動作を理解するのが本稿の目的なのでそこは割愛します． 今回の字句解析は以下のようにカッコにスペースを追加する形にして(replace)，スペースでトークンを区切ります(split)．

def tokenize(chars):
    return chars.replace('(', ' ( ').replace(')', ' ) ').split()

実行例

>>> tokenize("(* 1 3)")
['(', '*', '1', '3', ')'] #トークン毎に分離
>>> tokenize("(define square (lambda (r) (* r r)))") #square関数の定義(これは関数編で詳しく見ていきます．)
['(', 'define', 'square', '(', 'lambda', '(', 'r', ')', '(', '*', 'r', 'r', ')', ')', ')']

2. 構文解析(Syntactic Analysis)

さて，次に構文解析ですが，構文解析は３つの関数から構築していきます．

parseはプログラムを字句解析した結果を読み込む関数read_from_tokensのラッパー関数です．

def parse(program):
    return read_from_tokens(tokenize(program))

次に，read_from_tokensを見ていきましょう．

3行目：関数tokenizeの結果tokensはlistなので，pop(0)で最初の要素をtokenに入れます．

11行目:tokenが)から始まるとエラーSyntaxError('unexpected')を返します．

12行目:tokenが(,)のどちらでも無ければ，文字列であるシンボルを正しい型に変換する関数atomに渡す．

14行目から始まるatomは単純にintキャストを試みて，ダメだったらfloat,ダメだったらstrを返す関数です．

ここまでで，read_from_tokensがシンボルがあれば，シンボルを適切な値にして返す関数である事がわかりました． 次に，

4行目:tokenが(から始まるのであれば以下の動作を行います．

新しいリストLを作成しtokensの最初の要素が)になるまで再帰的に自分の返り値をLに入れる． つまり，１つのカッコの始まりから，終端までのトークンを入れていきます．また，その中にカッコが含まれると新しいLを作成し， 同様の動作を行います．文章で説明するのは難しいですね．例を見ていきましょう．

この関数の動作例．

プログラム(* 1 3)　があるとします．
parseに渡します．
>>> parse("(* 1 3)")
字句解析してトークンに分けます．
tokenize("(* 1 3)")
['(', '*', '1', '3', ')']
を得ます．
これをread_from_tokensに渡します．
read_from_tokens(tokens)

すると，カッコがあるので，
　Lを作成(以下再帰的に実行)
　Lに*を入れます．atomでstr型にする．
　Lに1を入れます．atomでint型にする．
　Lに3を入れます．atomでint型にする．
  )まできたので，カッコを捨てます．
  Lを返します．
read_from_tokens(tokens)の結果，
['*', 1, 3]をread_from_tokensの結果として返します（parseの結果）

で，Lなんの為にあるのと思うかもしれません．これは，カッコがネストになっている時に， 各カッコの中身を一時的に保持する役目を持ちます．一時的に保持してそれを，最終的には１つのリストに渡します． つまり，ネスト構造をとるリストになります．[[],[],[]]のような感じ

もう１つ例を見てみましょう．

プログラム(* (* 1 3) 5)　があるとします．
parseに渡します．
>>> parse("(* (* 1 3) 5)")
字句解析してトークンに分けます．
tokenize("(* (* 1 3) 5)")
['(', '*', '(', '*', '1', '3', ')', '5', ')']
を得ます．
これをread_from_tokensに渡します．
read_from_tokens(tokens)

すると，カッコがあるので，
　Lを作成(以下再帰的に実行)
　Lに*を入れます．atomでstr型にする．
     カッコがあるので，
　　 Lを作成します．（二個目のLで，これは一番最初のLとはメモリの場所が異なる．つまり，ネストしている中でのLである）
　　 Lに*を入れます．atomでstr型にする．　
　　 Lに1を入れます．atomでint型にする．
　　 Lに3を入れます．atomでint型にする．
　　 )まできたので，カッコを捨てます．
     結果を返します．この結果は外枠のLに渡します．
  Lに5を入れます．atomでint型にする．
  )まできたので，カッコを捨てます．
  Lを返します．
read_from_tokens(tokens)の結果，
['*', ['*', 1, 3], 5]をread_from_tokensの結果として返します．（parseの結果）

今回は，8行目にあるように動きを確認するためにLのprint文を挟んでいます． print文の実行結果を見てましょう．

parse("(* (* 1 3) 5)")
['*']
['*']
['*', 1]
['*', 1, 3]
['*', ['*', 1, 3]]
['*', ['*', 1, 3], 5]

まさに上記で説明したように，Lに値を入れていって，カッコがきたら新しいL(list)を作ってそれを元のLに入れていくというのを， 再帰で表現する事で，lispのネストを表現しています．

かなり重複するところもありましたが，これでparseの動きが分かったかと思います． 最後にまとめると，parseは文字列であるプログラムを字句解析でトークン化し，それをインタープリタが解釈出来る形に していきました．今回では，pythonが理解出来るlist型を利用して，構文木を表現しました． なんかもの凄く長く書き過ぎているし， もうやめたいと思ったりもしますけれども次に進みたいと思います．

3. 環境(Environment)

次は，環境についてです．ここまでは，文字列であるプログラムをインタープリタ内部でどう解釈していくかを 見てきました．では，*等の演算子や手続き(procedure)をどう解釈し，それを被演算子（operand）に適用していけば 良いのでしょうか．環境は，演算子・手続きとその動作を紐づけています． では，その環境をどう表現するか見ていきましょう．pythonの辞書で紐づけていきます．

7 ~ 10行目で各演算子の記号をpythonの演算子に紐づけています．このpythonの各演算子は引数を2つとります．

e.g

>>> import operator as op
>>> op.add(1,3)
4

このように，環境に各シンボルに対応づける処理のペアを格納します．

4. 評価(eval)

環境に各シンボルの行う処理のペアを格納しました．それでは，シンボルをどう評価し結果を出すのでしょうか． まず先に，復習をかねて評価までのステップ例を見ましょう．

>>> ast = parse("(* (* 1 3) 5)") #文字列のプログラムから構文木astを作成
>>> print(ast)
['*', ['*', 1, 3], 5]
>>> eval(ast) #astを評価し，実行結果を得る．
15

評価では，プログラムを解析して得られた構文木を実行して結果を得ます． そのために，引数としてastと利用する環境を指定します．

では，実行例を交えてコードの解説に入ります．

>>> ast = parse("(* (* 1 3) 5)") #['*', ['*', 1, 3], 5]
>>> eval(ast)

上記のとき，まずevalでは，listであるastを引数と取り，環境envは先程定義した環境（global env）を利用します．

1.　x(=ast)はシンボルでなく，リストであるので，一番最後のブロック(7行目~)が実行されます．
2.  手続きprocとして，astの最初の要素を再帰的に評価します．評価結果がprcに代入されます．
2.1 x(='*')はシンボルなので，3行目が実行されます．3行目では，環境に入っている関数を呼び出します．この場合`op.mul`を返し，procにop.mulを代入します
3   引数argsとして，最初の要素以外の部分を全て評価し，引数としてargsに代入します．
3.1 まず最初はargsに['*', 1, 3]が割り当てられ，これが評価されていきます
3.1.1 2.1, 2.2と同様に'*'が評価され，procにop.mulが代入されます．
3.1.2 x(=1)はシンボルでも，リストでも無いので，そのまま1を返します
3.1.3 x(=3)はシンボルでも，リストでも無いので，そのまま3を返します
3.1.4 args = [1,3]をとり，op.mul(1,3)が実行され，3を返します．
2.2 x(=5)はシンボルでも，リストでも無いので，そのまま5を返します
2.3 args = [3,5]をとり，op.mul(3,5)が実行され，15を返します．

結果，15が得られます

このように再帰的に，に演算子・手続きを被演算子に適用し評価していく形をとり，最終的な評価を行います． これで，演算子を評価するlispインタープリタが作成する事ができました．

REPL(read-evaluation-print-loop)を実装すればインタープリタのように実行し，結果の確認をする事ができます． 簡単に記述すると以下のようになります．

どうでしょうか，演算子を評価出来る簡単なlispインタープリタを作成できました． 単純な動作を積み上げていくだけでインタープリタが作成できるのは凄く面白かったと思います．

次回は，関数定義，if文等を実装してlispプログラミングできるようにしていきたいと思います． ですが，今回の演算子の作成方法が分かればあとは自分で作る事も可能です．次回の投稿までに 実装方法を考えてみて下さい．

今回の全体を通してのコードは以下のようになります．