JavaScriptでWebブラウザ版LISP処理系を作ってみた

公開:2020/11/05
更新:2020/11/06
4 min読了の目安(約4000字TECH技術記事

この記事は,拙作記事『シェルスクリプトでLISP処理系を作ってみた』の姉妹版というか追加補足版です. 言語仕様はほぼそのままに本体部分をJavaScriptで書き直し,REPL部分をHTMLの入力フォームと実行ボタンで簡易実装しています.下記URLから現バージョンの処理系の動作確認が可能です.とりあえず『PureLISP.js』と呼んでいます.

https://ytaki0801.github.io/PureLISP.html

シェルスクリプト版同様,ひとつのまとまったLISP記述を実行(評価)するには空行を一行入れる必要があることに注意して下さい.『eval』ボタンを押すと,そのすぐ下に最後のLISP記述の評価結果が表示されます.

【動作確認ブラウザ】Chrome 86 (Windows/Android),Edge 85,Safari 14 (iOS)
(下記画像はiPod touchのSafariとWindows 10のEdge)
PureLISP.js_iPodtouch
PureLISP.js_Windows10Edge

開発の経緯・目的

様々なコンピュータ環境にて,可能な限りインストール作業が必要ないようにすることを目的として開発した体験用LISP処理系が先の『PureLISP.sh』であり,AndroidやmacOSを含むUNIX系OSの標準シェルはもちろん,WindowsにおいてもBusyBoxやGit Bashなどで手軽に利用できることを確認しました.

が,唯一どうにも厳しいのがiOS/iPadOSで,少なくとも,POSIX仕様のシェルが移植されている様子がありません.そこで,シェル環境ほど手軽ではないものの,最近のJavaScriptの仕様に対応したWebブラウザ上で利用できるよう移植を行ったのが今回の処理系です.なお,本体の開発はNode.js (v10.21.0)で行っています.

ソースコード

本体である『PureLISP.js』は,次のGitHub Pagesのリポジトリより参照可能です.ネスト可能なリスト構造処理をあらかじめ備えていることもあって,JavaScriptによるLISP処理系の実装は比較的簡単です.200行弱/4.5KB前後と,小規模なコードとなっています.

https://github.com/ytaki0801/ytaki0801.github.io/blob/master/PureLISP.js

Node.jsでも動かすことはできますが,REPLがないため,次のように関数s_repへの文字列引数としてLISPプログラムを記述・実行することになります.

$ nodejs
> .load PureLISP.js
(読み込み時の表示は省略)
> s_rep("(def f (lambda (x) (cdr x)))")
'f'
> s_rep("(f '(a b c))")
'(b c)'
> s_rep("(car (f '(a b c)))")
'b'

HTMLによる簡易REPLは,先の動作確認ページのソースコードを表示しても良いですが,同じくGitHub Pagesのリポジトリでも参照することができます.コードの多くは,実際には埋め込みのJavaScript関数が占めています.

https://github.com/ytaki0801/ytaki0801.github.io/blob/master/PureLISP.html

構成としてはとても単純で,TEXTAREA内のテキストを取得し,改行を認識して行単位の文字列配列に変換,空行のたびにそれまでの行を文字列結合して上記関数s_repに渡す,ということを,文字列配列がなくなるまで繰り返しています.中核となるのは,次の埋め込みコードです.

function rep() {
  var estrings = document.form1.estrings.value
  estrings = estrings.replace(/\r\n|\r/g, "\n")
  estrings = estrings.split('\n');
  for (var i = 0, eoutput = ''; i < estrings.length; i++) {
    if (estrings[i] != '') {
      eoutput = eoutput + estrings[i];
    } else {
      document.getElementById("span1").textContent = s_rep(eoutput);
      eoutput = '';
    }
  }
}

関数処理や値を大域的に保持するグローバル環境変数GENVが本体PureLISP.js読み込み時に初期化されますので,ページ再読み込み等を行わなければ,グローバル環境は維持されます.起動時サンプルのように,まとまったLISPコード群をあらかじめメモ帳アプリの類で作成してTEXTAREA内にコピペ&evalしても良いのですが,都度入力&evalでも問題ないかと思います.ただし,上記のような入力処理を行っていることから,(くどいようですが)ひとつのまとまったLISP記述の後に空行を一行入れる必要があります.

LISPの言語仕様

元記事のシェルスクリプト版と全く同じ仕様となるよう作りましたが,念のため再掲しておきます.LISP体験用ということもあり,基本的に『純LISP』を志向しています.

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

HTML埋め込みのサンプル記述の概要は次の通りです.

ラムダ式の仮引数がアトムの場合は引数を全てリスト化することを利用した,リスト作成関数の定義
(def list (lambda x x))

マクロを用いたCommonLispスタイルの関数定義専用構文の定義
(def defun
  (macro (name args body)
    (list 'def name
          (list 'lambda args body))))

ふたつのリストに限定した要素結合関数の定義
(defun append2 (a b)
  (cond ((eq a nil) b)
        (t (cons (car a)
           (append2 (cdr a) b)))))

リストの要素数を自然数とみなした,末尾再帰型フィボナッチ数計算関数の定義
(defun fib (n f1 f2)
  (cond ((eq n '()) f1)
        (t (fib (cdr n)
           f2
           (append2 f1 f2)))))

10個の要素をもったリストの定義
(def 10 '(p p p p p p p p p p))

0の定義
(def 0 nil)

1の定義
(def 1 '(p))

10番目(0番目から数えて)のフィボナッチ数を求め,独自関数`length`を用いて結果のリストの要素数を表示
(length (fib 10 0 1))

備考

更新履歴

  • 2020-11-06:LISPの言語仕様とサンプル記述の概要を追加
  • 2020-11-06:簡易REPLに関する説明を追加
  • 2020-11-06:初版公開