HN 日本語サマリー

← 一覧へ戻る
プログラミング

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

(How to Write a (Lisp) Interpreter (In Python)) (2010) (norvig.com)

180 pointsby tosh60 コメント

要約

この記事は、Python 3を使ってScheme方言のLispインタープリタ「Lispy」を実装する方法を解説しています。アラン・ケイが言うところの「ソフトウェアのマクスウェル方程式」を簡潔に示し、コンパイラやインタープリタの仕組みを理解することの重要性を強調しています。Schemeのシンプルな構文と、インタープリタの主要な2つの部分である「パース」と「実行」について、具体的なコード例を交えながら説明しています。

全文翻訳

(Pythonで(Lisp)インタプリタを書く方法)

この記事は、一般的なコンピュータ言語のインタプリタの実装方法、特にPythonを実装言語として使用して、Lispの方言であるSchemeの大部分を解釈するインタプリタを構築する方法を説明することを目的としています。私の言語とインタプリタをLispyと呼びます(lis.py)。数年前、私はJavaで、そしてCommon Lispで、実用的なSchemeインタプリタの書き方を示しました。今回は、Alan Kayが「ソフトウェアのマクスウェル方程式」と呼んだものを、可能な限り簡潔かつ単純に実証することを目標とします。

なぜこれが重要なのでしょうか? Steve Yeggeが述べたように、「コンパイラがどのように機能するかを知らなければ、コンピュータがどのように機能するかを知らないことになります。」Yeggeは、コンパイラ(あるいは同様にインタプリタ、またはYegge特有の皮肉を大量に含んだもの)で解決できる8つの問題について説明しています。

Schemeプログラムの構文と意味論

言語の構文とは、正しい文や式を形成するための文字の配置であり、意味論とは、それらの文や式の意味です。例えば、数学的表現の言語(および多くのプログラミング言語)では、1に2を足す構文は「1 + 2」であり、意味論はその2つの数値に加算操作を適用し、値3を生成することです。計算結果を決定することを評価すると言います。「1 + 2」は3に評価されると言い、「1 + 2」 ⇒ 3と書きます。

Schemeの構文は、ほとんどの他のプログラミング言語とは異なります。以下をご覧ください:

JavaScheme
if (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)))

Javaには、キーワード、中置演算子、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は構文的に純粋である)の略だと考えています。)

この記事では、Scheme言語とその解釈の重要な点をすべて(いくつかの些細な詳細を除く)カバーしますが、まず単純化された言語を定義し、次にほぼ完全なScheme言語を定義するという2段階で進めます。

言語1:Lispy Calculator

Lispy Calculatorは、5つの構文形式(2つの原子式、2つの特殊形式、および手続き呼び出し)のみを使用するSchemeのサブセットです。Lispy Calculatorを使用すると、プレフィックス記法に慣れている限り、典型的な電卓で行えるあらゆる計算を実行できます。さらに、典型的な電卓言語にはない「if」式と、新しい変数の定義という2つの機能も実行できます。円の半径10の面積をπ r2の公式を使って計算する例を以下に示します。

(define r 10)
(* pi (* r r))

以下は、許可されているすべての式の表です。

