« ^ »
[WIP]

Lispを学ぶ

所要時間: 約 34分

最近、プログラミング言語について、Lispを作りながら少しずつ学んでいる。この記事は、その過程で情報を整理したり、実装したり、考えた事を書いている。技術ブログやテクニカルエッセイというよりも、何日も加筆した雑な日記またはただのメモと言った方が近いかもしれない。技術的な内容だけではなく、自分なりの捉え方をまとめたり、僕の個人的な状況や、その時々の気持ちも合わせて書いている。

だから技術的な内容を知りたい人にとってはかなりノイズが多い文章になっている。特にまとまってもないし、とりとめもない。けれど、こうやって自分なりに勉強している人がいるという事や、その記録であるこの文章が何かの役に立てればいいなと思う。

なぜ今さらLispを学ぶのか

何十年も前の研究成果や、古いプログラミング言語を引っ張り出してきて勉強するなんて、意味のない事のように感じるかもしれない。実際、今すぐお金を稼いだり、実務に役立つ事を学びたいなら、ここの内容は何の役にも立たない。

もっと実用的な技術を学ぶべきだと思うかもしれない。僕も半分ぐらいはそう思う。でも、もう半分ぐらいの部分で何か引っかかる。だから、まずはLispを学ぶ動機について書きたい。

個人的な出来事でいろんな事に失望した

これまで、学びたい事があり学ぶための教材があっても、学ぶ事ができなかった。目の前の仕事に追われていたり、自分の背負っていた色々な責任を果たすために、目先の仕事ややらなければならない事に一生懸命取り組んできたからだ。10年近くの間それらに粛々と取り組んだ。仕事は好きだったけれど、好きなだけでは長期間取り組み続ける事はできない。それをするだけの理由が必要で、その理由があったからこれまでやってこれた。

しかし個人的な事で、それらに意味を全く感じられなくなった。果たそうとしていた責任はもう果たすつもりはない。それで批判されたり、不利な立場になったとしても正直もうどうでもいい。極端な話、明日死ぬ人間に対して責任を果たせなんて言うのはバカげている。もちろん死ぬ勇気も、そのつもりも無いんだけれど、一生懸命取り組んで積み上げてきたものを、ぶち壊すぐらいの覚悟はできている。

もう機械や奴隷のように扱われるのはまっぴらだ。家族とかいう、人を人として扱わないクソくだらない集団に失望したし、地道に働いてなんとか生活を成立させてきたのに、税金や社会保険料、他にも色々な名目で生活が苦しくなる程お金を巻き上げる国や社会、他にもいろいろと失望した。

今日やりたい事を今やる

だから、それまでにやりたかった事はやっておきたい。くだらない集団に相対する前に、今日やりたい事、今やりたい事を大切にして、やりたいように生きておきたい。ただ仮に明日死ぬとしても、僕は昼間からお酒を飲まないし、パチンコにも行かない。そうしたいと思わないからだ。

そういう状況でも普段とは大きく異なる行動をする事は難しいと思う。先はないのだから勉強しても意味はないし、何も考えず美味しいものを食べに行きそうだ。けれど、ちょっと高い焼き肉を食べた後は、やっぱり何かを勉強しそうだ。たぶん、興味のある事について詳しくなる事がシンプルに好きなんだと思う。

Emacsの存在とLispを学びたいという事

僕はEmacsというテキストエディタを愛用している。とても長い時間をEmacsと一緒に過ごしている。これは、誇張ではなく本当にそうだ。長距離トラックの運転手にとってのトラック、学生にとっての鉛筆、もしくは多くの人にとってのスマホのような存在だ。

Emacsは、Emacs Lispの処理系と言っても良い。日常的にEmacs Lispを書くし、Lispの持つ便利さやパワフルさは、今でも有効だと思う。Emacs自身は束縛の方式を切り替える事もできる(そんな言語は、あまりない)。Emacs Lispにはリードマクロはないけれど、それがあるLisp処理系であれば、全く別の言語を作る事もできる。それでいて言語的な仕様は小さく、簡単な処理系ならすぐ書ける。なによりS式のパースはとても楽だ。歴史も長く、魅力ある言語だと思うし、だからLispをもっと勉強してみたいと感じていた。そんな事を考えていたからこそ、今学びたい事を素直に学ぼうと思う。

自分なりの方法でプログラミング言語に対する理解を深める

普段、Python、TypeScript、Emacs Lispといったプログラミング言語を行ったり来たりしながら暮らしている。それは僕がWebのシステムの開発を生業としており、Emacsというテキストエディタを愛用しているからだ。もちろん他のGoやRuby等他の言語も仕事で使用する。

いろいろなプログラミング言語を使っていると、プログラミング言語を作りたくなってくる。自分だけのプログラミング言語、隅から隅まで動きを把握できていて、自分の歩幅に合わせて一緒に成長するプログラミング言語というものに憧れる。

しかし、プログラミング言語を作る事は、普通に考えるとそこそこ大変な作業だ。何から始めたらいいか分からないし、言語そのものを作るのも大変だし、ライブラリ、コミュニティを含めたエコシステムなど言語以外の要素を考えると、製品として使えるレベルのプログラミング言語を作る事はとても長くて難しい道のりだ。そう考えると本当にRubyの凄さが良く分かる。

プログラミング言語を作るというと、文法も新しいものになるかもしれない。しかし僕が興味を持っているのは、プログラミングの構文というよりも、プログラミング言語が動作する仕組みを理解する事のような気がする。つまり、既存のプログラミング言語の別の実装を作るという事になる。

こういう出発点であれば、Lispが向いている。Lispはとてもシンプルな言語であり、言語としてのルールがとても少ない。僕はたぶん今、Lisp処理系が作りたいのだろう。もっと言うと、機能が限定された小さなLispを作りたい。

思い返せば、今までにも何度かそんな事を考えていた事もあった。以前それを考えていた時には、いろいろな理由を付けて、そこを素通りしてしまった。けれど、今回は少しだけ立ち止まって、この事を考えて取り組んでみる事にした。

きっかけや形は違うかもしれないけれど、似たような事は誰しも同じような事を考える事がありそうだ。あなたも一度はそんな事を考えた事があるんじゃないだろうか。たぶん、人生で一度は誰しもがLispを作る時が来る。そういう事なのだろう。

記事のスタンスと学ぶ姿勢

僕はLispも、プログラミングも、果ては情報工学もちゃんと誰かに師事して学んだ事がない。プログラミングは好きだけれど、好きな事を調べていった結果、今があるだけだ。だから認識を間違えている所が大いにある。それを前提に読んで貰えるとありがたい。

もちろんそれは、記述や内容の問題点や間違いに目をつぶって欲しいという事ではない。できれば何かしらの形で指摘してくれると嬉しい。ただ、全面的に正しい情報が書いてある訳ではないという事だ。それでは、一歩ずつ自分なりに情報を整理したり確認したりしながら、学んでいく。

現時点での実装

まずはPythonでLispを実装する事にした。Pythonを選んだのは、単純に一番慣れているからだ。PythonでLispを作る旨みは無い。それは分かるんだけれど、まずは仕組みを把握する事を目的として実装を進めていく。

現時点では幾つかの関数を実装しており、再帰呼出もできるようになっている。ただマクロはないし、末尾再帰最適化もないし、一般的なLisp処理系と比較すると、だいぶ見劣りする。しかし、これを書く事で処理系を作るという事がどういうものなのか、少しずつ見えるようになってきた。

