WebブラウザでCASL2を試せるCASL2 Playgroundをつくってみた
この記事は個人開発 Advent Calendar 2021の7日目の記事です!
CASL2とは基本情報技術者試験のために策定されたアセンブラ言語です!そのCASL2をWebブラウザ上で書いて実行できるWebサービスをつくりましたという日記です。
なぜつくったのか?
自分が欲しいとかこういう人に使って欲しいという理由ではなく、自分の勉強のためにつくりました。勉強のための車輪の再発明。
今年の2月の記事ですが、「計算機プログラムの構造と解釈」という本を読み始めました。
読み終えたんですけど最後の章「5 レジスタマシンによる計算」がうーむ。。という感じだったので似たようなものつくってみようと思ったのがきっかけです。
アセンブラ言語に全然馴染みがなくパッと思いついたのがCASL2だったので、Webブラウザ上で試せるようなツールをつくってみるか!とTypeScriptで実装しました。UIはJavaScriptでDOMをいじいじ...
「計算機プログラムの構造と解釈」のSchemaで実装されたアセンブラを元に、TypeScriptで実装していく形で実装を始めました。途中で家で積ん読になってた「言語実装パターン」という書籍を見つけこちらも途中から参考にします。最初から読んでいれば...という気持ちになるところもあり、すでに作り直したい部分がちらほら。
「計算機プログラムの構造と解釈」は、先日のブログ記事でも紹介させていただきましたが、hiroshi-manabeさんによる翻訳を読みました。
「言語実装パターン」は、O'Reillyの本です。
開発メモ
アセンブラってなんですか?
「計算機プログラムの構造と解釈」でのレジスタマシンとアセンブラの記述を自分なりのざっくり理解を書くと
- レジスタと呼ばれる記憶素子の中身を操作する命令を順に実行するコンピュータがレジスタマシン
- レジスタマシンを設計するためには、レジスタと演算を表すデータパス、それらの演算を正しく並べるコントローラが必要で、図で書いて表現できる
- だけど複雑になってくるとすぐに図で記述できなくなる
- そこで、レジスタマシン用言語で作って記述しよう。この言語(テキスト形式)を機械語(バイナリ形式)に変換するプログラムがアセンブラ
今回つくろうとしてるものに当てはめると、CASL2という言語をCOMMET2(基本情報技術者試験のために設計された仮想のコンピュータ=レジスタマシン)の機械語に変換し実行する、ということになる。
「言語実装パターン」ではアセンブラは、「パターン26 バイトコードアセンブラ」の章で
と同様のことが記述されてる。
さらに「言語実装パターン」では、アセンブラは4つの重要要素があるとも記述されている。
- 大域データ空間の大きさ
- コードメモリ
- mainプログラムのアドレス
- 定数プール
大域データ空間はメインメモリのことで、COMMET2のメインメモリは、1語16ビットで65536語の容量です。コードメモリというのは、メインメモリにアセンブラによって生成されたバイナリ形式の機械語そのものが格納される、ということ。mainプログラムのアドレスは、メインメモリのどのアドレスがプログラムの開始位置なのかを示す。定数プールは、文字列や浮動小数点、関数名などのオペランドをコードメモリ内に収まらないので別のアドレスに保管することを示していて、CASL2で言うとソースコードに記述されるラベルが該当します。
つまり、テキスト形式のソースコードから変換したバイナリ形式形式の機械語も定数も同じメインメモリ上に置かれる。
と、ここで気がつく。「計算機プログラムの構造と解釈」を読んでいてあまり腹落ちしなかったのは、この機械語とメインメモリとが具体的に出てこなかったからなのでは。メモリもリストとGCのところで抽象化してたからかもしれないなぁ。「計算機プログラムの構造と解釈」の 5 レジスタマシンによる計算 の書き出しを読み直すと以下のように書いてある。
典型的なレジスタマシンの命令は、レジスタの中身に基本的な演算を適用し、その結果をほかのレジスタに割り当てるというものです。レジスタマシンにより実行されるプロセスをこのように記述すると、従来式コンピュータの"機械語"に非常によく似ているように見えます。しかし、ここではある特定のコンピュータの機械語を扱うのではなく、いくつかのLisp手続きについて調べ、それぞれの手続を実行するための個別のレジスタマシンを設計していくことにします。そのため、課題に対する私たちのアプローチは、機械語のプログラマというよりも、ハードウェア設計者としての視点によるものとなります。
「ある特定のコンピュータの機械語を扱うのではなく」のせいでかえって取っ付きづらくなっている気がする。ハードウェア設計者としての視点...ワカラン...
ラベルの取り扱い
CASL2のソースコードを見ていて、普段のプログラミング言語と明らかに違うなぁと思うのはラベル。ソースコードのとある行にラベルづけをしておく。if文で条件分岐するようなことをしたい場合は、条件を満たす場合はラベルAにジャンプ、条件を満たさない場合はラベルBにジャンプというように使う。他にも関数呼び出しのようなことをしたい場合もラベルを使うし、定数名のようにラベルを使うこともできる。
「計算機プログラムの構造と解釈」では以下のように記述されている。
アセンブラは、命令実行手続きを生成する前に、ラベルの参照先をすべて知っておく必要があります。
これは分かるな。例えば以下のようなコードがあったとする。 ADDA
でレジスタ GR1
とラベル TWO
のアドレスにセットされている数値を加算する、というコード。ラベル TWO
に数値 2
がセットされる。
SAMPLE01 START LAD GR1,1 ADDA GR1,TWO TWO DC 2 END
このソースコードを上から順に解析すると、3行目時点ではラベル TWO
がまだ登場していないため、存在するラベルなのか?どの位置を指しているのか?ということが分からない。だから 命令実行手続きを生成する前に、ラベルの参照先をすべて知っておく 必要が出てくる。
まだ登場していないラベル(や関数名や変数や色々)を参照することを前方参照と言うらしい。
ラベルの前方参照とbackpatching
実装としては入力となるソースコードを行ごとでループして走査、 labelMap = Map<Label, Array<行>>
というMapにラベル毎に集約しておく。集約する過程で各行の命令とオペランドからバイト数が分かるのでラベルのメモリアドレスも分かる。集約後、Mapの全エントリをループすることで各行をもう一度走査することで全てのラベルにセットされた値も把握しながら解析できる。
ただこれ、ソースコード全体を2回ループしてるし、同じようなやってるような感じもするけどどうなのか。
「言語実装パターン」の パターン26 バイトコードアセンブラ を読んでみる。アセンブラの変換のパターンとしては「パターン29 構文手動変換器」であると書かれている。ここで言う構文手動変換器とは、入力1行を読んだら変換先の1行を生成する、というもので前方参照を扱えないパターンと書かれている。
ラベルの前方参照ができないと困るじゃないか。
解決策として backpatching という方法が紹介されている。
Labelを表すオブジェクトに isForwardRef
フラグというのを用意する。
type Label = { label: string memAddress: number isForwardRef: boolean }
さらに、「後から前方参照を解決すべき被演算数のリスト」を forwardRefs = Map<string, Array<行>>
で管理する。
const forwardRefs = Map<string, Array<行>>
先程のCASL2コード例をもう一度。
SAMPLE01 START LAD GR1,1 ADDA GR1,TWO TWO DC 2 END
この例だと、アセンブラは入力となるCASL2ソースコード3行目で TWO
というラベルを見つけたときに、以下のようにラベルMapとforwardRefsに追加する。
if (!labels.has("TWO")) { // 前方参照されているラベル(isForwardRef = true)としてラベルMapに追加 labels.set("TWO", { label: "TWO", memAddress: 0, isForwardRef: true }) } operandPos = ... bytecodeList[operandPos] = ... // bytecodeListは最終的に出力する機械語であるバイト列 if (labels.get("TWO").isForwardRef) { // "TWO" を前方参照してるオペランドの位置を追加 if (forwardRefs.has("TWO")) { forwardRefs.get("TWO").push(operandPos) } else { forwardRefs.set("TWO", [operandPos]) } }
4行目で TWO
ラベルが定義されると、「後から前方参照を解決すべき被演算数のリスト」を走査して修正する。
// ラベル "TWO" のアドレス currentMemAddress = ... if (!labels.has("TWO")) { labels.get("TWO").memAddress = currentMemAddress labels.get("TWO").isForwardRef = false } ... forwardRefs.get("TWO").forEach(operandPos => { bytecodeList[operandPos] = currentMemAddress })
こういうイメージか。たしかにソースコードの行すべてをもう一度走査することに比べたら「後から前方参照を解決すべき被演算数のリスト」を走査した方が効率良さそう。
構文手動変換器パターンのように、ソースコード全体を1回だけ走査することを1パスと呼ぶみたい。1パスは単純だけど、そのままだと前方参照ができない、入力と大きく並び順が異なる出力を生成できない、といったデメリットがある。1パスに対して、そうでないものをマルチパスと呼ぶらしい。
おわりに
学びたいポイントが次から次へと出てきて困るけど楽しいという感じでした!
自分の実装は、アセンブラとして機械語を生成する処理と、Commet2上で動きをシミュレートするための関数と、両方をごちゃっと実装してしまっている感じがあって分かりづらい。Commet2で動かす部分については「言語実装パターン」に書かれている パターン28 レジスタ方式バイトコードインタプリタ を参考しながら機械語を入力とするインタプリタとして作り直すと良さそう。
他にもbackpatchingで書き直したり、全然別の構文手動変換器ではない変換器をつくってみたりもしたいなぁ。
コーチングを受けてみた
元同僚と話していたら、いつのまにか(セミプロ?)コーチになっていたのでコーチングしてもらいました!という日記です。
急だったにも関わらずやってくれて @katsutomu に感謝です!
初めての経験だったのでどんな感じなんだろ?という気持ちで受けたのですが、結果的に気がついたことが多くありとても楽しく有意義な時間でした。コーチのスキルが良かったからなのか元々よくコミュニケーションをとっていた元同僚だったからなのか、自分自身の本音がぽろぽろ口から出てくる感じでとても良かったです。逆に言うと関係値が構築できていないコーチの場合はどういう風に進むのかなぁと気になりました。まずは関係を深めるところから徐々に進めていくのだろうか。
良かったところ
印象に残ってるのは、「コーチと私」と「私自身」の対話、というイメージですよと最初に説明してくれたところ。
このイメージを最初にできたことが本音で話す助けになっていたと思う。普段誰かとコミュニケーションを取る時には、相手と自分自身の間に「外向け用の自分」がプロキシサーバーのように機能していて、そのプロキシが相手に嫌な思いをさせてしまいそうな自分自身の本音を遮ったり逆に相手からの発言の意味を組み替えてしまって自分自身に伝えたりしているよなぁと。コーチングの時間は自分自身をコーチにさらけ出す時間だよと最初に説明してくれたことが良かったのかも。
もう1つ上記のイメージが良かったのは、自分自身と対話するのが自分だけではないところ。1人で内省するときなんかは「自分と自分自身」の対話になるけれど、その対話の中では色々なことを思いつくがスッと流してしまうこともある。自分では流してしまった考えをコーチが拾い上げてくれることで、自分の中に強く印象づけることができて良かった。新しいことを思いつくというよりは「昔も考えたことあったけどあんまり重要視してなかったなぁ、けどこれめっちゃ大事なことじゃん!」というような気づき。
ピンと来ていないところ
今回はお試しというか急だったので1回だけコーチングしてもらったけど、あんまり分かっていないのが本来はある程度の期間で複数回やった方が良いものになるんだろうなぁというところ。コーチングで色々得られるものはありつつも行動しないと意味ないし、行動の結果を改めてコーチと話すべきなのだろうと思う。コーチングの中でどういうアクションをしましょうか?という話があったけど、そのアクションを取ることがとても重いと感じる場合は次のコーチングの予定まで決めてしまったほうが良さそう。締め切り駆動的な。
おわりに
というわけでコーチングを受けていた時間はとても楽しかったです。自分自身との対話が好きだったり、自分の思考の仕方に興味があったり、本当の価値観を知りたい、みたいな人にとっては楽しいのではないでしょうか?こうやって書いてみると、解決したい何かにぶつかった時に自分のことをよく知ってることって大事なんだな〜。
SICPを読み始めた
SICPを何年か前に読んでいたのですが、途中まで読んでそのまま積ん読になってました。そのことをふと思い出したのでまた読み始めております。読みながらコード書く時の環境についての日記です。
SICPとは計算機プログラムの構造と解釈という本の略称。
翻訳したPDFを公開してくれている方がおり、とても感謝です。
どんな感じで読もうか
REPLを使う( Guile + rlwrap )
読みながらコード写経したくなったり問題を解きたいときがあります。そういうときはGuileのREPLを使ってます。PCはmacかchromebookか日によって。
guile
で起動して、 ,h
でヘルプ、 ,q
で終了。
$ guile scheme@(guile-user)> (+ 1 2) $1 = 3 scheme@(guile-user)> ,h Help Commands [abbrev]: ,help [all | GROUP | [-c] COMMAND] [,h] - Show help. ... scheme@(guile-user)> ,q
このままだと、 Ctrl-p
や Ctrl-a
が効かず辛いのでrlwapを使います。rlwrapは対話モードで動くようなコマンドにreadlineの機能を後付けして、コマンド履歴を Ctrl-p
で遡れるようにしたりEmacsキーバインドを使えるようにしてくれます。
guile単体で起動して Ctrl-p
すると以下のようになる。
$ guile scheme@(guile-user)> (+ 1 2) $1 = 3 scheme@(guile-user)> ; Ctrl-pを入力すると... scheme@(guile-user)> ^[[A ; Ctrl-p が使えない!
rlwrapといっしょに使う。rlwrap便利!
$ rlwrap guile scheme@(guile-user)> (+ 1 2) $1 = 3 scheme@(guile-user)> ; Ctrl-pを入力すると... scheme@(guile-user)> (+ 1 2) ; 履歴が使える!
ファイルに書いて読み込む
関数の行数が増えてくるとREPLで記述するのが辛いし間違えて消しちゃったら悲しいので、VS Codeで書いてファイルに保存してからREPLで読み込んで実行してます。
VS Codeのscheme拡張機能でコードハイライトとインデントづけを楽に。
rlwrapの -c
オプションを使うとファイル名の補完が効くので便利。
;; fib.scm (define (fib x) (cond ((= x 0) 0) ((= x 1) 1) (else (+ (fib (- x 1)) (fib (- x 2))))) )
$ rlwrap -c guile scheme@(guile-user)> (load "fib.scm") ; tabでファイル名の補完が効く! scheme@(guile-user)> (fib 5) $1 = 5
,trace
,trace使うとこんな風に表示される。
scheme@(guile-user)> ,trace (fib 5) trace: (fib 5) trace: | (fib 3) trace: | | (fib 1) trace: | | 1 trace: | | (fib 2) trace: | | | (fib 0) trace: | | | 0 trace: | | | (fib 1) trace: | | | 1 trace: | | 1 trace: | 2 trace: | (fib 4) trace: | | (fib 2) trace: | | | (fib 0) trace: | | | 0 trace: | | | (fib 1) trace: | | | 1 trace: | | 1 trace: | | (fib 3) trace: | | | (fib 1) trace: | | | 1 trace: | | | (fib 2) trace: | | | | (fib 0) trace: | | | | 0 trace: | | | | (fib 1) trace: | | | | 1 trace: | | | 1 trace: | | 2 trace: | 3 trace: 5
末尾再帰の形に書き換えると、反復処理になってることが分かる。ちなみに fib
内部で fib-iter
を記述すると ,trace
の出力にでてこない、残念。出力させる方法あるのかな。
;; fib.scm (define (fib x) (fib-iter x 1 0) ) (define (fib-iter x a b) (cond ((= x 0) b) (else (fib-iter (- x 1) (+ a b) a))) )
scheme@(guile-user)> ,trace (fib 5) trace: | (fib 5) trace: | (fib-iter 5 1 0) trace: | (fib-iter 4 1 1) trace: | (fib-iter 3 2 1) trace: | (fib-iter 2 3 2) trace: | (fib-iter 1 5 3) trace: | (fib-iter 0 8 5) trace: | 5
おしまい
こんな感じで読み進めて行こう。問題解いたらとりあえずgistに追加していこっかなぁ。