JavaScriptにSchemeを実装する

この記事は完成していません
更にコードに誤りがあったりして修正されていなかったりするので、一度整理されるまで落とすかもしれません

この記事の内容

プログラマが美しい言語を求めて最終的にたどり着く言語、LISP。

プログラミング言語を作るということは、難しいと思われがちですが、実際のところ読み取った文字列を解釈するプログラムを作成するだけで独自の言語を作ることができます。

ただし、プログラミング言語として利便性を実用レベルまで持っていくのは通常、容易ではありません。しかし、Schemeであれば比較的実装が簡単かつ高度な言語を作ることができます。

Schemeはシンプルさとパワフルさの両方を兼ね備えたLISP方言の言語であり、ミニマルな仕様から世界で最も実装される言語です。今回はそんなSchemeをJavaScriptに実装します！

最終的な目標は、ブラウザにCUIを表示して対話形式でSchemeを動作させることです。

この記事は、JavaScriptにSchemeを実装する過程と苦労、過去のエピソードや、発見したことをまとめたもので「LISPの世界をもっと知りたい！」「Schemeを実装してみたい！」と考えている読者様に少しでも役に立てばいいなという気持ちから作成されました。

何故Schemeなのか？

LISPは世界で2番目に作られた言語です。僕はずっと、この神の言語と呼ばれるLISPを作りたいという好奇心がありました。それは、かつてCommon LISPの本を買ってActionScriptにLISPの実装を試みたほどです。

その時はLISPのことをあまりよく理解しておらず、Schemeと呼ばれるLISP方言があるなんてことは知りもしませんでした。

Schemeは、Schemeコミュニティ内のワーキンググループによって定められた様々なバージョンの仕様があって、それはRnRSと呼ばれています。中でもR5RSは小さな言語仕様に対してのこだわりが見られ、仕様書は50ページにも満たないため、世界で最も実装される言語となっています。

ちなみにWikipediaでは「Schemeの言語仕様はIEEEによって公式に定められている」と記載がありまして、これを参考に同じ主張をさせていただいたのですが、これは誤りであると@SaitoAtsushi様からコメントをいただき、修正させていただきました！

@SaitoAtsushi様曰く、IEEEのSchemeは1991年に制定されて以来、更新されておらず、Schemeユーザの間ではIEEEが定めた仕様はほとんど無視されているとのことです。

また、IEEEの他に規格のあるLISPとしては、他にもISOによって規格化されたISLispというものが存在するようです。こちらは@asciian様に教えていただきました！

Schemeの仕様を満たすということは、既存のSchemeのコードを動作させることができることを意味します。その重要性は捨てきれません。

僕は数ある言語の中からLISPを選び、その中でもシンプルで知名度があり、最もよく実装されているSchemeを作成することにしました。

すでに存在するJavaScriptで動くLISPたち

独自の処理系を作ることは楽しいですが、すでに存在するJavaScriptで動作するLISP処理系はいったいどれくらいあるのでしょう？

良いものを作るためには、まず調査から始めることが鉄則です。

目標は「ブラウザにCUIを表示して対話形式でSchemeを動作させる」ことなので、このことを意識しながら似たようなものがどのくらい存在するのか調べてみました。

また、個人的に気になった独特な処理系もピックアップさせていただいてます！

名前	方言	特徴
BiwaScheme	Scheme	サイクリングとピアノが趣味の83年生まれの日本人、yharaさんが実装したScheme。人気があって海外や国内で実際に使われているのを見かける。現時点でダウンロード可能な最新版のbiwascheme-0.6.8.jsのコードを眺めてみると内部にjQueryが埋め込まれていて個人的に残念に思った（node版にはjQueryは無い模様）現在の開発状況は不明だが、R6RS準拠を目指して開発を進められているようだ。本人のサイトはテキストブラウザでも見れそうなシンプルな構成をしててSchemerらしさが出ている。
ClojureScript	Clojure	Java仮想マシンと.NET共通ランタイムで動作するLISP方言Clojure言語を使ってJSに変換可能なトランスパイラ。LISPは実用されない言語として有名だがClojureは唯一実用LISP方言言語としてのポジションを確立していると言える言えるかもしれない。
ClojureJS	Clojure	ブラウザとnodeで動作するClojure。ClojureScriptのインタプリタ版と考えられる。公式サイトは存在しないようだがデモページが存在することに好感が持てた。Clojureで定義されている関数は一通り利用できるようだが、2012年から開発が止まっている。
Chicken Scheme	Scheme	R5RSにほぼ準拠したScheme。標準を超える多くの拡張を持っているライセンスフリーな処理系。実用的でポータブルなScheme処理系を目指しておりSchemeプログラムはC言語にコンパイルされた後、機械語に変換されるため高速に動作する。JavaScript上でコンパイルすることは不可能だが、人気があり特徴的だったので紹介。かつてはCPSCMというJSの上で動作するChikcken Schemeと相性の良い処理系もあったらしいが探しても見つからなかった。公式サイトのドメインがcall-cc.orgなのがとってもチキンである。
Lisp Front-End to JavaScript Engine	Common Lisp	LISPコードを一度JavaScriptに変換できるトランスパイラライクなCommon Lisp。lessみたいにクライアントサイドで動的に動かせるのもイカしてる。ここまで作ったんだからGitHubなどで公開してnpm installできるようにして欲しいところ。ちゃんとした名前もないので作者の名前のDmitry Nizhegorodovをとって「Dmitry Nizhegorodov's Lisp System」なんて呼ばれてた。色々惜しい。
PicoLisp	独自	関数がリストそのものという一見よくわからない独自方言のLISP。C言語とJavaのライブラリを使うことができ、apt-getで気軽にインストールできる。+OnClickのドキュメントを見た感じ、JavaScript上でも動作するように思われたがサーバサイドでjsを吐き出すコードを書けるといった感じで残念ならがクライアントサイドで動くインタプリタではない様子。個性が強かったので紹介。Canvasを使ったデモがあるところからもJavaScriptとの相性は良いみたいだ。国内での人気はほぼゼロに等しく開発は2011年から止まっている。
GoldenScheme	Scheme	yukobaさんが作ったJavaScriptで動くマイクロScheme。日本のIT業界を変えるカンファレンス 1000speakersの二次会でSICP読書会の話で盛り上がったのち、ノリと勢いで三次会兼Scheme実装大会が行われ、5時間で作ったらしい。実用性は無いが、Scheme実装に役立つシンプルなJavaScriptのコードが閲覧できる。
JSCL	Common Lisp	オランダのdavazpさんが作ったCommon LispをJavaScriptに変換するコンパイラ。GitHubのスターもそこそこ集めていて今後の期待が高まる。残念ながらブラウザでコンパイルすることはできない様子。比較的最近作られていて、アイコンが可愛い。
newLISP	独自	ドット対が存在しないため(cons 'x 'y)が(x y)となる独特なLISP。それだけで毛嫌いされそうだが根強い人気がありmacOS、Windows、Linux、やUnix系OSで動作し、専用のエディタも存在するという太っ腹。コンパイルして実行ファイルが作れるその気軽さに惚れるユーザも多い。大胆なアプローチにより実装はよりシンプルになり、処理系は200KBと軽量で、ロードも素早くメモリ消費もわずかで動作するらしい。ちなみにnewって付いてるけどCommon Lispが登場するより前に登場している。にもかかわらず、現時点で最新版の10.7.3は2017年10月9日にリリースされており長期的に開発が続いている様子。フォーラムとかもある。日本語のサイトで情報が一番多いのはココかも。日本語マニュアルはココ。
Fargo	Scheme	R5RSに準拠したJavaScriptで動作するScheme。公式サイトにアクセスするといきなり対話形式のSchemeが立ち上がるがSafariでは動作しなかった。自分がこれから作成するものに一番近い存在と思われる。2013年から開発が止まっていて実用レベルかどうかは怪しい。ソースが参考になるかも！とか思ったけどネストすげぇ...
Javathcript	独自	う〜ん、このネーミングセンス。紹介するべきか否か迷ったがもしかしたらソースが参考になるかもしれないと思ったので念のため紹介。もし会話の中でこの言語が出ることがあったら、ちゃんと舌を噛んで発音しよう。
jsScheme	Scheme	R5RSの仕様を満たしており、かつシンプルに実装された多分一番参考になるやつ。コードがHTMLに直接書かれていて最後まで頑張れ！感がすごい。ある程度出来上がったらここで使われてるSchemeライブラリを突っ込んで問題なく動作するかチェックしようかなと思っている。
Iris	ISLisp	ISOによって規格化されたISLispの処理系のひとつ。ISLispの仕様ではマクロは実行準備時に展開され、自分で定義した関数によるマクロの展開は行うことが出来ないという欠点があると、取り消し線の文のような誤解がよくなされる。しかし、実際はIrisも含めマクロ展開時にも自分で定義した関数を使うことは可能。なお、ISLispは日本人の開発者の割合が高く、オブジェクト指向ILOSが規格に含まれており、例外処理が充実していることが特徴である。日本人の@asciianさんの手によって作られた。Go言語で開発されておりGopherJSによってブラウザで動作する貴重なISLispで、現在はブラウザ拡張を作成している模様。開発者本人からコメント欄にてご指摘をいただいたきました！ちなみに、asciianさんのホームページは縦文字を使っていてシンプルで可愛い。
mal	独自	MALという独自LISPを実装するプロジェクト。現時点で70を超える言語の上に実装されている。もちろんJavaScriptも含まれており、色々と参考にできそう。実装一覧を見るとPostgreSQLも含まれていて、ちょっと何言ってるのかよくわかんないっす。また追加で紹介いただいたソースコードが932バイトのminiMALはJSONをそのまま評価できるという好奇心をそそる。
JScreme	scheme	Mostly Softwareのブログを運営しているプログラマが作成したJavaScriptで動くSchemeインタプリタ。新しいプログラミング言語を学ぶ時は必ずSchemeを実装するらしい。そしてJSchemeもその一つ。FirefoxやChromeで動作するがテストはちゃんと行ってないと言うことで実用に欠ける。しかしブログによくまとまっているため実装の際の参考になりそう。
JSGEN	Common Lisp	JSGENはCommon Lispで書かれたWebサーバであるAllegroServe(Aserve) を拡張したもので、JavaScriptプログラムをS式の構文で書くことができる。ソースマップが出力されないためJSで発生したエラーに対応する箇所を手動で探さなければならないとのこと。
LispScript	Common Lisp	現時点で基本的な算術関数、defun、IF、マクロ、LETをサポートしてたCLISPで動作するJSトランスパイラ。JavaScriptは素晴らしいスクリプト言語であるが、マクロとLETの欠落に悩まされていた開発者がそれらの問題を解決するために開発したとのこと。
LispyScript	独自	Javascriptの問題はマクロが使えないことにあり、マクロはJavascriptのような言語では実現できない。LispyScriptは、JavaScriptをツリー構造で記述できるようにしたトランスパイラで、すべてのJavascript関数、オブジェクト、リテラルはLispyScriptで使用できる。結構好感が持てたけど開発は3年前から止まってるっぽい。

