Lispy: Python を用いた Scheme 方言インタプリタの実装

この記事では、コンピュータ言語のインタプリタを実現する一般的な方法を解説するとともに、Python 3 を実装言語として Lisp のスキーム（Scheme）方言の大部分を実装可能なインタプリタ

Lispy

• 目的: アラン・ケイが「ソフトウェアのマクスウェルの方程式」と呼んだ内容（言語定義と解釈の関係）を簡潔かつ明快に示すこと。
• 重要性: スティーブ・イエグーは、「コンパイラ（あるいはインタプリタ）の動作原理を理解していない人は、コンピュータの真の仕組みを理解したとは言えない」と述べている。

1. スキームプログラムの構文と意味

基本概念

• 構文: 正しい演算子や式を形成するための文字の配置仕方。
• 意味: 演算子または式の持つ内容（価値）。
• 評価: 式に値を決定させる処理。例：

  1 + 2 ⇒ 3

スキームのシンプルな構文

スキームは Java や Python と異なり、非常に単純で統一された構文を持っています。

+

>

(

)

if

fn

+

• 比較: スキームはわずか 5 つのキーワードと 8 つの構文形式で完結する一方、Python は 33 キーワード・110 形式、Java は 50 キーワード・133 形式を持つ。
  • 注釈: 「Lots of Irritating Silly Parentheses（Lisp）」という冗談に対し、「Lisp Is Syntactically Pure（スキームは構文的に純粋）」と解釈します。

2. 言語 1: Lispy カルキュレータ

まずは簡易版の「Lispy Calculator」から始めます。これは前置記法を用いた電卓のようなものです。

定義可能な表現

以下の 5 つの構文形式のみを使用します。

symbol

r ⇒ 10

number

12 ⇒ 12

(if test conseq alt)

conseq

alt

(define symbol exp)

symbol

exp

(proc arg...)

if

define

quote

インタプリタの構成要素

インタプリタは主に 2 つのプロセスで成り立ちます。

graph LR
    A[プログラム文字列] -->|パース | B[抽象構文木 (AST)]
    B -->|評価 | C[実行結果]

1. パース (

   parse

   ): 文字列をトークン化し、内部表現（AST）に変換。
2. 実行 (

   eval

   ): AST を意味規則に従って処理して計算を行う。

パースの実装 (

parse

,

tokenize

,

read_from_tokens

)

• トークン化:

  str.split

  を使い、括弧の周囲にスペースを挿入して分割。
• 解析: 括ごとの構造を確認し、記号/数値を識別して AST を構築。

コード例：パース関数

def tokenize(chars: str) -> list:
    return chars.replace('(', ' ( ').replace(')', ' ) ').split()

def parse(program: str) -> Exp:
    return read_from_tokens(tokenize(program))

def read_from_tokens(tokens: list) -> Exp:
    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) # ')' を削除
        return L
    elif token == ')':
        raise SyntaxError('unexpected )')
    else:
        return atom(token)

def atom(token: str) -> Atom:
    try: return int(token)
    except ValueError:
        try: return float(token)
        except ValueError:
            return Symbol(token)

評価の実装 (

eval

) & 環境 (Env)

変数の値を取得するためには、**環境（Environment）**が必要です。環境は「変数名 → 値」のマッピング表です。

型定義と標準環境

# スキームオブジェクトの Python での表現
Symbol = str              # 記号
Number = (int, float)     # 数
Atom = (Symbol, Number)   # 原子
List = list               # リスト
Exp = (Atom, List)        # 表現
Env = dict                # 環境（変数: 値の辞書）

# 標準関数と演算子を初期化
def standard_env() -> Env:
    env = Env()
    import math
    import operator as op
    env.update(vars(math)) # sin, cos, sqrt, pi など
    env.update({
        '+': op.add, '-': op.sub, '*': op.mul, '/': op.truediv,
        '>': op.gt, '<': op.lt, 'eq?': op.eq, 'sqrt': math.sqrt,
        # ... 他多数の関数定義 ...
    })
    return env

global_env = standard_env()

評価関数

eval

のロジック

symbol

env[variablename]

number

proc(*args)

def eval(x: Exp, env=global_env) -> Exp:
    if isinstance(x, Symbol):        # 変数参照
        return env[x]
    elif isinstance(x, Number):      # 定数
        return x                
    elif x[0] == 'if':               # 条件式
        _, test, conseq, alt = x
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif x[0] == 'define':           # 定義
        _, symbol, exp = x
        env[symbol] = eval(exp, env)
    else:                            # 関数呼び出し
        proc = eval(x[0], env)       # 手続きの評価
        args = [eval(arg, env) for arg in x[1:]]
        return proc(*args)