式構文意味論と例
変数参照シンボルシンボルは変数名として解釈され、その値は変数の値です。例: r ⇒ 10(rが以前に10と定義されていたと仮定)
定数リテラル数値数値はそれ自体に評価されます。例: 12 ⇒ 12 または -3.45e+6 ⇒ -3.45e+6
条件分岐(if test conseq alt)testを評価します。真ならconseqを評価して返します。偽ならaltを評価して返します。例: (if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
定義(define symbol exp)新しい変数を定義し、式expの評価結果をその値として与えます。例: (define r 10)
手続き呼び出し(proc arg...)procがif、define、quoteのいずれかのシンボルでない場合、手続きとして扱われます。procとすべてのargsを評価し、その後、手続きがarg値のリストに適用されます。例: (sqrt (* 2 8)) ⇒ 4.0

この表の構文列では、シンボルはシンボルである必要があり、数値は整数または浮動小数点数である必要があり、その他の斜体で示された単語は任意の式で構いません。arg...という表記は、argが0回以上繰り返されることを意味します。

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

言語インタプリタは2つの部分からなります。

  1. 構文解析(Parsing): 解析コンポーネントは、文字のシーケンスとしての入力プログラムを受け取り、言語の構文規則に従って検証し、プログラムを内部表現に変換します。単純なインタプリタでは、内部表現はツリー構造(しばしば抽象構文ツリーと呼ばれる)であり、プログラム内の文や式のネスト構造を密接に反映します。コンパイラと呼ばれる言語トランスレータでは、抽象構文ツリーから始まり、コンピュータが直接実行できる命令シーケンスに進む一連の内部表現が存在することがよくあります。Lispyのパーサーはparse関数で実装されています。
  2. 実行(Execution): 次に、内部表現が言語の意味論規則に従って処理され、計算が実行されます。Lispyの実行関数はevalと呼ばれます(Pythonの同名の組み込み関数をシャドウしていることに注意してください)。

解釈プロセスを示す図を以下に示します。

program ➡ parse ➡ abstract-syntax-tree ➡ eval ➡ result

そして、parseとevalが何ができるかの簡単な例を以下に示します(beginは各式を順番に評価し、最後のものを返します)。

>> program = "(begin (define r 10) (* pi (* r r)))"

>>> parse(program)
['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

>>> eval(parse(program))
314.1592653589793

型定義

Schemeオブジェクトの表現について明確にしましょう。

Symbol = str              # SchemeのシンボルはPythonのstrとして実装されます
Number = (int, float)     # Schemeの数値はPythonのintまたはfloatとして実装されます
Atom   = (Symbol, Number) # Schemeの原子はシンボルまたは数値です
List   = list             # SchemeのリストはPythonのlistとして実装されます
Exp    = (Atom, List)     # Schemeの式は原子またはリストです
Env    = dict             # Schemeの環境(後述)は{変数: 値}のマッピングです

解析:parse、tokenize、read_from_tokens

解析は伝統的に2つの部分に分けられます。字句解析では、入力文字文字列がトークンのシーケンスに分割され、構文解析では、トークンが抽象構文ツリーに組み立てられます。Lispyのトークンは括弧、シンボル、数値です。字句解析には多くのツール(Mike LeskとEric Schmidtのlexなど)がありますが、ここでは非常にシンプルなツールを使用します:Pythonのstr.splitです。tokenize関数は文字の文字列を入力として受け取ります。各括弧の周りにスペースを追加してから、str.splitを呼び出してトークンのリストを取得します。

def tokenize(chars: str) -> list:
    """Convert a string of characters into a list of tokens."""
    return chars.replace('(', ' ( ').replace(')', ' ) ').split()

ここで、サンプルプログラムにtokenizeを適用します。

>>> program = "(begin (define r 10) (* pi (* r r)))"
>>> tokenize(program)
['(', 'begin', '(', 'define', 'r', '10', ')', '(', '*', 'pi', '(', '*', 'r', 'r', ')', ')', ')']

tokenize関数は、入力文字列をトークンのリストに変換します。このリストは、括弧、シンボル、数値を個別の要素として含みます。次に、read_from_tokens関数がこのトークンリストを受け取り、Schemeの式を表す抽象構文ツリー(Pythonのリスト構造)を構築します。read_from_tokensは、トークンの先頭を調べ、それが開き括弧「(」であれば、対応する閉じ括弧「)」が見つかるまで再帰的に式を読み込み、リストとして返します。それ以外のトークンは原子(数値またはシンボル)として扱われ、atom関数によって適切なPythonの型(int、float、またはSymbol)に変換されます。

def parse(program: str) -> Exp:
    """Read a Scheme expression from a string."""
    return read_from_tokens(tokenize(program))

def read_from_tokens(tokens: list) -> Exp:
    """Read an expression from a sequence of tokens."""
    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF')
    token = tokens.pop(0)
    if token == '(':
        L = []
        while tokens[0] != ')':
            L.append(read_from_tokens(tokens))
        tokens.pop(0) # pop off ')'
        return L
    elif token == ')':
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token: str) -> Atom:
    """Numbers become numbers; every other token is a symbol."""
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token)

