（（Lisp）インタープリターの作成方法（Python））

Peter Norwigによる記事（How to a（Lisp）Interpreter（in Python））の翻訳。 この記事では、Peterがインタプリタの仕組みを簡潔かつ簡潔に説明し、Scheme言語のサブセットの非常に小さな（Pythonでは90行のみ）インタプリタを作成する方法を示します。 翻訳は著者の許可を得て公開されています。



Peter Norvigはアメリカのコンピューター科学者です。 現在、Googleのリサーチディレクター（以前の検索品質ディレクター）として働いています。 以前は、NASAのAmes Research Centerのコンピューターエンジニアリング部門の責任者であり、解剖学とロボット工学、コンピューター支援ソフトウェア開発とデータ分析、神経工学、協調システム設計、シミュレーションベースの意思決定の分野で、NASAの200人の研究者のスタッフを率いていました。





この記事には2つの目的があります。プログラミング言語のインタープリターの実装を一般的に説明することと、 Pythonを使用するLisp方言であるScheme言語のサブセットの実装を示すことです 。 インタープリターにLispy （ lis.py ）という名前を付けました。 1年前、 JavaとCommon Lispで Schemeインタープリターを書く方法を示しました。 今回、目標は、 Alan Kayが Maxwellのソフトウェアの方程式と呼んだものを、できる限り簡潔かつアクセスしやすいものにすることです。

Lispyの構文とセマンティクス

ほとんどのプログラミング言語には異なる構文規則（キーワード、中置演算子、括弧、演算子の優先順位、ドット表記、セミコロンなど）がありますが、Lisp言語ファミリーのメンバーとして、すべてのScheme構文は括弧で囲まれたリストに基づいていますプレフィックス表記。 この形式はなじみがないように見えるかもしれませんが、単純さと一貫性の点で利点があります。 「Lisp」は「刺激的な愚かな括弧がたくさんある 」というジョークもありますが、 「 Lispは構文的に純粋です」という意味だと思います。 参照：

Java		スキーム
if ( x.val() > 0 ) {<br> z = f(a * x.val() + b); <br>}		(if (> (val x) 0)<br> (set! z (f (+ (* a (val x)) b))))

感嘆符はSchemeの特殊文字ではなく、名前「 set!



」の一部にすぎないことに注意してください ブラケットのみが特殊文字です。 先頭に特別なキーワードが付いた(set! xy)



などのリストは、Schemeでは特別な形式と呼ばれます。 この言語の美しさは、6つの特別な形式と3つの構文構造（変数、定数、手続き呼び出し）だけが必要であるという事実にあります。

