🛠

シェルスクリプトでLISP処理系を作ってみた

2020/11/03に公開

shell

【2022-01-22追記】簡易版のLISP処理系をPOSIX準拠シェル（＋sed）で作成する様子の動画を作成してみました．
https://youtu.be/jZKcLPcbtr4

この記事は，筆者がシェルスクリプトで簡易実装している純LISP処理系の開発についてまとめたものです．『PureLISP.sh』と呼んでおり，次のGitHubリポジトリでパブリックドメインとして開発・公開しています．

基本的には，上記リポジトリのREADMEの内容を記事として膨らませたような構成です．このことから，今回の記事内容に関するコメント等だけでなく，『PureLISP.sh』そのものへの御意見等（GitHubのIssues/Forkを含む）も受け付けます．ただし，開発の経緯・目的から，次の3点は維持します．

最低限必要な要素で構成されたLISP処理系を志向すること
POSIX準拠のシェルスクリプトで実装すること
パブリックドメインにて開発・公開すること

なお，他のプログラミング言語による簡易LISP処理系実装も試しています．他サイト公開記事としてまとめたため直接的な言及は避けますが，当方のユーザ名である『ytaki0801』と『簡易LISP処理系』で検索すると出てくると思います．

開発の経緯・目的

筆者はとある教育機関の教員で，ここ二十年ほど毎年，学生にLISP系やその他の言語（Python，Prolog，C/C++など）を用いたプログラミングのごく基本的なことを教えています．最近は学生もノートPCを所有しているので，各処理系をインストールさせて講義・演習を実施してきました．ところが，今年（2020年）のコロナ禍の影響のため，前期初日から遠隔授業の体制となった結果，各学生の自宅において

処理系のインストールミスが多発しました．

もちろん，動画キャプチャや資料などでインストール手順や初期設定を細かく述べたり，ビデオ会議システムでインストールデモを行ったりして，サポートの限りを尽くしたのですが，『せんせー，うごきません』のメッセージばかりが並ぶ結果となりました．理由のほとんどがコマンドやプログラムコードのスペルミスにどうしても気づかないという，プログラミング教育あるあるですが，他にも，デスクトップフォルダがネットワーク共有されていることを知らなかったことに伴うトラブルや，ペアレンタルロックの表示をエラーメッセージと思っていたなど，直接対応ではあまり見られない状況もありました．

そこで，基本的な機能だけならば実装が簡単なLISP処理系については，教育用に必要最低限な機能を備えたものを独自に開発・配布することで，様々なコンピュータ環境で可能な限りインストール作業が必要ないようにすることを考えました．このような実装については，Peter Novig氏のLispyあたりが有名ですが，筆者が様々なプログラミング言語でLISP評価器やコンスセル操作，S式入出力の実装を試した結果，POSIX仕様のシェルスクリプトが今回の目的に最も適していると判断し，LISP体験用として簡単なREPLを付けて開発・公開するに至りました．

PureLISP.shの利用方法と言語仕様

現時点で500行程度のひとつのシェルスクリプトとなっていますので，リポジトリのファイルをWebブラウザで表示してテキストファイルにコピペしても良いですし，Gitでcloneしても良いかと思います．

次は，そのようにして取得したシェルスクリプト『PureLISP.sh』を，Windowsで利用可能なbusybox-w32のシェルで実行している例です．S>はプロンプトです．なお，ひとつのまとまったLISP記述を実行（評価）するには，空行を一行入れる必要があることに注意して下さい．exitで処理系を終了できます．

C:\Users\TAKIZAWA Yozo\busybox>busybox.exe sh PureLISP.sh
S> (def reduce
     (lambda (f L i)
       (cond ((eq L nil) i)
             (t (f (car L) (reduce f (cdr L) i))))))

reduce
S> (reduce cons '(a b c) '(d e f g))

(a b c d e f g)
S> (def rappend (lambda (x y) (reduce cons x y)))