parseは次のように機能します。

>>> program = "(begin (define r 10) (* pi (* r r)))"

>>> parse(program)
['begin', ['define', 'r', 10], ['*', 'pi', ['*', 'r', 'r']]]

evalを定義する準備がほぼ整いました。しかし、まずもう一つ概念が必要です。

環境(Environments)

環境とは、変数名とその値のマッピングです。デフォルトでは、evalは、sin、cos、sqrt、piなどの標準関数(および*などの演算子)の名前を含むグローバル環境を使用します。この環境は、(define symbol value)式を使用して、ユーザー定義変数で拡張できます。

import math
import operator as op

def standard_env() -> Env:
    """An environment with some Scheme standard procedures."""
    env = Env()
    env.update(vars(math)) # sin, cos, sqrt, pi, ...
    env.update({
        '+':op.add, '-':op.sub, '*':op.mul, '/':op.truediv, 
        '>':op.gt, '<':op.lt, '>=':op.ge, '<=':op.le, '=':op.eq, 
        'abs':     abs,
        'append':  op.add,  
        'apply':   lambda proc, args: proc(*args),
        'begin':   lambda *x: x[-1],
        'car':     lambda x: x[0],
        'cdr':     lambda x: x[1:], 
        'cons':    lambda x,y: [x] + y,
        'eq?':     op.is_, 
        'expt':    pow,
        'equal?':  op.eq, 
        'length':  len,
        'list':    lambda *x: List(x), 
        'list?':   lambda x: isinstance(x, List),
        'map':     map,
        'max':     max,
        'min':     min,
        'not':     op.not_,
        'null?':   lambda x: x == [], 
        'number?': lambda x: isinstance(x, Number),  
	    'print':   print,
        'procedure?': callable,
        'round':   round,
        'symbol?': lambda x: isinstance(x, Symbol),
    })
    return env

global_env = standard_env()

評価:eval

これでevalの実装に進む準備ができました。復習のために、Lispy Calculatorのフォームの表を繰り返します。

式構文意味論と例
変数参照シンボルシンボルは変数名として解釈され、その値は変数の値です。例: r ⇒ 10(rが以前に10と定義されていたと仮定)
定数リテラル数値数値はそれ自体に評価されます。例: 12 ⇒ 12 または -3.45e+6 ⇒ -3.45e+6
条件分岐(if test conseq alt)testを評価します。真ならconseqを評価して返します。偽ならaltを評価して返します。例: (if (> 10 20) (+ 1 1) (+ 3 3)) ⇒ 6
定義(define symbol exp)新しい変数を定義し、式expの評価結果をその値として与えます。例: (define r 10)
手続き呼び出し(proc arg...)procがif、define、quoteのいずれかのシンボルでない場合、手続きとして扱われます。procとすべてのargsを評価し、その後、手続きがarg値のリストに適用されます。例: (sqrt (* 2 8)) ⇒ 4.0

以下は、表に密接に従ったevalのコードです。

def eval(x: Exp, env=global_env) -> Exp:
    """Evaluate an expression in an environment."""
    if isinstance(x, Symbol):        # variable reference
        return env[x]
    elif isinstance(x, Number):      # constant number
        return x                
    elif x[0] == 'if':               # conditional
        (_, test, conseq, alt) = x
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif x[0] == 'define':           # definition
        (_, symbol, exp) = x
        env[symbol] = eval(exp, env)
    else:                            # procedure call
        proc = eval(x[0], env)
        args = [eval(arg, env) for arg in x[1:]]
        return proc(*args)

完了です! 全てが動作しているのを見ることができます。

>>> eval(parse("(begin (define r 10) (* pi (* r r)))"))
314.1592653589793