GaucheとかGuileとか、それこそEmacs Lispとか、そういったメジャーなものを省いてもこのんなにたくさんの処理系が見つかりました！

正直なところ、全部まとめられるだろうといった気持ちで始めた処理系調査ですが、JavaScriptで動く処理系に絞ってもまだまだ探せば見つかりそうです

キリが無いと判断したため、処理系調査は中断させていただきます！もしも「なんでこの処理系が入ってないんだ！」と思われた方は、是非追加させて頂きたいのですコメントよろしくお願いします。

筆者のscheme理解レベル

先ほども話しましたが、僕はかつてActionScriptにLISPを実装したことがあります。しかし、正直言ってその完成度は小学生の工作レベルで「とりあえず動くLISPのような何か」が作れたという程度のものでした。

けれど初めてのLISP実装体験から得られたものは多く、LISPを通して「プログラムとは何なのか」という本質に触れることができました。不思議なことにLISPの実装は体の芯から興奮させられる魅力があるんです。

予想外だったのはLISPの実装はLISPをよく知らなくてもできるということでした。LISPの最大の特徴である前置記法、つまりリストの先頭は関数名で以降は引数となり数学の要領でカッコから評価していくという単純なLISPの理解さえあれば、LISPやSchemeを熟達していなくともLISPインタプリタの作成はできるのです。

LISPインタプリタの作成は容易であるとまでは言えませんが、不思議なことに「こうすればいいんだ！」とか「こうしてみよう！」といった閃きが実装中絶え間なく発生するはずです。少なくとも僕はそうでした。このような閃きはおそらくLISPにはeval（自分自身を解釈実行する機能）が必要であり、evalは本質的に強力かつミニマルであるからなんだと思います。

正直なところ、今現在僕はまだSchemeをちゃんと理解していません。Schemeの本は一冊も読んでないしLISPとSchemeの違いはSchemeの方がよりシンプルなんだってことくらいです。

Schemeの理解レベルが高ければ初めから高度に設計できるのは言うまでもありません。しかし、難しいことは考えずとにかく実装してみましょう！きっと、失敗も含めて記事にした方がわかりやすいものとなるはずです。

evalの魅力とエピソード

と、その前にevalってなんぞ？って思う方がいるかもしれないので、ここでevalの燃えるエピソードを紹介させていただきます。

僕がevalにハッ！とさせられたのは確かPerlを学んでいたときでした。当時はWebの世界ではPHPかPerlのどちらかが使われていた時代で、自分が初めて勤めた会社ではPerlを利用していました。

Perlにはeval()という関数があって、これは文字列のコードをそのまま実行できるという単純な機能でした。人によっては「え？これ意味なくね？」って思えるかもしれません。しかし僕はこの関数を初めて見たときに「ウオオオオオ！！」ってなったんです。それはきっと、僕が学生時代にスクリプトを組んでいたからなんです。

学生時代に組んだスクリプトとは、恋愛シミュレーションとかでよく使われるものでした。ポチポチ画面をクリックしていくとテキストが流れていき、読み終えると選択肢が出たりするヤツです。

このような簡易スクリプトプログラムを組んだことがない方はパッとしないかもしれませんが、仕組みは簡単です。

あらかじめ用意しておいた物語のテキストを画面に一文字ずつ表示していき「、」や「。」や「！」が来るタイミングで雰囲気の間をとるためにプログラムを待機させます。「そんな！！まさかアイツが......」みたいな文字を読ませるときは「...」の所でじっくり間をとって緊張感を与えたりします。

そして、改行したいところでは[改行]といった命令文を物語テキストに書いて、改行させたりします。[改行]が画面に表示されるタイミングで文字を表示する代わりに改行させてあげればいいのです。

このように、命令文どんどん定義していくんです。例えば[繰り返し 3]逃げちゃダメだ[/繰り返し]のような独自タグを作れば繰り返される言葉を何度も記述する必要がなくなって便利になります。

もちろん命令文カッコは<...>でも{{{...}}}でも構いませんし$から始まる文字列のようにカッコでなくても良いです。独自のスクリプトですから、記法は何でも自由に定義できます。とにかく、ある文字が来たら画面に文字を表示する代わりに別の処理をさせるようにするんです。

このようなプログラムを作って僕は「うおおお！！これめっちゃ楽しい！！！」と興奮しながらどんどん独自タグを追加していきました。そしてGOTO的な機能や変数定義ができるようにしていくと気がついて来るんです。「あれ？俺ってプログラミング言語を作ってるんじゃないか？」と。

