Skip to content

Textbook.md

Latest commit

 

History

History
136 lines (103 loc) · 5.67 KB

Textbook.md

File metadata and controls

136 lines (103 loc) · 5.67 KB
Raw

公式 Textbook 要約

公式 Textbook「Introduction to Systems Programming」は、Littleman を インタラクティブな例で順に学ぶ入門教材である。厳密な仕様ではなく概念理解を 目的としており、曖昧な点は Spec.md と公式 Language Reference を 優先する。

基本モデル

Littleman のソース（.man）は ASCII 文字の 2 次元 grid。@ で表される little man が room 内を移動し、踏んだ文字を命令として実行する。

  • room は +, -, | で囲む長方形。
  • little man は room の外へ出られず、壁に衝突するとプログラム全体が error。
  • @ は常に右向きで開始する。
  • 1 回の実行・移動単位を tick と呼ぶ。
  • H はその little man を halt させる。
  • 空白と . は何もしない。未知の文字を踏むと error。
  • >, <, ^, v は進行方向を変える。

手、数値、算術

各 little man は main hand A、off hand B、backpack BP という 3 個の 整数状態を持ち、すべて 0 で開始する。

  • 数字 0–9 を踏むと A にその値を入れる。
  • M: A を B にコピー。
  • W: A と B を交換。
  • + - * / % N: 四則演算、剰余、符号反転。
  • & | ~ { }: AND、OR、XOR、左 shift、右 shift。
  • 二項演算は基本的に A op B で、主結果を A に入れる。除算だけは商を A、余りを B に入れる。

10 以上の定数は backtick で `123` のように囲む。closing backtick を 踏んだとき A に入る。逆方向に通れば桁も逆順（321）となり、縦書きも可能。 内部の空白は無視される。

複数 room と pipe

プログラムは複数の room を持てる。room は重複・入れ子にできず、各 room の little man は同じ tick で lockstep に実行される。

pipe は room 間の一方向 channel で、矢印 > < ^ v と直線 - | で描く。 値は 1 tick に 1 cell 進み、各 cell は 1 値だけ保持する。

  • s: 最寄りの outgoing pipe に A を送る。
  • r: 最寄りの incoming pipe から A に受け取る。
  • S: すべての outgoing pipe に同じ値を同時送信。
  • R: 値が用意できたいずれかの incoming pipe から受信。
  • U: R と同様に受信し、受信元 pipe から離れる方向へ向く。
  • 満杯の pipe への send と空の pipe からの receive は block し、同じ cell で 次 tick に再試行する。

pipe の作図、最寄りの定義、tie-break は間違えやすい。Web エディタでは命令 cell を選ぶと対象 pipe が highlight され、pipe 内の値も確認できる。

入出力

特殊な 3×3 room を使う。

+-+       +-+
|I|       |O|
+-+       +-+
  • Input room から出る pipe を r 等で読む。
  • Output room に入る pipe へ s 等で値を送る。
  • 入出力値は空白区切りの整数。
  • Input room と Output room はそれぞれ最大 1 個、接続 pipe もそれぞれ最大 1 本で、方向も決まっている。

分岐と loop

X は A の符号で分岐する。

  • A > 0: 時計回りに 90°。
  • A < 0: 反時計回りに 90°。
  • A = 0: 直進。

backpack は loop counter や bit 列として使える。

  • b: BP = A
  • m: BP -= 1
  • d: BP > 0 なら時計回り、そうでなければ直進
  • a: BP > 0 なら反時計回り、そうでなければ直進
  • x: BP の最下位 bit が 1 なら時計回り、0 なら反時計回り
  • ]: 算術右 shift で BP >>= 1
  • q: 最寄りの incoming pipe に現在入っている値の個数を BP に入れる

b → body → m → a/d という配置で count loop を作れる。x と ] は 整数を bit ごとに処理するループに向く。

LM-75 Display

Display は +, =, : で囲む。内部は最大 64×64 pixel。pipe を接続する 辺により役割が変わる。

  • 上 ADDR: cursor を row * width + column に移動。
  • 左 DATA: next buffer の cursor 位置へ色 0–15 を描き、cursor を次へ進める。
  • 下 SWAP: next buffer を current buffer に表示する。0 なら next を黒で clear して cursor を左上へ戻し、1 なら next と cursor を保持する。

current は表示中、next は次 frame の作画先。cursor は左上 (0, 0) から row-major に進む。これにより全画面順次描画と、ADDR を使った sparse drawing の両方ができる。

教材としての推奨順

  1. room、@、tick、halt、error
  2. 方向命令と 2 次元経路
  3. A, B と算術
  4. 複数 room と pipe
  5. I/O room
  6. X による条件分岐
  7. backpack による loop・bit 処理
  8. backtick 数値 literal
  9. LM-75 Display
  10. Grading を読み、Practice Problems へ進む

実装時の要点

  • Littleman は「普通のコードを 2D に置き換えただけ」ではない。pipe の latency、容量、blocking と複数 room の並行実行を積極的に設計に使う。
  • 問題スコアには bounding box の最大辺が二乗で効く。横長・縦長に伸ばす より、部品を詰めて正方形に近づける方が有利になりやすい。
  • まず正しさを確認し、その後 footprint と tick を別々に最適化する。
  • round 制問題ではプログラム状態が保持され、次入力は必要出力まで来ない。 単発入力だけで動く設計では不十分なことがある。

参照