対話:REPL

eval(parse("..."))を常に呼び出すのは面倒です。Lispの偉大な遺産の一つは、インタラクティブな読み込み-評価-表示ループ(REPL)の概念です。これは、プログラマが式を入力し、それがすぐに読み込まれ、評価され、表示される方法であり、長いビルド/コンパイル/実行サイクルを経ることなく行えます。そこで、repl関数(read-eval-print-loopの略)と、Schemeオブジェクトを表す文字列を返すschemestr関数を定義しましょう。

def repl(prompt='lis.py> '):
    """A prompt-read-eval-print loop."""
    while True:
        val = eval(parse(raw_input(prompt)))
        if val is not None: 
            print(schemestr(val))

def schemestr(exp):
    """Convert a Python object back into a Scheme-readable string."""
    if isinstance(exp, List):
        return '(' + ' '.join(map(schemestr, exp)) + ')' 
    else:
        return str(exp)

以下はreplの動作例です。

>>> repl()
lis.py> (define r 10)
lis.py> (* pi (* r r))
314.159265359
lis.py> (if (> (* 11 11) 120) (* 7 6) oops)
42
lis.py> (list (+ 1 1) (+ 2 2) (* 2 3) (expt 2 3))
lis.py> 

言語2:完全なLispy

ここで、言語に3つの新しい特殊形式を追加し、ほぼ完全なSchemeサブセットにします。

式構文意味論と例
引用(quote exp)expを文字通り返します。評価しません。例: (quote (+ 1 2)) ⇒ (+ 1 2)
代入(set! symbol exp)expを評価し、その値をsymbolに代入します。symbolは以前に定義されている(defineまたは囲む手続きのパラメータとして)必要があります。例: (set! r2 (* r r))
手続き(lambda (symbol...) exp)パラメータ名symbol...と本体expを持つ手続きを作成します。例: (lambda (r) (* pi (* r r)))

lambda特殊形式(難解な命名選択で、Alonzo Churchのラムダ計算を参照しています)は、手続きを作成します。手続きは次のように機能させたいと思います。

lis.py> (define circle-area (lambda (r) (* pi (* r r))))
lis.py> (circle-area (+ 5 5))
314.159265359

ここには2つのステップがあります。最初のステップでは、lambda式が評価されて手続きが作成されます。この手続きは、グローバル変数piとを参照し、単一のパラメータを受け取り、それをrと呼びます。この手続きは、新しい変数circle-areaの値として使用されます。2番目のステップでは、先ほど定義した手続きがcircle-areaの値となり、値10を引数として呼び出されます。rが値10を取るようにしたいのですが、グローバル環境のrを単に10に設定しても問題ありません。rを他の目的で使用している場合、circle-areaの呼び出しがその値を変更するのを望まないでしょう。代わりに、グローバル変数と同じ名前を持つローカル変数rを、干渉を気にせずに10に設定できるようなローカル*変数を用意したいのです。手続きを呼び出すプロセスは、これらの新しいローカル変数を導入し、関数のパラメータリストの各シンボルを、関数呼び出しの引数リストの対応する値に束縛します。

Envをクラスとして再定義

ローカル変数を処理するために、Envをdictのサブクラスとして再定義します。(circle-area (+ 5 5))を評価するとき、手続き本体(* pi (* r r))を取得し、rが唯一のローカル変数(値10を持つ)であり、かつグローバル環境を「外側の」環境として持つ環境で評価します。そこで、*とpiの値が見つかります。つまり、次のような環境を望んでいます。ローカル(青)環境が外側の(赤)グローバル環境の中にネストされています。

pi: 3.141592653589793
*: <built-in function mul>
...

r: 10

このようなネストされた環境で変数を検索するとき、まず最も内側のレベルを探しますが、そこで変数名が見つからなければ、次の外側のレベルに進みます。手続きと環境は絡み合っているので、一緒に定義しましょう。