とりあえず、実装出来た所までを掲載する。

"""My Lisp"""
import math
import re
import sys
import traceback

sys.setrecursionlimit(200)

RE_TOKEN = re.compile(r"""[\s,]*(~@|[\[\]{}()'`~^@]|"(?:[\\].|[^\\"])*"?|;.*|[^\s\[\]{}()'"`@,;]+)""")


class LispObject:
    pass


# 2種のデータ型「アトム」と「ペア」
class Atom(LispObject):
    pass


# アトム
class Nil(Atom):
    def __repr__(self):
        return "nil"

    def __bool__(self):
        return False


class T(Atom):
    def __repr__(self):
        return "t"

    def __bool__(self):
        return True


NIL = Nil()
TRUE = T()


class String(Atom, str):
    pass


class Integer(Atom, int):
    pass


class Symbol(Atom, str):
    pass


class ConsCell(LispObject):
    def __init__(self, car, cdr=NIL):
        self.car = car
        self.cdr = cdr

    def __repr__(self):
        return f"({self.car} . {self.cdr})"


def mapcar(fn, cell):
    if cell.cdr is NIL:
        return [fn(cell.car)]
    return [fn(cell.car)] + mapcar(fn, cell.cdr)


def symbolp(obj):
    return TRUE if isinstance(obj, (Symbol,)) else NIL


class InitialTreeParsingError(Exception):
    pass


def make_ast(tree):
    """
    >>> make_ast("nil")
    nil

    >>> make_ast("t")
    t

    >>> make_ast('"foo"')
    '"foo"'

    >>> isinstance(make_ast('"foo"'), String)
    True

    >>> make_ast('foo')
    'foo'

    >>> isinstance(make_ast('foo'), Symbol)
    True

    >>> make_ast([])
    nil

    >>> make_ast(["foo"])
    (foo . nil)

    >>> make_ast(["foo", "bar"])
    (foo . (bar . nil))
    """
    if isinstance(tree, str):
        if tree == "nil":
            return NIL
        elif tree == "t":
            return TRUE
        elif tree.isnumeric() or (tree.startswith("-") and tree[1:].isnumeric()):
            return Integer(tree)
        elif tree.startswith('"') and tree.endswith('"'):
            return String(tree)
        else:
            return Symbol(tree)

    elif isinstance(tree, list):
        if len(tree) == 0:
            return NIL
        elif len(tree) == 1:
            return ConsCell(car=make_ast(tree[0]), cdr=NIL)
        else:
            return ConsCell(
                car=make_ast(tree[0]),
                cdr=make_ast(tree[1:]),
            )
    assert False


def sum_form(ast, env):
    nums = []
    for v in mapcar(lambda n: n, ast):
        num = eval_ast(v, env)
        nums.append(num)
    return Integer(sum(nums))


def product_form(ast, env):
    nums = []
    for w in mapcar(lambda n: n, ast):
        num = eval_ast(w, env)
        nums.append(num)
    return Integer(math.prod(nums))


def greater_than(cell, env):
    return TRUE if eval_ast(cell.car, env) > eval_ast(cell.cdr.car, env) else NIL


global_env = {
    # The four basic arithmetic operations
    "+": sum_form,
    "*": product_form,
    ">": greater_than,
}


def eval_ast(ast, env):
    """
    Pure Lisp Function
    - "atom": atom,
    - "eq": eq,
    - "cons": cons,
    - "car": car,
    - "cdr": cdr,

    Pure Lisp Special Form
    - "cond": cond_form,
    - "quote": quote_form,
    - "lambda": lambda_form,
    - "define": define_form,

    5つの基本的な関数


    | 関数 | 説明                                | 記号的説明                       |
    |------+-------------------------------------+----------------------------------|
    | atom | 値がアトムなら T を返す。           | atom[(A B)] → nil、atom[nil] → T |
    | eq   | 二つの値が同一のものなら T を返す。 | eq[A;A] → T                      |
    | car  | ペアの左値をとり出す。              | car[(A . B)] → A                 |
    | cdr  | ペアの右値をとり出す。              | cdr[(A . B)] → B                 |
    | cons | ペアを作る。                        | cons[A;B] → (A . B)              |


    再帰呼出もできる。

    >>> _ = read_eval("(define (- p q) (+ p (* -1 q)))", global_env)
    >>> _ = read_eval("(define (factorial v) (cond ((eq v 0) 1) (t (* v (factorial (- v 1))))))", global_env)
    >>> read_eval("(factorial 5)", global_env)
    120


    >>> fn = lambda line: make_ast(parse_initial_tree(make_tree(tokenize(line)))[0])

    * lambda

    >>> eval_ast(fn("(lambda (x) (quote x))"), global_env)
    ((x . nil) . ((quote . (x . nil)) . nil))

    * car

    >>> eval_ast(fn("(car '(1 2 3))"), global_env)
    1

    * cdr

    >>> eval_ast(fn("(cdr '(1 2 3))"), global_env)
    (2 . (3 . nil))

    * cons

    >>> eval_ast(fn("(cons 1 2)"), global_env)
    (1 . 2)

    * eq

    >>> eval_ast(fn("(eq 1 1)"), global_env)
    t

    * atom

    >>> eval_ast(fn("(atom 1)"), global_env)
    t

    * define

    関数

    >>> eval_ast(fn("(define (foo x w) (+ x w))"), global_env)
    ((x . (w . nil)) . ((+ . (x . (w . nil))) . nil))

    >>> eval_ast(fn("(foo 1 2)"), global_env)
    3

    変数

    >>> eval_ast(fn("(define bar 2)"), global_env)
    2

    >>> eval_ast(fn("bar"), global_env)
    2

    * cond

    >>> eval_ast(fn("(cond (nil 1) (t 2))"), global_env)
    2

    """

    if symbolp(ast) is TRUE:
        # シンボルを評価するとシンボルテーブル内にあるかを検索する
        val = env.get(ast)
        if val is None:
            raise ValueError(f"no symbol: {ast}")

        return eval_ast(val, env)  # 値は更に評価して返す

    if isinstance(ast, (Atom,)):
        return ast

    if not isinstance(ast, ConsCell):
        raise ValueError(f"not cons cell: {ast}")

    if ast.car == Symbol("lambda"):
        return ast.cdr

    if ast.car == Symbol("quote"):
        return ast.cdr.car

    if ast.car == Symbol("car"):
        return eval_ast(ast.cdr.car, env).car

    if ast.car == Symbol("cons"):
        return ConsCell(
            car=eval_ast(ast.cdr.car, env),
            cdr=eval_ast(ast.cdr.cdr.car, env),
        )

    if ast.car == Symbol("eq"):
        val1 = eval_ast(ast.cdr.car, env)
        val2 = eval_ast(ast.cdr.cdr.car, env)
        return TRUE if val1 == val2 else NIL

    if ast.car == Symbol("atom"):
        sub_ast = ast.cdr.car
        val = eval_ast(sub_ast, env)
        return TRUE if isinstance(val, (Atom,)) else NIL

    if ast.car == Symbol("cdr"):
        sub_ast = eval_ast(ast.cdr.car, env)
        return sub_ast.cdr

    if ast.car == Symbol("define"):
        if isinstance(ast.cdr.car, ConsCell):  # 関数
            func_name = ast.cdr.car.car
            global_env[func_name] = ConsCell(
                car=ast.cdr.car.cdr,
                cdr=ast.cdr.cdr,
            )
            return global_env[func_name]
        elif symbolp(ast.cdr.car):  # 変数
            global_env[ast.cdr.car] = eval_ast(ast.cdr.cdr.car, env)
            return global_env[ast.cdr.car]
        else:
            raise ValueError()

    if ast.car == Symbol("cond"):
        def _progn(sub_ast):
            if sub_ast is NIL:
                return NIL
            val = eval_ast(sub_ast.car, env)
            if sub_ast.cdr is NIL:
                return val
            return _progn(sub_ast.cdr)

        def _fn(sub_ast):
            if sub_ast is NIL:
                return NIL

            if sub_ast.car is not NIL:
                val = eval_ast(sub_ast.car.car, env)
                if val is not NIL:
                    if sub_ast.car.cdr is NIL:
                        return val
                    return _progn(sub_ast.car.cdr)
            return _fn(sub_ast.cdr)
        return _fn(ast.cdr)

    if symbolp(ast.car) is TRUE:
        fn = env[ast.car]
    else:
        fn = eval_ast(ast.car, env)

    if callable(fn):  # ネイティブ実装
        return fn(ast.cdr, env)

    # Lispでの関数呼び出し
    arg_list = mapcar(lambda x: x, fn.car)
    value_list = mapcar(lambda x: x, ast.cdr)
    local_env = env.copy()
    for sym, val in zip(arg_list, value_list, strict=True):
        local_env[sym] = eval_ast(val, env)
    return progn(fn.cdr, local_env)


