（Pythonで）Lispインタープリタを（作成する）方法 (2010)

（Pythonで）Lispインタープリタを作成する方法\nこのページには二つの目的があります。一つは、コンピュータ言語のインタープリタ全般の実装方法を説明すること、もう一つは、実装言語としてPython 3を使用して、LispのScheme方言のほとんどに対応するインタープリタを構築することです。私は自分の言語とインタープリタをLispy（lis.py）と呼んでいます。数年前、私はJavaとCommon Lispで半実用的なSchemeインタープリタを作成する方法を示しました。今回、目標としているのは、アラン・ケイが「ソフトウェアのマクスウェル方程式」と呼んだものを、できるだけ簡潔かつシンプルに示すことです。なぜこれが重要なのでしょうか？スティーブ・イエッゲが言ったように、「コンパイラの仕組みを知らないなら、コンピュータの仕組みを知らないことになる」からです。イエッゲは、コンパイラ（またはインタープリタ、あるいはイエッゲ特有の皮肉たっぷりな視点でも）で解決できる8つの問題について説明しています。\nSchemeプログラムの構文と意味論\n言語の構文とは、正しい文や式を形成するための文字の配置であり、意味論とは、それらの文や式の意味です。例えば、数学的表現の言語（そして多くのプログラミング言語）では、1足す2の構文は「1 + 2」であり、意味論は2つの数に加算操作を適用して値3を生成することです。値が決定されるときに式を評価すると言います。私たちは「1 + 2」が3に評価されると言い、「1 + 2」⇒ 3と書きます。Schemeの構文は、他のほとんどのプログラミング言語とは異なります。比較してみましょう：\nJava Scheme\nif (x.val() > 0) { return fn(A[i] + 3 * i, new String[] {"one", "two"}); } (if (> (val x) 0) (fn (+ (aref A i) (* 3 i)) (quote (one two)))\nJavaには多種多様な構文規則（キーワード、中置演算子、3種類の括弧、演算子の優先順位、ドット記法、引用符、コンマ、セミコロン）がありますが、Schemeの構文ははるかにシンプルです。Schemeプログラムは式のみで構成されます。文と式の区別はありません。数値（例：1）とシンボル（例：A）はアトミック式と呼ばれ、分割できません。これらはJavaの対応するものと似ていますが、Schemeでは+や>のような演算子もシンボルであり、Aやfnと同じように扱われます。その他のすべてはリスト式です：「(」に続いて0個以上の式が続き、「)」で閉じます。リストの最初の要素がその意味を決定します：キーワードで始まるリスト、例えば(if ...)、は特殊形式であり、意味はキーワードに依存します。キーワード以外で始まるリスト、例えば(fn ...)、は関数呼び出しです。Schemeの美しさは、完全な言語に必要なキーワードが5つ、構文形式が8つしかないことです。対照的に、Pythonには33のキーワードと110の構文形式があり、Javaには50のキーワードと133の構文形式があります。多くの括弧は威圧的に見えるかもしれませんが、Schemeの構文はシンプルさと一貫性という美徳を持っています。（「Lisp」は「Lots of Irritating Silly Parentheses（たくさんの煩わしいおかしな括弧）」の略だと冗談を言う人もいますが、私は「Lisp Is Syntactically Pure（Lispは構文的に純粋である）」の略だと思います。）\nこのページでは、Scheme言語とその解釈に関するすべての重要な点（いくつかの細かい詳細は省略）を扱いますが、そこに到達するために2つのステップを踏みます。まず単純化された言語を定義し、その後にほぼ完全なScheme言語を定義します。\n言語1：Lispy計算機\nLispy計算機は、わずか5つの構文形式（2つのアトミック、2つの特殊形式、および手続き呼び出し）を使用するSchemeのサブセットです。Lispy計算機では、典型的な電卓でできるあらゆる計算ができます。ただし、前置記法に慣れていればの話です。また、典型的な電卓言語では提供されていない2つのことができます：「if」式と新しい変数の定義です。半径10の円の面積をπ r2の公式を使って計算するプログラムの例を次に示します。\n(define r 10)\n(* pi (* r r))\n許容されるすべての式のリストを次に示します。\n* 変数参照 (symbol)：シンボルは変数名として解釈され、その値は変数の値です。例：r ⇒ 10（rが以前に10と定義されていると仮定）\n* 定数リテラル (number)：数値はそれ自体に評価されます。例：12 ⇒ 12 または -3.45e+6 ⇒ -3.45e+6\n* 条件分岐 ((if test conseq alt))：testを評価し、真であればconseqを評価して返し、そうでなければaltを評価して返します。例：(if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6\n* 定義 ((define symbol exp))：新しい変数を定義し、式expを評価した値を与えます。例：(define r 10)\n* 手続き呼び出し ((proc arg...))：procがif、define、quote以外のシンボルである場合、それは手続きとして扱われます。procとすべてのargsを評価し、その後、手続きがarg値のリストに適用されます。例：(sqrt (* 2 8)) ⇒ 4.0\nこの表の「構文」列では、symbolはシンボル、numberは整数または浮動小数点数である必要があり、他の斜体語は任意の式です。表記arg...は、argの0回以上の繰り返しを意味します。\n言語インタープリタの機能\n言語インタープリタには二つの部分があります。パース：パースコンポーネントは、一連の文字の形式で入力プログラムを受け取り、言語の構文規則に従って検証し、プログラムを内部表現に変換します。単純なインタープリタでは、内部表現はプログラム内の文や式のネストされた構造を密接に反映するツリー構造（しばしば抽象構文木と呼ばれる）です。コンパイラと呼ばれる言語トランスレータでは、抽象構文木から始まり、コンピュータが直接実行できる一連の命令へと進行する一連の内部表現がしばしばあります。Lispyのパーサは関数parseで実装されています。実行：内部表現はその後、言語の意味規則に従って処理され、それによって計算が実行されます。Lispyの実行関数はevalと呼ばれます（これはPythonの同名の組み込み関数をシャドウしていることに注意してください）。インタープリタ処理の図を次に示します：program ➡ parse ➡ abstract-syntax-tree ➡ eval ➡ result\nparseとevalが実行できることを示す短い例を次に示します（beginは各式を順番に評価し、最後のものを返します）：\n>> program = "(begin (define r 10) (* pi (* r r)))"\n>>> parse(program)\n['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]\n>>> eval(parse(program))\n314.1592653589793\n型定義\nSchemeオブジェクトの表現について明示しましょう：\nSymbol = str # SchemeシンボルはPythonのstrとして実装されます\nNumber = (int, float) # Scheme数値はPythonのintまたはfloatとして実装されます\nAtom = (Symbol, Number) # SchemeアトムはSymbolまたはNumberです\nList = list # SchemeリストはPythonのリストとして実装されます\nExp = (Atom, List) # Scheme式はAtomまたはListです\nEnv = dict # Scheme環境（下記で定義）は{変数: 値}のマッピングです\nパース：parse、tokenize、およびread_from_tokens\nパースは伝統的に二つの部分に分けられます：字句解析では、入力文字列がトークンのシーケンスに分割され、構文解析では、トークンが抽象構文木に組み立てられます。Lispyのトークンは括弧、シンボル、数値です。字句解析には多くのツール（Mike LeskとEric Schmidtのlexなど）がありますが、ここでは非常にシンプルなツールであるPythonのstr.splitを使用します。関数tokenizeは、文字の文字列を入力として受け取ります。各括弧の周りにスペースを追加し、str.splitを呼び出してトークンのリストを取得します：\ndef tokenize(chars: str) -> list:\n "Convert a string of characters into a list of tokens."\n return chars.replace('(', ' ( ').replace(')', ' ) ').split()\nここで、tokenizeをサンプルプログラムに適用します：\n>>> program = "(begin (define r 10) (* pi (* r r)))"\n>>> tokenize(program)\n['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']\n私たちの関数parseは、プログラムの文字列表現を入力として受け取り、tokenizeを呼び出してトークンのリストを取得し、その後、read_from_tokensを呼び出して抽象構文木を組み立てます。