4. アセンブリ言語を読んでみよう
前回、パーザがWhitespaceのhelloworldプログラムをパーズして生成したリストは構造的には一種のアセンブリ言語だ、と言う話をした。
再録してみる。
'((Push 0)
(Push 72)
(Store)
(Push 1)
(Push 101)
(Store)
(Push 2)
(Push 108)
(Store)
(Push 3)
(Push 108)
(Store)
(Push 4)
(Push 111)
(Store)
(Push 5)
(Push 44)
(Store)
(Push 6)
(Push 32)
(Store)
(Push 7)
(Push 119)
(Store)
(Push 8)
(Push 111)
(Store)
(Push 9)
(Push 114)
(Store)
(Push 10)
(Push 108)
(Store)
(Push 11)
(Push 100)
(Store)
(Push 12)
(Push 32)
(Store)
(Push 13)
(Push 111)
(Store)
(Push 14)
(Push 102)
(Store)
(Push 15)
(Push 32)
(Store)
(Push 16)
(Push 115)
(Store)
(Push 17)
(Push 112)
(Store)
(Push 18)
(Push 97)
(Store)
(Push 19)
(Push 99)
(Store)
(Push 20)
(Push 101)
(Store)
(Push 21)
(Push 115)
(Store)
(Push 22)
(Push 33)
(Store)
(Push 23)
(Push 0)
(Store)
(Push 0)
(Call write)
(Call newline)
(End)
(Label add)
(Infix Plus)
(Return)
(Label write)
(Dup)
(Retrieve)
(Dup)
(If Zero write_end)
(OutputChar)
(Push 1)
(Infix Plus)
(Jump write)
(Label write_end)
(Discard)
(Discard)
(Return)
(Label read)
(Dup)
(Dup)
(ReadChar)
(Retrieve)
(Dup)
(Push 10)
(Infix Minus)
(If Zero read_end)
(Discard)
(Push 1)
(Infix Plus)
(Jump read)
(Label read_end)
(Discard)
(Push 1)
(Infix Plus)
(Push 0)
(Store)
(Return)
(Label newline)
(Push 10)
(Push 13)
(OutputChar)
(OutputChar)
(Return))
この生成されたコードはリストの先頭から逐次実行される性質のものだ、と言うのが基本だが、細かく言うと逐次実行の対象はリストの先頭からEndまで、と言う事である。
それ以降はLabelで定義されてるサブルーチンと呼ばれるプロセスの集合となっている。
例えば次の部分を抜書してみる。
(Label write)
(Dup)
(Retrieve)
(Dup)
(If Zero write_end)
(OutputChar)
(Push 1)
(Infix Plus)
(Jump write)
(Label write_end)
(Discard)
(Discard)
(Return)
ここは、高級言語風に言うと「write」と「write_end」と言う関数を書いてるのと同等である。
細かく見て行きたくはないんだが(笑)、こういうBASIC辺りでお馴染みのベタ書きの逐次実行のプロセスだと確かにフローチャートなんぞを書いた方が概要を掴みやすいかもしんない。
ちなみに、これらの「命令」をHaskell原作では「Instruction」と呼んでるが、一般にアセンブリ言語上の命令はニーモニック、等と称する。
ある意味前回出した「構文」の再掲だが、各ニーモニックの意味は次のようになっている。
大まかにはサブルーチン「write」は「Jump」を用いたループ構造になっていて、「If Zero」が条件を満たした時、サブルーチン「write_end」に飛ぶようになっている。
そしてサブルーチンwrite_endの最後に注目してもらいたい。Returnが鎮座している。
いつぞや書いたが、これがC言語やPython等のreturn文の元ネタ、である。制御を呼び出し側へ「返す」からReturnなのだ。呼び出し側がどこなのか、と言うと当然メインルーチン内でCall writeした位置である。
メインルーチンを精査してみれば分かるだろうが、Call writeが終わったら次はCall newlineして、newlineが実行された後、同じ場所へとReturnされる。
そしてEndを迎えてプログラムは無事終了するのである(※1)。
どうだろうか?これがアセンブリレベルでの「コンピュータの動き方」であり、これなら「コンピュータの仕組み」がある程度理解可能だろう。
実際問題、現時点ではWhitespaceに於いて、構文解析した時点でアセンブリ言語へとコンパイルされてて(通常こんなに簡単にはいかない※4)、それぞれの「命令」は、メモリの「番地」とも結びついている・・・吐き出したアセンブリの第一行目はメモリの0番地に対応してて第二行目はメモリの1番地に対応してて・・・になってる(機械語的には本来、バイナリになるべきだが)。
この辺は後に仮想機械を作った時点でよりハッキリするだろう。
いずれにせよ、念仏のように「C言語を学べばコンピュータの仕組みが分かる」とか唱えてるより、どんな言語でもいいからWhitespaceを実装してみたほうが、よりコンピュータの仕組みは分かるんじゃないかな、と思う。
さて、構文解析器の残り、補助関数をちょっと見ていこう。
5. パーザの補助関数を見てみよう
まずはHaskellでの原版を覗いてみる。
parseNumber :: Num x => [Token] -> (x, [Token])
parseNumber ts = parseNum' ts []
where
parseNum' (C:rest) acc = (makeNumber acc,rest)
parseNum' (x:rest) acc = parseNum' rest (x:acc)
parseString :: [Token] -> (String, [Token])
parseString ts = parseStr' ts []
where
parseStr' (C:rest) acc = (makeString acc,rest)
parseStr' (x:rest) acc = parseStr' rest (x:acc)
makeNumber :: Num x => [Token] -> x
makeNumber t
| (last t) == A = makeNumber' (init t) 1
| otherwise = -(makeNumber' (init t) 1)
where
makeNumber' [] pow = 0
makeNumber' (A:rest) pow = (makeNumber' rest (pow*2))
makeNumber' (B:rest) pow = pow + (makeNumber' rest (pow*2))
makeString :: [Token] -> String
makeString [] = ""
makeString (t:ts) = (show t)++(makeString ts)
実はparseNumberとparseString、makeNumberとmakeStringと言うそれぞれの関数はやってる事はほぼ同じである。
parseNumberはRefとSlideを見かけると、以降のWhitespaceコードで#\newlineが出てくるまでを全て符号付き二進数として解釈する。
parseStringはLabel、Call、Jump、If Zero、そしてIf Negativeを見かけると、以降のWhitespaceコードで#\newlineが出てくるまでを全て二進数として解釈する。
うん、ほぼ同じなのだ。
この辺はRacket/Schemeでそのまま一気に翻訳が可能だ。
(define (parseNumber ts)
(let loop ((ts ts) (acc '()))
(let ((x (car ts)) (rest (cdr ts)))
(if (char=? x #\newline)
(values (makeNumber acc) rest)
(loop rest (cons x acc))))))
(define (parseSymbol ts)
(let loop ((ts ts) (acc '()))
(let ((x (car ts)) (rest (cdr ts)))
(if (char=? x #\newline)
(values (makeSymbol acc) rest)
(loop rest (cons x acc))))))
全く構成が同じだ、と言う事が分かるだろう。
二つ注意点がある。
Haskellはラムダ算法に従った純粋関数型言語で、原理的には一つしか引数が取れないし、返り値も一つだけ、と言う縛りがある(忘れてるかもしれないが、中学校数学辺りで、関数は定義域と値域で1対1対応が原則だ、と習ったと思う)。
しかし、返り値を二つ想定したい場合、リストとして返す事は可能だ。
そしてその返り値の受け取り側は、アンパックと言う機能によってリストをバラバラに分解する事が出来る。
これはどっちかと言うとPythonのタプルによるreturnとアンパッキングに近い。
>>> t = 12345, 54321, 'hello!'
>>> x, y, z = t
>>> x
12345
>>> y
54321
>>> z
'hello!'
>>>
一方、Racket/Schemeにはこういう「アンパック」と言う機能はない。
しかし、HaskellやPythonの「擬似的に複数の値を返す」のではなく、もっと強力な「複数の値をそのまま返す」機能がある。これを多値と言う。
Racket/Schemeではvaluesと言う関数で複数の値を同時に返す事が可能となっており、結果、parseNumberとparseSymbolは多値を返す関数となっている。
結局、両者とも関数parseからケツまでのWhitespaceのコードを受け取り、最初に#\newlineを見つけるまで二進数のシーケンスとして本体に保持し、数値なり文字列(と言うかRacket/Scheme版ではシンボル)に変換して「Whitespaceのコードの残り」と合わせてparseに返さなければならない。
この多値を受け取る側で必要なのがlet-values(※2)である。
> (let-values (((x y z) (values 12345 54321 "hello!")))
(list x y z))
'(12345 54321 "hello!")
>
もう一つは、気づいた人は気づいたろうが、Haskell原版ではparseStringだった関数がRacket/Scheme版だとparseSymbolになっている。
Haskell原版だとLabel名を付ける際にその名前を文字列で表現してる、と言う事だ。一方、文字列を生成してはいるが、これらは実際の出力には全く使われない。
Lispの場合、Label名を判定する際、文字列を利用するよりシンボルを使った方が圧倒的に速く効率的なのだ(※3)。よって出力が関係しないのなら、Label名をシンボルにするのがLispでは定石なのである。
あとは、実際に変換を司ってるのがmakeNumberとmakeSymbolである。
まずはRacket/Schemeに翻訳されたmakeNumberから見ていこう。
(define (makeNumber t)
(let ((sign (last t)) (ls (reverse (take t (- (length t) 1)))))
(if (null? ls)
0
(let ((num (string->number
(list->string
(map (lambda (x)
(cond ((char=? x #\space) #\0)
((char=? x #\tab) #\1))) ls)) 2)))
(if (char=? sign #\space)
num
(- num))))))
まずはRacket/Schemeでの二進数の取扱に関して。
元々Racket/Schemeでは二進数は#b0、#b1として表現が可能だが、これらは即、Racket/Schemeでは十進数として評価されてしまう。
このプログラムのように、バイト表現を用いる場合、面倒臭いようだがRacket/Schemeでは一旦文字列に変換して扱う。
具体的には、数を文字列に変換するnumber->stringや文字列を数に変換するstring->numberを用いる。
;; 12を二進数表記に変換する> (number->string 12 2)
"1100";; 二進数表記での"100"を十進数表記に変換する> (string->number "100" 2)
4
>
makeNumberはparseNumberからリストを受け取るが、そのリストはparseNumber内のconsingから生成されたリストで、逆順になっている。
このリストは符号付き二進数を意図してる為、結果、リストのケツは「符合」を意味している。つまり、ここが正の整数なのか負の整数なのかの判定になるわけだ(※5)。
あとはmap関数で残りの部分を数値として解釈出来るように組めば良い。#\tabなら#\1、#\spaceなら#\0と言う文字に変換し、結果、文字のリストを構成してそれをlist->stringで文字列に変換、そしてそれをstring->numberで数値として解釈する。
以上で#\spaceと#\tab表現によるバイナリは無事数値に変換されるわけだ。
;; '(#\space #\space #\tab #\space)は二進数"0100"の逆順を意図してる> (makeNumber '(#\space #\space #\tab #\space))
4;; '(#\space #\space #\tab #\tab)は二進数"1100"の逆順を意図してる
> (makeNumber '(#\space #\space #\tab #\tab))
-4
>
次はmakeSymbolを見ていこう。
この部分は、Haskell原作より複雑になっている。
理由はこうだ。
実は最初のバージョンだと、これで充分じゃないか、と思っていた。
(define makeString list->string)
これならHaskell原作より短く書ける。
ところが、実際問題、これだと「何がLabelとして定義されているのか」読めない。
しかしながら、恐らくHaskell原作でもここは「読まれる」意図になっていない(なんせ出力の為の文字列ではない事はもはや明確である)。
プログラミング言語の「内部で」受け渡す形式を内部表現、等と称しているが、これは実は人に読まれる事を前提としていない。要するにあるLabelとあるLabelが同じ、あるいは違う、って事さえ確定出来ればいいわけで、人が読めるかどうか、と言うのは関係ないわけだ。
Haskell原作ではトークンを型として定義してるがここで提案されてるshowは文字列での各種の表現しか見せていない。
従って、makeStringに使われてるshowに従って、「何らかの意図/完成された文字列」を返すのではなく、単に#\spaceと#\tabだけで構成された文字列を返す事を意図してると思われる。
> (makeString '(#\space #\tab #\space #\space #\space #\space #\space #\tab))
" \t \t"
>
まぁ、確かに内部表現ならこれで充分ではあるのだ。
ただし、それじゃあ面白くない、ってのが一つ。
もう一つは先程書いた通り、Lispでは文字列同士を比較するよりシンボル同士を比較した方が速い。
そして一体、WhiteSpaceの作者が「Labelとして何を名付けたかったのか」知りたかった、と言う事もあり、Haskell原作よりも複雑な関数を書く事に決めたのである。
前提として、手渡されるリストはmakeNumberと同様に実は逆順であるビット列である。
そして1文字を構成するビット数は8ビットが前提となる。何故ならこれはアスキーコードだからだ。
結果、手渡されるリストの長さは、必ず8の倍数になってないといけない。
これらを前提としてmakeSymbolを書くと、次のようなコードになる。
(define (makeSymbol ls)
(let loop ((s (string-map (lambda (x)
(cond ((char=? x #\space) #\0)
((char=? x #\tab) #\1)))
(list->string (reverse ls))))
(acc '()))
(if (string-null? s)
(string->symbol (list->string (reverse acc)))
(loop (string-drop s 8)
(cons (integer->char (string->number (string-take s 8) 2))
acc)))))
基本的な処理はやはりmakeNumberと同じである。受け取るリストがビット列を意図してる、と言うのは同じだからだ。ただし、それを「数」として解釈するのか、あるまとまった長さの部分を「文字」として解釈するのか、が違う。
ローカル変数sは受け取ったリストを完全なビット列へと変換したものとしている。string-mapは文字列の為のマッピング関数である。
あとは再帰で用いるcar代わりにstring-take、cdr代わりにstring-dropを用いてる。これらはSRFI-13に含まれてる関数で、生成された文字列sから8文字づつ消費する為に使われている。この時点で文字は#\0か#\1かのどっちかであるが、8文字単位でアスキーコードを意図した表現になっているからだ。
従って、8文字でのビット列をまずは整数に変換し、「その整数が意図する文字」へと変換する為にinteger->char関数を用いている。
要するに、次のような事を行っているわけだ。
;; 二進数"01000001"は65であり、アスキーコードで65は#\Aである> (integer->char (string->number "01000001" 2))
#\A;; 二進数"01000010"は66であり、アスキーコードで66は#\Bである
> (integer->char (string->number "01000010" 2))
#\B
>
これをアキュムレータaccにconsしていき、終わったら逆順に並べ替えてlist->stringを適用して文字列にし、それをstring->symbolでシンボルへと変換して返している。
実際問題、最初はマジでラベルに何を意図した「文字列」を付加してるのか、サッパリ分からなかったのだが、この関数を作って構文解析したら意味のあるラベルになっていたため、原作者はキチンとした意図を持ってWhilespaceでのHello Worldプログラムを書いてたんだな、と分かってホッとしてた。
さて、これで構文解析部は終了だ。
残りは本体の仮想マシンを組み立てよう。
6. WhiteSpace仮想マシンを作ろう
Whitespace仮想マシン(Virtual Machine)の名前はそのままvmである。
まずはRacket/Schemeで書かれたvmの定義を見てみよう。
(define (vm prog stack cstack heap pc)
(let ((instr (list-ref prog pc)))
((doInstr prog stack cstack heap (+ pc 1)) instr)))
まずは前回の最初の方に書いてた事を押さえておこう。
ここから仮想CPU、あるいは仮想コンピュータを作っていく。
とは言ってもあまり緊張はせんように。
前回書いてた通り、この仮想CPUはメモリが4本別々に挿さっている設計になってて、その4本が
- prog: パーザが生成したアセンブリを保持しておく記憶領域
- stack: 数値をpushしたりpopしたりするスタック
- cstack: コールスタック
- heap: ヒープ
である。
加えてCPUはプログラムカウンタ(pc)も持ってないとならない、と言うのも前回説明した。
そしてプログラムカウンタとprogは連動している。いや、連動するように設計する、と言うべきか。
パーザが生成したアセンブリは今まで見てきた通りリストのリストであり、要素の方のリストは低レベルの命令、ニーモニックを含んでいる。そしてpcが0の時、大枠のリストの第0要素を実行し、pcが1の時大枠のリストの第1要素を実行し・・・と関連付けられているのだ。
つまり、生成されたアセンブリは僕らが(比較的)読みやすい形式となってるが、ここでは実際にメモリ上に展開されてる、って考えて良い。幸いな事に機械語にはさすがになっていないが、それは仮想マシンがそういう設計になってるから、に過ぎない。実際、かなり現実的なCPU＋メモリの構造をこのプログラムはなぞっている、って考えて良い。
今実行すべき命令がインストラクション(inst)で、それはprogのpc番目に位置している。progは先程書いた通りリストのリストなんで、実行すべきインストラクションはRacket/Schemeの組み込み関数list-refで引っ張ってこれる。
そして実際の動作振り分けはdoInstr関数が担っている。これが端的に言うとLisp等のインタプリタで言うEval(evaluator: 評価器)に相当し、現実のCPUで言うと内部的な各種演算回路だ。
ここではdoInstr関数は関数を返す高階関数として設計されており、返り値の関数はinstを引数とする(だからカッコが多いように感じるだろう)。
また、doInstr関数が呼び出された時点でプログラムカウンタが1進められる。よって次の命令を実行する準備は常に整ってる、と言う事だ(※6)。
あとはdoInstr関数を書くだけ、だが、要は上の方に上げた表に従って、スタック、コールスタック、ヒープを弄ったvmを返せば良い。つまり、関数としては長いが作業としては単なる「消化作業」なのだ。ある意味実は一番ラクなパートである(構文解析器を書く方が手間だった・笑)。
(define (doInstr prog stack cs heap pc)
(lambda (instr)
(case (car instr)
;;; スタック操作
;; 数値をスタックに積む
((Push) (let ((n (cadr instr)))
(vm prog (cons n stack) cs heap pc)))
;; スタックの一番上を複製する
((Dup) (let ((n (car stack)))
(vm prog (cons n stack) cs heap pc)))
;; スタックのi番目をコピーして一番上に積む
((Ref) (let ((i (cadr instr)))
(vm prog
(cons (list-ref stack i) stack)
cs heap pc)))
;; スタックの一番上を残しそこからi個削除する
((Slide) (let ((i (cadr instr)) (n (car stack)))
(vm prog
(cons n (drop (cdr stack) i))
cs heap pc)))
;; スタックの1番目と2番目を交換する
((Swap) (let ((n (car stack)) (m (cadr stack)))
(vm prog
(cons m (cons n (cddr stack)))
cs heap pc)))
;; スタックの一番上を捨てる
((Discard) (vm prog (cdr stack) cs heap pc))
;;; 演算
((Infix) (let ((op (cadr instr))
(y (car stack))
(x (cadr stack)))
(vm prog
(cons ((case op
((Plus) +)
((Minus) -)
((Times) *)
((Divide) /)
((Modulo) modulo))
x y) (cddr stack))
cs heap pc)))
;;; I/O (入出力)
;; スタックの一番上を文字として出力する
((OutputChar) (let ((n (car stack)))
(write-char (integer->char n))
(flush-output)
(vm prog (cdr stack) cs heap pc)))
;; 一文字読み込み、スタックの一番上が指し示すヒープ上の場所を書き換える
((ReadChar) (let ((loc (car stack))
(ch (read-char)))
(let ((hp
(store (char->integer ch) loc heap)))
(vm prog (cdr stack) cs hp pc))))
;; 数字を一つ読み込み、スタックの一番上が指し示すヒープ上の場所を書き換える
((ReadNum) (let ((loc (car stack))
(ch (read-line)))
(let ((num (string->number ch)))
(let ((hp (store num loc heap)))
(vm prog (cdr stack) cs hp pc)))))
;; スタックの一番上を数値として出力する
((OutputNum) (let ((n (car stack)))
(write-string (number->string n))
(flush-output)
(vm prog (cdr stack) cs heap pc)))
;;; フロー制御
;; ラベルを付ける
((Label) (let ((_ (cadr instr)))
(vm prog stack cs heap pc)))
;; サブルーチンを呼ぶ
((Call) (let ((l (cadr instr)))
(let ((loc (findLabel l prog)))
(vm prog stack (cons pc cs) heap loc))))
;; ラベルへと飛ぶ
((Jump) (let ((l (cadr instr)))
(let ((loc (findLabel l prog)))
(vm prog stack cs heap loc))))
;; 条件を満たした時、ラベルへと飛ぶ
((If) (let ((t (cadr instr))
(l (caddr instr))
(n (car stack)))
(if ((case t
((Zero) zero?)
((Negative) negative?)) n)
(let ((loc (findLabel l prog)))
(vm prog (cdr stack) cs heap loc))
(vm prog (cdr stack) cs heap pc))))
;; サブルーチンを終了し、制御を呼び出し側へ戻す
((Return) (let ((c (car cs)))
(vm prog stack (cdr cs) heap c)))
;;; ヒープアクセス
;; ヒープに書き込む
((Store) (let ((n (car stack)) (loc (cadr stack)))
(let ((hp (store n loc heap)))
(vm prog (cddr stack) cs hp pc))))
;; ヒープを参照する
((Retrieve) (let ((loc (car stack)))
(let ((val (retrieve loc heap)))
(vm prog (cons val (cdr stack)) cs heap pc))))
;;; フロー制御
;; プログラムを終了する
((End) (format #t "Done.~%Stack size ~a~%Heap size ~a~%"
(length cs) (length heap)))
(else (error "Can't do " (car instr))))))
コメントも付けているので、特に詳細に立ち入る必要もないだろう。どれも極端に言うとvmのメモリ操作に終始してる、ってのが実際だ。
ただし、注意点がいくつかある。
まず1つ目。この関数は関数を返す関数、つまり高階関数として設計されている。
従って、全体的にはラムダ式を返す、と言うのがその役割で、それが冒頭の(lambda (inst)〜である。
2つ目。各インストラクションはリストとなってる。ニーモニックはそのリストのcarなのでcase構文上、判定すべき場所は一律(car instr)になってる。
ただし、各ニーモニックは、既にお気づきの事と思うが、引数を取るケースと取らないケースがある。(cadr instr)はニーモニックが引数を引き連れているケースに対応している。
3つ目。スタック操作に混乱しない(笑)。特に演算上で複数popする場合があるのでその時のスタック処理には気をつける事(※7)。
4つ目。Label命令だが、仮想マシン上では実は「何もしていない」。
これは初見だと不思議かもしれないが、良く考えてみると、受け取ったプログラムには既にラベルが添付されてるので、doInstr側で特に新しく何かする必要がないのだ。
あくまでdoInstrはラベルが付けられた部分にジャンプする使命はあるが、それ以上の事をする必要がないのである。事実、上のコード的には「何も無かったように」vmをそのまま呼び出している。
言い換えると「ラベルを付ける」と言うのはコンピュータ側への司令ではなく、コンパイラ(この場合は構文解析器)自身への命令で、コンピュータには何も関係がない、と言う事なのだ。
5つ目。Haskell原作ではEndは空リストを返す事で終了動作としてたが、コンパイル済みのコードを実行すると終了メッセージ等が表示されてたので、ここでもその実装に従うようにした。
以上である。
これを「言語設計」から始めれば大変なのは事実だが、先に挙げたニーモニックの表なんかがあればこれを組み立てるのはさして難しくない。
そう、仕様さえキチンとしてれば何とかなるものなのだ。
次にdoInstr関数の補助関数、ヒープ操作関数の中身を見てみよう。
7. Whitespace仮想マシンの補助関数を書こう
まずは前項のdoInstrに対する注意点その4、ラベル関連に絡む補助関数を書く。
その名もそのまんまfindLabelで、progの内容から欲しいラベルがある「位置」を探してくる関数である。
(define (findLabel l p)
(let loop ((p p) (i 0))
(if (null? p)
(error "Undefined label" l)
(let ((m (car p)))
(if (and (eq? (car m) 'Label) (eq? (cadr m) l))
i
(loop (cdr p) (+ i 1)))))))
何度も書くが、アセンブリを読み込んでるprog変数は事実上、アセンブリ(と言うか機械語)が展開されたメモリと言って良い。従って、リストの要素番号はそのままメモリのアドレス番号を意味している。
結局、この関数はラベル名をヒントに必要なメモリアドレスをサーチして返す関数なのだ。
何故それが必要なのか、と言うと繰り返すがprogが象徴するメモリのアドレスはプログラムカウンタに対応してる。要するにジャンプする際にここで拾ったメモリアドレスでプログラムカウンタを書き換えるのである。
残りはヒープ操作だ。ヒープから値を参照してくる関数retrieveとヒープの値を書き換えるstore関数を定義する。
まずはretrieveから。とは言ってもこれを書くのは難しくはない。なんせ、機能的にはRacket/Schemeビルトイン関数であるlist-refそのもの、である。
よって名前を書き換えるだけ、で済む。ただし、Haskell原作に合わせて引数の順番を交換するだけ、だ。
(define (retrieve x heap) (list-ref heap x))
これでオシマイ。簡単だね!
残るはstoreだけ、だ。
HaskellはLisp語族より厳格な関数型言語で、破壊的操作を一切許さない。
従って「メモリを書き換える」のも非破壊操作にしなければならない、と言う前提があり、結果、若干込み入った関数となっている。
store :: Integer -> Integer -> Heap -> IO Heap
store x 0 (h:hs) = return (x:hs)
store x n (h:hs) = do hp <- store x (n-1) hs
return (h:hp)
store x 0 [] = return (x:[])
store x n [] = do hp <- store x (n-1) []
return (0:hp)
基本的にはリストをコピーしてパターンマッチングにより分解、そして任意の位置のcarをすげ替えて新しいリストを生成する、と言う手順を踏んでいる。
しかし、これを直訳するとRacket/Schemeにはちと効率が悪い、って事になる。
そう、再帰のせいだ。
Haskellでは末尾再帰は意図しては使わない。と言うのも遅延評価前提の言語なので、フツーに再帰しても非効率ではないのだ。
逆にHaskellで末尾再帰すると、意図に反して無限ループに陥ったりする。なかなかRacket/Scheme観点では厄介な性質を持っている。
結局任意の位置でリストをheadとtailに分解して、(cdr tail)に値をconsして再びheadとappendすればいいだけ、なのでstoreはRacket/Scheme用に一から作った方が良い。リストの分解関数はSRFI-1でsplit-at関数として提供されてるし(※8)。
(define (store x n Heap)
(let ((h (length Heap)))
(if (< n h)
(let-values (((head tail) (split-at Heap n)))
(append head `(,x) (cdr tail)))(append Heap (make-list (- n h) 0) `(,x)))))
中でmake-listを使ってるのは仮に値の挿入位置が現時点のヒープのサイズより大きかった場合、ヒープのケツからその挿入位置まで0で埋め尽くす為、である。それがHaskell原作の仕様の要求である。
さて、これでWhitespaceは殆ど完成である。
8. 実行関数を作ろう
あとはHaskell原作に従って実行関数を作るだけ、である・・・・・・が、実はこれが複合バグの原因であった(笑)。
取り敢えず、実行関数executeは次のようになる。
(define (execute fname)
(let ((prog (string-append (read-file fname) "\n")))
(let ((tokens (tokenize prog)))
(let ((runtime (parse tokens)))
(vm runtime '() '() '() 0)))))
単純にファイル名を引数とし、Whitespaceプログラムを読み込み、トーカナイズし、パーズして仮想マシンを呼び出すだけ、である。
そして仮想マシンの初期状態はプログラム(今まで見てきて分かるだろうが、構文解析器が返してきたアセンブリ)を保持し、スタック、コールスタック、ヒープは全て空リスト、そしてプログラムカウンタは0に合わせておく。
しかし、気づく人は気づくだろうが、ファイル読み込みがちと素直ではない。
(string-append (read-file fname) "\n")
何で改行文字と連結させてるんだ?と言う話になるだろう。
いや、実はここが複合バグの原因だったのだ。
どの言語でも大抵そうだが、ファイル読み込みの為の「パーツ」は提供してるが、簡単に使えるファイル読み込み用の関数が存在しない。
Pythonなんかでもファイルを読み込ませる度に何らか長ったらしい事を書かなければならなくってウンザリする。それはSchemeでも事情は変わらない。
とにかくファイル操作は書きたくないのだ。メンド臭い。
一方、Haskell原作を読むと、Haskellには副作用目的のreadFile関数と言うのがビルトインで存在してる模様だ。
まぁな、Haskellでは副作用を目の敵にしてるような設計をしてる為(笑)、モナドと言う数学理論を学ばないと使えない、と言うどーしよーもない性質がある。
それじゃいくら何でもアレなんで、readFileとかファイル操作を簡単に行える関数を用意してくれてるんだろう。偉い。
でも何かRacketでビルトインで使えるreadFileみてぇな関数がねぇのかな、とか探したらあった。それがこれ、read-fileだったの。しめしめ、と。
ところがコイツが複合バグの原因だったのだ(怒
端的に言うと、こいつがファイルを読み込むと、ファイル末尾の改行文字を勝手に削除した文字列を返すんだな(笑)。それでWhitespaceのコードがぶっ壊れる、と(笑)。
まさかそんな挙動をする、なんつーのを夢にも思わなかったんで、構文解析のmatchが不可思議な挙動をする、って悩みまくってた、ってわけ。半数の原因はmatchじゃなくってこっちだったんだ。
これこそmatchらを立てればこちらが立たず、である(謎
うん、端的に言うとread-fileのバグでしょ。でもread-fileを自作したくねぇんで(笑)、場当たり的な治療法としてread-fileの返す文字列のケツに"\n"を付け足した、と。
そういう事でござんす。
と言うわけで、これでWhitespaceのRacketへの移植は終了だ。あとはスクリプトとして使えるようにmain関数を書いて付け足しただけ、で、これもHaskell原作に従っただけ、である。
お疲れ様。
参考までに、ここにWhitespaceでの階乗計算のプログラムをあげておく。
※1: 実はこのコードを読んで分かるのは、この生成されたアセンブリ内で定義されているaddとreadは、定義されているだけで実は使われていない、と言う事である。それらはメインルーチンから結局一回も呼ばれていない。
事実、これらの定義を削除してWhitespaceの仮想機械に食わしてみても問題なく動作する。
これが指し示す事は、実はWhitespaceの作者は手書きでWhitespaceのコードを書いてるわけではなく、何らかの生成器を作ってWhitespaceのコードを書いたのだろう。
言わば逆アセンブラを作ってたんじゃないか。
※3: シンボルは定義された時点で唯一無二の存在となるので、Lispが構成するメモリ上でも唯一無二の存在となる。
結果、同値判定する際にメモリ上のアドレスを調べるだけで良く、詳細を解析する手間が省けるのだ(文字列の場合、「同一」を判定するには含まれる文字が全部同じなのかどうか調べないとならない)。
これがRacket/Schemeのeq?がやってる事であり、他の等価判定関数より圧倒的に比較速度が速い理由である(専門的にはポインタ比較、と言う)。
※4: つまり、事実上WhitespaceのHaskell原作が指し示してるのは、この実装に於いてはパーザ = コンパイラ、だと言う事である。我々は知らんうちに実はコンパイラを書いて完成させてたのだ。
もちろん、フツーは、パーザ = コンパイラ、なんて事はあり得ない。
※5: ただし、良くC言語辺りで使われる「2の補数」の表現にはなっていない事に注意。
2の補数表現はC言語等で扱う「bit列の長さの上限が決まってる」場合には有効だが、HaskellもRacket/Schemeもbit列の長さの上限を規定していない。要するに理論的には「どんなに長い整数」でも扱えるので、補数のやり方は意味を成さないのだ。
※6: 結果、実はvmはdoInstrを呼び出し、doInstrはvmを呼び出す構造となっていて、二つの関数が合わさって全体的にループ構造を形成してる。
このように、一つの関数が別の関数を呼び出し、それがまた元の関数を呼び出し・・・と言う形式を相互再帰と呼ぶ。
なお、vmもdoInstrも最後にお互いしか呼ばないので、これは全体としても末尾再帰になっていて、Racket/Scheme上では末尾再帰最適化の要求により、再帰としてのコストはかからない。
※7: もうお気づきだろうが、スタック操作とは低レベル操作であり、原理的には「スタックの破壊的変更」を伴っている。
Haskell原作ではvmのスタック引数の与え方をプロセス上変える事によって、これを非破壊的に記述して関数型言語として矛盾無く行っているが、原理的には破壊的操作である。
バグで悩んでた際にRacketのユーザーグループの一人に指摘された次第である(笑)。
よって、他のScheme処理系に移植する事を考えなければSRFI-1をrequireする必要はない。
手癖って怖いね(笑)!