def progn(ast, env):
    if ast is NIL:
        return NIL
    val = eval_ast(ast.car, env)
    if ast.cdr is NIL:
        return val
    return progn(ast.cdr)


def read_eval(line, env):
    """
    >>> read_eval("'a", global_env) == Symbol("a")
    True

    >>> read_eval("1", global_env)
    1

    >>> read_eval("nil", global_env)
    nil

    >>> read_eval("t", global_env)
    t

    >>> read_eval("(+ 1 2)", global_env)
    3

    >>> read_eval("(car '(1 2 3))", global_env)
    1

    >>> read_eval("(car (cdr '(1 2 3)))", global_env)
    2

    >>> read_eval("(+ (car '(1 2 3)) (car (cdr '(1 2 3))))", global_env)
    3

    >>> read_eval("((lambda (a) (+ a 1)) 2)", global_env)
    3

    >>> read_eval("(define fn '(+ 1 2))", global_env)
    (+ . (1 . (2 . nil)))

    >>> read_eval("fn", global_env)
    3

    >>> read_eval("'(1 2 3)", global_env)
    (1 . (2 . (3 . nil)))

    >>> read_eval("(car '(1 2 3))", global_env)
    1

    >>> read_eval("(cdr '(1 2 3))", global_env)
    (2 . (3 . nil))

    >>> read_eval("(cons 1 2)", global_env)
    (1 . 2)

    >>> read_eval("(atom t)", global_env)
    t

    >>> read_eval("(atom nil)", global_env)
    t
    """
    # READ
    tokens = tokenize(line)
    plain_tree = make_tree(tokens)
    reader_macro_expanded_tree = parse_initial_tree(plain_tree)
    res = NIL

    for tree in reader_macro_expanded_tree:
        ast = make_ast(tree)
        res = eval_ast(ast, env)
    return res


def parse_initial_tree(tokens: list) -> list:
    """
    リードマクロはここで展開する。

    >>> parse_initial_tree(['a'])
    ['a']

    >>> parse_initial_tree(['a', 'b'])
    ['a', 'b']

    >>> parse_initial_tree(['a', ['b', 'c']])
    ['a', ['b', 'c']]

    >>> parse_initial_tree(["'", 'a', 'b'])
    [['quote', 'a'], 'b']

    >>> parse_initial_tree(["'", ['1', '2', '3'], 'b'])
    [['quote', ['1', '2', '3']], 'b']

    >>> parse_initial_tree(['a', '.', 'b'])
    ['cons', 'a', 'b']

    >>> parse_initial_tree(['cdr', "'", ['1', '2', '3']])
    ['cdr', ['quote', ['1', '2', '3']]]

    >>> parse_initial_tree([['cdr', "'", ['1', '2', '3']]])
    [['cdr', ['quote', ['1', '2', '3']]]]

    >>> parse_initial_tree([['-', ['car', "'", ['1', '2']], ['car', ['cdr', "'", ['2', '3']]]]])
    [['-', ['car', ['quote', ['1', '2']]], ['car', ['cdr', ['quote', ['2', '3']]]]]]

    """
    if isinstance(tokens, list) and len(tokens) == 0:
        return []

    if isinstance(tokens, list) and len(tokens) >= 3 and tokens[1] == ".":
        if len(tokens) != 3:
            raise ValueError()

        return [
            "cons",
            parse_initial_tree(tokens[0]),
            parse_initial_tree(tokens[2]),
        ]

    if isinstance(tokens, list) and len(tokens) >= 2 and tokens[0] == "'":
        return [
            [
                "quote",
                parse_initial_tree(tokens[1]),
            ]
        ] + parse_initial_tree(tokens[2:])

    if isinstance(tokens, list):
        return [
            parse_initial_tree(tokens[0]),
        ] + parse_initial_tree(tokens[1:])

    if isinstance(tokens, str):
        return tokens

    assert False


def make_tree(tokens):
    """
    >>> make_tree(['1'])
    ['1']

    >>> make_tree(['(', '+', '1', '2', ')'])
    [['+', '1', '2']]

    >>> make_tree(['(', 'car', "'", '(', '1', '2', '3', ')', ')'])
    [['car', "'", ['1', '2', '3']]]

    >>> make_tree(["'", '(', '1', '2', '3', ')'])
    ["'", ['1', '2', '3']]

    >>> make_tree(['(', '-', '(', 'car', "'", '(', '1', '2', ')', ')', '(', 'car', '(', 'cdr', "'", '(', '2', '3', ')', ')', ')', ')'])
    [['-', ['car', "'", ['1', '2']], ['car', ['cdr', "'", ['2', '3']]]]]
    """
    tree = []
    while tokens:
        token = tokens.pop(0)
        if token == ")":
            return tree
        elif token == "(":
            subtree = make_tree(tokens)
            tree.append(subtree)
        else:
            tree.append(token)

    return tree


def tokenize(line: str) -> list[str]:
    """
    >>> tokenize("'a")
    ["'", 'a']

    >>> tokenize("1")
    ['1']

    >>> tokenize("'(1 2 3)")
    ["'", '(', '1', '2', '3', ')']

    >>> tokenize("(car '(1 2 3))")
    ['(', 'car', "'", '(', '1', '2', '3', ')', ')']

    >>> tokenize("((car . ((quote . ((1 . (2 . (3 . nil))) . nil)) . nil)) . nil)")
    ['(', '(', 'car', '.', '(', '(', 'quote', '.', '(', '(', '1', '.', '(', '2', '.', '(', '3', '.', 'nil', ')', ')', ')', '.', 'nil', ')', ')', '.', 'nil', ')', ')', '.', 'nil', ')']

    >>> tokenize("(- (car '(1 2)) (car (cdr '(2 3))))")
    ['(', '-', '(', 'car', "'", '(', '1', '2', ')', ')', '(', 'car', '(', 'cdr', "'", '(', '2', '3', ')', ')', ')', ')']

    """
    return [m for m in RE_TOKEN.findall(line)]


