zick pages

Googleスプレッドシートで（名前付き関数とか使わず）LISPインタプリタを作った

はじめに

こんなの を作った。 前回つくったものと見た目はほぼ同じだが作りはかなり異なる。 前回は「非常に使いにくい純粋関数型言語」でLISPを実装した話だが、 今回は「癖の強すぎるアセンブリっぽい何か」でLISPを実装した話だ。 同じGoogleスプレッドシートとはいえ、3000倍くらい難しい。

ループを有限個のセルで近似する

Googleスプレッドシートでは、名前付き関数や LAMBDA を使わなければ、 ループ（や再帰）をする方法がない。 そのためLISPを実装することは困難だ。だが方法がないわけではない。

簡単な例としてNの階乗を求める方法を考えてみよう。 階乗をCommon Lispで末尾再帰的に書くと次のようになる。

(defun fact (n &optional (acc 1))
  (if (= n 0)
      acc
      (fact (1- n) (* n acc))))

これをスプレッドシートで再現しよう。 セルA1に整数Nが入力されているとする。

  A
1 5

現在のNを表すためにA2に =A1 を入力し、 計算途中の値としてB2に1を入力する。

  A B
1 5  
2 =A1 1

ここまでが下準備だ。 A列の値は1行下がるごとに1ずつ減らす。 ただし、0より下に行かないように IF を使う必要がある。 A3には =IF(A2 = 0, A2, A2 - 1) を入力する。 B列の値はひとつ上の行のAとB積とする。 ただし、Aが0のときはひとつ上のBの値を維持する。 B3には =IF(A2 = 0, B2, A2 * B2) を入力する。

  A B
1 5  
2 =A1 1
3 =IF(A2 = 0, A2, A2 - 1) =IF(A2 = 0, B2, A2 * B2)

あとはオートフィルを使ってA列とB列の続きを自動入力する。

  A B
1 5  
2 =A1 1
3 =IF(A2 = 0, A2, A2 - 1) =IF(A2 = 0, B2, A2 * B2)
4 =IF(A3 = 0, A3, A3 - 1) =IF(A3 = 0, B3, A2 * B3)
5 =IF(A4 = 0, A4, A4 - 1) =IF(A4 = 0, B4, A2 * B4)
6 =IF(A5 = 0, A5, A5 - 1) =IF(A5 = 0, B5, A5 * B5)
7 =IF(A6 = 0, A6, A6 - 1) =IF(A6 = 0, B6, A6 * B6)

このように式を入力するとB7に計算結果である120が出力される。

  A B
1 5  
2 5 1
3 4 5
4 3 20
5 2 60
5 1 120
7 0 120

A1の値を変更しても、必要なだけオートフィルする限り正しい値が求まる。 とりあえず1000行までオートフィルしてやれば、 理屈上は998の階乗までの値は常にB1000に格納される （実際に998の階乗を求めようとするとオーバフローしてしまうが）。 もっと大きい数を試したい場合は行を増やしてやればよい。 階乗の場合はNの大きさで必要な行数が決まるが、 いわゆる無限ループを実現しようとすると、無限個のセルが必要になる。 もちろんそんなことはできない。 セルの個数は有限なので計算を有限回で打ち切ることになる。 そんなものは正しいループではないとの意見もあるかもしれないが、 人間も計算機も有限の寿命を持っている以上、 真の無限ループなどそもそも計算機では実現できないのだ。 そんな感じの哲学っぽい屁理屈でお許し頂きたい。

話がそれたが、これがLISPを実装するための基本的なアイディアだ。 各セルが1つ上のセルを見て、計算を1ステップ進める。 答えが求まれば1つ上のセルの値をそのまま維持する。 これで一応はLISPを書くことができるのだが、 このまま複雑な式（プログラム）を書くと迷子になってしまう （少なくても私は迷子になった）。 楽をするためにもう少し道具を準備したほうがよい。

状態とレジスタ

先程の例ではA列とB列の2つの列を使ったが、 複数の列に異なる式を書くのは煩わしい。 この問題は複数の値を1つの文字列に埋め込むことで解決できる。 先程の例では A2に =CONCATENATE(";n=", A1, ";acc=1;") と書いてやると ;n=5;acc=1; のような文字列が得られる。ここで、 REGEXEXTRACT(A2, ";n=([^;]*);") と書いてやれば n の中身が取り出せ、 REGEXEXTRACT(A2, ";acc=([^;]*);") と書いてやれば acc の中身が取り出せる。 これでB列を使う必要がなくなった。 この;n=5;acc=1; のような文字列のことを「状態」、 状態に含まれる n や acc のことを「レジスタ」と呼ぶことにしよう。