そんな予感を感じながらもノリノリでいろんな機能を搭載していった結果、僕は本当に簡易的なプログラミング言語を作ってしまったんです！ものすごい興奮しました！！しかし、同時に自分は何もしていなかったということに気がつかされたんです。だって、自分が作った言語より、元々の言語の方がよくできてるんですよ？「どうして今自分はプログラミング言語を使ってイケてないオレオレ言語を作っているんだ？素直に元々の言語使えばよくね？」と。

話が脱線しますが、この体験は優れたプログラマになりたい人は一度は経験しておくべき体験であると僕は思ってます！この後、僕は「自分は何もしていなかった」という虚無感が一体なぜ起こったのかということを思考しました。そして最終的にこれは「わかりやすさと利便性のトレードオフ」であるということや「みんなで開発するということの意味」「人は物事をすぐに理解できない」ということに気がつかされたのです。世の中に様々な言語がある理由も、大規模な開発に独自言語が必要になる理由もここから理解が得られます。もっとこの話をしたいですが、脱線しすぎて帰ってこれなくなりそうなのでここまで。

でもその時はC言語を使って開発していたので、コンパイル不要でスクリプトが実行できるメリットは存在したわけです。

ですから僕は文字列で定義されたC言語を実行してくれる関数が無いか探しました！それがあれば独自スクリプトなんて作らなくていいんだ！！でも全然見つからないんですね。

そして月日が流れ、僕は学校を卒業し初めて勤めたWeb会社でPerlに出会いました。僕はラクダ本が面白くてついPerlの勉強に夢中になってしまいました。そして運命の日、eval()に出会うのです。「これだ！これだーー！！うおおおおおおお！！！」

つまりeval()とは、ひとつの言語を作る手間を省くほどのポテンシャルがあるということなんです。コンパイル言語とスクリプト言語の大きな違いを実感したのも、この瞬間でした。

このような体験をしなければ、通常eval()の本当のポテンシャルに気がつくことはできないと思います。そして、プログラミング言語作成にはこのeval()が重要な鍵となるのです。

それでは早速言語作成をしていきましょう！

STEP0: 実装前に知っておくべきLISPの知識

突然ですがLISPはコード見た目の悪さからよく嫌われる言語です。

こんな感じです。

(defun fibonacci (N)
  "Compute the N'th Fibonacci number."
  (if (or (zerop N) (= N 1))
      1
    (let
	((F1 (fibonacci (- N 1)))
	 (F2 (fibonacci (- N 2))))
      (+ F1 F2))))

オエッ！とかなっちゃう人がいるのはわかります。正直なところLISPの第一印象は良いものとはいえません。実際、そうなっちゃう人が多いからLISPは実用されないのです。

でも、LISPにカッコが多いからといってそのほかの言語に比べコードに複雑さが増したり、読みにくくなるということはありません。それどころかLISPは言語自体の抽象度を上げてより読みやすくすることができる唯一の言語です。

LISPのコードが読みにくいと感じるのは、単にまだよく知らないというだけのことです。このカッコにはちゃんと意味があるんです。

この記事を読んでいる人は恐らくLISPに詳しい人が多いでしょう。そのため「実装前に知っておくべきLISPの知識」なんてものを今更解説されても退屈だと思います。しかし、僕みたいにLISPのことをよく知らないのにLISPを作ってみたい！と、熱意だけ先走ってる人がいるかもしれないので、事前に知っておくべきLISPの知識をまとめさせていただきました！

当たり前のことしか書いていないので、すでにご存知の方はスキップしてください。

前置記法

LISPの最大の特徴といったらやはりコレ。通常の言語では、関数をcallするにはfunc()のように関数名の末尾にカッコをつけて呼び出すことが多いです。しかし、LISPでの関数callは(func)となります。func(1, 2)のような引数を取る関数のcallは(func 1 2)となるのです。

まずこの地点で「ハァ？」となる人が大半です。僕も初めてLISPの前置記法を知った時には同じような反応をしました。しかしLISPは優れた言語であるという話はよく聞いていたので、これには何か意味があるのだろうと考えを改めました。実際、深い意味があります。

その深い意味を除いたとしても、通常1 + 2 + 3 + 4 + 5などと+記号のオペレータをたくさん書かなければならないコードが(+ 1 2 3 4 5)とスッキリ書けることは美しいと感じないでしょうか？

んなこまけぇことどうでもいいんだよ！とか思うかもしれませんが、逆に言えばLISPという言語はこんな細部まで美しさを洗練させることができる言語ということです。

また、前置記法は数学のようにカッコに結果が置き換わるということも直感的です。(+ 1 2 3 (* 4 5))のコードは(* 4 5)が先に評価され(+ 1 2 3 20)となり最終的に26の結果が得られます。最も深いカッコから順に評価されるのです。

リスト

LISPがあえてカッコだらけの言語であり続ける理由、それは前置記法を使うことによってデータもコードもリストになるからです。

デジカメの中に入っている写真、MP3プレイヤーに入っている楽曲、スマートフォンに入ってる電話帳。当たり前ですがこれらを「データ」と言います。そして重要なのがXMLやJSONといった構造化されたテキストデータも「データ」だということです。

それではコードは何でしょうか？C言語で書かれたプログラム、JavaScriptで書かれたプログラム、SQLなど、様々な言語で書かれたプログラムのことを「コード」と言います。厳密には、コンパイラや「インタプリタが解釈できるデータ」をコードというのです。

つまり、結局のところコードもデータあり、全てはデータなのです。当たり前のことですが、知識が豊富な人ほど盲点になっているのではないでしょうか？僕はそうでした。

JavaScriptはときにJSONデータを読み込んで利用したりしますが、JavaScriptの言語構造とJSONのデータ構造は全く異なります。しかしLISPはどうでしょう？JSONの{name:yamada, age:18}は((name yamada) (age 18))とリストで表現でき、そしてこのリストの構造はLISPプログラムの構造そのものです。

さらっと言ってますが、ここが最もLISPの革新的な部分です。

LISPの素晴らしい点はプログラムの「コード」とプログラムが使う「データ」の構造を「リスト」というひとつのフォーマットに統一させたことです。このおかげてLISPはプログラムを書くプログラムを作成することが容易なだけでなく、他のプログラムには見られない強力で美しいマクロを使うことができるのです。

クオート

他のプログラミング言語ではみられないが、LISPでは多用する機能を紹介します。クオートです！

LISPのリストデータはインタプリタに解釈されると評価されてしまいますが、評価しないで式そのものを扱いたい時があります。そんな時はquoteを使います。

(quote (1 2 3)) ; 結果:(1 2 3)

(1 2 3) ; これはエラー！

上記のコードを見てください。(1 2 3)のリストに対してquoteすると結果は(1 2 3)となります。エッ！なにそれ意味あんの？とか思う方がいらっしゃるかもしれませんがこれが結構意味あります。

すぐ下のquoteを利用しない(1 2 3)の場合、これを評価しようとすると1という関数に2と3の引数を渡そうとするのです。当然1などという名前の関数は存在しませんのでエラーとなります。

このような時にquoteを使うと、quoteに渡されたリストが評価されず、リストをそのまま返すようになります。リストをそのまま返せるということは、そのリスト自体に何らかの処理を施すことができることを意味します。