class Env(dict):
    """An environment: a dict of {'var': val} pairs, with an outer Env."""
    def __init__(self, parms=(), args=(), outer=None):
        self.update(zip(parms, args))
        self.outer = outer
    def find(self, var):
        """Find the innermost Env where var appears."""
        return self if (var in self) else self.outer.find(var)

class Procedure(object):
    """A user-defined Scheme procedure."""
    def __init__(self, parms, body, env):
        self.parms, self.body, self.env = parms, body, env
    def __call__(self, *args): 
        return eval(self.body, Env(self.parms, args, self.env))

global_env = standard_env()

すべての手続きには3つのコンポーネントがあることがわかります:パラメータ名のリスト、本体の式、そして本体から他のどの変数がアクセス可能かを示す環境です。トップレベルで定義された手続きの場合、これはグローバル環境になりますが、手続きがそれが定義された環境のローカル変数(そしてそれが呼び出された環境のローカル変数ではない)を参照することも可能です。

環境はdictのサブクラスなので、dictが持つすべてのメソッドを持っています。さらに2つのメソッドがあります:コンストラクタ__init__は、パラメータ名のリストと対応する引数値のリストを受け取り、それらの{変数: 値}ペアを内部部分とし、指定された外側の環境を参照する新しい環境を作成することで、新しい環境を構築します。findメソッドは、変数の適切な環境を見つけるために使用されます:内側の環境または外側の環境のいずれかです。

これらがすべてどのように連携するかを見るために、次のプログラムと(account1 -20.00)を評価したときに形成される環境を示します。

(define make-account   (lambda (balance)     (lambda (amt)       (begin (set! balance (+ balance amt))              balance)))) (define account1 (make-account 100.00)) (account1 -20.00)+: <built-in operator add> make-account: <a Procedure> balance: 100.00 amt: -20.00 account1: <a Procedure>

各長方形のボックスは環境を表し、ボックスの色は環境内で新しく定義された変数の色と一致します。プログラムの最後の2行でaccount1を定義し、(account1 -20.00)を呼び出します。これは、100ドルの初期残高を持つ銀行口座の作成、それに続く20ドルの引き出しを表します。(account1 -20.00)を評価する過程で、黄色でハイライトされた式をevalします。この式には3つの変数があります。amtは最も内側の(緑色の)環境ですぐに見つかります。しかし、balanceはそこでは定義されていません。緑色の環境の外側の環境、つまり青色の環境を見る必要があります。そして最後に、変数+はどちらの環境でも見つかりません。グローバル(赤色)環境へのもう1つの外側のステップを実行する必要があります。内側の環境から検索し、次に外側の環境から検索するというこのプロセスは、lexical scoping(字句的スコープ)と呼ばれます。Env.find(var)は、字句的スコープの規則に従って適切な環境を見つけます。

次に、evalの新しい定義を示します。変数参照の句が変更されていることに注意してください:xが存在するレベルを見つけるためにenv.find(x)を呼び出す必要があり、その後そのレベルからxの値を取得できます。(define句は変更されていません。なぜなら、defineは常に最も内側の環境に新しい変数を追加するからです。)新しい句が2つあります:set!の場合、変数が存在する環境レベルを見つけて新しい値に設定します。lambdaの場合、指定されたパラメータリスト、本体、および環境を持つ新しい手続きオブジェクトを作成します。

def eval(x, env=global_env):
    """Evaluate an expression in an environment."""
    if isinstance(x, Symbol):    # variable reference
        return env.find(x)[x]
    elif not isinstance(x, List):# constant 
        return x   
    op, *args = x       
    if op == 'quote':            # quotation
        return args[0]
    elif op == 'if':             # conditional
        (test, conseq, alt) = args
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif op == 'define':         # definition
        (symbol, exp) = args
        env[symbol] = eval(exp, env)
    elif op == 'set!':           # assignment
        (symbol, exp) = args
        env.find(symbol)[symbol] = eval(exp, env)
    elif op == 'lambda':         # procedure
        (parms, body) = args
        return Procedure(parms, body, env)
    else:                        # procedure call
        proc = eval(op, env)
        vals = [eval(arg, env) for arg in args]
        return proc(*vals)

