🪓

悪ノリで Lisp トランスパイラを実装した with Python。

2024/02/10に公開

はじめに

友達がこんなことを呟いていた。

https://x.com/xeki00/status/1753426382410183054?s=20

気持ちは分かるよ。私も Python には滅んでほしいと思っている。そしてプログラミング界隈にはこんなジョークがあるんだ。

https://x.com/wsuzume/status/1753427254645051723?s=20

パンがないならケーキを焼いて食べればいいのに。対する友の返答はこうだった。

https://x.com/xeki00/status/1753427989805891862?s=20

え、マジ? 作るけど?

というわけで作成した Lisp トランスパイラを以下に置いておいた[1]

→ Google Colab

試しに FizzBuzz のコードを実行した結果が以下。

lisp = Lisp("""
(
    (define fizzbuzz (x)
        (if (== (% x 15) 0) (print "FizzBuzz")
            (if (== (% x 3) 0) (print "Fizz")
                (if (== (% x 5) 0) (print "Buzz")
                    (print x)
                )
            )
        )
    )
    (define FizzBuzz (x)
        (if (== x []) ()
            (
                (fizzbuzz (car x))
                (FizzBuzz (cdr x))
            )
        )
    )
    (FizzBuzz (list (range 1 31)))
)
""")
exec(lisp.transpile())
output
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Fizz
22
23
Fizz
Buzz
26
Fizz
28
29
FizzBuzz

ここから先は泥臭い話なので結末だけ知りたい人は

この話のオチへ

実装の方針

いざプログラミング言語を作るとき、おそらくもっともキツいのはコンパイル後のコードを実行することである。たとえばC言語をバイトコードに変換しても、現代的な環境ではそのバイトコードを正しいプログラムとして実行するまでに何段階か手順を踏まなければならない[2]

だが Python には悪名高い exec 関数がある

exec 関数は与えられた Python のコードを現在のコンテキストで実行する。Web からの入力をそのまま渡せば一瞬で任意コード実行可能の脆弱性の完成だ。

exec("""
print('Hello!')
print('1+1 =', 1+1)
""")
output
Hello!
1+1 = 2

つまり、Lisp を Python にトランスパイルして exec 関数で実行するならば、コンパイル後のコード実行が難しいという最大の問題はクリアされる。

そして Python の文法は意外とガバガバで割と無茶なハックができる。文法構造が単純な Lisp からのトランスパイルはおそらくさほど難しくない。頑張っちゃうぞ。

雛形

雛形となるクラスは以下だ。以下のクラスは与えられたコードをそのまま返すだけで何もしない。

class Lisp:
    def __init__(self, code: str):
        self.code = code
    
    def transpile(self):
        return self.code

あとで transpile メソッドの中身を実装すれば、以下のように Lisp を実行できるという算段だ。

lisp = Lisp("""
print('Hello!')
print('1+1 =', 1+1)
""")

exec(lisp.transpile())
output
Hello!
1+1 = 2

Lisp の構文:S式

現代的な Lisp の構文のフルセットはさすがに作るのが大変だが、糖衣構文やマクロを除いた原始的かつ基本的な部分だけ実装すればよいのであれば、Lisp とはただのS式である。

そしてS式は以下のたった2つのルールのみから成る。

  1. アトムはS式である。
  2. xy がS式であるならば (x . y) という形式の式はS式である。

Lisp はたったこれだけのルールで、データとプログラムの両方を記述できる。たとえば (x y z) という3つの要素を持つ順序集合たるリストは (x . (y . (z . ()))) というS式の糖衣構文である[3]

また、関数適用 print(a, b, c)(print a b c) というS式で記述することができる。実装としては、リストの先頭が関数であれば以降の要素を引数として関数を呼び出し、そうでなければデータとして扱う。

これらのルールをもとに簡易的に実装した Lisp ランタイムは以下のようになる[4]

from typing import Callable