rappend
S> (reduce rappend '((a b) (c d e) (f) (g h i)) ())

(a b c d e f g h i)
S> exit

C:\Users\TAKIZAWA Yozo\busybox>

また，シェルを利用していることもあり，あらかじめLISPプログラムをテキストファイルに記述しておき，リダイレクトで読み込ませることもできます．プロンプトを表示しない-snlまたは-slオプションを併用すると結果表示が見やすくなります．ただし，テキストファイルに記述する際にも，ひとつのまとまったLISP記述の後には空行を一行入れる必要があることに注意して下さい．

C:\Users\TAKIZAWA Yozo\busybox>busybox.exe sh
~/busybox $ cat examples/closure-stream.plsh
(def make-linear
  (lambda (x)
    (cons x (lambda () (make-linear (cons 'n x))))))

(def s (make-linear nil))

(car s)

(car ((cdr s)))

(car ((cdr ((cdr s)))))

(car ((cdr ((cdr ((cdr s)))))))

(car ((cdr ((cdr ((cdr ((cdr s)))))))))

(car ((cdr ((cdr ((cdr ((cdr ((cdr s)))))))))))

exit

~/busybox $ sh PureLISP.sh -snl < examples/closure-stream.plsh
make-linear
s
()
(n)
(n n)
(n n n)
(n n n n)
(n n n n n)
~/busybox $ exit

C:\Users\TAKIZAWA Yozo\busybox>

以上の利用方法は，今後の開発の進捗によって変更となる可能性があります．

LISPの仕様については，最低限必要な要素で構成された純LISPに相当し，今回の処理系の名称の由来ともなっています．ただし，純LISPという言葉に明確な定義はなく，LISP評価器自身を（超循環評価器として）自己実装できるものに限定したり，参照用のモデル処理系として簡単な数値演算を含んでいたりするなど，割とまちまちです．

そこで，当方も独自の構成とすることとし，現時点では次のような仕様となっています．

基本関数：cons car cdr atom eq
基本構文：quote cond lambda（名前束縛やスコープはSchemeと同じ）
独自構文：def（グローバル環境に名前束縛するため）
独自構文：macro（マクロによるメタプログラミングを行いやすくするため）
独自関数：length（リストを数として扱いやすくするため）

また，処理系の入出力まわりは，現時点では次のような構成です．

ひとつの文字列をひとつのまとまったS式として処理するよう簡易実装されたS式入力
次のコマンドやオプションを扱う簡易REPL（Read-Eval-Print Loop）およびS式出力
- exitコマンド，;が冒頭にあるS式記述を無視する簡易コメント機能
- リダイレクト入力や初期設定ファイルを想定したオプション
  - なし：プロンプトを表示，カレントディレクトリのinit.plsh読み込みあり
  - -snlまたは-s：プロンプトなし，init.plsh読み込みなし
  - -sl：プロンプトなし，init.plsh読み込みあり
  - -nlプロンプトを表示，init.plsh読み込みなし

シェルスクリプトによる実装

次は，シェルスクリプトで実装するにあたっての技術的な事柄を羅列したものです．

コンスセル操作機能の実装

言語処理系実装といえば通常，字句解析・構文解析（パーサ）開発から始めます．ですが，LISPの場合はプログラム自体がLISPの基本データ構造表現であるS式であり，基本処理であるコンスセル操作（cons，car，cdr）を用いて構文木を生成できた方が実装が楽になります．加えて，パーサを実装する前に，実装言語においてLISPプログラムと同等の基本リスト処理を行うことができるようになるため，既に存在している様々な超循環評価器（LISPでLISPを実装したもの）を参照することで，LISP処理本体である評価器evalも実装しやすくなります．

コンスセルとは，下図の構造をもつシンプルなデータ構造ですが，CAR部，CDR部と呼ばれるそれぞれのセルが，コンスセル構造か，コンスセル構造ではないアトムと呼ばれる基本データのいずれかを参照できる必要があります．

下図は，S式によるリスト構造(a (hoge 10) (hage 20))をコンスセル構造で示した例です．consはCAR部とCDR部の参照情報を用いてコンスセルを生成，carとcdrはそれぞれCAR部，CDR部の参照情報を取り出して返す基本関数となります．
リスト構造の例
PythonやRubyなど，ネスト可能なリスト構造処理をあらかじめ備えていえれば実装は簡単ですが，言語によっては，特定の基本データの一次元有限配列しか扱えなかったり，複雑な型定義を必要としたりするなどで，困難を極めることになります．POSIX仕様のシェルスクリプトに至っては，そもそも配列の類さえありません．

そこで，ひとつのコンスセルをCAR＋連番およびCDR＋連番の大域変数として実現し，その連番管理も大域変数CNUMで行うことにしました．consによってコンスセルをひとつ生成するたびにCNUMの値を増やし，シェルのevalによって，CAR$CNUMやCDR$CNUMにアトムとしての文字列か，または，特定のコンスセルを示す連番情報をセットするようにします．carとcdrは，指定したコンスセルの連番情報を基に，CAR$CNUMやCDR$CNUMから同じくevalで参照情報を取り出します．

なお，cons，car，cdrのいずれの処理も関数として実装していますが，サブシェル呼び出しによる実行は大域変数の変更ができず，処理も遅くなることから，各関数の戻り値もCONSR，CAAR，CDRRといった大域変数にセットすることで返す，通常の関数呼び出しを行っています．

大域変数を用いたスタック処理

LISP評価器側のevalを始め，処理系の様々な箇所で再帰処理が発生しますが，そのままですと，上記の大域変数による戻り値管理の関係で，自身を呼び出す処理や同一関数の連続処理などによって，処理途中の戻り値が上書きされてしまいます．たとえば，LISP評価器evalによる次のLISPプログラムの処理を考えます．

((lambda (x y) (cons x (cons y nil))) (car '(a b c)) (car '(x y z)))

このプログラムは，関数部であるラムダ式と，ふたつの引数で構成されています．これを，関数適用部applyに渡す前に，それぞれの部分を自分自身であるevalを再帰呼び出しで処理することになります．具体的には次のようになります．

評価器evalで各要素を再帰的に評価
(lambda (x y) (cons x (cons y nil))) ⇒ 独自の名前空間をもつ手続き処理
(car '(a b c)) ⇒ a
(car '(x y z)) ⇒ x
↓
関数適用部applyで(手続き処理 a x)を処理
(cons a (cons x nil)) ⇒ (a x)

ここで，(手続き処理 a x)を生成するまでに何度も自身であるevalを呼び出すことになり，生成された手続き処理や(car '(a b c))の関数適用結果であるaなどが(car '(x y z))の結果であるxによって上書きされてしまいます．

そこで，再帰処理対応のため，コンスセル生成と同じく，大域変数による疑似的な配列処理を用いたスタック処理を実装し，必要な箇所にPUSH/POP処理を挿入することにしました．実装といっても込み入ったものではなく，そのまま抜粋すると次の通りとなります．

# Stack implementation for recursive calls

stackpush () {
  eval STACK$STACKNUM=$1
  STACKNUM=$((STACKNUM+1))
}

stackpop ()
{
  STACKNUM=$((STACKNUM-1))
  eval STACKPOPR="\$STACK$STACKNUM"
}

STACKNUM=0

このスタック処理を，次のように挿入していくことになります．変数の値をPUSH/POPする順番に気をつけます．

評価器evalで各要素を再帰的に評価
(lambda (x y) (cons x (cons y nil))) ⇒ 独自の名前空間をもつ手続き処理
手続き処理をPUSH
(car '(a b c)) ⇒ a
aをPUSH
(car '(x y z)) ⇒ x
aをPOP
手続き処理をPOP
↓
関数適用部applyで(手続き処理 a x)を処理
(cons a (cons x nil)) ⇒ (a x)

なお，当初はこの問題を解決する方法として，あらゆる関数処理をサブシェル呼び出しとする一方，『ひとつのコンスセルにつきひとつのテキストファイルを生成』していました．こうすれば，サブシェル呼び出し時に関数処理の途中内容が自動的にシェル内部でスタックに出し入れされ，テキストファイルとしてのコンスセルはどの関数からも参照できます．ですが，簡単なLISP記述だけでも膨大なコンスセルファイルが生成される上に，サブシェル呼び出しとテキストファイルの生成・参照によって，処理時間も膨大なものとなりました．

文字列のパターンマッチング処理

コンスセル操作関数やS式出力を含む内部処理の実装が済んだ後，ようやくS式入力部の実装に移ります．ここでは，LISP構文に対応した入力処理は行わず，ひとつのまとまったS式を文字列として受け取り，それを，空白や( ) 'といった構文を示す記号によって分割し，同じく大域変数による疑似配列TOKEN$TNUMに格納するといった流れで字句解析を行っています．

この簡易的な方法は，Peter Novig氏のLispy初版で見られ，rlwrapと連動させた入力も可能となります．ですが，Pythonでは標準で利用できる splitとreplaceによって2行程度で済む字句解析が，POSIX仕様のシェルスクリプトではそのような機能がないため簡単にはいきません．split相当は引数の空白区切りによる再帰処理によって比較的楽に実装できましたが，replace相当については，当初はsedとtrを用いていました．

そうしたところ，POSIX仕様でも文字列置換を行うことができる関数定義replace_all_posixのコードを提供いただけました．パブリックドメインでの使用の許可も頂いていますが，提供コードであることを示すため，ここにそのまま抜粋します．replace_all_posixで検索すれば提供元もすぐに見つかるかと思います．

replace_all_posix() {
  set -- "$1" "$2" "$3" "$4" ""
  until [ _"$2" = _"${2#*"$3"}" ] && eval "$1=\$5\$2"; do
    set -- "$1" "${2#*"$3"}" "$3" "$4" "$5${2%%"$3"*}$4"
  done
}

なお，このような文字列のパターンマッチング処理は，関数の引数処理を中心に他でも使用しており，直接的な文字列処理機能が少ないシェルスクリプトでの強力な実装手段となっています．

備考

記事に関する補足

~~evalをマクロ機能に置き換える可能性あり．LISPによるメタプログラミングの真髄だし．ただ，純LISP的な必要最低限の機能かというと…．~~ 置き換えました．
~~簡単な整数演算くらいは導入する可能性あり．リスト処理を用いた数値演算は実行速度が悲しいどころかセグフォ吐く時もあってつらたん．~~ 純LISP的にはこちらは不要と判断．
空行一行必須のS式入力も改善したいところだけど，rlwrap併用不可が予想されるのが辛いところ．
いずれにしても，実用性を求めるならGauche/Guile/SBCL/Emacsなどの本格実装を使えばいいよねという話が．LISP体験用の簡易実装だしなあ．うーん．
評価器については，当初はJohn McCarthy氏の原初評価器（と，それをCommon Lispで実装したPaul Graham氏のjmc.lisp）を参照していたのだけれど，のちにSICP 4.1の評価器参照へと変更．レキシカルスコープ＆クロージャ対応とするには，構文処理と関数適用にきちんと分けなければならなくて…．

変更履歴

2022-01-22：作成動画に関する記述を冒頭に追記
2020-11-04：evalを削除しmacroに差し替え
2020-11-03：実装に関する解説を追加・整理
2020-11-03：初版公開