手続きと環境がどのように連携するかを理解するために、次のプログラムと(account1 -20.00)を評価したときに形成される環境を見てみましょう。

(define make-account   (lambda (balance)     (lambda (amt)       (begin (set! balance (+ balance amt))              balance)))) (define account1 (make-account 100.00)) (account1 -20.00)+: <built-in operator add> make-account: <a Procedure> balance: 100.00 amt: -20.00 account1: <a Procedure>

各長方形のボックスは環境を表し、ボックスの色は環境内で新しく定義された変数の色と一致します。プログラムの最後の2行でaccount1を定義し、(account1 -20.00)を呼び出します。これは、100ドルの初期残高を持つ銀行口座の作成、それに続く20ドルの引き出しを表します。(account1 -20.00)を評価する過程で、黄色でハイライトされた式をevalします。この式には3つの変数があります。amtは最も内側の(緑色の)環境ですぐに見つかります。しかし、balanceはそこでは定義されていません。緑色の環境の外側の環境、つまり青色の環境を見る必要があります。そして最後に、変数+はどちらの環境でも見つかりません。グローバル(赤色)環境へのもう1つの外側のステップを実行する必要があります。内側の環境から検索し、次に外側の環境から検索するというこのプロセスは、lexical scoping(字句的スコープ)と呼ばれます。Env.find(var)は、字句的スコープの規則に従って適切な環境を見つけます。

これで何ができるか見てみましょう。