対話型環境 (REPL)

read-eval-print loop

repl

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

def schemestr(exp):
    if isinstance(exp, List):
        return '(' + ' '.join(map(schemestr, exp)) + ')' 
    else:
        return str(exp)

3. 言語 2: フル Lispy

より完全な言語にするため、以下の 3 つの新しい構文形式を追加します。

• quote

  : 文字通り評価せず、そのまま返す。

• set!

  : 変数に値を割り当てる（再割り当て）。

• lambda

  : ローカル変数を持つ手続きを作成する。

手続きとローカル環境の必要性

単純な辞書ではスコープを区別できません。「関数内の局部変数」がグローバル変数を指してしまう問題を解決するため、階層構造を持つ環境クラスを導入します。

新しい環境クラス

Env

と

Procedure

class Env(dict):
    "環境：辞書サブクラス。内側の環境を持つ。"
    def __init__(self, parms=(), args=(), outer=None):
        self.update(zip(parms, args)) # ローカル変数の割り当て
        self.outer = outer
    def find(self, var):
        "変数を最優先で検索（リーザルスコープ）"
        return self if (var in self) else self.outer.find(var)

class Procedure(object):
    "ユーザー定義手続き"
    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()

拡張された

eval

• 変数参照:

  env.find(var)

  を使用して、内側のスコープから外側へ検索。
• quote: 引数をそのまま返す（評価しない）。
• set!: 存在する環境の変数に値を設定。
• lambda: 新しい

  Procedure

  オブジェクトを生成。

def eval(x, env=global_env):
    if isinstance(x, Symbol):      # 変数参照 (スコープ検索)
        return env.find(x)[x]
    elif not isinstance(x, List): # 定数
        return x   
    op, *args = x       
    if op == 'quote':              # クォート
        return args[0]
    elif op == 'if':               # 条件式
        (test, conseq, alt) = args
        exp = (conseq if eval(test, env) else alt)
        return eval(exp, env)
    elif op == 'define':           # 定義 (常に最も内側)
        (symbol, exp) = args
        env[symbol] = eval(exp, env)
    elif op == 'set!':             # 割り当て
        (symbol, exp) = args
        env.find(symbol)[symbol] = eval(exp, env)
    elif op == 'lambda':           # 手続き作成
        (parms, body) = args
        return Procedure(parms, body, env)
    else:                          # 関数呼び出し
        proc = eval(op, env)
        vals = [eval(arg, env) for arg in args]
        return proc(*vals)

フル機能のデモ

• 再帰: ファクツリアルやフィボナッチ計算。
• 束縛（Binding）: 関数内部での変数更新は、外部環境に影響しない。
• 高階関数:

  map

  ,

  filter

  のような処理が可能。

>>> (define fact (lambda (n) (if (<= n 1) 1 (* n (fact (- n 1))))))
>>> (fact 10)
3628800

4. Lispy の特性評価

サイズと効率

• 小さい: コメント・空白除くと117行（約 4KB）。ソースコードの軽量化に成功。
• 速い:

  (fact 100)

  を計算する時間は 0.003 秒。十分高速。

機能と制限

• 完全性: スキーム標準より若干劣るが、核心機能を備えている。
  • 欠けている構文: コメント、

    cond

    ,

    let

    ,

    quasiquote

    など。
  • 欠けている型: 文字列、ブール値、ポートなど。
  • 欠ける特性: Tail Call Optimization (テイル再帰)、Continuation (

    call/cc

    ) など。
• エラー回復: エラーを許容せず、妥当なプログラムを書くことを前提とする。

「真実の話」：言語の境界線

インタプリタの実装には面白いエピソードがある（Peter Norvig による）。 1984 年、共同研究者 Tony DeRose は LaTeX 以前のテキスト処理のために「前方参照可能なラベル」という機能を求めたが、当時の Lisp が非-LaTeX 表現の読み出しに遅すぎた。そこで二人は役割を分担した：

• Tony (C): プログラムを C コードに変換するループを実装（Python と異なり、高速な C を用いる）。
• Peter (Lisp): その変換されたコードを解釈するための Lisp インタプリタを実装。

これにより、「最も強力な言語の一つ」（Alan Kay 談）であるインタプリタは、CとLispのハイブリッドとして生まれ、二人とも博士号を取得した。

5. まとめと参考資料

この

Lispy

より深く学ぶには

• 書籍: 『The Little Schemer』(Friedman, Felleisen), 「Scheme 入門」など。
• 動画: SICP (Structure and Interpretation of Computer Programs) の講義。
• ソースコード: より高度な

  Lispy

  のバージョンや解説は別ページで扱っている。