こないだ星田さんとブログでWhitespaceの話をやり取りしてた。
あと、実用性ゼロのプログラミング言語として「空白、タブ、改行」なんかで作られた見えない言語とか！面白いこと考える人がいるもんだなぁ
それで急になんだか思い立ってWhitespaceの公式ページ(跡)を漁ってみた。
何の気無しにソースコードを見たら
「こいつ、Haskellで書かれとる・・・・・・!!」
はい、今回初めて知ったんだが、実は冗談プログラミング言語、WhitespaceってオリジナルはHaskellで書かれてるのだ。
んでHaskellで書かれてるって事は・・・・・・?
そう、Scheme/Racketに直訳するのが比較的簡単だ、と言うことだ。
うん、これがC言語なんかで書かれていればそういう発想にはならない。翻訳するのがかなり面倒なんで、仕様見た方が早い、なんて事になっちゃうんだよな。
と言うわけで、唐突にWhitespaceをRacketで書いてみた。
取り敢えず最初に全ソースを提示しておく。
Whitespaceは300行に満たないで書けたプログラミング言語である。
以下、これについての細々とした解説を書いていこうと思う。
ところで、確かにHaskellで書かれたソースコードをRacketに翻訳する事は手間ではない。数時間もあればこの程度なら全ソースコードを(Haskellの細かいトコを調べる手間が若干かかるとは言え)翻訳出来る・・・・・・ガワならな(笑)。
このテの作業で問題なのは、「翻訳する事」じゃない。むしろバグ取りの方に手間がかかるのだ。
両者(この場合はHaskellとRacket)の構造の細かい違いが足を引っ張る事となる。
特に、個人的には、良く知らなかったRacketオリジナルライブラリの仕様に・・・物凄く足を引っ張られたのだ(笑)。
SRFIなら仕様がハッキリしてるが、Racketオリジナルの「組み込み機能」だと、ドキュメンテーションも完全じゃなく、参照出来るモノも無いので、思った通りに動いてくれない時に何がエラーの原因だか分からなくってハマる、っつー事だな(※1)。
結果、翻訳は大して時間が取られないのにデバッグでその三倍〜五倍程度は時間が取られてしまうのだ・・・・・・まぁ、そうでなくてもデバッギングの方がプログラミングより時間がかかるってのが相場ではある。
プログラマだって使う時間を考えると、実際はプログラミングしてる時間よりデバッグしてる時間の方が長い・・・職業プログラマじゃなくって職業デバッガって言った方が単位時間辺りの作業数で言うと妥当な筈である。
今回はRacketのドキュメンテーションがワヤなせいで輪をかけて時間がかかった、と言うだけの話である。それだけは想定外だった。
でははじめよう。
1. コンピュータの一番簡単な仕組み
ところで、以前何気なしに「WhitespaceはBrainfuckの仲間だ」と言う言い方をした。
これは言外に、仕様的には「Brainfuckを改造すればWhitespaceになるだろ」って意味なのだが、今回、Haskellでの実装を見てみると意図は違う、と言う事が分かった。
BrainfuckとWhitespaceは「難解プログラミング言語」と言う枠組みでは仲間だが、その実装は大きく違う、と言う事だ。
あー、ちなみに。
Brainfuckをちょこちょこと改造すればWhitespaceになるだろ、って言うのは別に間違いではない。明らかに仕様的にはそれは伺えるから、だ。
僕が言ってるのは「実装を見ると」と言う事。少なくともWhitespaceの作者がこの実装を組んだ時、Brainfuckを改造して・・・ってつもりじゃなかったんだろうな、と言うことである。
仕様と実装の話はごちゃ混ぜにすべきではない。仕様と実装の話は分けて考える、のがマナーである。
いずれにせよ、このオリジナルのHaskellによる実装は、恐らくBrainfuckのそれよりもかなり複雑である。
と言うのも。
実はプログラミング言語の仕組みと言うのは、大きく言えば、度合いの違いはあるけれど、どれも「コンピュータ」のシミュレータである。
ハッキリ言うと「人間により分かりやすいコンピュータのシミュレータ」から「人間により分かりづらいコンピュータのシミュレータ」まで数多く取り揃えてるのがプログラミング言語、と言うモノなのだ。
よって、プログラミング言語をプログラムする場合、ザックリでいいからコンピュータの仕組みをある程度知ってた方が良い、と言う事になる。
そしてWhitespaceのHaskellによる実装は、Haskellと言う高級で明解なプログラミング言語を用いてはいるけれど、書いてるのはかなり低レベルな「抽象機械」であるのは間違いない(※2)。
例えて言うと実装的には、Brainfuckが抽象的なチューリングマシンだとしたら、Whitespaceは現実のコンピュータである。それくらいの違いはある。
そうだとすれば、オリジナルのWhitespaceの仕組みを理解するには簡単なコンピュータの仕組みを理解すること、逆にWhitespaceの実装を通じてコンピュータの仕組みを朧気ながら理解するフィードバックを得られるだろう、と言う事である。
最小限のコンピュータとは、恐らくCPUとメモリ、と言う二つのデバイスを繋いだだけ、のものだ。
もちろん現実ではさすがにそれだけのモンは存在しないが、ある種低レベルのプログラミング言語、Whitespace実装の「仕組み」を理解するにはこの二つだけで考えた方が良い。
CPU(中央演算処理装置)は「加算・減算等の命令を詰め込んだ」機械で、メモリの中身を順番に持ってきては「命令を実行して」「結果を返す」のがザックリ言うとその役目である(※3)。
つまり、プログラミング言語のプログラミングは、一つは「CPUの機能をエミュレートする」と言うことだ(※4)。
もう一つはメモリである。これも実際我々が使ってるメモリを直に、の意味ではなく、配列やらリスト等を使って抽象化したメモリと言う意味である。
僕らが作るプログラミング言語、つまり仮想機械はこのCPUとメモリが直結してるイメージである。
まずはこのイメージを押さえる。
次にWhitespaceの原作の実装に従ってもうちょっと細かくこの「仮想機械」を見ていく。
このCPUはメモリを最低2つに分けて使ってるらしい。
それはこれらである。
実は僕らが使ってる現実のPCでも、OSはメモリをこの二つの領域に分けて使っている。
覚え方としてはまずはスタックを押さえる。これが特徴的だから、だ。
極端に言うと、ヒープと言うのは「スタック以外の部分」を指す。そしてヒープは僕らがフツーにイメージする、いわゆる「メモリの使い方」をする部分だ。
例えば、エクセルのデータを読み込んだり、ワードのデータを読み込んだり、エロゲのデータを読み込んだりして保持してくれる部分だ。これが通常の「メモリの使い方」と言われて想像するモノだろ?
スタックはちょっと違う。正直言うと、僕も最初、「スタック」ってのを学んだ時、「何だこれ?何のためにこんなモン学ばなアカンのや」って思った(笑)。
平たく言うと、このように「プログラミング言語を作ったり」「類する処理系を作る際に」必要なんだけど、全般的に必要か、って言われると、ぶっちゃけ良く分からんのだ(笑)。いまだにな。
OSはスタックを確かに使ってる。が、OSがスタックを使ってるから全員が全員何が何でもこれを知らんとアカンかと言うと・・・正直微妙なんだよな。
そしてスタックの定義が難しい。逆説的に、pop出来たりpush出来たりするメモリ領域、あるいは構造をスタックと呼ぶ、としか言えないのだ。
多分意味が分からんだろ。
ちょっとPythonのリストを用いてpopとpushの動作を説明してみよう。
我々が使うようなPythonを含む「超」高級言語では、通常リストを使ってスタックを表現する。
Pythonのリストにはpopと言うメソッドがあり、これが示す事はPythonのリストはスタックとして使用される前提で設計されてる、って事だ。
>>> fruits = []
>>> fruits.append('バナナ')
>>> fruits.append('リンゴ')
>>> fruits.append('キウィ')
>>> fruits.append('バナナ')
>>> fruits.append('ナシ')
>>> fruits.append('オレンジ')
>>> fruits
['バナナ', 'リンゴ', 'キウィ', 'バナナ', 'ナシ', 'オレンジ']
>>> fruits.pop()
'オレンジ'
>>> fruits.pop()
'ナシ'
>>> stack = []
>>> stack.append(3)
>>> stack.append(4)
>>> stack.append(5)
>>> stack
[3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]
>>>
こういう状態になるのがスタックで、スタックをそういう状態に持ち込むのがpopとpush(Pythonではappend)の役割である。それしか言いようがない。
結果、原則としてはスタックと言うのはスタックの先頭(あるいは実装によっては末尾)に対しての二つの操作方法しか持っていないメモリ構造である。
逆に、ヒープというのは、Pythonで言うとフツーのリストであり、「リストの要素番号に従って中身を書き換えられる」メモリ構造である。
>>> heap = [0, 0, 0, 0, 0, 0, 0, 0]
>>> heap[3] = 1
>>> heap
[0, 0, 0, 1, 0, 0, 0, 0]
>>>
結局、PythonやRacket/Schemeみたいな超高級言語を使う以上、「利用する操作によって」メモリの種類がスタックとヒープに分かれる、と考えた方が現実的だろう。
従って、プログラミング上、スタックにヒープ操作をしてはいけないし、ヒープにpopやpushしてはいけない。
このWhitespace、実際のトコ「全部で4種類」のメモリをくっつけてるカタチとなっている。現実のコンピュータで言うとRAMを4つの領域に分けて使ってる、ってトコか。
そして、内情は大雑把には2つのスタックと2つのヒープによって構成されている。
それらは
- プログラム領域
- スタック
- コールスタック
- ヒープ
である。
1と4がヒープ(※5)で、1番はプログラムの中身が置かれる場所でここにプログラムがロードされたら中身は一切変更されない。
2. のスタックは、この場合、何らかの意味を持った数値を詰め込むためのスタックである。
それは四則演算の為の引数かもしれないし、その計算結果かもしれない。
3. のスタックは一般にコールスタックと呼ばれる、構造的には2. のスタックと全く同じものである。
ただし、関数やプログラムの制御に関わるデータを扱う辺りが2. と違う辺りである。
4. がヒープ。こっちは1. と違ってプログラム(1. )に対するデータだ、と考えて良いだろう。
例えばここでは、端末からの入力情報、などは一旦4. に置かれる。
「メモリの使い方」に関しての概要は以上である。
繰り返すが、このWhitespaceの実装に於いては「理論的にはどんなに長くもなれる」メモリを4本CPUに挿し込んでる、と言うカンジで実装されてる。
しかしそんな設計は現実的にはあり得ないわけで、メモリはハードウェアの都合やOSの設計によって使用目的別に(論理的に※6)分割されている。
さてあとはCPUに付いて、だが。
先にも書いたがCPUと言うのは「処理をする/命令を振り分ける」と言うのが役割である。
現実のCPUには演算装置や制御装置等、ハードウェアとして「機能」が詰め込まれてるが、ここでは今そこには触れない。実際には「命令」及びメモリとのやり取りは全て0と1を使う(つまり二進数)がそこにも今んトコ触れない。
ただ、一つ重要な「機能」にプログラムカウンタと言うものがある、と言う事だけは書いておこうと思う。
CPUとメモリがくっついてるとして。CPUはどうメモリを読んで実行していくのだろうか。
実はCPUはメモリの各部分(※7)に「番地」を振って、小さい方から大きな方に向かって一つづつ進む。そしてその「番地」の内容を食って実行するわけだ。
と言うわけでCPUは「今自分がメモリの何番地にいるのか」知るためのカウンタが必要になるわけである。言い換えるとCPUはカウンタが示す数値が指してる番地へ進み、その「中身」を実行するわけだな。
これをプログラムカウンタ(※8)、と呼ぶ。
分かるだろうか?C言語のfor文なんかのカウンタは、基本、このCPUのプログラムカウンタの抽象化である。
極論、CPUはメモリの0番地から始まって繋がってるメモリの最大の番地へ向かって「一つづつ大きくなる番地の中身」を順次実行していくわけである。
これがコンピュータの原理、である・・・・・・いやマジで。
算術計算を除くと、基本的にあと出来る事と言ったらプログラムカウンタの値を書き換えるくらいである・・・「x番地に飛べ」とか「y番地に行け」とかな・・・・・・。
そう、そうすると「ifに拠る分岐」とか「繰り返し」が可能になるわけである。
お分かりだろうか?「全てのプログラミング言語は程度の差こそあれコンピュータのシミュレータだ」と言った意味が。低レベルでも高レベルでも「何らかを受け取って」逐次実行してる、って大枠は実は何も変わらないのだ。
そして低レベルで「xxx番地に飛べ」と言ってプログラムカウンタを操作する行為が、もうちょっと高級な言語だとif文とかfor文にラップされてる、と言う事を(Lispだったらifとかcond等だ)。
そしてCPUは「メモリの先頭から順番にメモリの内容を実行していく」と言った。
プログラミング言語のインタプリタは「ファイルの先頭から順番にファイルに書かれた内容を実行していく」・・・何だろう、このアナロジーは。
そう、実はコンピュータとは原理的にはインタプリタなのだ。我々はハードウェア・インタプリタ上でソフトウェアとしてのインタプリタを使ってるわけだ。
ある意味、超循環環境を形成してるのがハードウェアとソフトウェアの関係なのだ。
さて、最低限の「コンピュータの仕組み」は既に見た。
そして原作のWhitespaceは上で見た「CPUとメモリ4本が直結してるような」仮想機械として設計されている。
ではWhitespaceをSchemeに訳しながら解題していこう。
2. トーカナイザを作ろう
え〜と、どうすっかな。
うん、まずは最初にトーカナイザを作ろうか。
これはWhitespaceの場合、真っ先に自作せなあかん部分である。
トーカナイザは日本語では字句解析器と訳される。平たく言うと、与えられた文章・・・プログラミング用語だと文字列、を規則に従って分解するソフトウェアである。
実は日本語だと厄介だけど、一般に(プログラミング言語を含み)言語は記述法として「分かち書き」を採用してるケースが多い。つまり単語はスペースで区切られてる、と言う事だ。
この前提だとわざわざトーカナイザを作らなくても済む。Pythonでは文字列のsplitメソッドを使えば文章をトークンのリストに分解してくれる。
>>> "This is an ordinal English sentence".split()
['This', 'is', 'an', 'ordinal', 'English', 'sentence']
>>>
そう、これがトーカナイズ、つまり一番単純な「字句解析」の例だ。
簡単だろ?
Scheme/RacketなんかではSRFI-13の関数を使えば同様な事が出来る。関数名はそのままstring-tokenizeである。
> (string-tokenize "This is another English sentence for Racket/Scheme!")
'("This" "is" "another" "English" "sentence" "for" "Racket/Scheme!")
>
どっちのケースも「空白」を頼りに文章をトークン(字句)へと分解してる。
これがトーカナイズの一番単純な挙動なのだが・・・これじゃあ今回はマズいのが分かるだろ(笑)?
我々が今、Whitespaceで欲しい字句解析はむしろ逆で、アルファベットなんかの文字を消して空白を遺したいのである(笑)。
従って・・・言いようによっては逆トーカナイザ的なモノが欲しいのである(※9)。
と言うわけで、文字列を受け取って空白文字(Scheme/Racketでは#\space、#\tab、#\newlineの三種類)だけ遺してリストとし、他は全部消してしまう関数
tokenizeは次のように書ける。
(define (tokenize str)
(filter (lambda (x)
(or (char=? x #\space)
(char=? x #\tab)
(char=? x #\newline))) (string->list str)))
そう、原理的には単なるフィルタである。文字列をリスト化して、文字が空白文字じゃないブツは全部フィルタリングする。そうすると空白文字だけのリストが返ってくる(※10)。
例えばWhitespaceで書かれたHello Worldプログラムはこんなカンジだが(見えないが・笑)、tokenizeを噛ますとこのような(要素数が1,000を超えてる)リストを返す。
いずれにせよ、これがRacketによるWhitespaceプログラムに対する「字句解析」である。
そして次にこの「字句解析済みのリスト」をパーズ、つまり構文解析する。
#\space、#\tab、#\newlineの3つを使ったリストを先頭から見ていって、ルールを参照して「意味を見出していく」のである。
3. 構文解析器(パーザ)を作ろう
Brainfuckみたいな極単純なプログラミング言語は例外だが、通常、プログラミング言語での「入力」は二段階に分かれてて、最初は先に見たトーカナイザ(字句解析器)を通ってトークンを得、そしてその後、パーザ(構文解析器)を通り、各トークンないしはトークンの組み合わせに「意味」を持たせる。
さて、ぶっちゃけると、ここで一番大変な思いをした。
その背景を説明しよう。
Haskellと言う言語は「何でもパターンマッチング」言語である。
関数の定義でさえパターンマッチで記述する、と言う徹底ぶりだ。
でもパターンマッチとはなにか?
このパターンマッチ、と言うのは耳慣れないかもしれないけど、ある意味「caseによる条件分岐」のより強力な機構で、僕個人の印象だと「ヨーロッパ生まれのプログラミング言語」だと良く採用されている気がしてる。
反面、北米生まれのプログラミング言語だと採用してるケースが少ないような気がする(※11)。ある意味プログラミング言語にビルトインするには機構が複雑過ぎるし、突飛な印象を受けるから、だ(浮いてる、とも言う・笑)。
例えば、「リストの中に0があるかないか調べるcontain-zero?を書け」と言う問題を考える。
Scheme/Racketに慣れてれば3秒くらいでハナクソをほじりながら次のような関数をでっち上げるだろう(※12)。
(define (contain-zero? ls)
(if (null? ls)
#f
(let ((x (car ls)))
(if (zero? x)
#t(contain-zero? (cdr ls))))))
ところが、同じ関数をRacketのパターンマッチ機能で書くと次のようになる。
(define (contain-zero? ls)
(match ls
('() #f)
((cons x xs) (if (zero? x)
#t(contain-zero? xs)))))
違いが分かるだろうか?
matchはSchemeのcaseに見た目良く似てるが、上のmatchを使ったバージョンの場合、
- lsには二つの状態があると仮定している。
- ls が空リストであるパターン
- ls が(中身はなんでもいいから)xが(中身はなんでもいいから)xsにconsされてるパターン
と定義されてる。
特徴的なのは2番の定義で「なんでもいいから」何かが「なんでもいいから」何かにconsされてる、と言う判別法。
要するにlsのある状態を「大雑把に」パターンとして記述してるわけだ。
これにより、例えばリスト(1 2 3)は「何か(1)」が「何か((2 3))」にconsされてる状態だ、と判別が付く・・・・・・。
そう、最初のcontain-zeroは律儀かつ再帰的にリストのcarを直接調べていたが、パターンマッチングの場合は式の記述法の形式を調べているのである。
後者は場合によってはとてつもなく記述がシンプルに「なる場合がある」と言うのに気づくんじゃないか。
;;; 整数のリストを受け取ったら合計を返す関数(define (sum lst)
(let loop ((lst lst) (acc 0))
(match lst
('() acc)
((cons x xs) (loop xs (+ x acc))))))
;;; 階乗を返す関数
(define (factorial x)
(let loop ((x x) (acc 1))
(match x
(0 acc)
(else (loop (- x 1) (* x acc))))))
;;; 累乗を返す関数
(define (power x y)
(let loop ((x x) (acc 1))
(match x
(0 acc)
(else (loop (- x 1) (* y acc))))))
これが(僕の感覚では)「ヨーロッパ人が大好きな」パターンマッチングである。
もう一回繰り返すと、パターンマッチングは詳細に入らない。単に表層的に「記述形式」に反応して演算を起動する。
一般に、プログラミング言語そのものとは必ずしも関係無いが、パターンマッチングが駆使されてるのが文字列操作の範疇である。そう、性器表現である。
間違えた。
正しくは正規表現である。
ここでは詳細には入らないが、いずれにせよ、正規表現、とはテキスト・・・文字列の中から特定のパターンを見出すパターンマッチング操作である。
そして、プログラミング言語の入力に於いても、プログラムが書かれたソースファイルをトーカナイズして、「構文規則」とパターンマッチングさせる・・・・・・。
そう、原理的には「構文解析」とは「ルール」に照らし合わせたパターンマッチングであり、構文解析器、ないしはパーザとはパターンマッチャーなのだ(※13)。
ここまではイイ?
それで、Whitespaceの「構文」は次のようになっていて、Haskellの原作ではパターンマッチ構文でベタ書きされている。
もう定義されてる内容を見ると「低レベル操作」っぽいのが分かるだろうか。
そう、まさしくアセンブリ的な低レベルさ、なのだ(後にそれがハッキリと分かるだろう)。
いずれにせよ、パーザはトーカナイズ済みのリストを受け取って、先頭から内容を、消費しながら見ていく。
そこで例えば#\space #\spaceと言うパターンを見かけたら「数値をスタックに積む」と言う命令に変換する(これが構文解析だ)。#\tab #\spaceを見かけたら「次は四則演算(剰余含む)になるな」と言うのが「規則」に従い分からないとならない。
また、表には書いてないが、Whitespaceは二進数で数値を扱っている。
#tabが1、#\spaceが0を表す二進数表現で、「数値コード」は終端記号である#\newlineが出てくるまで二進数で表現された値だと解釈される。
すげぇだろ(笑)?徹底してる。
さて、パターンマッチングの為の機能があり、トークンは三種類しかねぇし、文法規則の定義もハッキリしてる。
ってぇんでここまで色々と明らかならパーザを書くのはフツーは簡単なんだけど。
ここで大失敗したの。エラー食らって。
しかもデバッガかけて見てみても原因がハッキリせんかった、ってぇんで久々にドツボだったんだよなぁ。
最初のバージョンでは、Haskellでのプログラムの表記に従って
(define *A* #\space)
(define *B* #\tab)
(define *C* #\newline)
としてた(実際はHaskell版だとtokenと言う型を作ってた、って事なんだが)。
それで最初は
(define (parse ls)
(let loop ((ls ls) (acc '()))
(if (null? ls)
(reverse acc)
(match ls
((list *A* *A* xs ...)
(let-values (((num rest) (parseNumber xs)))
(loop rest (cons `(Push ,num) acc))))
((list *A* *C* *A* xs ...)
(loop xs (cons '(Dup) acc)))
((list *A* *B* *A* xs ...)
(let-values (((num rest) (parseNumber xs)))
(loop rest (cons `(Ref ,num) acc))))
((list *A* *B* *C* xs ...)
(let-values (((num rest) (parseNumber xs)))
(loop rest (cons `(Slide ,num) acc))))
((list *A* *C* *B* xs ...)
(loop xs (cons '(Swap) acc)))……
みたいにしてた。
ところが書き終わってから動かしてみると上手く動かない。
と言うか、第一節に入りっぱなしでマトモに構文解析しない。
「何故に?」と久々に混乱。デバッガにかけても原因が分からん、と。
あまりにハマったのでRacketのユーザーグループに相談してみたのだが。
実はRacketのmatch、中で使われてる変数はレキシカル変数にならなく、新規作成された変数と解釈されるのである。
要するにmatchの内側で使われてる、例えば*A*はmatchの外側にある*A*と同じじゃないのだ・・・・・・。え"え"え"え"え"え"え"え"。
まさかRacketでレキシカルスコーピングに反するような動作にお目にかかるたぁ思わんかった。
それで、もし外部で定義された変数を参照したい場合はmatch-expanderと言う記号を使わなアカンとの事。
つまりこう書け、って事だな。
(define (parse ls)
(let loop ((ls ls) (acc '()))
(if (null? ls)
(reverse acc)
(match ls
((list (== *A*) (== *A*) xs ...)
(let-values (((num rest) (parseNumber xs)))
(loop rest (cons `(Push ,num) acc))))......
Lispで==って記号は相当キショイ(苦笑)。
えぇ〜〜、ガッカリだよ。
っつーか、この辺が個人の力で直らんかったのは、ひとえにもう一つ、Racketの提供する関数の挙動がこちらの予想と違ってて、このパーザの演算に影響を与えていたからだが、それについては後述しよう。
要するに複合バグだとデバッガがあっても対処が難しくなる、と言うことだ。
ま、最初から「Haskellで書かれたオリジナルのコード」に無理に合わせなければ良かったのだが・・・・・・。
いずれにせよ、パーザを完成させ、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))
これ分かるだろうか?
いや、ひょっとしたらBASICとかやったことがある人の方がピンと来るかもしんない。
実はこの、パーザから吐き出されたブツは一種のアセンブリ言語になっている。当然、バッチ式のプログラムだ。
つまり、Haskellで書かれたWhitespaceの実装は事実上、Whitespaceのコードをトーカナイズしてパーズした時点で仮想機械に食わせる「アセンブリ言語」を吐き出してるのである。・・・いやホント「低レベル」な事やってんだよ。
機械語が出てこないだけマシ・・・・と言えるのか(笑)?
いやよ、よく考えてみると、だ。
Whitespaceって言語は機械語じゃないんだけど、事実上そもそもそれに近いわけ。
機械語は0と1で記述されて2つしか「数値がない」からバイナリなわけじゃん?
Whitespaceは構成要素が3つしかないんで、バイナリじゃなくってトリナリだ、て話なだけなんだよな(笑)。いや、むしろ、マシン語に近いと言うよりマシン語そのものなんだよな。三進法コンピュータ(なんてものがあれば、だが)のマシン語だ。
三進法コンピュータのマシン語をトーカナイズしてパーズすれば、ほら、抽象度が一つ上がって内部表現がアセンブリレベルになりました、と(笑)。
そりゃどこをどう突いても難解だろ、と言う(笑)。
で上で吐き出された内部表現、をちと眺めてもらいたい。
例えばプログラムリストの後半になる(※14)とやたら「Label」が目に付く。
「Label」は当然「ラベル」である。「名のある何か」。一体何だろこれは。
実は「Label」＋名前、から始まって、大まかに次の「Label」までの間のコード群をまとめて「サブルーチン」と言う。これらは前半の「メインルーチン」から呼び出される為に定義されてるのだ(C言語の「main」はこれに由来する)。
そう、サブルーチンは高級言語で言うトコの「関数」の実体である。実際僕らがフツーにプログラムで関数を書いた時、中間コードの時点なのかアセンブリレベルなのかは分からないけど、取り敢えずどっかでこういう「サブルーチン」に落とし込まれてる、と言う事だ。
長くなったので次回へ続く、とする。
※1: ちなみにScheme系の実装だと大方のケースでこれは良く当てはまり、「Scheme系はドキュメンテーションが良くない」と言えると思う。とにかく例示もないし、ユーザーは「想像して」読むしかないのだ。そして具体例が乏しいリファレンスマニュアルはクソと言って良い。結果あってもなくても良くないか?
多分、今まで読んで一番ドキュメンテーションが良かったのは、Gaucheだ。例示も豊富で、恐らく世界中のScheme処理系のマニュアルの中ではダントツで分かりやすいモノとなっている。
結局、開発者の川合史朗氏はANSI Common Lispハッカーでもあり、CLHSの「書き方の有用性」も良く理解してて、Common Lisp文化圏なマニュアルの書き方をSchemeに持ち込んでいるように思う。だから世界一分かりやすいScheme実装のマニュアルになってしまった。
実際、Scheme実装はお互いに(実装依存)機能を借りて似たような機能を持ってる事があり、ぶっちゃけ、Racketでの「良くわからない機能の使い方」で困った際に、Gaucheのマニュアルを読むと氷解する、なんつー事がしばしばある(笑)。
※2: 何度も言うけど、「C言語を学べばコンピュータの仕組みが分かる」と言うのは大嘘である。
ただし、大学の授業なんかで「C言語を使って言語インタプリタやコンパイラの仕組み」を学んだりするのでコンピュータの仕組みが、大まかでも分かるようになる、と言うだけだ。
分かったね?「"C言語である/なければならないこと"とは全く関係がない」のだ。
言い換えると、BASICで言語インタプリタやコンパイラを実装してみればコンピュータの仕組みが分かるだろう。
もっと言うと「仮想マシンの作り方が分かる」事でコンピュータの仕組みを朧気ながら想像出来るようになるわけである。
このように、プログラマはよく「因果関係を間違えて」とんでもない事を流布したりするわけで、これをもって、「プログラミングと論理性は全く関係がない」と言う証拠にもなるだろう。
「因果関係をはき違える」論理性なんざあり得ないから、だ。
※3: ホントに「ザックリ言うと」である。
細かく言うとメモリからその内容を持ってくるにもLOAD命令や何やらあってややこしい。
また、実際「計算を行う場所」(これも性質的にはメモリである)はCPU本体内にあり、それを特にレジスタと呼ぶ。
※4: 極端に言うと、Lispファミリー等のインタプリタで、この「CPU」の役目を果たすものをeval(評価器: evaluator)と呼ぶ。
そう、eval ≒ CPUなのだ。
※5: 厳密には「プログラムを置いた」領域をヒープと呼ぶべきかどうかは分からない。場合によっては「テキスト領域」なり「プログラム領域」と呼ばれるが、OS側から見ればどれも大差なく、結局伸長させたり縮めたり、と管理すべき対象になってる、ってのはどれも変わらんから、だ(そして「ヒープ」と言う言い回しがそもそも厳密には何を指してるのか、と言うのも分からん、と言うオマケ付きである)。
また、何をどういう順番で置くか、等と言うのも現実的にはCPUの設計やらOS側の都合に拠ることが大きく、そもそも「理屈付けて」「正式な名称として」「一般化して」構わない話なのかどうかも分からないのだ。
※6: ここで言う「論理的に」と言うのは、ハードウェア的な設計ではなく、と言う意味。
通常、今どきのCPUでは、メモリが一本、って認識されるようになってるだろう。それをどう分割するかはソフトウェア(と言うかOS)に委ねられるだろう。
※7: 慣習的にはバイトと呼ぶ。
ただし、バイトとはビットを幾つか纏めた塊の事を指すが、厳密には何ビットで1バイト、とは決められていない。っつーか厳密な定義が無いまま進んできてるのがコンピュータで、結果こんなデタラメなモノはとてもじゃないけど科学とは呼べないのだ。
そして何ビットで1バイトと決められてない癖にメガバイトとかギガバイトとかテラバイトがあるのだよ。デタラメにも程がある。
なお、慣習的には8bitで1byteっつー事になってるが、上にも書いたが、あくまで慣習であって厳密に定義されてるわけではない。
で、人によってはこのいい加減な「バイト」と言う言い回しを嫌い、8bitで表す塊の1単位をオクテットと呼んでいる。
※8: なお、プログラムカウンタは当然ながら「いくらでも大きくなれる」性質のモノではなく、上限値が存在する。
結果、原理的には、その「上限値」がアクセス可能なメモリ(バイト数)の上限値になるわけだ。
例えばファミコンで使われてた6502と言うCPUのプログラムカウンタの上限値は16ビット、つまり65536であり、1単位(バイト)=8bitだとすると、65,536バイト=64kバイトがアクセス可能なメモリ上限と言うことになる。ビットに直すと524288ビット≒524kビットのメモリがアクセス出来る最大値と言う事になる。とてもじゃないけど1Mビットのカセット、なんかは扱えないのだ。
・・・でも扱ってた。
秘訣は単純に言うとファミコンから「メモリを取り替えろ」と言う指示をして実際やってたのでファミコンのアクセス出来る最大メモリが見かけ上大きくなってたのだ。
それをバンク切り替え、と呼ぶ。
※9: ホントの事を言うとRacket/SchemeではSRFI-13のstring-tokenizeとSRFI-14のchar-set:whitespaceを組み合わせればWhitespace用のトーカナイザは以下のようにあっという間に書けるだろう。
(define (tokenize str)
(string->list (apply string-append
(string-tokenize str char-set:whitespace))))
ただし、UTF-8が通常の環境である昨今だと、実はスペース、タブや改行文字等の「空白文字」はなんと総勢で25個もある。一方Whitespaceで仮定してる空白文字はたった3個で、残り22個の扱いはどうなるのか、と言うのは仕様外である。
結局、SRFI-14の「文字セット」の細やかさが今回は仇となるだろう、と判断した。
※10: おかしな事に、原作のWhitespaceだとパターンマッチング再帰を行ってる・・・・・・明らかにPythonだったら「リスト内包表記を使え」と言われるケースなのに、だ。リスト内包表記の出自、Haskellなのに使われていない、のだ。
不思議である。
※11: Pythonはオランダ製だが、割にヨーロッパ臭くない。そしてパターンマッチング機構が欠けていた。
しかし最新版のPython、Python3.10(3.1ではない)で、恐らくメジャー言語では初めてパターンマッチングが導入される。
※12: 人によっては恐らく#tや#fと書きたくないので(笑)、and、or、notを利用した論理演算だけで再帰させて書くかもしれない。
(define (contain-zero? ls)
(and (not (null? ls))
(or (zero? (car ls))
(contain-zero? (cdr ls)))))
述語は真偽値を返すので、論理演算を駆使すれば#tや#fを返すのは自明、となる。
プログラムとして読みやすいか読みにくいか、と言った意見は人に拠る。だが、実際はプログラムよりは数学寄りの記述となるだろう。
まお、andとorは関数ではなくマクロなので、上の記述は見た目に反して末尾再帰である。
※13: 実はマトモにやるとこの「構文解析器」を書くのは至極面倒くさく、大学だと授業で取り扱うネタになってるらしい。メンド臭いから大学の授業向けなのだ(笑)。
なお、プログラミング言語をC言語で書くケースが多いのは、C言語の性能が良いから、ではなくって、yaccやBisonと呼ばれる構文解析器を自動生成する定番ツールがあり(このテのツールをコンパイラコンパイラ等と呼称したりする)、それがC言語で書かれた構文解析器を吐き出すから、である。
なお、直感に反して、速いコンパイラが書けたからと言ってそれが速いオブジェクトコードを吐くとは限らない。遅いコンパイラでも速いオブジェクトコードを吐く事は出来るのである。
従って、結構勘違いしてる人が多いが、何が何でもC言語でコンパイラを書く必然性は、実は「定番ツールがある」以外には何もないのだ。
とは言っても、それは富豪の時代の今だから言えるのであって、かつてPC-9801時代なんかだと「何時間にも渡ってコンパイルしてる」ような地獄を経験した層もいたみたいで、コンパイラ自体が速いのはやっぱ嬉しいらしい。 => この辺に当時の開発状況が書いてある。大変だ!
また、当時、PascalがCを向こうに回して頑張れたのは、一般に、Pascalコンパイラでのコンパイル時間は単純に、Cの1/3以下である、と言う爆速コンパイラだったからだ(Pascalは文法的に、一回ファイルを走査するとそのままコンパイルに取り掛かれるがCは何度もソースファイルを走査しなければならない欠点がある)。
※14: 正確に言うとこのケースでは「Endが出てくるまで」をメインルーチン、それ以降がサブルーチンとなり、多分大体どのアセンブリもそういうカンジでコードを置いていってるようだ。