(cons (quote +) (quote (1 2 3)) ; 結果:(+ 1 2 3)

; ちなみにquoteは'を使った省略記法がある
(cons '+ '(1 2 3)) ; 結果:(+ 1 2 3)

(1 2 3)というデータを(+ 1 2 3)というインタプリタが解釈可能なコードに変換することができました。ちなみにcons関数を使うと、リストを連結することができます。

通常、JavaScriptであれば入力されたJSONファイルをJavaScriptのソースコードに変換するなんて芸当は出来ません。しかし、LISPではこのようにコードを解析可能なデータとして気軽に扱うことができるのです。

そして、quoteは玉ねぎの皮のように評価機からデータを守ることができます。quoteによって守られたデータは評価される前に自由に書き換えることができるのです。

このようなプログラミングスタイルは、他の言語にはあまり見られません。

特殊式

LISPの特徴を解説しすぎると、入門書になってしまうので次で最後にします！LISPでは(func)で関数を実行できると解説しましたが、実は関数とは異なる特殊式というものものが存在し、関数のように実行することができるものがあります。

例えばifは関数ではなく特殊式です。別に知らなくても良いことですが、インタプリタを作成するとなると知っている必要があります。

なぜifが特殊式なのか？それはカッコの深い部分から評価されるというルールが適応されないからです。

(if (> x 1) (print "ok") (print "ng")) ; xが1より大きければ"ok"が出力される

もし上記のコードがカッコの深い部分から評価されてしまった場合、"ng"も"ok"も両方出力されてしまいますよね？

しかしこのようなことは起こりません。なぜならifは特殊式だからです。ifは(> x 1)の評価結果をもとにどちらか一方を評価するという期待通りの動作をしてくれます。

このようにLISPでは関数の他に特殊式というものを作成でき、この特殊式を使って通常の関数には実現できない機能をも実装できるのです。

通常の言語であればifやforといった制御構造を実装することはできません（C言語はマクロ使えるから可能だけど）しかしLISPは、言語自体を独自に拡張できるように作られているためこのような大胆な拡張を行うことができるのです。その点も他の言語にはあまり見られない特徴ですね！

STEP1: Schemeのリストを配列に変換する

それでは早速JavaScriptにSchemeを実装していきます！

Schemeインタプリタを実装するには、Schemeのコードとデータを表現できる「リスト」を作成しなければなりません。

LISPの名前は「list processor」に由来していて、その名の通りLISPは「リスト評価装置」です。そしてリストはJavaScriptの配列によく似ています。

(1 2 3 (4 5))というSchemeのリストを[1, 2, 3, [4, 5]]というJavaScriptの配列に変換できれば、リストを配列で扱うことができそうです。

簡単そうに見えませんか？カッコとカンマを除いたらリストはJavaScriptの配列とほぼ同じように見えます。さて、どうやって変換しよう。

JSON.parse()は使えないか？

有難いことにJavaScriptにはJSON.parse()という関数があり、これはJSON文字列をJSオブジェクトに変換してくれる優れもの。本来、JSON自体は{...}のオブジェクト記法を扱うのが自然だけど、配列記法の文字列を渡したらそのまま配列に変換できるかもしれない。

そう思って、試しにJSON.parse()配列文字列を渡してみました。

JSON.parse("[1, 2, 3, [4, 5]]"); // 結果：[1, 2, 3, [4, 5]]

わお、できた！！これが出来るなら()を[]に置換して、スペース区切りをカンマ区切りにするだけで(1 2 3 (4 5))は[1, 2, 3, [4, 5]]に変換できそうじゃないか！簡単だ！！

...と、考えられるんだけど実はこれはアンチパターン。Schemeには数字の他にシンボルというものがあってJSON.parse("[a, b, c, [d, e]]")といったダブルクォートで囲まない文字列を渡すとエラーになってしまうんです。

これを回避するために、強制的にダブルクオートをつけて(a b c (d e))を["a", "b", "c", ["d", "e"]]に置き換えることも考えてみました。しかし(a b c "a b c")といった文字列を含むリストが渡された時にまた問題が発生します。文字列の中の空白にもダブルクオートが添えられてしまうんです！orz

どうしたものか試行錯誤した結果、文字列の部分だけ置換しないよう動作する高度な正規表現を書くことを考えました。しかし、僕にはそんな呪文のような正規表現を書くのは荷が重い...

また、将来的に(quote (a b c))を'(a b c)と書けるように細かい対応することを考えると、正規表現地獄に陥りそうです。

というわけで、もう一歩踏み込んで独自に実装した方が良さそうだという結論に至りました。

一文字ずつfor文で回す

そこで原始的ではありますが、for文を使って入力された文字列を一文字ずつ見ていって配列に変換する関数を作ることにしました！

let code2list = (code)=>{
  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    console.log(c)
  }
}

まだ何も完成してませんが、上記のコードで変数cの中に入力されたコード一文字一文字が挿入されるようになったはずです。

とりあえず余計な文字を無視してみる

次に、コードの中に含まれる余計な文字を無視することを考えてみましょう。空白や改行、コメントなどの文字はインタプリタには解釈されないため無視する必要があります。

空白というと普段は半角と全角スペースくらいしか使わないけれど、文字コードってのは奥が深くて、僕たちの知らない様々な種類の空白があったりします。むかし「ゼロ幅スペース」と呼ばれる名前の通り幅を持たない空白文字が存在することを知って驚いたことがありました。

この様々な空白文字に対応するために、空白文字の文字コードを全てピックアップして処理させるのはとても面倒です。しかし正規表現を使えば、多様な空白や改行の種類に悩まされることはありません。

先ほどは正規表現を使ってコードを配列に変換しようとして諦めましたが、余計な文字列を検出するために正規表現は使えそうです。

このサイトでは正規表現で使えるエスケープの詳細な説明がありました。おそらく以下のコードで余計な文字を見つけることができるはずです。

c.match(/[\r\n\f\s\b\t\v\0]/)

正規表現で使ったエスケープ文字の説明は以下を参照。

文字	意味
\r	先頭にカーソルを戻す指示を出す制御文字。\nとの違いがよくわからないけど、改行のことだと思えばいい。
\n	次の行に移る指示を出す制御文字。まさに改行。環境によって\rが使われたり\nが使われたり両方使われたりする。
\f	改ページ。使ったことないけどVimやEmacsで使ったら1画面分の改行が挿入されたりするのだろうか？とにかく余計なことに間違いない。
\s	空白。空白には僕たちの知らない種類の空白文字がたくさんあるのでこれを使う。今回正規表現でわざわざマッチさせることにした1番の理由でもある。
\b	バックスペース。文字として存在する意味がわからん。pythonの正規表現での実例を見つけたが同じものなのだろうか？とにかく余計と判断。
\t	タブ文字。
\v	垂直タブ。そういえばあったな...。使ったことないけど使うとどうなるんだろうか。
\0	NULL文字。これを省くとC言語では色々おかしいことになってしまうのは経験から知っているが、おそらく必要ない。実はJavaScriptの文字列は全て自動で末尾にヌル文字が挿入されており、このNULL文字を何らかの手段で取り除いたりすると検出できなくなって大変なことになる！なんてことはさすがに無いだろう。

余計な文字の判定準備ができたところで、これらの文字が見つかったら無視するようにしてみましょう！先ほどのコードに追記します！

let code2list = (code)=>{
  for( let i=0; i<code.length; i++ ) {
    let c = code[i]

    // (1)追加したコード。余計な文字列が見つかったら無視する。
    if( c.match(/[\r\n\f\s\t\v]/) ) continue

    console.log(c)
  }
}

// 実行
// cの次に改行、dの次に全角スペース、eの次にタブ文字。
code2list(`(a b c
d　e	f)`)

// 結果
// (
// a
// b
// c
// d
// e
// f
// )

期待通りの結果です！実行してみると(1)の正規表現で空白や改行などの余計な文字が無視され、それ以外の文字が正しく出力されていることがわかります。

余計な文字を全てスペースと認識させる

余計な文字が見つかったらcontinueして無視するという考え方をしていますが、実際はスペースとして判定する必要があります。Schemeリストのスペースは、区切り文字を表します。

かと言って余計な文字を全てreplace()などで置換すると、ダブルクオートで囲まれた文字列の中身も影響を受けてしまうためできません。

そこで不要な文字はcontinueで無視するのではなく、区切り文字として判定させて見ましょう。

スペースが見つかったらシンボルとして要素を独立させればいいので、不要な文字を検出したらそこで要素を区切るようにします。検出できない場合はその文字は区切られていませんので結合していきます。

一気にコードを書き換えます。

let code2list = (code)=>{
  let ary = [''] // (1)要素を保存する配列を作成
    
  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary.length - 1 // (2)配列の最後のインデックスを用意しておく。
    
    // (3)文字結合と区切る処理を追加する。
    if( !c.match(/[\r\n\f\s\t\v]/) ) ary[l] += c
    else if( ary[l].length ) ary.push('')
  }

  return ary
}