def id_or_eval(xs):
    # 与えられたリストがプログラムであれば実行し、
    # データであればそのまま返す関数
    if not isinstance(xs, list):
        # アトムである
        return xs
    # リストである
    if len(xs) == 0 or not isinstance(xs[0], Callable):
        # データである
        return xs
    # プログラムである
    # ネストしたリスト構造にも再帰させる
    return xs[0](*(map(id_or_eval, xs[1:])))
print(id_or_eval( 'Hello!' ))     # アトムである
print(id_or_eval( [] ))           # 空のリストである
print(id_or_eval( [1, 2, 3] ))    # データである
print(id_or_eval( [max, 1, 2] ))  # プログラムである
print(id_or_eval( [max, 5, [min, 6, 7]]))  # ネストしたプログラムである
output
Hello!
[]
[1, 2, 3]
2
6

トランスパイラの作成

上で作成した Lisp ランタイムを完成させるにはさらに遅延評価やレキシカルスコープといった概念を実装する必要があるが、今回はランタイムに Python そのものを用いることで面倒な概念の実装の手間を省く。要するに Lisp のプログラムと等価な Python コードに変換するだけでよい。

プログラミング言語を実装する上でひとつの目標は、そのプログラミング言語がチューリング完全になることである。チューリング完全なプログラミング言語どうしは互いに翻訳可能[5]であり、要するにプログラミング言語でできることは何でもできるようになるからである。

プログラミング言語がチューリング完全となるには、簡単には

  1. 変数の定義と読み書き
  2. 関数の定義
  3. 配列の走査
  4. 条件分岐
  5. ループまたは再帰

といった要素が揃っていればよい[6]。ぶっちゃけ任意有限長の整数リストに対する FizzBuzz が書けるならばこの条件は満たされる[7]ので、FizzBuzz を実装できることが目標のひとつになる。

トークナイザ

Lisp ではリストを () で囲み、リスト内の要素を空白文字(スペースや改行文字)で区切る[8]

本来であれば各トークンを構成するルールを定めるべきだが、簡略化のために () または空白文字で区切られた文字列をトークンとみなす。ただし文字列リテラルだけは内部に区切り文字を含む可能性があるので、非効率ではあるが、文字列リテラルは事前に別のトークンに置き換えておく。

以下のコードは文字列リテラルに ID を割り振って {ID} というトークンに置換するコードである。波括弧 {} は今回作る Lisp の中では特殊トークンの目印として用いるので、文字列の外での使用は禁止する。

import re
import uuid

def find_double_quotes(xs):
    # 文字列の切取り位置に目印をつける
    return [ i for i, x in enumerate(xs) if x == '"' ]