base_lisp = '''
(define (- p q) (+ p (* -1 q)))
'''


def lisp():
    # setup
    read_eval(base_lisp, global_env)

    while True:
        try:
            line = input("LISP> ").strip()
            if not line:
                continue

            res = read_eval(line, global_env)
            print(f"=> {res}")
        except Exception:
            traceback.print_exc()


if __name__ == "__main__":
    lisp()

次からは、順を追って情報を整理し、開発を進め、理解を深めていく。

処理系を作る準備

最初、どこから始めるのか。ちゃんと体系立った学習の仕方をする人は、用語の定義や、分類から始めるかもしれない。でも僕はそういう勉強の仕方が苦手だった。反対に、とりあえず動くものを作ってみて、実行して少し書き変えて、調べてまた書き変えて、そうやって試行錯誤する方が性には合っているし楽しかった。だから今回も、そうやって進める。言語は慣れているPythonを使うけれど、それについては必要に応じて後々変更するかもしれない。

「Hello, world!」

まずは、"Hello, world!"から始めよう。

print("Hello, world!")
hello_world.py

これを実行すると、"Hello, world!"が表示される。

python3 hello_world.py

Hello, world!

簡素なREPL

処理系と一言で言っても色々な種類がある。ここでは簡単に実装できる方法を採用したい。インタプリタ言語でよくある仕組みにREPLというものがある。入力を待ち(Read)、入力されたコードを評価し(Eval)、その結果を表示する(Print)。この一連の流れを繰り返す(Loop)。REPLは、Read、Eval、Print、Loopのそれぞれの頭文字を取ったものだ。評価というのは、ここではコードを実行すると考えておく。

Evalの所は後回しにして、Read、Print、Loopを実装すると次のようになる。Printはとりあえず"Hello, world!"でも表示しておく事にする。

while True:
    code = input("CODE: ")
    # ここにEvalの処理が入る予定
    print("Hello, world!")
simple_repl.py

ここまでで既に外枠は完成した。後はLispを学びながら実装を進めるだけだ。

Lispをざっくりと捉える

簡単なREPLの骨組を作ったので、次は評価の部分に入っていきたい。ただ、それにはLispのコードがどのようなものかを、多少知る必要がある。そこで、Lispを実装するために、本当に雑で大まかにLispをざっくりと理解する事にした。なお、歴史とか、細かい或いはちゃんとした仕様とか、そういう事は考えない。というか大して詳しくもないから書けない。

リストについて考える

LISPは「LISt Processor」という意味であり、リストを操作する事が主眼にある。リストとは、並んでいるデータの事だ。+, 2, 3のように、何かしらが並んでいる状態のものをリストと呼ぶ。

順序データの例
1番目+
2番目2
3番目3

リストをS式で表現する

Lispでは、括弧で括り、半角スペースで区切ってリストを表現する。このような表現はS式と呼ばれる。

(+ 2 3)

0個並んでいる(つまり何も要素のない)状態もリスト(空リスト) という事だ。そのためLispで () として表現できるものも、リストと言える。

ただし () 自体は、それ単体ではリストではない。これはLispの数少ない構文の一つであり、リストの区切り位置を表している。また、半角スペースも構文と言える。

リストではないデータはアトム

リストではないデータは、アトムと言う。例えば、整数や文字列はアトムとして扱われる。 () として表現される空リストは少し注意が必要で、これはリストだけれどアトムとされる。また、空リストは NILnil と表記する。この記事では基本的にnilと表記する。つまり ()nil は等価となる。空リストなのでリストなのだが、空リストだけはリストでありながらアトムとしても扱われる。

整数

0, 1, 2, 3, 4, 5, 6, 7, 8, 9で組み合わされた表現は整数として扱う。また、その表現の先頭に - が付いている場合は負の数として整数として扱う。数値はアトムであり、整数以外の数値もあるが、ここでは整数のみ扱う。

  • 整数

    • 0
    • 12
    • -0
    • -1
    • -123
  • 整数ではない

    • a
    • -a
    • 1-
    • 1a
    • a1

文字列

ダブルクォート " で括られた表現は文字列として扱う。

  • 文字列

    • "ab"
    • "0"
    • "123"
    • "-0"
  • 文字列ではない

    • ab
    • "ab
    • ab"
    • a"b
    • 0
    • 123
    • -0
    • -a

S式を評価する

まずはLispで足し算を書き、それを観察してみよう。

(+ 1 2)

これはLispの足し算であり、大抵の処理系で実行できる。このS式はただの表現方法だけれど、この式を処理する事を「式を評価する」と言う。このS式を評価すると、なんとなく予想できる通り 3 という結果を得られる。

S式を評価すると、1つ目の要素として指定した手続きが実行される。その時に引数として渡されるのが2つ目以降の要素となる。先程の例では 12 を引数にして、 + という手続きを呼び出している。手続きというのは、関数などのように呼び出す事で何らかの処理を実行できるものだ。

(+ 1 2)
 ^ ^ ^
 | | |
 | +-+
 |  |
 |  +--------- 手続きに渡される引数
 |
 +------------ 手続き

これらがLispを使う上で本当に最低限把握しておく事だろう。S式やその他の解説で、正しい定義はもっときちんとするべきだと思うけれど、今はこの程度の理解度で良い。

ちょっとだけならもうLispを使える

ここまででLispをちょっとだけ把握した。これだけ分かっていれば、ちょっと使うだけならLispを使う事もできそうだ。Lispでの足し算は以下のに記述でき、評価した結果は7だ。

(+ 5 2)

+ はキーワードではなく、ただの手続きに付けられた名前だ。まだ、手続の定義を記述する方法はおさらいしていないけれど、例えば +++yay++!! みたいな名前の手続きも定義できる。

S式を評価すると、そのS式がアトムであればアトムそのものを返し、アトムでなければCDR(先頭より後ろの要素)の値に対し、CAR(先頭の要素)を手続として適応するという事になる。

Lispでプログラミングする事は、この手続を自分で定義し実装していく事になる。それぞれのLisp処理系にはあらかじめ手続が用意されており、それらを使えば、既にある程度はLispを使える。

簡易版Lispを作る

ここまででLispを少しだけ使えるようになった。しかし、処理系を実装しようとするともう少しだけLispを知る必要がある。コードを意味のある字句要素に分割するトークナイズ処理、分割した字句要素を処理しやすいデータ構造である抽象構文木に変換するパース処理などだ。以降ではそれらについて、観察していく。

式を評価するとは何をする事なのか

先程作成した簡易版REPLでは、評価の部分(Eval)を実装しなかった。Lispの記述方法をある程度把握した今、簡単なものなら、もう評価の部分も実装できるはずだ。

「式を評価する」とは、具体的には何をする事なのだろう。僕なりに厳密でない直感に基づく定義を考えてみた。

「式を規則に従って展開し、手続を適応し、その結果を返す。」

返された結果をどこかに束縛すれば、その結果を後から参照できる。束縛しなければ、参照を失い、闇に葬られる(GC)。