形	構文	セマンティクスと例
変数参照	var	シンボルは変数の名前として解釈され、その値は変数の値です。 例： x
定数リテラル	数	数字はそれ自体を意味します。 例： 12 または -3.45e+6
引用	(quote exp )	expを評価せずにそのまま返します。 例： (quote (abc)) ⇒ (abc)
条件付き	(if テスト結果がaltの (if )	テストを計算します 。 trueの場合、 conseqを計算して返します 。 それ以外の場合はaltを計算して返します。 例： (if (< 10 20) (+ 1 1) (+ 3 3)) ⇒ 2
割り当て	(set! var exp )	expを計算し、その値をvar変数に割り当てます。var変数は、事前に定義する必要があります（ define を使用define か、手続きパラメーターとして使用）。 例： (set! x2 (* xx))
定義	(define var expを (define )	ネストされた環境自体に新しい変数を定義し、式expを評価する値を与えます。 例： (define r 3) または (define square (lambda (x) (* xx))) 。
機能	(lambda ( var ... ) exp )	名前がvar ...でパラメーターが（s）で、本体に式を持つ関数を作成します。 例： (lambda ( r ) (* 3.141592653 (* rr)))
シーケンシング	(begin exp ...を (begin )	各式を左から右に計算し、最後の値を返します。 例： (begin (set! x 1) (set! x (+ x 1)) (* x 2)) ⇒ 4
手続き呼び出し	( proc exp ... )	procが if, set!, define, lambda, begin, quote いずれif, set!, define, lambda, begin, ないif, set!, define, lambda, begin, プロシージャと見なされます。 ここで定義されているのと同じルールに従って計算されます。 すべての式が評価された後、引数の式のリストを使用して関数が呼び出されます。 例：（ (square 12) ⇒ 144

この表では、 varはx



やsquare



などの識別文字でなければなりません。 number-整数または浮動小数点数である必要がありますが、斜体の残りの単語は任意の式にできます。 exp ...という指定は、 expが 0回以上繰り返されることを意味します。



スキームの詳細については、次の優れた書籍（ Friedman and Fellesein 、 Dybvig 、 Queinnec 、 Harvey and WrightまたはSussman and Abelson ）、ビデオ（ Abelson and Sussman ）、紹介（ Dorai 、 PLT 、またはNeller ）、またはリファレンスガイドを ご覧 ください 。

言語インタープリターが行うこと

インタープリターは2つの部分で構成されています。

1. 解析：解析コンポーネントは、文字のシーケンスとしてプログラム入力を受け取り、言語の構文規則に従ってチェックし、プログラムを内部表現に変換します。 単純なインタープリターでは、内部表現はツリー構造のように見え、プログラム内のネストされた演算子と式の構造を正確に反映します。 コンパイラと呼ばれる言語変換プログラムでは、内部表現はコンピューターによって直接実行できる一連の命令です。 スティーブ・イェッジが言ったように 、 「コンパイラの仕組みがわからなければ、コンピューターの仕組みはわからない」 Egggeは、コンパイラー（または同等のインタープリター）を使用して解決できる8つのシナリオを説明しました。 Lispyパーサーは、 parse
   
   
   
   関数を使用して実装されます。
   
   
2. 実行：内部表現は言語のセマンティックルールに従って処理され、それによって計算が実行されます。 実行はeval
   
   
   
   関数によって実行されます（Python組み込み関数が非表示になることに注意してください）。
   
   

これは、解釈プロセスと対話型セッションがどのように見えるかであり、 parse



とeval



が短いプログラムを処理する方法を示しています。

>>プログラム= "（begin（define r 3）（* 3.141592653（* r r））））"



>>>解析（プログラム）

[ ' begin '、 [ ' define '、 'r'、 3 ] 、 [ ' * '、 3.141592653 、 [ ' * '、 'r'、 'r' ] ] ]



>>> eval （解析（プログラム） ）

28.274333877

最も単純な内部表現を使用します。リスト、数字、およびスキーム文字は、それぞれPythonリスト、数字、および文字列で表されます。

実行： eval

上記の表の9つのケースには、それぞれ1行、2行、または3行のコードがあります。 eval



を定義するためにこれ以上必要なものはありません：

def eval （ x、env = global_env ） ：

「環境で式を評価します。」

if isa （ x、Symbol ） ： ＃変数参照

envを返します。 検索 （ x ） [ x ]

elif not isa （ x、 list ） ： ＃定数リテラル

xを返す

elif x [ 0 ] == 'quote' ： ＃（quote exp）

（ _、exp ） = x

expを返す

elif x [ 0 ] == 'if' ： ＃（if test conseq alt）

（ _、 test 、conseq、alt ） = x

戻り値 eval （ （ eval （ test 、env ）の 場合は conseq 、 else alt ） 、env ）

elif x [ 0 ] == 'set！' ： ＃（設定！var exp）

（ _、var、exp ） = x

環境 find （ var ） [ var ] = eval （ exp、env ）

elif x [ 0 ] == 'define' ： ＃（define var exp exp）

（ _、var、exp ） = x

env [ var ] = eval （ exp、env ）

elif x [ 0 ] == 'lambda' ： ＃（lambda（var *）exp）

（ _、 vars 、exp ） = x

return lambda * args： eval （ exp、Env （ vars 、args、env ） ）

elif x [ 0 ] == 'begin' ： ＃（begin exp *）

x [ 1 ： ]の expの場合：

val = eval （ exp、env ）

戻り値

その他 ： ＃（proc exp *）

exps = [ xのexp に対して eval （ exp、env ） ]

proc = exps。 ポップ （ 0 ）

return proc （ * exps ）



isa = isinstance



シンボル= str

evalが必要なのはこれだけです！..環境を除いては。 環境とは、単に文字をそれらに属する値にマッピングすることです。 define



または（ lambda



expression）を使用して、新しい文字/値の関係が追加されdefine



。



Schemeで関数を宣言して呼び出すとどうなるかを見てみましょう（ヒントlis.py>



は、PythonではなくLispインタプリタと対話していることを意味します）。

lis.py > （面積を定義 （ lambda （ r ） （ * 3.141592653 （ * r r ） ） ） ））

lis.py > （エリア3 ）

28.274333877

(lambda ( r ) (* 3.141592653 (* rr)))



を実行すると、 elif x[0] == 'lambda'



ブランチにelif x[0] == 'lambda'



し、3つの変数(_, vars, exp)



にリストx



対応する要素を割り当てます（長さx



3 x



ない場合はエラーを通知します。 呼び出されたときに、関数の正式なパラメーターの束（この場合は1つのパラメーターr



のみ）によって形成される環境で式['*', 3.141592653 ['*', 'r', 'r']]



を評価する新しい関数を作成します関数呼び出しの引数、およびパラメーターではない変数（この例では変数*



）に現在の環境を使用します。 次に、この新しく作成された関数の値がglobal_env



area



値として割り当てられます。



さて、 (area 3)



を計算するとどうなりますか？ なぜなら areaは特殊な形式の文字ではなく、関数呼び出し（最後のelse:



eval



）を意味し、式のリスト全体が一度に実行されます。 area



計算は、作成した関数を返します。 計算3



は3



返します。 次に（ eval



の最後の行に従って）、引数リスト[3]



新しく作成された関数[3]



呼び出されます。 これは、 r



が3



で外部環境がグローバルである環境でexp



['*', 3.141592653 ['*', 'r', 'r']]



を実行することを意味します。したがって、 *



は乗算関数です。



これで、 Env



クラスの詳細を説明する準備ができました。

クラス Env （ dict ） ：

「環境：{'var'：val}ペアの辞書、外部Env。」

def __init__ （ self 、parms = （ ） 、args = （ ） 、outer = None ） ：

自己 。 更新 （ zip （ parms、args ） ）

自己 。 アウター =アウター

def find （ self 、var ） ：

「varが現れる最も内側のEnvを見つけます。」

var が selfの 場合 は selfを 返し 、そうでない場合 は selfを 返し ます 。 アウターの 検索 （ var ）

Env



クラスはdict



サブクラスであることに注意してください。つまり、通常の辞書操作がEnv



クラスで機能します。 さらに、コンストラクター__init__



とfind



2つのメソッドがあり、変数の正しい環境を見つけます。 このクラスを理解するための鍵（およびdict



を使用しているだけではない理由）は、 外部環境の概念です。 次のプログラムを検討してください。







各長方形は環境を表し、その色はこの環境で定義された変数の色に対応します。 最後の2行では、 a1



を定義して(a1 -20.00)



を呼び出します。 これらの2行は、残高が100ドルの銀行口座の作成と、その後の20ドルの引き出しを表しています。 実行中(a1 -20.00)



黄色で強調表示された式を評価します。 この式には3つの変数が関係しています。 amt



変数は、最もネストされた（緑の）環境ですぐに見つけることができます。 ただし、ここでbalance



定義されていません。外部環境で比較的グリーンな、つまり 青で。 そして最後に、変数+



これらの環境のいずれ+



も見つかりませんでした。グローバル（赤）環境にもう一歩踏み込む必要があります。 外部環境から外部へステップするこの検索プロセスは、字句スコープと呼ばれます。 Procedure.find



は、字句スコープに従って正しい環境を見つけます。



あとは、グローバル環境を定義するだけです。 +



および他のすべての関数をSchemeに組み込む必要があります。 それらをすべて実装することについて心配する必要はありません。Pythonでmath



モジュールをインポートし、20の人気のあるモジュールを明示的に追加することにより、必要なものを大量に取得します。

def add_globals （ env ） ：

「いくつかのScheme標準手順を環境に追加します。」

数学 、 演算子 を op として インポート

環境 更新 （ vars （ math ） ） ＃sin、sqrt、...

環境 更新 （

{ '+' ：op。 追加 、 「-」 ：op。 sub 、 「*」 ：op mul 、 「/」 ：op。 div 、 'not' ：op。 not_ 、

'>' ：op。 gt 、 '<' ：op。 lt 、 '> =' ：op。 ge 、 「<=」 ：op le 、 「=」 ：op eq

「等しい？」 ：op。 eq 、 'eq？' ：op。 is_ 、 'length' ： len 、 'cons' ： ラムダ x、y： [ x ] + y、

'car' ： ラムダ x：x [ 0 ] 、 'cdr' ： ラムダ x：x [ 1 ： ] 、 'append' ：op。 追加 、

'list' ： lambda * x： list （ x ） 、 'list？' ： ラムダ x：isa （ x、 list ） 、

「ヌル？」 ： ラムダ x：x == [ ] 、 'symbol？' ： ラムダ x：isa （ x、Symbol ） } ）

envを返す



global_env = add_globals （ Env （ ） ）

解析： read



とparse

次に、 parse



関数について説明します。 分析は伝統的に2つの部分に分割されます。 字句分析 （文字の入力文字列はトークンのシーケンスに分割されます）と解析 （トークンは内部表現で収集されます）。 Lispyトークンは、角括弧、文字（ set!



またはx



）、および数字です。 仕組みは次のとおりです。

>>> program = "（set！x * 2（* x 2））"



>>> tokenize （プログラム）

[ ' （ '、 ' set！ '、 'x * 2 '、 ' （ '、 ' * '、 'x'、 ' 2 '、 ' ） '、 ' ） ' ]



>>>解析（プログラム）

[ ' 設定！ '、' x * 2 '、 [ ' * '、' x '、 2 ] ]

字句解析用のツールはたくさんありますが（たとえば、Mike LeskとEric Sc​​hmidtのlex ）、簡単な方法を使用しますstr.split



を使用します。 各ブラケットの周りにスペースを追加するだけで、 str.split



を呼び出してトークンのリストを取得します。



構文解析について。 Lisp構文は非常にシンプルであることがわかりましたが、一部のLispインタープリターは、リストとしての文字列をプログラムとして受け入れることで、解析をさらに簡単にしました。 言い換えると、文字列(set! 1 2)



は構文的に正しいプログラムによって受け入れられ、実行時にのみインタープリターはそのset!



誓いset!



最初の引数として、数字ではなく文字が必要です。 JavaまたはPythonでは、 1 = 2



同等の割り当てがコンパイル時エラーとして認識されます。 一方、JavaおよびPythonは、 x/0



式のエラーのコンパイル中に検出を必要としません。したがって、ご覧のとおり、エラーを認識する必要がある場合、常に厳密に定義されているわけではありません。 Lispy read



、任意の式（数値、文字、またはネストされたリスト）を読み取る関数であるread



を使用してparse



を実装しread



。



read



関数は、字句解析後に受け取ったread_from



トークンを渡すread



機能します。 トークンのリストがあるため、最初のトークンを見てください。 ')'



は構文エラーです。 これが'('



場合、対応する')'



到達するまで式のリストの作成を開始します。 それ以外はすべて文字または数字である必要があり、それ自体が完全な表現です。 最後の秘Theは、 '2'



が整数を表し、 '2.0'



が浮動小数点数を表し、 x



が文字を表すことを知ることです。 Pythonでこれらの違いを作ることができます：括弧で囲まれていないトークンごとに、まず整数として、次に浮動小数点数として、最後に文字として解釈しようとします。 これらの指示に従うと：

def read （ s ） ：

「文字列からScheme式を読み取ります。」

return read_from （ tokenize （ s ） ）



解析=読み取り



def tokenize （ s ） ：

「文字列をトークンのリストに変換します。」

を返します。 replace （ '（' 、 '（' ） 。replace （ '）' 、 '）' ） 。 分割 （ ）



def read_from （ tokens ） ：

「トークンのシーケンスから式を読み取ります。」

len （ tokens ） == 0の場合 ：

SyntaxErrorを発生さ せ ます （ 「読み取り中の予期しないEOF」 ）

トークン =トークン。 ポップ （ 0 ）

'（' == トークンの場合 ：

L = [ ]

一方、トークン[ 0 ] ！ = '）' ：

L. append （ read_from （ tokens ） ）

トークン。 pop （ 0 ） ＃pop off '）'

リターン L

elif '）' == トークン ：

Raise SyntaxError （ 'unexpected）' ）

その他 ：

戻りアトム（ トークン ）



defアトム（ トークン ） ：

「数字は数字になります。他のすべてのトークンはシンボルです。」

try ： int （ token ）を 返し ます

ValueError を除く ：

try ： return float （ トークン ）

ValueError を除く ：

シンボル（ トークン ）を 返し ます

最後に、式を読みやすいLisp文字列に変換するためにto_string



関数を追加します。また、インタラクティブなインタープリターの形式でread-eval-printサイクルに必要なrepl



関数を追加しrepl



。

def to_string （ exp ） ：

「PythonオブジェクトをLispで読み取り可能な文字列に変換し直します。」

return '（' + '' 。join （ map （ to_string、exp ） ） + '）' if isa （ exp、 list ） else str （ exp ）



def repl （ prompt = 'lis.py>' ） ：

「プロンプト読み取り評価印刷ループ。」

Trueの場合 ：

val = eval （ parse （ raw_input （ prompt ） ） ）

val が None で ない 場合 ：to_string （ val ）を出力します

作業中のコードは次のとおりです。

>>> repl （ ）

lis.py > （面積を定義 （ lambda （ r ） （ * 3.141592653 （ * r r ） ） ） ））

lis.py > （エリア3 ）

28.274333877

lis.py > （ファクトを定義 （ lambda （ n ） （ if （ <= n 1 ） 1 （ * n （ fact （ -n 1 ） ） ） ） ） ） ） ）

lis.py > （事実10 ）

3628800

lis.py > （事実100 ）

9332621544394415268169923885626670049071596826438162146859296389521759999322991

5608941463976156518286253697920827223758251185210916864000000000000000000000000

lis.py > （エリア（事実10 ） ）

4.1369087198e + 13

lis.py > （最初の車を 定義 ）

lis.py > （ rest cdrを 定義 ）

lis.py > （ count （ lambda （ item L ）を 定義する （ if L （ + （ equal？ item （ first L ） ） （ count item （ rest L ） ） ） ） ） ） ） ） ）

lis.py > （カウント0 （ リスト 0 1 2 3 0 0 ） ）

3

lis.py > （ count （ quote the ） （ quote （ merrierが大きければ大きいほど良い） ） ））

4

Lispyはどのくらい小さい/速い/完全な/良いですか？

Lispyは次の基準で判断します。

• サイズ： Lispy tiny、コメントなしの90行、4K未満のソースコード。 96行の最初のバージョンに比べて行が少なくなっていますProcedure
  
  
  
  クラスの定義を削除し、代わりにPython lambda
  
  
  
  を使用するというEric Cooperの提案を受け入れました。 私のSchemeの最小Javaバージョン（ Jscheme ）は、1664行と57Kのソースコードで構成されていました。 Jscehemeは元々SILK（50キロバイトのスキーム、50キロバイトのスキーム）と呼ばれていましたが、結果のバイトコードに関してのみこの制限を満たしました。 これは、「コードページ」で「世界で最も強力な言語」を定義できるという1972年のアランケイの要件を満たしていると思います。
  
  

  bash $ grep "^ \ s * [^＃\ s]" lis.py | トイレ
  
  90 398 3423

  
  
  
• 速度： Lispyは0.004秒で(fact 100)
  
  
  
  計算します。 私にとっては、これは十分に高速です（ただし、他の多くの方法よりもはるかに遅いです）。
  
  
• 完了： LispyはScheme標準に完全には準拠していません。 主な欠点は次のとおりです。
  
  
  • 構文：コメントの欠落、引用符/準引用符、＃リテラル、派生式タイプ（ cond
    
    
    
    、 if
    
    
    
    から派生、 let
    
    
    
    、 lambda
    
    
    
    から派生）、およびドット付きリスト表記。
    
    
  • セマンティクス：呼び出し/ ccおよび末尾再帰が欠落しています。
    
    
  • データ型：行なし、単一文字、ブール型、ポート、ベクトル、正確/不正確な数値。 Pythonのリストは、実際にはペアやリストよりもSchemeのベクトルに近いです。
    
    
  • 関数： 100個以下のプリミティブ関数があり、そのほとんどは欠落データ型用に設計されており、その他にもいくつかあります（ set-cdr!



set-car!
    
    
    
    やset-cdr!



set-cdr!
    
    
    
    完全にPythonリストで使用できないset-cdr!
    
    
    
    ） 。
    
    
  • エラー処理： Lispyは、エラーの検出、許容可能なレポートの作成、または回復を試みません。 Lispyはプログラマーの優秀さを期待しています。
    
    
  
  
  
• 良い：読者次第です。 Lispインタプリタを説明することは、私の目的にとって良いことです。
  
  

実話

通訳がどのように機能するかを知ることが非常に役立つという考えに戻り、話をします。 1984年に、博士論文を書きました。 これはLaTeXの前、Microsoft Wordの前-troffを使用しました。 残念なことに、troffにはシンボリックラベルを参照する方法がありませんでした。「@ theoremxページで見るように」と書き、適切な場所に「@（set theoremx \ n％）」 troffは、ページ番号として\ n％を予約しています）。 私の友人のトニー・デロスも同じニーズを感じていたので、一緒にプリプロセッサとして機能する簡単なLispプログラムをスケッチしました。 しかし、当時持っていたLispは、Lisp式を読むのには適しているが、他のすべてを読むのは非常に遅く、迷惑であることが判明した。



トニーと私はさまざまな方法で行きました。 彼は式のインタープリターが難しい部分であると信じていたため、Lispが必要でしたが、非Lisp文字を繰り返してLispプログラムに関連付けるための小さなCサブルーチンの書き方を知っていました。 私はこのバインディングの作り方を知りませんでしたが、この些細な言語のインタープリター（変数の設定、変数値の取得、文字列の連結）を書くのは簡単な作業であると信じていたので、このインタープリターをCで書きました。 Tonyは私がCプログラマーだったのでLispでプログラムを書き、私がLispプログラマーだったのでCでプログラムを書いた。



最終的に、我々は両方の結果を達成しました。

すべて一緒に

完全なLispyコードはダウンロード可能です： lis.py