def replace_strings(xs: str):
    idxs = find_double_quotes(xs)

    if len(idxs) % 2 != 0:
        # ダブルクォートの数が合わない
        raise RuntimeError(f"Unpaired string literal.")
    
    ret = []
    table = {}

    def get_unique_id():
        while True:
            uid = f"{{{str(uuid.uuid4()).split('-')[-1]}}}"
            if uid not in table:
                break
        return uid

    def prohibit_curly_braces(xs: str):
        # 波括弧は文字列の外では禁止する
        if re.search('[\\{\\}]', xs) is not None:
            raise RuntimeError(f"curly braces are not allowed: {xs}")
        return xs

    # 置換処理
    prev_end = 0
    for begin, end in [ (idxs[2*i], idxs[2*i+1]) for i in range(len(idxs) // 2) ]:
        ret.append(prohibit_curly_braces(xs[prev_end: begin]))
        
        uid = get_unique_id()
        table[uid] = xs[begin: end+1]
        ret.append(uid)

        prev_end = end+1

    ret.append(prohibit_curly_braces(xs[prev_end:]))
    
    return ''.join(ret), table
動作テスト
Test1
replace_strings('abc "def" ghi')
output
('abc {{0a26389258b6}} ghi', {'{0a26389258b6}': '"def"'})
Test2
ret, table = replace_strings("""
    abc "def ghi
      jkl
    " mno "p(qr)s" t u "vwxyz"
""")

print(ret)
print(table)
output
    abc {711da8911493} mno {f29cb82f3a2e} t u {81f226d4fd30}

{'{711da8911493}': '"def ghi\n      jkl\n    "', '{f29cb82f3a2e}': '"p(qr)s"', '{81f226d4fd30}': '"vwxyz"'}

あとは空白文字で区切り、先頭と末尾に () がくっついていたら分離すればよい。

def split_parens(xs):
    # '((hoge))' を ['(', '(', 'hoge', ')', ')'] みたいにしたい
    if re.search('\\)[^\s\\)]', xs):
        # ) の直後に ) 以外の文字が来るのは文法エラー
        raise RuntimeError(f"Needs space after ')': {xs}")

    m = re.match('^(?P<prefix>[\\(\\)]*)(?P<infix>[^\s\\(\\)]*)(?P<suffix>[\\(\\)]*)$', xs)
    if m is None:
        raise RuntimeError(f"Unknown parse failed error: {xs}.")

    prefix, infix, suffix = m.group('prefix'), m.group('infix'), m.group('suffix')

    return list(prefix) + [ infix ] + list(suffix)

def tokenize(xs: str):
    xs, table = replace_strings(xs)

    ret = []
    for x in re.split('\s', xs):
        if x != '':
            ret.extend(split_parens(x))
    
    def restore_strings(x, table):
        # 一度よけた文字列をもとに戻す
        if x in table:
            return table[x]
        return x
    
    return [ restore_strings(x, table) for x in ret if x != '']
動作テスト
Test
tokenize("""
(
    (let a 1)
    (let b 2)
    (define f (x y)
            (+ x y))
    (let c (f a b))
    (if (> c 2) (print "Hello, world!") (print "Good night, baby!"))
)
""")
output
# 縦長なので折り返しは手で調整した
['(',
   '(', 'let', 'a', '1', ')',
   '(', 'let', 'b', '2', ')',
   '(', 'define', 'f', '(', 'x', 'y', ')',
     '(', '+', 'x', 'y', ')',
   ')',
   '(', 'let', 'c',
     '(', 'f', 'a', 'b', ')',
   ')',
   '(', 'if', '(', '>', 'c', '2', ')',
     '(', 'print', '"Hello, world!"', ')',
     '(', 'print', '"Good night, baby!"', ')',
   ')',
 ')']

パーサ

Lisp のコードをトークンに分割できたので、これを抽象構文木に変換する。といっても Lisp は抽象構文木そのものなので、スタックマシンで簡単に実装することができる。Python で木構造を作るのは面倒なので辞書で代用する。

class Context:
    # スタックを管理するクラス
    def __init__(self):
        self.stack = []

class Expression:
    # ネストを解除した S 式に対応するクラス
    def __init__(self, uid):
        self.uid = uid
        self.tokens = []
    
    def __repr__(self):
        return f"Expression({self.uid}, {str(self.tokens)})"

def _parse(ctx: Context, xs: list):
    # S 式を1階層ごとに分割して辞書に表を作る
    table = {
        ctx.stack[-1].uid: ctx.stack[-1], 
    }

    def get_unique_id():
        while True:
            uid = f"{{{str(uuid.uuid4()).split('-')[-1]}}}"
            if uid not in table:
                break
        return uid

    for x in xs:
        if x == '(':
            uid = get_unique_id()
            ctx.stack[-1].tokens.append(uid)
            # 新しいS式の開始
            exp = Expression(uid)
            ctx.stack.append(exp)
            ctx.stack[-1].tokens.append(x)
        elif x == ')':
            last_exp = ctx.stack[-1]
            last_exp.tokens.append(x)
            table[last_exp.uid] = ctx.stack.pop()

            if len(ctx.stack) == 0:
                # 閉じ括弧が多すぎる
                raise RuntimeError(f"Excessive close parenthesis: {last_exp}")
        else:
            ctx.stack[-1].tokens.append(x)

    if len(ctx.stack) != 1:
        # 閉じ括弧が少なすぎる
        raise RuntimeError(f"Unpaired parentheses: {ret}, {ctx.stack}")

    return table

def parse(xs: list):
    # 再帰前の調整をして再帰関数 _parse に渡す
    if len(xs) == 0:
        raise RuntimeError(f"No source code.")

    if xs[0] != '(':
        raise RuntimeError(f"Lisp must be start with '(': {xs[0]}")
    
    ctx = Context()
    exp = Expression('')  # エントリーポイント
    ctx.stack.append(exp)

    return _parse(ctx, xs)
動作テスト
Test
tokens = tokenize("""
(
    (let a 1)
    (let b 2)
    (define f (x y)
            (+ x y))
    (let c (f a b))
    (if (> c 2) (print "Hello, world!") (print "Good night baby!"))
)
""")

parse(tokens)
output
{'': Expression(, ['{23c31acbaf12}']),
 '{f1fb435b7e82}': Expression({f1fb435b7e82}, ['(', 'let', 'a', '1', ')']),
 '{ea386a3df7e3}': Expression({ea386a3df7e3}, ['(', 'let', 'b', '2', ')']),
 '{231e53bbbe07}': Expression({231e53bbbe07}, ['(', 'x', 'y', ')']),
 '{40560f09a5d8}': Expression({40560f09a5d8}, ['(', '+', 'x', 'y', ')']),
 '{d97ae81fa44b}': Expression({d97ae81fa44b}, ['(', 'define', 'f', '{231e53bbbe07}', '{40560f09a5d8}', ')']),
 '{c91b6f4c8435}': Expression({c91b6f4c8435}, ['(', 'f', 'a', 'b', ')']),
 '{df3aeeb8cce6}': Expression({df3aeeb8cce6}, ['(', 'let', 'c', '{c91b6f4c8435}', ')']),
 '{f2a1f8a54d10}': Expression({f2a1f8a54d10}, ['(', '>', 'c', '2', ')']),
 '{b890e1c0bc24}': Expression({b890e1c0bc24}, ['(', 'print', '"Hello, world!"', ')']),
 '{7964a76036da}': Expression({7964a76036da}, ['(', 'print', '"Good night baby!"', ')']),
 '{10f4ee68863d}': Expression({10f4ee68863d}, ['(', 'if', '{f2a1f8a54d10}', '{b890e1c0bc24}', '{7964a76036da}', ')']),
 '{23c31acbaf12}': Expression({23c31acbaf12}, ['(', '{f1fb435b7e82}', '{ea386a3df7e3}', '{d97ae81fa44b}', '{df3aeeb8cce6}', '{10f4ee68863d}', ')'])}

トランスパイラ

あとはこの抽象構文木を Python に変換するだけだ。抽象構文木を表す辞書の先頭はエントリーポイントなので、そこから順に辿って Python コードを構築すればよい。

テストに用いる Lisp コードは以下。

( "This is a comment." )
"This is a comment too."
(
    "This is also a comment."
    (let a 1)
    (let b 2)
    (define f (x y)
            (+ x y))
    (let c (f a b))
    (if (> c 2) (print "Hello, world!") (print "Good night, baby!"))
)

これとおおよそ等価な Python コードは以下であり、これを機械的に生成すればよい。

def _f_0():
    _ret = []
    def _f_x1_d1():
        _ret = []
        _ret.append("This is a comment.")
        return _ret
    _ret.append(_f_x1_d1())
    _ret.append("This is a comment too.")
    def _f_x3_d1():
        _ret = []
        _ret.append("This is also a comment.")
        a = 1
        _ret.append(a)
        b = 2
        _ret.append(b)
        def f(x, y):
            return x + y
        _ret.append(f)
        c = f(a, b)
        _ret.append(c)
        _ifcond = c > 2
        if _ifcond:
            _ifret = print("Hello, world!")
        else:
            _ifret = print("Good night, baby!")
        _ret.append(_ifret)
        return _ret
    _ret.append(_f_x3_d1())
    return _ret

要するに (def _f():, _ret = [] に置き換えたり、先に評価しなければならない式は関数として定義して実行するように書き換えるだけである。Lisp はS式を評価すると何らかの値を取るので、

  • 変数定義 → 定義された変数の名前(文字列)
  • 関数定義 → 定義された関数の名前(文字列)
  • 条件分岐 → 分岐した結果の式の評価値

になるようにしてある[9]。また、Lisp は演算子を前置するので、トランスパイル時には中置記法に置き直すか前置記法に対応した Python 関数を定義してやらねばらない。

最終的なコードは以下。

from io import StringIO

def writer(token, ast, operators, q, tab, indent, append_val=True):
    if token == '':
        # プログラムのエントリーポイント
        ## 全体となる関数を作成して
        q.append(f'def _f_0():\n')
        q.append(f'{tab*(indent+1)}_ret = []\n')

        ## 関数の中身を書き込んで
        for t in ast[''].tokens[1: -1]:
            writer(t, ast, operators, q, tab, indent+1)

        ## 戻り値をつけて
        q.append(f'{tab*(indent+1)}return _listeval(_ret)\n')
        ## 評価する
        q.append(f'_f_0()\n')
    elif token in ast:
        # トークンが AST にあって
        fst_token = ast[token].tokens[1]
        if fst_token not in {'let', 'define', 'if'}:
            # マクロではないなら
            ## 関数で括ってスコープを作成して
            q.append(f'{tab*indent}def _f_{indent}():\n')
            q.append(f'{tab*(indent+1)}_ret = []\n')

            ## 中身を書き込んで
            for t in ast[token].tokens[1: -1]:
                writer(t, ast, operators, q, tab, indent+1)

            ## 閉じる
            q.append(f'{tab*(indent+1)}return _listeval(_ret)\n')
            if append_val:
                ## これはつけたいときとそうでないときがあるので切り替え可能にしておく
                q.append(f'{tab*indent}_ret.append(_f_{indent}())\n')
        elif fst_token == 'let':
            # 変数の定義
            if ast[token].tokens[3] not in ast:
                # 代入する値が複雑な式でないとき
                q.append(f'{tab*indent}{ast[token].tokens[2]} = {ast[token].tokens[3]}\n')
                q.append(f'{tab*indent}_ret.append("{ast[token].tokens[2]}")\n')
            else:
                # 代入する値が複雑な式のとき
                writer(ast[token].tokens[3], ast, operators, q, tab, indent, append_val=False)
                q.append(f'{tab*indent}{ast[token].tokens[2]} = _f_{indent}()\n')
                q.append(f'{tab*indent}_ret.append("{ast[token].tokens[2]}")\n')
        elif fst_token == 'define':
            # 関数の定義
            params = ','.join(ast[ast[token].tokens[3]].tokens[1:-1])
            q.append(f'{tab*indent}def {ast[token].tokens[2]}({params}):\n')
            q.append(f'{tab*(indent+1)}_ret = []\n')
            writer(ast[token].tokens[4], ast, operators, q, tab, indent+1, append_val=False)
            q.append(f'{tab*(indent+1)}return _f_{indent+1}()\n')
            q.append(f'{tab*indent}_ret.append("{ast[token].tokens[2]}")\n')
        elif fst_token == 'if':
            # if 文
            writer(ast[token].tokens[2], ast, operators, q, tab, indent, append_val=False)
            q.append(f'{tab*indent}_ifcond = _f_{indent}()\n')
            q.append(f'{tab*indent}if _ifcond:\n')
            writer(ast[token].tokens[3], ast, operators, q, tab, indent+1, append_val=False)
            q.append(f'{tab*(indent+1)}_ifret = _f_{indent+1}()\n')
            q.append(f'{tab*indent}else:\n')
            writer(ast[token].tokens[4], ast, operators, q, tab, indent+1, append_val=False)
            q.append(f'{tab*(indent+1)}_ifret = _f_{indent+1}()\n')
            q.append(f'{tab*indent}_ret.append(_ifret)\n')
    else:
        # それ以外のときは演算子なら置き換え、そうでないならそのまま
        if token in operators:
            t = operators[token]
        else:
            t = token
        q.append(f'{tab*indent}_ret.append({t})\n')


def transpile(ast):
    tab = '    '
    indent = 0

    # リストを Lisp 風に評価する関数と、
    # リストの先頭とそれ以降を取り出す重要な関数の定義
    queue = [
        'from typing import Callable\n',
        'def _listeval(xs):\n',
        '    if len(xs) == 0:\n'
        '        return None\n'
        '    if isinstance(xs[0], Callable):\n',
        '        return xs[0](*xs[1:])\n',
        '    return xs\n',
        'def _car_(xs):\n',
        '    return xs[0]\n',
        'def _cdr_(xs):\n',
        '    return xs[1:]\n',
    ]

    # Lisp 演算子を Python 関数に置き換えるための辞書
    operators = {
        '+': '_add_',
        '-': '_sub_',
        '*': '_mul_',
        '/': '_div_',
        '%': '_mod_',
        '==': '_eq_',
        '!=': '_neq_',
        '>': '_gt_',
        '<': '_lt_',
        '>=': '_ge_',
        '<=': '_le_',
    }

    # 演算子置き換え用の関数を生成
    for op, fn in operators.items():
        queue.append(f'def {fn}(x, y):\n')
        queue.append(f'    return x {op} y\n')

    # 演算子以外の特殊関数を定義
    operators.update({
        'car': '_car_',
        'cdr': '_cdr_',
    })

    # 全体が複数のS式から成る場合、全体を括ってひとつのS式にする
    root = ast['']
    if root.tokens[0] != '(':
        root.tokens = ['('] + root.tokens + [')']

    # エントリーポイントから書き込み
    writer('', ast, operators, queue, tab, indent)

    # 出力
    with StringIO() as f:
        for line in queue:
            f.write(line)
        code = f.getvalue()
    return code                
トランスパイルで生成されたコード
from typing import Callable
def _listeval(xs):
    if len(xs) == 0:
        return None
    if isinstance(xs[0], Callable):
        return xs[0](*xs[1:])
    return xs
def _car_(xs):
    return xs[0]
def _cdr_(xs):
    return xs[1:]
def _add_(x, y):
    return x + y
def _sub_(x, y):
    return x - y
def _mul_(x, y):
    return x * y
def _div_(x, y):
    return x / y
def _mod_(x, y):
    return x % y
def _eq_(x, y):
    return x == y
def _neq_(x, y):
    return x != y
def _gt_(x, y):
    return x > y
def _lt_(x, y):
    return x < y
def _ge_(x, y):
    return x >= y
def _le_(x, y):
    return x <= y
def _f_0():
    _ret = []
    def _f_1():
        _ret = []
        _ret.append("This is a comment.")
        return _listeval(_ret)
    _ret.append(_f_1())
    _ret.append("This is a comment too.")
    def _f_1():
        _ret = []
        _ret.append("This is also a comment.")
        a = 1
        _ret.append("a")
        b = 2
        _ret.append("b")
        def f(x,y):
            _ret = []
            def _f_3():
                _ret = []
                _ret.append(_add_)
                _ret.append(x)
                _ret.append(y)
                return _listeval(_ret)
            return _f_3()
        _ret.append("f")
        def _f_2():
            _ret = []
            _ret.append(f)
            _ret.append(a)
            _ret.append(b)
            return _listeval(_ret)
        c = _f_2()
        _ret.append("c")
        def _f_2():
            _ret = []
            _ret.append(_gt_)
            _ret.append(c)
            _ret.append(2)
            return _listeval(_ret)
        _ifcond = _f_2()
        if _ifcond:
            def _f_3():
                _ret = []
                _ret.append(print)
                _ret.append("Hello, world!")
                return _listeval(_ret)
            _ifret = _f_3()
        else:
            def _f_3():
                _ret = []
                _ret.append(print)
                _ret.append("Good night, baby!")
                return _listeval(_ret)
            _ifret = _f_3()
        _ret.append(_ifret)
        return _listeval(_ret)
    _ret.append(_f_1())
    return _listeval(_ret)
_f_0()
実行結果
Hello, world!

完成

あとは雛形にはめ込んで外面を取り繕えば完成。

class Lisp:
    def __init__(self, code: str):
        self.code = code

    def transpile(self):
        tokens = tokenize(self.code)
        ast = parse(tokens)
        return transpile(ast)

この自前の Lisp の中で再帰関数がうまくワークするかは考えてなかったけど、Python のランタイムがよしなに計らってくれると信じて FizzBuzz を書いてみよう!

lisp = Lisp("""
(
    (define fizzbuzz (x)
        (if (== (% x 15) 0) (print "FizzBuzz")
            (if (== (% x 3) 0) (print "Fizz")
                (if (== (% x 5) 0) (print "Buzz")
                    (print x)
                )
            )
        )
    )
    (define FizzBuzz (x)
        (if (== x []) ()
            (
                (fizzbuzz (car x))
                (FizzBuzz (cdr x))
            )
        )
    )
    (FizzBuzz (list (range 1 31)))
)
""")

というわけでその結果は冒頭に再帰する。

やってみた感想

プログラミング言語を実際に動かすところまで作るのは初めてだったけどなんとかなったNE☆

おしまい

https://x.com/xeki00/status/1756296262973104427?s=20

脚注
  1. 自分で書かなくても Hy という Lisp on Python があるので@t-sin さんの記事などを教えてあげればそれで話は終わりだけど、それじゃあつまらないなって。友から任されたのは私が Lisp を作ることなんだ。 ↩︎

  2. ELF フォーマットにしたり、必要なライブラリをリンクしたり。 ↩︎

  3. 空のリスト () はアトムである。 ↩︎

  4. ただし Lisp における (x . y) というドット対で、リストの末尾に相当する y が空リストでないケースは Python に対応する表現がない(タプルで作れるとは思うが面倒である)ので本記事では割愛する。 ↩︎

  5. 厳密には万能チューリングマシンと等価になるだけであって、万能チューリングマシンよりも真に大きい能力を持つプログラミング言語とそのランタイムが存在する場合は、チューリング完全なプログラミング言語で表現できない文法や機能を持つ可能性がある。 ↩︎

  6. どの要素があればプログラミング言語がチューリング完全になるかどうかは本来数学的に厳密な議論が必要だが、ここでは見逃してほしい。実際、Lazy K のような非常に小さな言語ですらチューリング完全なので、ここに書かれているような要素があれば大抵はチューリング完全である。 ↩︎

  7. 固定長の整数リストに対してでよいならば、対応する数の print を仕込むだけでよいのでチューリング完全とならないケースがある。 ↩︎

  8. カンマ(,)はスペース同様に有効な区切り文字とされる場合が多いが、処理が煩雑になるので今回は区切り文字は空白文字のみとする。何が面倒かというと、連続するスペース2個(x y)と、連続するカンマ2個(x,,y)では意味合いが変わってしまい、処理を統一できないのである。 ↩︎

  9. 関数定義については、定義された関数への参照を返す実装も試してみたが、リストの先頭で関数定義をして、その式を評価したときに関数の実行とみなされてしまうケースが出てきたので名前を返すことでお茶を濁した。 ↩︎

Discussion