入力した式を分割したり(トークナイズ)、構造を解析したり(パース)、マクロの展開、関数や特殊形式の実行、結果の返却、これら一連の処理を評価と呼ぶ事にする。また、マクロ展開を含まず関数や特殊形式を呼び出す処理は、関数の実行や特殊形式の実行という表現を使う事にする。

ここからは簡単なS式 (+ 1 10) を例に、順を追って式を評価する事にする。それに伴い各処理の実装を進める。

トークナイズ(簡易版)の実装

REPLで入力したこのS式は、最初は"(+ 1 10)"という1つの文字列として扱われる。S式は、「(」「)」「 」(半角スペース)といった特別な文字によって、S式を表現しており、それぞれの式の意味(この場合は「1と10を足す」という意味)を持たされている。そのため、先程の文字列からS式を構成する要素に分割する必要がある。

入力された文字列を分割し、S式の構成要素を抽出する処理をトークナイズと呼び、分割した後の要素1つ1つをトークンと呼ぶ。何をトークンとするかについては、処理系によって多少異なるかもしれない。

"(+ 1 10)"をトークナイズすると、次のように並んだトークンを得られる。

「(」「+」「1」「10」「)」

この例は簡単な式なので、「(」と「)」とそれ以外に分割し、それ以外の部分は半角空白で更に分割し、得られたトークンの並びをフラットにすればトークナイズできる。通常のコードでは、コメント記号、改行等もう少し考慮する点があるだろう。

Pythonでこのトークナイズ処理をしてみる。正規表現を使う方法が簡単だろうけれど、ここでは1文字ずつチェックし分岐する方法でトークナイズする。


def tokenize(code: str) -> list[str]:
    code_chars = list(code)
    tokens = []
    token = ""

    while code_chars:
        c = code_chars.pop(0)
        if c in ("(", ")"):
            if token:
                tokens.append(token)
                token = ""
            tokens.append(c)
        elif c == " ":
            if token:
                tokens.append(token)
                token = ""
        elif c == '"':  # ダブルクォート(文字列リテラル)
            if token:
                # ダブルクォート以前に溜った字句があれば追加する
                tokens.append(token)
                token = ""
            # 文字列リテラルを字句として追加する
            # 次のダブルクォートの登場までを1つの字句とする
            token = c  # 先頭のダブルクォートを含める
            try:
                index = code_chars.index('"')
                token += "".join(code_chars[:index+1])  # 末尾のダブルクォートも含める
                tokens.append(token)
                token = ""
                # 未トークナイズの位置を閉じダブルクォートまで進める
                code_chars = code_chars[index+1:]
            except ValueError:  # 閉じられてるダブルクォートがない
                # ダブルクォートは対である必要がある。
                # 対応関係がおかしい場合、構文エラーにするしかない
                print(code_chars)
                raise LispException("syntax error")
        else:
            token += c

    if token:
        tokens.append(token)

    return tokens

抽象構文木を作る(簡易版)

トークナイズしたトークンの並びの構造を解析し、根もしくは枝の所にS式の先頭の要素を置き、葉にそれ以降の要素を置き、木構造を作る事をパースすると呼び、出来上がった木構造を抽象構文木と呼ぶ。

簡単な例

トークナイズされたトークンの並びにある両端の括弧と、括弧に挟まれた要素では意味合いが異なる。両端の括弧はS式の分割位置を表しており、括弧に挟まれた要素は持たされた意味(この場合は「1と10を足す」という意味)を表わしている。


               +----- 式自体に持たされた意味を表している
               |
      +--------+--------+
      |                 |
  (     +     1     10    )
  ^                       ^
  |                       |
  +----------------- S式の分割位置を表している

構造と意味を分離し扱いやすくするために、木構造を使う。木構造とはデータ構造の1つで、次のような親子関係を持つ葉、枝、そして1つだけの根(ルート)で、データを表現する。

       o <--- 根(ルート、他の葉や枝から親を辿った終着点。
      / \        根は唯一親を持たない)
     /   o <- 葉(子要素を持たない)
    o <------ 枝(葉を子要素として持つ)
   / \
  o   o    <- 葉(子要素を持たない)

トークナイズしたトークンの並びの構造を解析し、根もしくは枝の所にS式の先頭の要素を置き、葉にそれ以降の要素を置き、木構造を作る事をパースすると呼び、出来上がった木構造を抽象構文木と呼ぶ。

それでは、トークナイズしたS式をパースし、この木構造に当てはめる。

      +
     / \
    1   10

この木構造を辿ってより下にある枝に置かれた手続を、その枝の葉に適応し、その結果を置き換える。そしてこれを繰替えす事によって、S式全体を計算できる。この一連の操作を評価すると呼ぶ。先程の抽象構文木を構築したS式には評価した結果11となり、この木が置き換えられる。

      +
     / \     => 11
    1   10
もう少し複雑な抽象構文木の例

先程は非常に簡単な抽象構文木の例を示した。次に、もう少し複雑なS式を考えてみる。

(+ 1 (+ 2 8))

評価は通常、S式の先頭以外の値から評価され値となり、その後先頭の手続が呼び出される1。それではこのS式を入力と考え、トークナイズする。

「(」「+」「1」「(」「+」「2」「8」「)」「)」

トークナイズしたこれらのトークンを元に、抽象構文木を作成する。今回は括弧が入れ子になっている事に注意が必要だ。

  1つ目の木
  +---------------------------------------+
  |                                       |
  |    根   葉   部分木                   |
  |    |    |    +-------------------+    |
  |    |    |    |                   |    |
「(」「+」「1」「(」「+」「2」「8」「)」「)」
                 |    |    |    |    |
                 |    枝   葉   葉   |
                 |                   |
                 +-------------------+
                 2つ目の木

木構造を図にすると以下のようになる。

      +
     / \
    1   +
       / \
      2   8
パース処理(簡易版)の実装

Pythonで実装すると次のようになる。


def make_tree(tokens: list)  -> str | list:
    tree = []
    while tokens:
        token = tokens.pop(0)
        if token == ")":
            return tree
        elif token == "(":
            subtree = make_tree(tokens)
            tree.append(subtree)
        else:
            tree.append(token)

    return tree

抽象構文木は誰かが発明したというよりも、長いコンパイラ技術の研究の中で培われてきたノウハウの集合のようなものらしい。正しいのかどうか分からないけれど、また調べてみたい。

抽象構文木を走査し手続を適応する(簡易版)

以下の、S式について考える。

(+ 1 (+ 2 8))

このS式は、抽象構文木で表すと、次のようになった。

      +
     / \
    1   +
       / \
      2   8

これは、どの順番で評価する事が適切だろう。上記の式では、まず 1 が評価され 1 となり、次に (+ 2 8) が評価され 10 となり、最後に (+ 1 10) が評価され 11 が得られる。

まず親から辿り、子がある場合は子供を先に評価する。子供が複数ある場合は、どちらから評価するかという問題があるが、ここでは左側から評価する事にする。すると、次の順番で評価される事になる。

      + (5)
     / \
    1   + (4)
  (1)  / \
      2   8
     (2)  (3)

(1)、(2)、(3)、(4)、(5)のそれぞれの評価結果は以下のようになる。

  • (1) => 1 (理由: アトムなので)
  • (2) => 2 (理由: アトムなので)
  • (3) => 8 (理由: アトムなので)
  • (4) => 10 (理由: 2と8の足し算が行われた)
  • (5) => 11 (理由: 1と11の足し算が行われた)

