PythonでLispインタプリタを書く方法
PythonでLispインタプリタを書く方法
Lispインタプリタの実装は、コンピュータとコンパイラの仕組みを理解するための主要な手法です。Peter Norvigの"Lispy"プロジェクトは、LispのScheme方言の機能的なサブセットが、約117行のPython 3コードで実装可能であることを示しており、「世界で最も強力な言語」が非常に少量のソースコードで定義できることを証明しています。
言語インタプリタのアーキテクチャ
言語インタプリタは、主に「解析（parsing）」と「実行（execution）」の2つのコンポーネントで構成されます。プロセスは線形パイプラインに従います：Program $\rightarrow$ Parse $\rightarrow$ Abstract Syntax Tree (AST) $\rightarrow$ Eval $\rightarrow$ Result。
解析 (Parsing)
解析は、一連の文字を内部表現、通常は抽象構文木（AST）に変換します。Lispyでは、これは2つのフェーズに分割されます：
- 字句解析 (Tokenization): 入力文字列はトークン（括弧、シンボル、数値）に分解されます。Lispyは、括弧の周囲にスペースを追加し、Pythonの
str.splitを使用することでこれを実現しています。 - 構文解析: トークンは入れ子になったリスト構造に組み立てられます。
read_from_tokens関数は、開始括弧に遭遇すると再帰的にリストを構築し、括弧以外のトークンはアトム（整数、浮動小数点数、またはシンボル）として扱います。
実行 (Evaluation)
実行は、言語のセマンティクス（意味論）のルールに従ってASTを処理します。Lispyでは、eval関数が式のタイプに基づいて式の値を決定します：
- Symbols: 現在の環境（environment）で検索されます。
- Numbers: それ自身として評価されます。
- Special Forms:
ifやdefineのようなキーワードは、特定のロジック（例：条件分岐や変数代入）をトリガーします。 - Procedure Calls: オペレータと引数が評価され、結果として得られたプロシージャが引数の値に適用されます。
Lispy Calculatorの実装
インタプリタの最初のイテレーションである「Lispy Calculator」は、5つの基本的な構文形式をサポートしています：
| Expression | Syntax | Semantics |
|---|---|---|
| Variable Reference | symbol |
変数の値を返します。 |
| Constant Literal | number |
数値そのものを返します。 |
| Conditional | (if test conseq alt) |
testが真であればconseqを返し、そうでなければaltを返します。 |
| Definition | (define symbol exp) |
expの値をsymbolにバインドします。 |
| Procedure Call | (proc arg...) |
procとargsを評価し、その結果として得られたプロシージャを適用します。 |
完全なLispyへの拡張：プロシージャとレキシカルスコープ
計算機から、ほぼ完全なSchemeサブセットへと移行するために、Lispyはquote, set!, そしてlambdaを導入します。lambdaの追加には、環境（environments）を通じた高度な変数管理のアプローチが必要です。
Envクラスとレキシカルスコープ
ローカル変数と入れ子になった関数をサポートするために、環境はdictを継承するクラスとして再定義されます。各Envインスタンスは、独自のローカルなマッピングと、outer環境への参照を保持しています。
変数が参照されるとき、インタプリタはfindメソッドを使用して、まず最も内側の環境を検索します。変数が見つからない場合、再帰的にouter環境を検索します。このメカニズムはレキシカルスコープを実装しており、プロシージャが呼び出される場所ではなく、定義された場所の環境を参照することを保証します。
プロシージャの実装
Procedureオブジェクトは、パラメータ名、関数の本体、およびそれが作成された環境を保持します。呼び出されたとき、それは提供された引数をパラメータにバインドする新しいEnvを作成し、プロシージャの元の環境をouterスコープとして設定します。
パフォーマンスと完全性
Lispyは、本番環境での使用ではなく、教育的な明快さを目的として設計されています。その特徴は以下の通りです：
- Size: 極めてコンパクトであり、約117行の非空白行と4KBのソースコードで構成されています。
- Speed:
(fact 100)を約0.003秒で計算可能です。 - Limitations: テイルコール最適化、
call/cc、文字列、文字、ブール値、および包括的なエラーリカバリが欠如しているなど、いくつかの標準的なSchemeの機能が欠われています。
コミュニティの洞察
開発者や教育者は、Lispインタプリタの実装はコンピュータサイエンスの基礎的な演習であると考えています。議論の中で述べられているように：
"If you ever wondered how to write a programming language, this is probably the best resource to get started."
他の貢献者たちは、Lispのツリー構造と、言語学者が文構造を annotate するために使用する句構造文法との同型性を指摘しました。また、AIが現在そのようなコードを生成できるようになった一方で、プログラマーにとってインタプリタのプロジェクトは依然として「啓発的な経験」であると指摘する人もいました。