// 実行
// 正しく区切られるか確かめるため前回の"a"を"aaa"とした。
let result = code2list(`(aaa bbb ccc
ddd　eee	fff)`)

// 結果
console.log(result) // ["(aaa", "bbb", "ccc", "ddd", "eee", "fff)"]

新しく追加した(1)の配列には、区切った要素の結果が入ります。空文字列があらかじめ用意されているのは、区切り文字が検出されるまでは文字結合を行うため、あらかじめ結合先を用意しているということです。

そして、for文で回したcの中身を配列末尾の文字列にどんどん追加していきます。余計な文字が見つかった時は区切り文字として判定し、配列末尾に新しい空文字列をpushして要素を区切るというわけです！

念のためもう少し詳しく解説しましょう！(2)の部分では、配列の末尾にアクセスするためのインデックスをlに用意しています。ちなみにlはlastのlです。

次の(3)ですが、ここが今回のポイントです。もし余計な文字列にマッチしなければ配列末尾の文字列に読み取った一文字cを結合します。マッチした場合には空文字列をpushして要素を区切ります。この時、配列末尾に空白文字が存在していないか確認し、余計に要素が区切られてしまうことを回避しています。

さて、実行結果を見るとソコソコうまく動作しています！しかし、aaaの先頭に(が、fffの最後に)が付いているのがわかります。

現在は(1)で配列をあらかじめ用意してしまっていますが、本来はこれらのカッコを見つけた時に配列作成しなければなりません。そして新たにカッコを検出した際には配列をネストする必要も生まれてきます。

"("を発見したら配列を作成する

というわけで、次はネストされたリストに対処できるようにしてみましょう！あらかじめ配列を用意するのではなく、(を見つけたら配列を作成するのです。

コードを書き換えます！

let code2list = (code)=>{
  let result, ary // (1)結果を返すためのresult変数を用意してaryの初期化をやめる。
    
  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1 // (2)ary未定義時のエラー回避

    // (3)新しく追加したコード。カッコが見つかったら新しい配列を作成する。
    if( c == '(' ) {
      if( !ary ) result = ary = [''] // (4)resultとaryの初期化。一番外側の親配列。
      else ary = ary[l] = [''] // (5)カッコが見つかったら新しい配列を作成しaryの参照を変える。
      continue
    }
    
    if( !c.match(/[\r\n\f\s\t\v]/) ) ary[l] += c
    else if( ary[l].length ) ary.push('')
  }

  return result
}

// 実行
let result = code2list(`(aaa bbb ccc
ddd　eee	fff)`)

// 結果
console.log(result) // ["aaa", "bbb", "ccc", "ddd", "eee", "fff)"]

結果を見てみると(aaaとなっていた箇所がaaaとなっており、先頭の(を識別して配列を作成することに成功しました！

説明します！まず(1)ですが、戻り値用変数resultを作成しました。

そして、ary = ['']のように配列の初期値を与えるのをやめています。理由は(を見つけたら配列を作成するため、前もって用意しておくのはおかしいからです。

次に(2)ですが、これは(1)でaryの初期化をやめた影響でaryの中身が存在しない時のエラー対処となります。

次に(3)ですが、ここが新たに追加されたコードになります。cがカッコだったらif文の中に入ります。そして(4)で配列が未定義の場合はresultとaryの中に空文字配列を挿入します。これは配列の初期化がただここに移動しただけのことです。

ポイントとしてはresultにも同じ配列を挿入している点です。このおかげで最終的にreturnする結果（親配列）をキープしています。

そしてaryの初期化が行われていると判定した場合にはelseの項目(5)が実行されます。配列の末尾に新しい空文字配列を挿入し、ary自体もその新しい配列を参照するようにしています。

本当に正しく動作しているか確認するため、テスト用コードをネストしたリストに置き換えてみましょう！

let code2list = ... // 省略

// 実行
// bbbとcccをカッコに入れる
let result = code2list(`(aaa (bbb ccc)
ddd　eee  fff)`)

// 結果
console.log(result) // ["aaa", ["bbb", "ccc)", "ddd", "eee", "fff)"]]

ちょっとおかしいですが、配列の作成とネストには成功しているようです。

現時点では閉じカッコ)に対応していないので、"ccc)"以降の要素もネストされた配列の中に含まれてしまっていますが、しっかりと"(bbb"の部分で配列が正しくネストされていることが確認できます。

それではこの調子で)に対応してみましょう！)が見つかったらネストされた配列から抜け出すのです！

配列をスタックに記憶する

と、ここで問題発生です！どうやってネストされた配列から抜け出せばいいのでしょう？？aryはfor文の中で、現在の対象となっている配列を扱っています。その配列から抜け出すということは、元の配列に参照を戻すということです。

しかし現在、元の配列をどこにも保持していないため参照を戻すことができません。この問題に対処するため元配列を記憶するスタックを作成します。

let code2list = (code)=>{
  let result, ary, stack = [] // (1)新しい配列stackを作成。スタックには元配列がストックされる。

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary=ary[l]=['']  // (2)新しい配列に参照が移る前にスタックに元配列をunshiftで記憶。
      continue
    }

    if( !c.match(/[\r\n\f\s\t\v]/) ) ary[l] += c
    else if( ary[l].length ) ary.push('')
  }

  return result
}

閉じカッコ)を検出した際に配列の参照を戻すため、(1)の部分でstack配列を新たに定義しました。今回は(2)の部分が重要です。追加されたコードはstack.unshift(ary),です。

コメントで解説しているためあえて説明するまでも無いかもしれませんが、これはaryの参照が新しい配列に変わる前にaryをスタックにunshift()で押し込むことで、元配列をstackに記憶しているということです。

見慣れない,カンマがややこしいですが、{}ブロックで囲むまでもない複数の処理は、実はカンマ区切りで記述することができます。（あまり知られていないJSテクニックかも）

これでネストした配列をスタックに蓄え、元の配列に参照を戻せる準備ができました。

")"を見つけたらネスト元に戻る

それではいよいよ)に対応してみましょう！

let code2list = (code)=>{
  let result, ary, stack = []

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary=ary[l]=['']
      continue
      
    } else if( c == ')' ) {
      if( ary[l]=='' ) l--, ary.pop() // (1)元配列に戻る前に余計な空文字があれば取り除く。
      ary = stack.shift() // (2)ネスト元配列に戻る。
      if( ary ) ary.push('') // (3)ネスト元配列の末尾を区切る。
      continue
    }
    
    if( !c.match(/[\r\n\f\s\t\v]/) ) ary[l] += c
    else if( ary[l].length ) ary.push('')
  }

  return result
}

// 実行
let result = code2list(`(aaa (bbb ccc)
ddd　eee   fff)`)

// 結果
console.log(result) // ["aaa", ["bbb", "ccc"], "ddd", "eee", "fff"]

うまくできました！見ての通り、今回はelse ifで)の判定を追加しています。

(1)は余計な空文字を取り除いているだけです。今回のポイントは(2)です！ary = stack.shift()しているだけですが、これだけで現在の配列からネスト元の配列に戻ることができます！wow！スタック万歳！

最後の(3)は、ネスト元配列に戻った時に末尾を区切る必要があるため、お約束の空文字列をpushをしているだけです。

軽くリファクタリングする

ここまでできたところで少しリファクタリングしましょう！continueを多用していて気持ち悪いのでif, else if, elseの形式に変えてcontinueを取り除きたいと思います！

let code2list = (code)=>{
  let result, ary, stack = []

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary=ary[l]=['']

    } else if( c == ')' ) {
      if( ary[l]=='' ) l--, ary.pop()
      ary = stack.shift()
      if( ary ) ary.push('')
      
    } else if( !c.match(/[\r\n\f\s\t\v]/) ) {
      ary[l] += c
      
    } else if( ary[l].length ) {
      ary.push('')
    }
  }

  return result
}