この処理を実現する。


class LispException(Exception):
    pass


def eval_ast(ast: list | str):
    if isinstance(ast, str):  # 文字列(つまりリスト以外)
        if ast.isnumeric():  # 0以上の整数(アトム)
            return int(ast)
        elif ast.startswith("-") and ast[1:].isnumeric():  # 負の整数(アトム)
            return int(ast)
        elif len(ast) >= 2 and ast.startswith("") and ast.endswith(""):  # 文字列(アトム)
            return str(ast)  # 元々strだけど、文字列に変換する
        else:  # これ以外はおかしなトークン
            raise LispException("bad token")
    elif isinstance(ast, list):  # リスト(つまり抽象構文木)
        procedure_name = ast[0]  # 先頭は手続名
        if procedure_name == "+":  # 足し算
            return sum(map(eval_ast, ast[1:]))
        else:  # それ以外は現状未対応
            raise LispException("no procedure")

    else:  # それ以外はエラー
        raise LispException("bad ast")

評価処理をREPLに組み込む

ここまで整理した情報でも簡単なLispは実装できる。はりぼてのREPLに、評価の部分を追加する。足し算しか実装していないが、Lispで足し算ができるようになった。

from simple_eval import eval_ast
from simple_parse import make_tree
from simple_tokenize import tokenize


ret = None
while True:
    # Read
    code = input("LISP> ")

    # Eval
    tokens = tokenize(code)

    tree_list = make_tree(tokens)
    for tree in tree_list:
        ret = eval_ast(tree)

    # Print
    print(ret)

これを実行すると LISP> というプロンプトマークが表示され、入力を待つ。 (+ 3 4) というS式を入力すると、 7 が表示される。 (+ (+ 1 2) 4) というS式を入力しても 7 が表示されるだろう。

足し算はできるようになっている。それ以外の計算は何もできない。またS式としておかしい入力をすると、異常終了する。

さらにLispへの理解を深める

Lispがどんなプログラミング言語で、簡単な処理系を実装するにはどうすればいいかを確認してきた。これで「Lisp、完全に理解した」と言えるだろうか。

少なくとも僕はもっと知りたいので、もう少しだけ理解を深める事にした。確かに簡単なLispは作ったかもしれないけれど、実際の所それは「S式で記述された足し算インタプリタ」だった。

Lispの処理系を作る事が簡単そうな雰囲気は感じ取れたけれど、できる事な少ないし、そのパワフルさを微塵も感じ取れないし、他の処理系の事も分からない。足し算なら前置記法(+ 1 2)よりも中置記法(1 + 2)の方が慣れているから分かりやすいのでは、とも思える。実際には、前置記法を使ったS式はとても強力だ。

またLispの歴史も気になる。そういった気になる点はまだ沢山ある。そこで、いろいろな角度からLispを観察していく。

nil

Lispにおけるnilは「何もない」という意味を表わすデータであり、アトムとして扱われる。C言語ではNULL、PythonではNoneなどと似たようなデータの表現と言える。Lispでは、nilは空リスト(長さ0のリスト)と等価だが、nil自体は特別な意味を持つシンボルとして実装される。ここではPythonで簡単に実装した。

class _NilObject:
    def __repr__(self):
        return "nil"


NIL = _NilObject()

コンスセル

Lispにはコンスセルという基本的なデータ構造がある。これは、2つのデータを入れる事ができるデータ構造で、前と後ろという順序がある。前のデータはCAR(カー)、後ろのデータはCDR(クダー)と呼ぶ。


 前           後ろ
+--------+--------+
|        |        |
|        |        |
+--------+--------+
  CAR      CDR

コンスセルを実装する

コンスセルをPythonのクラスとして実装した。CDRにはポインタを設定するが、Pythonの場合そもそも参照であるため、そのまま保持する事にした。

from simple_nil import NIL

class ConsCell:
    def __init__(self, car, cdr=NIL):
        self.car = car
        self.cdr = cdr

    def __repr__(self):
        return f"({self.car} . {self.cdr})"

そもそもコンスセルはCARとCDRのペアであるため、tupleでもよかったが、 carcdr を明示的に指定したかったから、クラスで実装する事にした。

cons

このデータ構造を作るための cons という手続きを実装する。

from simple_conscell import ConsCell
from simple_nil import NIL


class LispException(Exception):
    pass


def eval_ast(ast: list | str):
    if isinstance(ast, str):  # 文字列(つまりリスト以外)
        if ast.isnumeric():  # 0以上の整数(アトム)
            return int(ast)
        elif ast.startswith("-") and ast[1:].isnumeric():  # 負の整数(アトム)
            return int(ast)
        elif len(ast) >= 2 and ast.startswith('"') and ast.endswith('"'):  # 文字列(アトム)
            return str(ast)  # 元々strだけど、文字列に変換する
        elif ast == "nil":
            return NIL
        else:  # これ以外はおかしなトークン
            raise LispException("bad token")
    elif isinstance(ast, list):  # リスト(つまり抽象構文木)
        procedure_name = ast[0]  # 先頭は手続名
        if procedure_name == "+":  # 足し算
            return sum(map(eval_ast, ast[1:]))
        elif procedure_name == "cons":  # コンスセル
            return ConsCell(
                car=eval_ast(ast[1]),
                cdr=eval_ast(ast[2]),
            )
        else:  # それ以外は現状未対応
            raise LispException("no procedure")

    else:  # それ以外はエラー
        raise LispException("bad ast")

コンスセルの表記方法

S式では () で括った2つの値の間に . を記述する。ドットを中心に置いた対(ペア)として表現する事から、ドット対とも呼ばれる。

(1 . 2)
 ^   ^
 |   |
 |   +-- CDR
 +------ CAR

コンスセルでリストを作る

ここまでリストを「並んでいるデータ」といった曖昧な表現で考えてきた。Pythonのような言語では、もう既にリストがあるから、それをそのまま使う事もできる。しかしそういったデータ構造が常に最初からある訳ではない。それではリストは、どのように作られているのだろう。

「並んでいるデータ」と言っても、いろんな種類のデータ構造がある。配列、連結リスト、キューなんかも順序があるデータ構造だ。Lispでは連結リストを使って基本的なリストを表現する。

連結リストとは次の要素へのポインタを持たせる事で、データの並びを表現する。以下はアドレスと値とリストの要素の番号を表している。

アドレス要素
000030番目の要素
000100030番目の要素
0002
000311番目の要素
000400071番目の要素
0005
0006
000792番目の要素
0008NULL2番目の要素
0009

このデータは 3, 1, 9 というデータが並んでいる。要素はそれぞれ値と次の要素へのアドレスを持っている。2番目の要素の次の要素へのアドレスはNULLになっている。これは最後の要素である事を表している。

コンスセルは実に単純な構造だけれど、これを数珠繋ぎの要領で繋げる事ができる。コンスセルのCARには値を、コンスセルのCDRには次のコンスセルへのポインタを保持すると、連結リストとして扱う事ができる。図にすると次のようになる。

+-----+---+      +-----+--+    +-----+-----+
|     |   |      |     |  |    |     |     |
|  |  |  ------->|  |  | ----->|  |  | nil |
|  |  |   |      |  |  |  |    |  |  |     |
+--|--+---+      +--|--+--+    +--|--+-----+
   |                |             |

   3                1             9

これをLispで表現すると次のようになる。

