Lispインタプリタを作った

とうとうApple MusicにPerfumeが追加されたので、ここ数日はワンルーム・ディスコを聞きながらコーディングをしている。

Perfume、良い。良すぎる。幸せになれる。

そう、幸せといえばLisp

1週間労働を耐え抜いてまた週末にのんびりLispを書ける。

安定感がすごい。

そんな感じで週末Lisperとして今日もLispに向き合っていたのだけれど、そういえば前にLispでCのコンパイラを書く個人プロジェクトを立ち上げたものの完全に放置していたのを思い出した。

で、久しぶりに取り組もうと書きかけのコードを見ていたのだが、なんかグッとこない。

どうも自分のコードにときめかない...

ということで中途半端な自分のクソコードをガチャガチャ触って気分の悪い土曜日にしてしまうくらいならまた別のプロジェクトをやった方がいいだろうと判断。

ただ、全く別の何かをやるのも少し気が引けたので、コンパイラに近しいものとしてインタプリタを作ることにした。

そんなこんなで今日はLispインタプリタを作ったので、その簡単な概要をつらつらと書いていこうと思う。

ちなみに今回のLispインタプリタは1時間とかそんなもんで作ったので超絶しょぼい。

ただ、その程度の作業量でLispは実装できるので今回のエントリーでLispにときめいてくれる人がいると嬉しいかも?

目標

今回は最終的にREPLを作り上げるのをゴールにする。

REPLとはRead Eval Print Loopの頭文字をとったもので、対話的環境とか言われるもの。

ターミナルでPythonと打つとその場でコードを書けて逐次的に結果を得られる機能があると思うのだけれど、まさにそれである。

最終的に今回はこれを作る。

使用言語

今回のLispインタプリタは実用性などを考えたら速度の出るものを採用するべきなのだけれど、別に今回は雑に作るもので、あとは1時間くらいでサクッと仕上げたいのでPythonで実装しようと思う。

別にPythonが好きとかそういうわけじゃないんだけれど。

ただ、言語実装という観点では関数を引数にとったり返り値にできたりする方が嬉しい(カリー化すごい)のでこうしたメタプログラミングにはRubyPythonHaskellが嬉しいのは一つある。

実装

今回のコードはあらかじめ以下のリポジトリにあるので、実行や参照は適宜よろしくお願いしますという感じで。

github.com

準備

まずは変数などを格納する環境を定義する。

ここにdefineなどで定義された関数の名前が入ったりする。

class Env(dict):
    def __init__(self, parms=(), args=(), outer=dict):
        self.update(zip(parms, args))
        self.outer = outer

    def find(self, var):
        if var in self:
            return self

        else:
            return self.outer

dictのサブクラスとして定義することでシンボルから実際の値を取り出すのが容易になる、というお気持ち。

一つ重要なこととして、この環境クラスにouterとして外部環境を用意することであり、この外部環境はラムダ式を使うときの仮変数を格納するためにある。

さて、ここに+carなどの実際に使うような関数をあらかじめ突っ込んでおく。

from __future__ import division
import math
import operator as op

    
def add_globals(env):
    env.update(vars(math))
    env.update({
        '+':op.add,
        '-':op.sub,
        '*':op.mul,
        '/':op.truediv,
        'not':op.not_,
        '>':op.gt,
        '<':op.lt,
        '>=':op.ge,
        '<=':op.le,
        '=':op.eq,
        'equal?':op.eq,
        'eq?':op.is_,
        'length':len,
        'cons':lambda x,y: [x]+y,
        'car':lambda x: x[0],
        'cdr':lambda x: x[1:],
        'append':op.add,
        'list':lambda *x: list(x),
        'list?': lambda x: isinstance(x,list),
        'null?':lambda x: x == [],
        'symbol?':lambda x: isinstance(x, str)
    })
    
    return env

Parser

Lispの構文はシンボルと数値、カッコからなるので構文解析がめちゃくちゃ簡単なのである。

def tokenize(s):

    return s.replace('(', ' ( ').replace(')', ' ) ').split()


def read_from(tokens):

    if len(tokens) == 0:
        raise SyntaxError('unexpected EOF while reading')

    token = tokens.pop(0)

    if '(' == token:
        L = []
        while tokens[0] != ')':
            L.append(read_from(tokens))
        tokens.pop(0) # pop off ')'

        return L

    elif ')' == token:
        raise SyntaxError('unexpected )')

    else:
        return atom(token)
    

def parse(s):

    return read_from(tokenize(s))

うーん、なんと構文解析が簡単なんだろう。

カッコと空白でsplitして中のシンボルを抽出するだけ。

優しい世界。

Evaluator

さあ、いよいよEvaluator。

ここで各構文を定義していく。

import sys
from environment import Env
from environment import add_globals


def check_string(x):
    if isinstance(x, str):
        return x[0] == x[-1] == '"' or not '"' in x[1:-2]
    else:
        return False

def my_eval(x, env):
    print("Here x is : ", x)

    # Check symbol ?
    if isinstance(x, str):

        return env.find(x)[x]

    # Check atom ?
    elif not isinstance(x, list):

        return x                

    # (quote exp)
    elif x[0] == 'quote':
        (_, exp) = x

        return exp

    # (if test conseq alt)
    elif x[0] == 'if': 
        (_, test, conseq, alt) = x

        if my_eval(test, env):
            return my_eval(conseq, env)

        else:
            return my_eval(alt, env)


    # (set! var exp)
    elif x[0] == 'set!': 
        (_, var, exp) = x
        env.find(var)[var] = my_eval(exp, env)

    # (define var exp)
    elif x[0] == 'define':
        (_, var, exp) = x
        if check_string(exp):
            env[var] = exp
        else:
            env[var] = my_eval(exp, env)

    # (lambda (var*) exp)
    elif x[0] == 'lambda': 
        (_, vars, exp) = x

        return lambda *args: my_eval(exp, Env(vars, args, env))

    # (exit)
    elif x[0] == 'exit':
        sys.exit("bye")

    # (begin exp*)
    elif x[0] == 'begin': 
        for exp in x[1:]:
            val = my_eval(exp, env)

        return val

    # (proc exp*)
    else:
        exps = [my_eval(exp, env) for exp in x]
        proc = exps.pop(0)

        return proc(*exps)

もう基本的にゴリゴリ再帰で処理していく感じ。

簡単な解説として、最初のcheck_string"hoge"のようにダブルクオーテーションで囲われたシンボルを文字列として認識するために、それが文字列かどうか確認するものである。

そして、my_evalの中では各構文を用意しているが、まあだいたい眺めれば理解できると思われる。

ifなどはほぼ見た通りのような感じだし、defineは後の構文を値として環境にセットしている。

lambdaの実装について、一度プログラムの実行立場を外部環境に移して一時変数をその外部環境にセットしてからその関数の中身を実行するという形式をとっており、そうしてラムダ式を実現している。

動かす

ちゃんと動いてる模様。

実際に動いててウキウキして騒いでいた。

まとめ

今回はPythonを使ってLispインタプリタを作った。

だいたいここらへんの基礎部分を作り上げるとあとは楽しいことが待っていて、構文糖衣を導入したり最適化したりとなんでもできる状態。

これからが一番楽しい感じなので、引き続きLispインタプリタを作っていこうと思う。

参照

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