本当にこれで動いているのでしょうか？検証するために、複雑なSchemeリストを渡してそれが正しく配列に変換されるか確認してみましょう！

// 実行
let result = code2list(`(aaa   ( bbb (ccc ddd ) eee)fff)`)

// 結果
console.log(result) // ["aaa", ["bbb", ["ccc", "ddd"], "eee"], "fff"]

今回は実行のコードをあえて崩してみました。aaaの後には空白を3つ追加しています。これで空白が連続しても問題なく動作するかチェックしています。

次のbbbでは、カッコの後に余計な空白を入れています。そして、dddの後にも余計な空白を入れて問題なく動作するかチェックしています。

最後にeee)fffの部分ですが、今度は逆に空白が無かったときに問題なく動作するかチェックしています。

実行してみると、どうやら問題なく動作しているようです！これでSchemeのコードをJavaScriptの配列に変換することができました！！

...と、思いたいのですが次のコードを実行するとどうなるでしょうか。

// 実行
let result = code2list(`(aaa   ( bbb (ccc ddd ) eee)fff "I am String")`)

// 結果
console.log(result) // ["aaa", ["bbb", ["ccc", "ddd"], "eee"], "fff", "\"I", "am", "String\""]

うーん。"I am String"の中身も分割されてしまいました。

しかし何も問題ありません！code.replace()を使って解析しやすいコードに置換することをグッと堪えて、わざわざfor文で回してここまで頑張ってきた甲斐が今まさにここで発揮されるのです！！

入力されたコードのダブルクオートに対応する

この問題に対処するためには、ダブルクオートが見つかったら、次のダブルクオートが見つかるまでは問答無用で文字を結合していけば良さそうです。

let code2list = (code)=>{
  let result, ary, smode, stack = [] // (1)文字列モードフラグsmodeを作成。

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    // 新しく追加されたコード
    if ( !smode ) smode = c=='"' // (2)smodeが無効の時はsmodeを有効にする機会（ダブルクオートの発見）を伺う。
    else {
      if( c == '"' ) smode=false, ary.push('') // (3)末尾のダブルクオートが見つかったらsmodeを無効にして区切る。
      ary[l] += c // (4)文字を問答無用で結合。
      continue;
    }
      
    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary = ary[l] = ['']

    } else if( c == ')' ) {
      if( ary[l]=='' ) l--, ary.pop()
      ary = stack.shift()
      if( ary ) ary.push('')
      
    } else if( !c.match(/[\r\n\f\s\t\v]/) ) {
      ary[l] += c
      
    } else if( ary[l].length ) {
      ary.push('')
    }
  }

  return result
}
  
// 実行
let result = code2list(`(aaa   ( bbb (ccc ddd ) eee)fff "I am String")`)

// 結果
console.log(result) // ["aaa", ["bbb", ["ccc", "ddd"], "eee"], "fff", "\"I am String\""]

苦戦するかなーと思っていましたが、結構あっさりできました。

まず(1)の部分ですが、文字列の中身が分解されないようにするため、文字列モードフラグを作成しました。smodeが有効の時は、要素を区切ることなく末尾のダブルクオートが見つかるまで問答無用で文字を結合していく作戦でしたね！

次に新しく追加されたコードの(2)の部分ですが、ここではsmodeが無効の時にダブルクオートが来るのを監視しているということになります。もしダブルクオートが見つかったらsmodeはtrueとなってelseに処理が移ります。

そのelseの中のコードですが(3)では、今度は末尾のダブルクオートを探しています。もし見つかったら、smodeを無効にして要素を区切ります。

その次の、(4)は説明するまでもありませんね！今回一番やりたかった問答無用で文字を追加しているコードはまさにココです！

これで正しく動作しているように見えますが、まだ問題が残っています！文字列の中でダブルクオートを使いたい場合に対応できていません。そのため今度はエスケープされたダブルクオート\"を利用できるようにする必要があります。

対応しましょう！！

let code2list = (code)=>{
  let result, ary, smode, stack = []

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    if ( !smode ) smode = c=='"'
    else {
      if( c == '"' ) smode=false, ary.push('')
      else if( c == `\\` ) c = code[i+=1] // (1)バックスラッシュの次の文字を結合させる
      ary[l] += c
      continue;
    }
      
    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary = ary[l] = ['']

    } else if( c == ')' ) {
      if( ary[l]=='' ) l--, ary.pop()
      ary = stack.shift()
      if( ary ) ary.push('')
      
    } else if( !c.match(/[\r\n\f\s\t\v]/) ) {
      ary[l] += c
      
    } else if( ary[l].length ) {
      ary.push('')
    }
  }

  return result
}
  
// (2)実行。文字列に"yeah!"を追加。
let result = code2list(`(aaa   ( bbb (ccc ddd ) eee)fff "I am String \\\"yeah!\\\"" ggg)`)

// 結果
console.log(result) // ["aaa", ["bbb", ["ccc", "ddd"], "eee"], "fff", "\"I am String \"yeah!\"\"", "ggg"]

(1)でelse ifを付けることで、バックスラッシュが見つかったらバックスラッシュの次の文字が結合されるようcを書き換えています。つまり\"の場合"の文字を問答無用で結合します。これでエスケープされたバッククオートに対応できるというわけです。

それでは実行して見ましょう！(2)の実行部分のコードを修正しています。

バックスラッシュやダブルクオートが連続していて意味不明ですが、これは自作したエスケープの処理を行う前にJSが文字列をエスケープ処理してしまうためエスケープのエスケープをしているということです。（ああっ！ややこしい！）

本来Schemeのコードを外部から読み込んでいればこのようなことは起きませんが、JSに直接Schemeのコードを書いているため複雑になっちゃってます。しかし、単に(aaa ( bbb (ccc ddd ) eee)fff "I am String \"yeah!\"" ggg)の文字列を渡してるだけです。

バックスラッシュの処理は\"や\\だけでなく\nの改行などを表現することができるため現時点では全てのエスケープシーケンスに対応しきれていませんが、ひとまずこれでダブルクオートが見つかってもエスケープされていれば文字列が途中で区切られることはなくなりました。

ちなみに、@javacommonsさんに頂いた指摘で文字列モードの判定にフラグを使って処理させることで正規表現に劣らないパフォーマンスを出すことができることを教えていただき、コードを修正させていただいております。

おめでとう！そして、ひとまずお疲れ様でした！これでSchemeのコードをJavaScriptの配列に変換することができました！！しかし、まだSchemeの実装は始まったばかりです。

次のステップではリストを評価します。本当のお楽しみの始まりはここからです！

STEP2: リストを評価する

それではリスト評価機を作成しましょう！

もう一度おさらいするとSchemeは(+ 1 2 3)というコードを評価した際、+という名前の関数に対し1,2,3の引数を渡して実行します。

いきなりlambdaやletなどの難しい関数を動作するようにするのは気が早いので、まずは足し算をできるようにしてみましょう！

ということで(+ 1 2 3)を評価すると6という結果が得られるようにするところから始めます。

クラスを作成する

と、その前にcode2list関数をSchemeクラスのメソッドにしましょう。

// (1)Schemeクラスを作成しcode2listをSchemeクラスのメソッドにする
let Scheme = function(){
  this['code2list'] = (code)=>{ ... } // 長いので省略
}

let scheme = new Scheme() // Schemeインスタンスを作成
console.log(scheme.code2list('(+ 1 2 3)')) // 結果: ["+", "1", "2", "3"]

ES6からclass構文を利用できますが、(1)ではあえて旧式のfunctionを利用してクラス作成をしています。理由は+なんて通常定義できない名前のメソッドを定義しなければならないからです。

実行するコードは(+ 1 2 3)に変更しました！それではリストを評価していきましょう！

まずは電卓として機能させる

先ほどのcode2list実行結果で["+", "1", "2", "3"]の配列が得られています。この配列を料理して6が得られれば良いのです。