lis.py> (define circle-area (lambda (r) (* pi (* r r))))
lis.py> (circle-area 3)
28.274333877
lis.py> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
lis.py> (fact 10)
3628800
lis.py> (fact 100)
9332621544394415268169923885626670049071596826438162146859296389521759999322991
15608941463976156518286253697920827223758251185210916864000000000000000000000000
lis.py> (circle-area (fact 10))
4.1369087198e+13
lis.py> (define first car)
lis.py> (define rest cdr)
lis.py> (define count (lambda (item L) (if L (+ (equal? item (first L)) (count item (rest L))) 0)))
lis.py> (count 0 (list 0 1 2 3 0 0))
3
lis.py> (count (quote the) (quote (the more the merrier the bigger the better)))
4
lis.py> (define twice (lambda (x) (* 2 x)))
lis.py> (twice 5)
10
lis.py> (define repeat (lambda (f) (lambda (x) (f (f x)))))
lis.py> ((repeat twice) 10)
40
lis.py> ((repeat (repeat twice)) 10)
160
lis.py> ((repeat (repeat (repeat twice))) 10)
2560
lis.py> ((repeat (repeat (repeat (repeat twice)))) 10)
655360
lis.py> (pow 2 16)
65536.0
lis.py> (define fib (lambda (n) (if (< n 2) 1 (+ (fib (- n 1)) (fib (- n 2))))))
lis.py> (define range (lambda (a b) (if (= a b) (quote ()) (cons a (range (+ a 1) b)))))
lis.py> (range 0 10)
(0 1 2 3 4 5 6 7 8 9)
lis.py> (map fib (range 0 10))
(1 1 2 3 5 8 13 21 34 55)
lis.py> (map fib (range 0 20))
(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

これで、手続き、変数、条件分岐(if)、および順次実行(begin手続き)を持つ言語ができました。他の言語に慣れている場合、whileループやforループが必要だと考えるかもしれませんが、Schemeはこれらを必要とせずにうまく機能します。Schemeのレポートには、「Schemeは、非常に少ない数の式形成ルールが、構成方法に制限なく、実用的で効率的なプログラミング言語を形成するのに十分であることを示している」と書かれています。Schemeでは、再帰関数を定義することで反復処理を行います。

Lispyはどれくらい小さい/速い/完全/良いか?

いくつかの基準でLispyを評価します。

  • 小さい: Lispyは非常に小さいです:コメントや空白行を除くと117行、ソースコードは4KBです。(以前のバージョンはわずか90行でしたが、標準手続きが少なく、やや簡潔すぎました。)私のJavaでのSchemeの最小バージョンであるJschemeは、1664行、ソースコード57KBでした。Jschemeは当初SILK(50キロバイトのScheme)と呼ばれていましたが、ソースコードではなくバイトコードを数えることで、その制限内に収まっていました。Lispyははるかに優れています。Alan Kayの1972年の「世界で最も強力な言語を「1ページのコード」で定義できる」という主張を満たしていると思います。(ただし、AlanはPythonコンパイラをコードの一部と見なすため、私は1ページをはるかに超えていると彼が言うでしょう。)

    bash$ grep "^\s*[^#\s]" lis.py | wc
         117     497    4276
    
  • 速い: Lispyは(fact 100)を0.003秒で正確に計算します。それは私にとっては十分速いです(ただし、ほとんどの他の計算方法よりははるかに遅いです)。

  • 完全: LispyはScheme標準と比較してあまり完全ではありません。いくつかの主要な欠点があります。

    • 構文:コメント、quoteとquasiquote表記、#リテラル、派生式(ifから派生したcond、lambdaから派生したletなど)、およびドット付きリスト表記が欠けています。
    • 意味論:call/ccと末尾再帰が欠けています。
    • データ型:文字列、文字、ブール値、ポート、ベクトル、正確/不正確な数値が欠けています。Pythonのリストは、実際にはSchemeのペアやリストよりもSchemeのベクトルに近いですが、それらをリストで実装しています。
    • 手続き:100以上のプリミティブ手続きが欠けています。
    • エラー回復:Lispyはエラーを検出、合理的に報告、または回復しようとしません。Lispyはプログラマが完璧であることを期待しています。
  • 良い: それは読者の判断に委ねられます。私は、Lispインタプリタを説明するという私の目的にとって良いものだと感じました。

実話

インタプリタがどのように機能するかを知ることが非常に役立つという考えを裏付けるために、ここに話があります。1984年、私は博士論文を書いていました。LaTeX、Microsoft Word for Windowsが登場する前で、troffを使用していました。残念ながら、troffにはシンボリックラベルへの前方参照の機能がありませんでした。「定理xのページで見るように」と書きたいのですが、適切な場所(troffレジスタ\n%はページ番号を保持します)に「@(set theorem-x \n%)」のようなものを書きたいと思っていました。同級生のTony DeRoseも同じ必要性を感じ、一緒にこれを前処理プログラムとして処理する簡単なLispプログラムのスケッチを作成しました。しかし、当時のLispはLisp式の読み込みには適していましたが、Lisp以外の文字単位の式の読み込みには非常に遅かったため、私たちのプログラムは使用するのが煩わしいことが判明しました。

そこからTonyと私は別々の道を歩みました。彼は、難しい部分は式のインタプリタであると推論しました。そのためにLispが必要でしたが、非Lisp文字の読み込みとエコーを行うための小さなCルーチンを書き、それをLispプログラムにリンクする方法を知っていました。私はそのリンク方法を知りませんでしたが、この些細な言語(変数設定、変数取得、文字列連結しかありませんでした)のインタプリタを書くことは簡単だと推論し、Cでインタプリタを書きました。皮肉なことに、TonyはCプログラマーだったのでLispプログラム(小さなCルーチン付き)を書き、私はLispプログラマーだったのでCプログラムを書きました。

最終的に、私たちは両方とも論文を完成させました(Tony、Peter)。

全体

プログラム全体はここにあります:lis.py。

参考文献

Schemeについてさらに学ぶには、いくつかの優れた書籍(Friedman and Fellesein、Dybvig、Queinnec、Harvey and WrightまたはSussman and Abelson)、ビデオ(Abelson and Sussmanによる)、チュートリアル(Dorai、PLT、またはNellerによる)、またはリファレンスマニュアルを参照してください。

また、より高度なLispyのバージョンを説明する別のページもあります。


Peter Norvig