(cons 3 (cons 1 (cons 9 nil)))

これはドット対の記法で表現すると、以下のようになる(先頭のシングルクォートについては後述する)。

'(3 . (1 . (9 . nil)))

このドット対のS式は、 .nil があったり、括弧が増えて煩雑なので、以下のように簡略化できる。

'(3 1 9)

コンスセルとリストとS式

コンスセルを数珠繋ぎにする事でリストを表現し、ドット対表記のリストは . や最後の nil を省略する事を確認してきた。つまり、 '(3 . (1 . (9 . nil)))'(3 1 9) は等価だ。

次にS式の足し算を考える。

(+ 2 3)

この式は評価すると 5 になるが、これは以下のようにコンスセルを数珠繋ぎにしたリストだと考える事ができる。

(+ . (2 . (3 . nil)))

この式を実際に評価すると5が得られる。

アトムの定義をもう一度考えると、リストではないものはアトムであり、S式はリストで構成されている。

Pythonのリストから脱却する

今の抽象構文木はPythonのリストを使って、入れ子構造にする事で抽象構文木の形にしているが、コンスセルによって構成されたリストでASTを作る事で、Pythonのリストから脱却できる。

トークナイズ処理はそのままで良い。パース処理で返す値を、Pythonのリストではなくコンスセルによるリストを返すように修正する。

from simple_conscell import ConsCell
from simple_nil import NIL


def make_tree_phase1_structuring(tokens: list):
    tree = []
    while tokens:
        token = tokens.pop(0)
        if token == ")":
            return tree
        elif token == "(":
            subtree = make_tree_phase1_structuring(tokens)
            tree.append(subtree)
        else:
            tree.append(token)

    return tree
    
def make_tree_phase2_conscelling(token: list):
    if not isinstance(token, list):
        return token
    elif len(token) == 0:
        return NIL
    elif len(token) == 1:
        return ConsCell(
            car=make_tree_phase2_conscelling(token[0]),
            cdr=NIL,
        )
    else:
        return ConsCell(
            car=make_tree_phase2_conscelling(token[0]),
            cdr=make_tree_phase2_conscelling(token[1:]),
        )


def make_tree(tokens: list):
    list_py = make_tree_phase1_structuring(tokens)
    list_cons = make_tree_phase2_conscelling(list_py)
    return list_cons.car

また評価処理も、Pythonのリストではなくコンスセルによるリストを受け取り処理するように修正する。

from simple_conscell import ConsCell
from simple_nil import NIL


class LispException(Exception):
    pass

def mapcar(fn, ast: ConsCell):
    if ast.cdr is NIL:
        return [fn(ast.car)]
    else:
        return [fn(ast.car)] + mapcar(fn, ast.cdr)

def eval_ast(ast: ConsCell | str):
    if isinstance(ast, str):  # 文字列(つまりリスト以外)
        if ast.isnumeric():  # 0以上の整数(アトム)
            return int(ast)
        elif ast.startswith("-") and ast[1:].isnumeric():  # 負の整数(アトム)
            return int(ast)
        elif len(ast) >= 2 and ast.startswith('"') and ast.endswith('"'):  # 文字列(アトム)
            return str(ast)  # 元々strだけど、文字列に変換する
        elif ast == "nil":
            return NIL
        else:  # これ以外はおかしなトークン
            raise LispException(f"bad token: {ast}")
    elif isinstance(ast, ConsCell):  # コンスセルで構成されたリスト
        procedure_name = ast.car  # 先頭は手続名
        if procedure_name == "+":  # 足し算
            return sum(mapcar(eval_ast, ast.cdr))
        elif procedure_name == "cons":  # コンスセル
            return ConsCell(
                car=eval_ast(ast.cdr.car),
                cdr=eval_ast(ast.cdr.cdr.car),
            )
        else:  # それ以外は現状未対応
            raise LispException("no procedure")

    else:  # それ以外はエラー
        raise LispException(f"bad ast: {ast}")

REPLも少しだけ修正しておく。

# from simple_eval import eval_ast
# from simple_eval_with_cons import eval_ast
from simple_eval_with_cons_conscell import eval_ast
# from simple_parse import make_tree
from simple_parse_with_cons import make_tree
from simple_tokenize import tokenize


ret = None
while True:
    # Read
    code = input("LISP> ")

    # Eval
    tokens = tokenize(code)
    ast = make_tree(tokens)
    ret = eval_ast(ast)
        
    # Print
    print(ret)

更にドット対の表記に対応する

抽象構文木を作成する過程でドット対の表記( (1 . 2) )が登場したら、 cons を使った表記になるように修正した。

クォート

以下のS式を評価すると5が返される。

(+ 2 3)  ; => 5

これは、括弧の先頭で指定した手続が実行された結果なので当然5になる。では2、3のリスト、つまり (2 3) を得たい時はどうすればいいのだろう。

(2 3) という式を評価しようとすると、2を手続きを解釈してしまいエラーが発生する。

(2 3)  ; 評価すると2を手続きとして処理しようとするためエラー

この2を手続きとして扱わないようにしたい、つまり、式をデータとして扱いたい。これを行うために quote を用意する。

quote は、後に続く式を評価せずそのまま返す。 (2 3) というリストを取得したい場合、 (quote (2 3)) を評価する事で (2 3) を得られる。

quote は後に続く式を評価せずそのまま返す。 (2 3) というリストを取得したい場合、 (quote (2 3)) を評価する事で (2 3) を得られる。

(quote (2 3)) ; => (2 3)

足し算のS式もこれと同様に扱うことができる。 (quote (+ 2 3)) を評価した場合、5ではなく (+ 2 3) というデータを得られる。

これは通常の関数の評価順序とは異なる。このように評価順序が通常とは異なるものを 特殊形式 と呼ぶ。

足し算のS式もこれと同様な扱いができる。 (quote (+ 2 3)) を評価した場合、5ではなく (+ 2 3) というデータを得られる。

これは通常の関数の評価順序とは異なる。このように評価順序が、通常とは異なるものを 特殊形式 と呼ぶ。

from simple_conscell import ConsCell
from simple_nil import NIL


class LispException(Exception):
    pass

def mapcar(fn, ast: ConsCell):
    if ast.cdr is NIL:
        return [fn(ast.car)]
    else:
        return [fn(ast.car)] + mapcar(fn, ast.cdr)

def eval_ast(ast: ConsCell | str):
    if isinstance(ast, str):  # 文字列(つまりリスト以外)
        if ast.isnumeric():  # 0以上の整数(アトム)
            return int(ast)
        elif ast.startswith("-") and ast[1:].isnumeric():  # 負の整数(アトム)
            return int(ast)
        elif len(ast) >= 2 and ast.startswith('"') and ast.endswith('"'):  # 文字列(アトム)
            return str(ast)  # 元々strだけど文字列に変換する
        elif ast == "nil":
            return NIL
        else:  # これ以外はおかしなトークン
            raise LispException(f"bad token: {ast}")
    elif isinstance(ast, ConsCell):  # コンスセルで構成されたリスト
        procedure_name = ast.car  # 先頭は手続名
        if procedure_name == "+":  # 足し算
            return sum(mapcar(eval_ast, ast.cdr))
        elif procedure_name == "quote":  # クォート
            return ast.cdr.car
        elif procedure_name == "cons":  # コンスセル
            return ConsCell(
                car=eval_ast(ast.cdr.car),
                cdr=eval_ast(ast.cdr.cdr.car),
            )
        else:  # それ以外は現状未対応
            raise LispException("no procedure")

    else:  # それ以外はエラー
        raise LispException(f"bad ast: {ast}")