階乗の例では常に n と acc を書き換えるので、 新たな状態を作るために CONCATENATE を使えばよいのだが、 レジスタが多数あるときに一つだけ書き換えたいときに 単純に CONCATENATE を使うと式が非常に長くなってしまう。 ;r0=0;r1=0;r2=0;r3=0; という状態の r1 を 1 に書き換えたいときは =REGEXREPLACE(A2, ";r1=([^;]*);", ";r1=1;") と書いてやればよい。 r1 に加えて、 r3 も 1に書き換えたいときは

=REGEXREPLACE(
  REGEXREPLACE(A2, ";r1=([^;]*);", ";r1=1;"),
  ";r3=([^;]*);",
  ";r3=1;")

このように REGEXREPLACE を入れ子にしてやればよい。 最初はやりたいことに対して式が長くて読みにくいことに戸惑うかもしれないが、 なれてしまえばどうということはない。

この代入は並列に行われることに注意する必要がある。 r1 に1を代入して、 r3 に r1 を代入してみよう。

=REGEXREPLACE(
  REGEXREPLACE(A2, ";r1=([^;]*);", ";r1=1;"),
  ";r3=([^;]*);",
  CONCATENATE(";r3=", REGEXEXTRACT(A2, ";r1=([^;]*);"), ";"))

この結果は ;r0=0;r1=1;r2=0;r3=0; となる。 r3 に代入されるのは一つ前の r1 であり、 新しい r1 ではない。 Common Lispでいえば (psetq r1 1 r3 r1) といったところだ。

r1 に1を代入した後に r3 に r1 を代入するといった 逐次代入を行うためにはもう少し道具を準備する必要がある。

プログラムカウンタとジャンプ

A2に状態 ;r0=0;r1=0;r2=0;r3=0; が入っているとする。 ここで「r1 に1を代入した後に r3 に r1 を代入」したい場合、 まずA3で r1 に1を代入して状態を ;r0=0;r1=1;r2=0;r3=0; に変化させ、 次にA4で r3 に r1 を代入して状態を ;r0=0;r1=1;r2=0;r3=1; に変化させる。 A5以降のセルはA4の状態を維持し続けるとする。

こういった逐次処理を実現するために「プログラムカウンタ」を導入する。 プログラムカウンタはレジスタであり、その値により処理を分岐する。 プログラムカウンタ pc を使うと式全体の構造は次のような形になる。

=SWITCH(REGEXEXTRACT(A2, ";pc=([^;]*);"),
"label0",
処理0,

"label1",
処理1,

"label2",
処理2,

CONCATENATE("INVALID PC: ", REGEXEXTRACT(A2, ";pc=([^;]*);")))

このプログラムカウンタを使って逐次代入を実装しよう。 まずA2に状態 ;pc=label0;r0=0;r1=0;r2=0;r3=0; を入れる。 pcが追加されていることに注意。 A3には次の内容を入れて以降のセルはオートフィルで埋める。

=SWITCH(REGEXEXTRACT(A2, ";pc=([^;]*);"),
"label0",
REGEXREPLACE(
  REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=label1;"),
  ";r1=([^;]*);", ";r1=1;"),

"label1",
REGEXREPLACE(
  REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=label2;"),
  ";r3=([^;]*);",
  CONCATENATE(";r3=", REGEXEXTRACT(A2, ";r1=([^;]*);"), ";")),

"label2",
A2,

CONCATENATE("INVALID PC: ", REGEXEXTRACT(A2, ";pc=([^;]*);")))

まずA3で pc と r1 が書き換えられ状態が ;pc=label1;r0=0;r1=1;r2=0;r3=0; に変化する。 次にA4で pc と r3 が書き換えられ状態が ;pc=label2;r0=0;r1=1;r2=0;r3=1; に変化する。 A5以降のセルは状態を変化させない。 プログラムカウンタ pc はただのレジスタであるため、 明示的に書き換えない限り値は変わらない。 そのため上の例では一度 pc が label2 になると、 それ以降 pc が書き換わることはない （それはカウンタではないという苦情は受け付けない）。

プログラムカウンタの書き換えは実質的なジャンプ命令なので、 これを使って条件分岐やループも実現できる。 試しにユークリッドの互除法を書いてみよう。 A2の r0, r1 に入力が入っており、結果は r0 に入れるとする。

