Hatena::ブログ(Diary)

mooz deceives you

(about 'mooz) ; => "See http://mooz.github.com/index-ja.html"

 | 

April 18 (Sun), 2010

JavaScript で Lisp の処理系 (と REPL) を実装してみた

f:id:mooz:20100419001214p:image

MiSPLi: http://mooz.github.com/mispli/

MiSPLi

Emacs に出会ったのが三年前. それから一年程して elisp をいじり始めたので, 僕と Lisp との付き合いはかれこれ二年ほどになる. JavaScript を始めたのが一年前だから, 僕の中では C 言語に次いで付き合いの長い言語だ.

必要にかられたときにちょこちょこと elisp を書いて, 終わったらしばらく別れを告げる. そんな中途半端な付き合いを続けていた三月も終盤, 竹内先生の書かれた「初めての人のための LISP」を読み, その内容に深い感銘を受けた. Lisp を Lisp で実装する, といった章があり, これまで何となしに使っていた Lisp の中身を垣間見ることができたような, そんな気分になっていた.

その時に, 「ひょっとしたら僕にも Lisp の処理系を実装できるんじゃないか?」という思いが芽生えたのかもしれない. およそ一週間程前, 特にすることもないので JavaScript でお遊びのコードを書いていたらどうにもスイッチが入ってしまったようで, 気づけば Lisp の処理系を書き始めている自分がいた. 実生活 (主に食事面) を適度に犠牲にしつつ "しゃにむに" コーディングを続けたところ, 何とかかたちになるものができたので公開してみることにする.

今回実装した処理系 MiSPLi (ミスプリと読む) の特徴は, 次のようなところか.

  • JavaScript で実装
  • 静的スコープ
  • レキシカルクロージャ
  • declare special による, 動的スコープを持った変数の部分的定義
  • マクロ
  • 関数仮引数中の &optional, &rest をサポート
    • &optional のデフォルト引数にも対応
  • setq, quote, let*, cond, progn, time など基本的なスペシャルフォーム
  • cons, car, list など基本的な関数
  • mapcar, some, every などの関数
  • あと, iota
    • FizzBuzz 用とは言わない

特に何らかの規格へ準拠させたということもないけれど, Common Lisp のサブセットと思ってもらって良いと思う.

また, 今回処理系を作るにあたっては REPL (Read-Eval-Print-Loop) の作成にもかなり力を入れてみた. 以前 JavaScriptで読む「ラムダ計算基礎文法最速マスター」 - 貳佰伍拾陸夜日記 を見て "いたく" 感動し, 「格好良いインタフェースだな, やはりインタフェースは重要だな」と思ったことが影響している.

そんなわけで, 今回作成した REPL の特徴を以下に.

  • JavaScript + HTML + CSS で実装
  • リアルタイムな文法チェッカー
  • アニメーション
  • ヒストリ機能
    • 上下キーを入力することで, コード履歴をたどれる
  • 組み込みコマンド
    • 変数, 関数, スペシャルフォーム, マクロなどの一覧表示や, JavaScript のコード実行が可能

中々自分でも気に入っているので, ぜひ他の方々にも触ってもらって, 感想をお聞きしたいところ.

REPL の使い方

まずは MiSPLi の REPL にアクセスする.

適当なコードを打ち込んで Enter キーを押すと, 実行結果が表示される.

f:id:mooz:20100419001250p:image

Lisp はさっぱり, という方は下の Samples から適当なものを選びクリック. 実行結果を眺めて, なるほどなあとでも思っていただければ.

f:id:mooz:20100419001346p:image

おなじみフィボナッチ関数を. (メモ化してないので, あんまり大きな数は計算できない)

f:id:mooz:20100419001345p:image

Tak は処理に中々時間がかかるので注意 (C2D 2.0 Ghz では, Firefox で 6 秒, Google Chrome で 1 秒程). これは, 冒頭で上げた竹内先生の発見された, 竹内関数 というもの.

利用できる関数 / スペシャルフォームなど一覧を見たい場合は REPL Commands のボタンをクリックする.

f:id:mooz:20100419001502p:image

以下のようにして, 一覧がずらっと表示される.

f:id:mooz:20100419001459p:image

構文チェッカ

Lisp のコードを書いていて悩まされるのが, 括弧. Lisper にとってみれば括弧など "存在していない" ようなもの, という話もあるけれど, 僕はまだまだその域に達していない.

Emacs にはカーソル下の括弧と対応するものをハイライト表示してくれる機能があるので, 普段 elisp のコードを書くときは余り気になっていなかった. しかし, そういった機能のない Web ページのテキストエリアでちょこちょこと Lisp のコードを修正し始めると, とたんに括弧の海へ飲み込まれ自分の居場所を見失ってしまう.

そんなわけで, 今回作成した REPL では, 括弧の海で遭難しないために "リアルタイムな構文チェッカ" を設けることにした.

例えば次のようなコードがあったときに,

f:id:mooz:20100419001542p:image

バックスペースキーを押して括弧を一つ削除してみると,

f:id:mooz:20100419001541p:image

構文エラーが検出され, 入力エリアの背景色が赤くなる.

このとても便利な機能, 実現はかなり簡単. ユーザが入力エリアへ文字を入力する度に入力エリアのテキストをパースして, パースエラーが出ているようなら背景色を赤くしている. 昨今の CPU は非常に高速で, また各ブラウザベンダが JavaScript エンジンの高速化を頑張っていることもあり, 速度的な問題は全く感じられなかった.

まとめ

今回 Lisp の処理系を JavaScript で実装し, 処理系における "環境" 部分の実装で色々と試行錯誤をしたため, 非常に勉強になった.

  • 変数のスコープ
    • 動的スコープ (初めはこれを実装)
    • 静的スコープ (最終的にはこちら)
  • 束縛
    • 浅い束縛
    • 深い束縛 (今回はこちらを採用)
  • クロージャの実装
    • クロージャがどういったものか, 実装してみて理解できた
      • 関数内関数が評価された時に, その時点での環境 (変数への参照が格納されたハッシュ表) をコピーして, 関数と一緒にしたものがクロージャ
      • JavaScript におけるプロトタイプチェーンやアクティベーションオブジェクトのイメージとつながった
    • カウンタが動いたときはとにかく感動

一方, Lisp は字句解析がほとんど構文解析のようなものなので, この辺りを実装するのは非常に容易だった.

他の言語だと構文解析の実装にかなりの時間を費やされるので, 先ほど述べた "環境" の辺りにたどり着くまでに力尽きてしまうことも多い. 実際, 僕も昨年 C ライクな言語のインタプリタを作らされたことがあったのだけれど, 構文解析の辺りが非常に面倒で, 苦痛でやっていられなかった. 結局そのときは yacc や bison などのツールを使うことになったのだけれど, 個人的にはそういったツールを使ってプログラミングをしても "全く" わくわくしない. (もちろん Ruby のような本格的なプロダクトになってくると, そんなことは言ってられないのだろうけれど)

というわけで, 僕が言いたいことをまとめておく.

  • 処理系の実装を始めるのなら, その対象として Lisp は良い選択肢の一つ
    • 構文解析に時間を取られない, または yacc の介入を防げる
    • 環境の実装に集中できる
    • Lisp はわくわくする
  • 実装に用いる言語として JavaScript は良い選択肢の一つ
    • どこでも動く
    • コンパイル作業が不要
    • HTML と組み合わせると楽しい
    • オブジェクト (ハッシュ) が柔軟でやりやすい
    • 総括すると, やわらかい
      • 気張らずにプログラミングできる

去年, C 言語で C 言語のサブセットを書いた時と比べると, 格段に楽しかった. Lisp のコードが動いたときは, 本当に感動した. REPL でみょーんみょーんとアニメーションさせた時は, 一人部屋の中でにんまりとしてしまった. この一週間, 退屈知らずだった.

というわけで皆さん, プログラミング言語処理の教材として, Lisp + JavaScript はいかがでしょうか?

sodexsodex 2010/04/24 18:50 REPLのUIがすごいかっこいいですね

moozmooz 2010/04/24 21:50 >sodex さん

そう言って頂けると大変ありがたいです. 今後も精進します.

yamayama 2010/09/10 19:38 MiSPLiをiPadにいれて動かしてみました。
PCでwebarchive保存して、Goodreaderで見たところ、オフラインでも動かすことができました。(当たり前かもしれませんが…)iOSでLispインタプリタが動くなんて…素晴らしいです!
自分はJavaScriptを全く知らなかったのですが、この記事を見てすごく興味がわきました。
素晴らしい記事をありがとうございます。

moozmooz 2010/09/10 20:51 >yama さん

なんと, iPad で動かされたのですか. 感動です.
JavaScript で書くと本当に色々な環境で動きますので, 書きがいがありますね. Scheme の影響も強く, 言語としてもシンプルで良くできていると思いますので, ぜひ始められてみてはどうでしょうか.

inuinu 2013/07/27 15:10 eq(l)が動かないようです。
> (eq nil nil)
eq : ReferenceError: a is not defined

moozmooz 2013/07/28 01:15 >inuさん

報告ありがとうございます。修正しました。

noblegardennoblegarden 2014/05/20 18:12 maxima がJavaScript で動くかもしれないということですね?android 版のlispでmaximaを動かすアプリもあることから、ひょっとしたら実現可能なのかと思ったりしました。

moozmooz 2014/05/22 21:18 >noblegardenさん

>android 版のlispでmaximaを動かすアプリもある

おお、そんなものがあるのですね。頑張って JavaScript で Lisp 処理系を実装すれば、不可能ではないかもしれないですね。

http://gnuplot.respawned.com/ なんてものもあるので Emscripten などをつかった Maxima の JavaScript port なども今後出てくるかもしれないですねぇ。

トラックバック - http://d.hatena.ne.jp/mooz/20100418/p1
 |