REPLも少しだけ変更する。

# from simple_eval import eval_ast
# from simple_eval_with_cons import eval_ast
# from simple_eval_with_cons_conscell import eval_ast
from simple_eval_with_cons_conscell_quote import eval_ast
# from simple_parse import make_tree
# from simple_parse_with_cons import make_tree
from simple_parse_with_cons_dotpair import make_tree
from simple_tokenize import tokenize


ret = None
while True:
    # Read
    code = input("LISP> ")

    # Eval
    tokens = tokenize(code)
    ast = make_tree(tokens)
    ret = eval_ast(ast)
        
    # Print
    print(ret)

評価器

ここまでの文章でも評価や評価器といった言葉が登場した。普段の生活では耳慣れない言葉だ。そこでこれらの用語を整理し、認識を確認していく。

評価器2は、ある表現をコンピュータで実行可能な形に変換し実行する。この ある表現 の最も一般的なものはプログラミング言語におけるソースコードの事であり、ソースコードを評価器により評価する事で処理を行う。

整理すると評価器は、与えられた表現を解析し、意味を理解し、それに基いた計算を実行するという役割を果たす。

評価器の分類

評価器は、解析、理解、実行の実現方法から分類する事ができる。

コンパイラ

ソースコード全体を解析し、実行可能な形式に変換する。コンパイル(またリンカによるリンク処理)が済むと、実行可能ファイルが生成される。

(例: C、C++のコンパイラ)

インタプリタ

ソースコードを一行ずつ読み取り、逐次実行する。

(例: Python、JavaScriptのインタプリタ)

仮想機械

ソースコードなどから生成される中間コード、バイトコードを生成し、その中間コードを処理するプログラムによって処理する。この中間コードを処理するプログラムを、仮想機械と言う。

(例: JVM)

ソースコードから中間コードを生成する処理は、コンパイラによって生成する場合と、インタプリタによって生成する場合がある。

超循環評価器

評価器と言っても結局の所、変換処理であって、それはプログムであり、何かしらのプログラミング言語で実装されている3。あるプログラミング言語で実装されている評価器が、そのプログラミング言語の変換器である場合、その変換器は超循環評価器と呼ばれる。つまり自分を作る言語を、自分自身で解析評価できる評価器という事になる。

例えばLispの eval 関数は、Lispの評価機能をLispで実装しており、正にこの超循環評価器に当たる。

超循環評価器の主要な要素として、次の点がある。

  1. 評価関数(eval) 式を評価する。
  2. 適応関数(apply) 関数と引数を受け取り、その関数を引数に適応する。
  3. 環境(environment) 式、変数、値を保持するデータ構造。超循環評価器は、環境を管理し、適切に変数の値を取得、設定する。

超循環評価器の説明はSICPにあるので、それを参考に読んでみると良いかもしれない4

純Lisp

純Lispとは 最低限必要な要素で構成されたLISP の事なのだが、特に厳密な取り決めは無いらしい5。Wikipediaにも純Lispとは何かについての説明はある。ただしこれが絶対的な定義という訳ではないようだ67

いずれにしても、純Lispは最小のLispと考えて良さそうだ。幾つかの特殊形式と機能を実装し、超循環評価器として eval を実装するという事が目標になる。とはいえ、まだ何もないし、何もできない訳だから、S式を解析、理解、実行する評価器を作りたい。

ここでは、4つの特殊形式、5つの基本的な関数と、2つの計算用の関数を前提とする。

  • 特殊形式

    cond
    条件分岐。
    quote
    以降のS式を評価せずに返す。
    lambda
    呼出可能なS式を作成し返す。
    define
    呼出可能なS式を作成し、シンボルに関連付けて返す。
  • 関数(基本的なもの)

    atom
    アトムかどうかを判定する。
    eq
    同じ値かどうかを判定する。
    car
    ドット対の左側を返す。
    cdr
    ドット対の右側を返す。
    cons
    ドット対を作成し返す。
  • 関数(計算に必要なもの)

    +
    足し算
    *
    かけ算

Pythonでの実装

PythonでLispを実装するメリットはたいしてないけれど、まずは慣れている言語で概要を掴む事を目指し、Pythonで実装した。それが冒頭に掲載したコードだ。少しだけ動くようになったが、現時点では、マクロも、末尾再帰最適化もない。

テスト

テストは doctest でコードの中に埋め込んでいる。実行は次のように行う。

python3 -m doctest lisp.py

doctest はインタプリタで実行するコードとその出力を docstring に記述する。テスト実行時には、そのコードを実行し出力が同じかを確認する。出力が異なる場合はテストが失敗したと判断される。そのため "a" という出力と 'a' という出力は、言語的には a という同じ文字列なのだけれど、別物として扱われてしまう。こういった扱いにくさはあるけれど、 doctest のテストの実装は圧倒的に楽なのだ。また実行も確認も楽だし、速い。テストする数が増えていくと管理しきれなくなるため、 unittest に移行する事になるけれど、限界が来るまでは doctest で粘る事は1つの有効な戦略だろう。

再帰呼出の実装にハマる

Lispインタプリタを愚直に実装していったが、再帰呼出で躓いた。末尾再帰最適化とかではなく、シンプルな再帰呼出が上手く実装できていなかった。

シンボルの解決に失敗したり、バグにより再帰の上限を越えてエラーしてしまったりといった状態になっていた。ひとつずつステップ実行して状態を確認し、問題を解消した。

動作の確認には階上の計算を使用した。

(define (- p q) (+ p (* -1 q)))
(define (factorial v) (cond ((eq v 0) 1) (t (* v (factorial (- v 1))))))
(factorial 5)

最後の式を評価すると 120 となる。

まとめ

プログラミング言語の仕組みを理解するために、簡単なLisp処理系をPythonを用いて実装した。それに伴い必要になって調べた情報をまとめた。

純Lispは、 最低限必要な要素で構成されたLISP であり、幾つかの機能を実装する事で構成される。評価器は、ある表現を解析、理解、実行する事で処理を行う。そして、それらの実現方法の違いから分類ができる。また評価器を実装する言語を、その評価器自身が評価できる場合、その評価器は超循環評価器と呼ばれる。Lispのeval関数は超循環評価器と言える。抽象構文木は、プログラムのソースコードを木構造として表現する事で、文法的な構造を捉える。プログラムの処理系はソースコードを一度このASTに変換する事で、処理や最適化を簡単にできるように工夫している。Lispの場合、S式自身が抽象構文木の形となっているため解析しやすい。最後に冒頭に掲載したPythonで実装したLisp処理系の詳細を少しだけ説明した。

この文書はまだ途中の段階だけれど、少しずつ理解を進めながら、実装を増やしたり、加筆していきたい。


1

後述するマクロなどを使うと、この評価順序を上手く迂回する事ができる。

2

エバリュエータ、インタプリタ等と呼ばれる。会話の中では、評価する事を「エヴァルする」とか「イーバルする」とか「evalする」と呼ぶ事もある。

3

もしかしたら、機械語で直接実装されているものもあるかもしれないけれど、そんなものは数少ない変わり種であるだろうから、考えない事にする。