=SWITCH(REGEXEXTRACT(A2, ";pc=([^;]*);"),
"gcd0",
IF(REGEXEXTRACT(A2, ";r1=([^;]*);") = "0",
 REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=exit;"),
 REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=gcd1;")),

"gcd1",
REGEXREPLACE(
  REGEXREPLACE(
    REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=gcd0;"),
    ";r0=([^;]*);",
    CONCATENATE(";r0=", REGEXEXTRACT(A2, ";r1=([^;]*);"), ";")),
  ";r1=([^;]*);",
    CONCATENATE(
      ";r1=",
      MOD(REGEXEXTRACT(A2, ";r0=([^;]*);"), REGEXEXTRACT(A2, ";r1=([^;]*);")),
      ";")),

"exit",
A2,

CONCATENATE("INVALID PC: ", REGEXEXTRACT(A2, ";pc=([^;]*);")))

gcd0 で exit か gcd1 に分岐し、 gcd1 は gcd0 に戻る。 ちなみに、このプログラムは説明のために冗長に書いているが、 gcd0 の中に gcd1 の内容を書けば余分なジャンプを消せる （gcd0 でプログラムカウンタを書き換えずにループできる）。

プログラムカウンタの導入で、 逐次実行、条件分岐、ループの三種の神器がそろったが、 LISPを書く上でまだ欲しいものがある。関数呼び出しだ。

スタックと関数呼び出し

関数呼び出しを実現するためにはスタックが欲しくなる。 スタックはレジスタにカンマ区切りで複数の値を詰め込むことで実現できる。 レジスタ stk をスタックとして使う場合、 スタックに1をpushするには REGEXREPLACE(A2, ";stk=", ";stk=1,") のように書く。 最後にカンマが付いていることに注意。 無駄なカンマが末尾に付くが、コードは単純になる。 スタックからpopして、その値を r0 に入れるには次のように書く。

REGEXREPLACE(
  REGEXREPLACE(A2, ";stk=([^,]*),", ";stk="),
  ";r0=([^;]*);",
  CONCATENATE(";r0=", REGEXEXTRACT(A2, ";stk=([^,]*),"), ";")),

このように常にカンマを付けて文字列の先頭を操作することで 比較的簡単にスタックを実現できる。 ちなみに、先頭ではなく末尾に値を追加するとキューになる。 キューは入出力を実装するのに使える。

スタックができたら関数呼び出しもできる。 プログラムカウンタカウンタを書き換えてジャンプするときに、 戻り先のアドレス（ラベル）をスタックにpushする。

REGEXREPLACE(
  REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=function;"),
  ";stk=", ";stk=return_address,"),

必要ならレジスタもスタックに退避させる。

関数から戻るときはスタックからpopした値をプログラムカウンタに入れる。

IF(REGEXEXTRACT(A2, ";stk=([^;]*);") = "",
 A2,
 REGEXREPLACE(
   REGEXREPLACE(A2, ";pc=([^;]*);",
   CONCATENATE(";pc=", REGEXEXTRACT(A2, ";stk=([^,]*),"), ";")),
   ";stk=([^,]*),", ";stk=")),

これはどの関数でも共通の処理なので、 return という名前をつけて、 ジャンプすればよい。

ためしに再帰的な階乗を実装してみよう。 Common Lispでは次のようなプログラムだ。

(defun fact (n)
  (if (= n 0)
      1
      (* (fact (1- n)) n)))

入力は r0 に入っていて、出力は r1 に書くとしよう。

=SWITCH(REGEXEXTRACT(A2, ";pc=([^;]*);"),
"fact0",
IF(REGEXEXTRACT(A2, ";r0=([^;]*);") = "0",
 REGEXREPLACE(
   REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=return;"),
   ";r1=([^;]*);", ";r1=1;"),
 REGEXREPLACE(
   REGEXREPLACE(
     REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=fact0;"),
     ";r0=([^;]*);",
     CONCATENATE(";r0=", REGEXEXTRACT(A2, ";r0=([^;]*);") - 1, ";")),
  ";stk=", CONCATENATE(";stk=fact1,", REGEXEXTRACT(A2, ";r0=([^;]*);"), ","))),

"fact1",
REGEXREPLACE(
  REGEXREPLACE(
    REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=fact2;"),
    ";stk=([^,]*),", ";stk="),
  ";r0=([^;]*);",
  CONCATENATE(";r0=", REGEXEXTRACT(A2, ";stk=([^,]*),"), ";")),

"fact2",
REGEXREPLACE(
  REGEXREPLACE(A2, ";pc=([^;]*);", ";pc=return;"),
  ";r1=([^;]*);",
  CONCATENATE(
    ";r1=",
    REGEXEXTRACT(A2, ";r1=([^;]*);") * REGEXEXTRACT(A2, ";r0=([^;]*);"),
    ";")),

"return",
IF(REGEXEXTRACT(A2, ";stk=([^;]*);") = "",
 A2,
 REGEXREPLACE(
   REGEXREPLACE(A2, ";pc=([^;]*);",
   CONCATENATE(";pc=", REGEXEXTRACT(A2, ";stk=([^,]*),"), ";")),
   ";stk=([^,]*),", ";stk=")))

fact0 は r0 が0のとき r1 に1を代入して return にジャンプする。 それ以外の場合はスタックに r0 と fact1 をpushして、 r0 をデクリメントしてから fact0 に（再帰的に）ジャンプする。 r0 はデクリメントされるので（初期値が正であれば）いつか0になり、 必ず return にジャンプする。 return はスタックから値を1つpopしてプログラムカウンタにいれる。 fact0 が再帰的に呼ばれた場合はスタックトップには必ず fact1 があるので fact1 にジャンプする。 fact1 はスタックから値を1つpopして r0 に入れる。この値は退避させた元々の r0 だ。 そして fact2 に処理が移り、 r0 と r1 の積を r1 に代入する。 r1 には再帰的に呼んだ fact0 の結果が入っているので、 これで r0 の階乗の結果が求まる。 そして最後に return にジャンプする。 return が繰り返し呼ばれるといずれ stk は空になり、 return は状態を変化させなくなる。 この時点で最終結果が r1 に格納される。

例えば3の階乗は次のようになる。

  A
2 ;pc=fact0;r0=3;r1=0;stk=;
3 ;pc=fact0;r0=2;r1=0;stk=fact1,3,;
4 ;pc=fact0;r0=1;r1=0;stk=fact1,2,fact1,3,;
5 ;pc=fact0;r0=0;r1=0;stk=fact1,1,fact1,2,fact1,3,;
6 ;pc=return;r0=0;r1=1;stk=fact1,1,fact1,2,fact1,3,;
7 ;pc=fact1;r0=0;r1=1;stk=1,fact1,2,fact1,3,;
8 ;pc=fact2;r0=1;r1=1;stk=fact1,2,fact1,3,;
9 ;pc=return;r0=1;r1=1;stk=fact1,2,fact1,3,;
10 ;pc=fact1;r0=1;r1=1;stk=2,fact1,3,;
11 ;pc=fact2;r0=2;r1=1;stk=fact1,3,;
12 ;pc=return;r0=2;r1=2;stk=fact1,3,;
13 ;pc=fact1;r0=2;r1=2;stk=3,;
14 ;pc=fact2;r0=3;r1=2;stk=;
15 ;pc=return;r0=3;r1=6;stk=;

これで自由に関数呼び出しができるようになった。 LISPを作る上で最後の道具はコンスセルを格納するためのヒープだ。

ヒープとコンス

コンスセルを実装するためには、 コンスセルにアドレスを割り振り、 アドレス経由でのアクセスを可能にする必要がある。 これには色々な実装方針が考えられるが、 今回はN個目のコンスセルを作るときに carN と cdrN というレジスタを状態に追加することにする。 例えば1個目のコンスセルは car1 と cdr1 だ。 世界に何個のコンスセルがあるかを記録するために head というレジスタを使う。

CAR部に r0, CDR部に r1 を持つコンセルを作るには以下のようなコードを書く。

CONCATENATE(
  ";car", REGEXEXTRACT(A2, ";head=([^;]*);"), "=",
  REGEXEXTRACT(A2, ";r0=([^;]*);"),
  ";cdr", REGEXEXTRACT(A2, ";head=([^;]*);"), "=",
  REGEXEXTRACT(A2, ";r1=([^;]*);"),
  REGEXREPLACE(
    A2,
    ";head=([^;]*);",
    CONCATENATE(";head=", REGEXEXTRACT(A2, ";head=([^;]*);") + 1, ";")))

r0 にコンスセルのアドレスが入っているときに、 そのCARを取り出すには次のようなコードを書く。

REGEXEXTRACT(
  A2,
  CONCATENATE(";car", REGEXEXTRACT(A2, ";r0=([^;]*);"), "=([^;]*);"))

基本的にはレジスタの読み込みと同じだ。 レジスタの名前を CONCATENATE で動的に作る。 CAR/CDRの書き換えもレジスタの書き換えと同様にできる。

そんなわけで、CAR/CDRをただのレジスタとして実装したので とくに難しいところはない。 ただ一つの問題は、コードがとんでもなく長くなることくらいだろう。

LISPを作る

ここまで道具がそろえばLISPを書くのは簡単だ。 ここまでの説明が読めた人には LISPの実装方法など自明と思われるので説明は省略する。

なぜ手で書くのか

今回の実装はレジスタの読み書き、スタック操作、簡単なヒープ操作といった 単純な処理の組み合わせでできている。 単純な処理の組み合わせということは自動生成しやすいということだ。 例えば小さなLISPのサブセットを作って、 そこからコンパイルしてやるのは簡単だろう。 それでも今回は手で書くことを選んだ。 あらゆる困難がAIで解決するこの令和の時代、 人間が心を込めて手書きしたコードからしか 感じられない温かみこそが大事なのではないだろうか。

2022-10-07