Googleスプレッドシートの名前付き関数で型なしラムダ計算の最左最外簡約

以前、「Googleスプレッドシートの名前付き関数でLISPインタプリタを作った」という記事を読んでスゲーと思った。
触発されてラムダ計算の簡約器を作ってみた。

作っただけで特に使いどころもないので、ネットの海に放流して供養しておく。
下記のリンクにアクセスすれば見れるはず。

型なしラムダ計算の最左最外簡約

ラムダ計算の簡約器で面倒な箇所

ラムダ計算の簡約器の実装で面倒なのは、変数が衝突したときにα変換しないといけない所だろうか。
衝突を気にしなくてもよい状況であれば、β基を探して束縛変数を引数で置換するだけで済む。
とても簡単だ。

ところが衝突を気にする場合、衝突していないか調べるために自由変数を取り出す必要がある。
自由変数を調べて衝突していたら、衝突しない新たな変数を作らなければならない。
新たな変数を作ったら、その新しい変数でα変換することで、ようやく置換に手が付けられる。
この一連の流れが個人的には面倒だ。

裏を返せば、それ以外は気を付けるところもなく、ラムダ計算の定義通りに素直に処理すればいい。
だから、簡約器の素朴な実装は難しくない。

Googleスプレッドシートで苦労する箇所

簡約器の実装が難しくなくとも、使う道具に制限があれば、本質とは無関係なところで困難が立ちはだかる。
Googleスプレッドシートの関数を使うときに、最も苦労するのはデータ構造だろう。
数値や文字列はあるが、データの集まりを扱う手段が少ない。

一応、配列数式で配列は扱える。
ただ、配列数式をどんなに入れ子にしても、N次元配列にはならず、二次元配列に平坦化される。
スプレッドシートだから二次元配列になるのは理にかなっているが、データ構造としては使いづらい。

また、LAMBDA関数でチャーチエンコーディングすれば、適当なデータ構造は表現できる。
しかし、セルにLAMBDA関数のまま書き出すことはできない。
「LAMBDA 関数の後には実際の値を含む呼び出しを続けて指定する必要があります」といったエラーが表示される。
計算の中であれば扱いやすいが、セルに書き出せないとなると、やはり使いづらい。

そんなこんなで、結局は文字列でデータを扱うハメになる。
データ構造を表す工夫した文字列を考えるのも面倒なので、今回の実装ではラムダ式に明示的に括弧を付けることにした。
明示的に括弧が付いている場合、開き括弧 "(" に対応する閉じ括弧 ")" の位置を特定すれば、括弧内の括弧といった入れ子構造の深いデータが取り出せる。

つまり、明示的に括弧を付けたラムダ式は、それ自体が十分なデータ構造として扱える。
後はこのデータ構造をやり繰りしながら、簡約器を素朴に実装すればOKだ。

触発元

すげー

GoogleスプレッドシートでLISPインタプリタを作ったので誰か遊んでください https://t.co/l7yWY3npaj

— zick (@zick_minoh) September 30, 2022

Googleスプレッドシートの名前付き関数でLISPインタプリタを作った