そのためには配列の先頭の+を抽出し、該当する関数に残りの["1", "2", "3"]を渡す機構があれば良さそうです。

let Scheme = function(){
  this['code2list'] = (code)=>{ ... }
  this['eval'] = (list)=>this[list.shift()](...list) // evalを実装する。
}

インタプリタのアイデンティティとも言えるevalを実装しました。エッ！1行で書けるの！？って感じですが、誰よりも驚いたのは筆者ですw

やってることは簡単。配列化されたリストを受け取り、リストの先頭要素をshift()を使って取り出しsに定義されている該当する関数を取得します。その関数にlistの残りの要素を展開してcallすれば出来上がりです！

ただ、このままではSchemeクラスに+なんてメソッド無いんだけど？と怒られてしまうので+関数を用意します。

let Scheme = function(){
  this['code2list'] = (code)=>{ ... }
  this['eval'] = (list)=>this[list.shift()](...list)
  this['+'] = (...args)=>args.reduce((a,b)=>a+b) // (1)+関数を作成する。
}

JavaScriptの配列のreduce()に慣れていない方は「はい？」って思うかもしれませんが何も難しいことはありません。ただ配列argsの中身を全て足しているだけです。もしreduce()を使ったことがない方は、かなり使えるので使い方を覚えることをオススメします。

それでは実行してみましょう！ついでにコードを実行する関数execも追加して見ました。

let Scheme = function(){
  this['code2list'] = (code)=>{ ... }
  this['eval'] = (list)=>this[list.shift()](...list)
  this['exec'] = (code)=>this.eval(this.code2list(code)) // exec関数を追加
  this['+'] = (...args)=>args.reduce((a,b)=>a+b)
}

let scheme = new Scheme()
console.log(scheme.exec('(+ 1 2 3)')) // 結果:123

結果が出ました！！1 + 2 + 3の結果は123です！ってうおおおおおおい！！幼稚園児かよ！！

ここまで改修

数を認識させる

ここで残念ながら再びcode2listの修正です。せっかく終わったと思ったのに！という気持ちをグッとこらえてササッと修正しちゃいましょう！！

入力された(+ 1 2 3)が123になってしまう理由は、数値が文字列だからです。["+", "1", "2", "3"]を["+", 1, 2, 3]とすれば良いのです。

それを実現するためにはcode2listで要素を区切った時に確定した数値をparseFloat()でキャストすればいいのです！parseInt()ではない理由は単純に少数にも対応するためです。

let s = {}
s['code2list'] = (code)=>{ ... }
s['eval'] = (list)=>s[list.shift()](...list)
s['+'] = (...args)=>args.reduce((a,b)=>a+b)

// (1)新しく追加したコード。
s['str2data'] = (v)=>{
  if( isFinite(v) ) return parseFloat(v)
  return v
}

文字列を数値に変換するため、まずはstr2data関数を作成しました。(1)の新しく追加したコードを見てください！受け取った値vが数値文字列であるか確認し、数であればparseFloat()で数値に変換する単純な関数です。（関数名がstr2numではなくstr2dataなのは、後に他のデータにも対応するためです）

この関数をcode2listで使います。思い出してください！code2listでは要素をary.push('')で区切っていました。要素を区切るということは、要素の内容が確定することを意味するため、確定と同時にstr2dataすればいいのです！

let s = {}
s['code2list'] = (code)=>{
  let result, ary, smode, stack = []

  // (1)文字列を適切なデータに変換し
  // 配列末尾に新しい空文字列を```push```して要素を区切る
  let put = (a,i,p=a)=>{ary[i]=s.str2data(ary[i]),p.push('')}

  for( let i=0; i<code.length; i++ ) {
    let c = code[i]
    let l = ary ? ary.length-1 : -1

    if ( !smode ) smode = c=='"'
    else {
      if( c == '"' ) smode=false, put(ary,l) // (2)
      else if( c == `\\` ) c = code[i+=1]
      ary[l] += c
      continue;
    }

    if( c == '(' ) {
      if( !ary ) result = ary = ['']
      else stack.unshift(ary), ary = ary[l] = ['']

    } else if( c == ')' ) {
      // (3)
      put(ary,l,prv) 
      ary = stack.shift()

    } else if( !c.match(/[\r\n\f\s\t\v]/) ) {
      ary[l] += c

    } else if( ary[l].length ) {
      put(ary,l) // (4)
    }
  }

  return result
}

s['eval'] = (list)=>s[list.shift()](...list)
s['+'] = (...args)=>args.reduce((a,b)=>a+b)
s['str2data'] = (v)=>{
  if( isFinite(v) ) return parseFloat(v)
  return v
}

let code = '(+ 1 2 3)'
console.log(s.eval(s.code2list(code))) // 結果:6

要素を確定させるコードが複雑になってきたので、(1)の部分で共通の関数を作成しました。第一引数aの配列と、第二引数iのインデックスで確定先の値を指定します。第三引数のpは空文字列をpushする対象の配列を指定します。

この関数putのおかげで、配列の文字列を適切なデータにstr2dataで変換し配列末尾に新しい空文字列をpushすることで要素を区切ることができます。

かなり原始的ですがこのput関数をcode2listのary.push('')を行なっていた(2)(3)(4)の3箇所に置き換えましょう。

実行結果は期待した6となっています！

ネストした式を評価できるようにする

喜ぶのはまだ早いです。先ほどのコードでは(+ 1 2 3)のような式は実行できても(+ 1 2 3 (+ 4 5)のようなネストした式に対応できていません。

この問題はevalに渡されたリストの引数に当たる値を評価しないために発生しています。やはりevalを1行で実装するのは無理があったようです。

というわけでevalの実装を書き換えましょう！

let s = {}
s['code2list'] = (code)=>{ ... }
s['eval'] = (v)=>Array.isArray(v) ? s[v.shift()](...v.map(w=>s.eval(w))) : v // (1)
s['+'] = (...args)=>args.reduce((a,b)=>a+b)
s['str2data'] = (v)=>{
  if( isFinite(v) ) return parseFloat(v)
  return v
}

let code = '(+ 1 2 3 (+ 4 5))'
console.log(s.eval(s.code2list(code))) // 結果:15

書き換えた箇所は(1)の部分です。ってあれ、結局1行で実装できてしまいましたねw

特に難しいことはしていません！解説します。まず受け取ったvの値がリストであるか確かめ、もしリストでなかった場合には値をそのまま返すようにしています。

しかしvがリストだった場合には評価しなければならないため、リストの先頭要素をshift()で取り出し、該当する関数を取得します。（ここは前と同じですね！）

そして、その関数にvの残りの要素を引数として渡すわけですが、ここがミソです。引数を渡す前にmap()を使って全ての引数を再びevalで評価します。そうすることで、渡されたリストは、ネストの深い部分から評価されるようになるというわけです。

再び軽くリファクタリングする

グローバルスコープsに関数を定義していましたが、若干の不都合があるためクラスにまとめたいと思います。ES6からclass構文を利用できますが、今回はあえて旧式のfunctionを利用します。（+なんて名前の関数を定義したりするからです）

コードが一新され、負担を感じるかもしれませんが難しいことはありません。グローバルスコープsのオブジェクトをnewで生成するようにしてsがthisに変更されただけです。

let s = new function(){
    
  this['code2list'] = (code)=>{
    let result, ary, smode, stack = []
    let put = (a,i,n)=>{ary[i]=this.str2data(ary[i]),!n?a.push(''):0} // this変更に注意
  
    for( let i=0; i<code.length; i++ ) {
      let c = code[i]
      let l = ary ? ary.length-1 : -1
  
      if ( !smode ) smode = c=='"'
      else {
        if( c == '"' ) smode=false, put(ary,l)
        else if( c == `\\` ) c = code[i+=1]
        ary[l] += c
        continue;
      }
  
      if( c == '(' ) {
        if( !ary ) result = ary = ['']
        else stack.unshift(ary), ary = ary[l] = ['']
  
      } else if( c == ')' ) {
        if( ary[l]=='' ) ary.pop()
        else put(ary,l,true)
        ary = stack.shift()
  
      } else if( !c.match(/[\r\n\f\s\t\v]/) ) {
        ary[l] += c
  
      } else if( ary[l].length ) {
        put(ary,l) // (4)
      }
    }
  
    return result
  }

  this['str2data'] = (v)=>{
    if( isFinite(v) ) return parseFloat(v)
    return v
  }

  this['eval'] = (v)=>Array.isArray(v) ? this[v.shift()](...v.map(w=>this.eval(w))) : v

  this['+'] = (...args)=>args.reduce((a,b)=>a+b)
}

let code = '(+ 1 2 3 (+ 4 5))'
console.log(s.eval(s.code2list(code))) // 結果:15

クラス化した一番の理由は、コード内にsを使いたくなかったからです。thisの方が将来的に独立したファイルにしてモジュール化しやすいですし、可読性も上がります。sってナニ？ってならなくなるので。

また、コードの実行がs.eval(s.code2list(code))となっており、なんとなくイケてないのでexecメソッドを以下で用意しました。

let s = new function(){
  this['code2list'] = (code)=>{ ... } // 略
  this['str2data'] = (v)=>{ ... } // 略
  this['eval'] = (v)=>Array.isArray(v) ? this[v.shift()](...v.map(w=>this.eval(w))) : v
  this['exec'] = (code)=>this.eval(this.code2list(code)) // 追加
  this['+'] = (...args)=>args.reduce((a,b)=>a+b)
}

console.log(s.exec('(+ 1 2 3 (+ 4 5))')) // 結果:15

これで電卓として機能させることができるようになりました！もちろん今は足し算しかできませんが、引き算や掛け算を追加するのは容易いです！ぜひ試してみてください

ここまでできればあとは様々な関数を追加するだけで独自の言語を自由に拡張することができます！しかし、今回目指しているのはSchemeの仕様に準拠した処理系の作成ですので、もう少し根っこから厳密に実装していく必要があります。

現時点では、数値と文字列をなんとか扱うことができるようになっていますが、Schemeのデータ型は数値と文字列以外にも様々なデータ型が存在します。

次のステップではScheme処理系に近ずけるため、Schemeの根っこである様々なデータ型に対応していきましょう！

STEP3: あらゆるデータ型に対応する

すでに突っ込みたくてウズウズしている方もいらっしゃると思いますが、"I am String"が"\"I am String \""のような形で配列に格納されていて、意味わからんですよね。ダブルクオートも文字列に含まれてしまってるんです！

しかし、アトムと文字列を区別するには仕方ないんです...。(aaa bbb "I am String")を["aaa", "bbb", "I am String"]にしてしまっては、アトムと文字列を区別できませんよね？

ですから「ダブルクオートで囲まれたシンボルは文字列と解釈する」といった方法を取ることで区別ができるわけです。しかしよく考えてみると、そもそもSchemeのデータ型はシンボルと文字列だけではないのです。

種類	型	記法	説明
真	boolean	#f	他言語のfalseやoffに同じ
偽	boolean	#t	他言語のtrueやonに同じ
整数	integer	123	123
2進数	integer	#b101	5
8進数	integer	#o777	511
16進数	integer	#x11F	287
指数表記	integer	#e1e8	100000000
小数	real	.12	0.12
分数	rational	1/2	0.5にならない
複素数	complex	0+4i	0.0+4.0i
文字	char	#\a	a一文字を表す
文字列	string	"abc"	文字の集合
シンボル	symbol	abc	変数名のようなもの
ペア	list	(a . b)	ドット対とも呼ばれる
リスト	list	(a b c)	リンクドリストとも呼ばれる
ベクタ	vector	#(1 2 3)	配列に該当
正規表現	regexp	#/.../i	直接かける

上記のデータ型一覧はGaucheとchibi-schemeを参考にピックアップさせていただきました。実は、こんなにもたくさんのデータ型がSchemeには存在します。

細かいことを言うと、どうやら正規表現はR7RSの仕様ではなく、SRFIとかいうSchemeに更に乗っけて実装する仕様で定義されてるらしいのですが、もうね！どれがR5RSでどれがR7RSで、どれがSRFIなのか？とかっていう仕様分類がめちゃめちゃわかりにくいんですよ！調べてもまともにわからないので、この辺の分類はもう少し実装が進んでから整理することにしました。（誰かcaniuseみたいなの作って！）

話が脱線しましたが、これらたくさんのデータ型に対して「数字だけだから整数」とか「ダブルクオートで囲まれてるから文字列」だとか、そういった記法によってevalされる度に型判定して評価するのは非常に非効率です。

そこでcode2listでコードが渡された時にそういった解釈を先に済ませてしまい、evalで評価されるときには、解釈済みのデータを使って評価できるようにしてみます。

しかし、一体どうやってこの数の型に対応すればいいのだ？？簡単です！全てのデータを配列でラップして識別できるようにするのです！つまり以下のようにします。

['boolean', true] // 真
['boolean', false] // 偽
['integer', 123] // 整数
['real', 0.12] // 小数
['rational', 1, 2] // 分数
['complex', 0.0, 4.0] // 複素数
['char', 'a'] // 文字
['string', 'abc'] // 文字列
['symbol', 'abc'] // シンボル
['vector', [1,2,3]] // 配列
['list', []] // リスト
['regexp', new RegExp(/.../i)] // 正規表現

['list', [['symbol', '+'], ['integer', 1], ['integer', 2]]] // (+ 1 2)

このように全てのデータを配列にします。そして、配列の[0]番目にはデータの型名を記憶し、[1]番目にデータそのものを入れます。

もともと"abc"となっていたデータは['string', 'abc']となり、余計なダブルクオートが取り除かれます。シンボルの場合は['symbol', 'abc']となるため、データが同じでも[0]を参照すればデータ型が得られるためデータ型を区別することができるというわけです。

["+", "1", "2"]となっていたJavaScriptのリストが['list', [['symbol', '+'], ['integer', 1], ['integer', 2]]]となるため、可読性はとてつもなく低下しますが、そもそもJavaScriptが理解できるデータ形式に変換することが重要であり、これら複雑なデータはevalさんが解釈するものであって我々が目にすること無いので何も問題ないのです！

STEP4: リンクドリストを作成する

かつてActionScriptでLISPを実装したとき、僕はコンスセルは必要なのか？と言う疑問を拭きれませんでした。

hojoさんと同じでリンクドリストは配列に似ているのにコンスセルを作成して連結して、わざわざ似たようなリストを作ることに本当に意味があるのだろうか？という思考に陥っていたんです（お前は俺か！）

しかし回答にもあるように、配列とリンクドリストには大きな違いがあります。それは本質的にリンクドリストは全ての要素がポインタで連結されていると言うことです。

配列でcdrを得るにはary.slice(1)を実行すれば同じことができるように思えます。しかしary.slice(1)は、新しく作られた配列を返すため、元の配列とは全く異なる配列を手にします。

しかしcdrはどうでしょうか？cdrはcarの対になったポインタの参照を得るだけで、新しいリストや配列を返したりしません。cdrによって得られる先頭の要素を取り除いたリストは、元々のリストのスタート地点が変わっただけで本質的に同じリストなのです。

回答にもあるように、ドット対はランダムアクセスに向いた構造ではないため、最適化のために内部ではベクターを利用していたりと色々工夫がなされていたりすることもあるようです。また、リストを書き換えることで他の参照の内容にも影響を与えるのは副作用であり、予期せぬ不具合の原因にも繋がるのではないかと考えられます。

ここまで話すといよいよリンクドリストのメリットは無いように思えます。javacommonsさんのコメントで紹介をいただきましたが、newLISPという独自方言のLISPではコンスセルが存在せず、リストは...

配列とリンクドリストの違い

...