これまでの流れ：
- ICFP Programming Contest 2006 “The Cult of Bound Variable” に挑戦してみる
- AArch64でJITしてみる
- Universal MachineのJITコンパイラーを書いた
- ICFP Programming Content 2006: ADVENTURE
目次
リンク集
英語圏の参加者の記事にもリンクを貼っておく。
- Frictionless Bananas – 2006 ICFP Programming Contest Entry
- The Caml Riders – ICFP Programming Contest 2006
- The CamlNuggets
- rmathew: ICFPC 2006
- The ICFP Programming Contest 2006 | Mostly Software
特に、2Dのaspects.spec、Antomatonのpuzzel10以降はコンテスト終了後に追加されたものだとわかる。
VMの改修
自動ログインできると便利だな〜〜と思って --input オプションを実装した。例えば
./run --input howie --input xyzzy umix.um
を実行すると最初の入力として
howie xyzzy
を与え、それ以降は標準入力を利用する。これで自動ログインができる。
Haskell版VM
HaskellでもVMを書いてみた。特徴はgetChar/putCharを m (Maybe Word8) / Word8 -> m () という風に任意の（PrimMonad制約を満たす）モナドに対する操作として外から注入できるようにしたことである。一方でVMの大半の操作はSTモナドで済んでしまうので、高速化のためにVMの大半の部分はSTモナドで実行し、Halt/Input/Outputに遭遇したらSTモナドを脱出、という形にしている。
コードは
に置いてある。
このHaskell製VMではsandmark.umzはApple M1上で30秒ほどで完了する（AArch64/GHC 8.10.7なのでLLVMバックエンド利用）。CのswitchベースのVMの2〜3倍ほどで、極端に遅いわけではない、はず。
ContTと組み合わせれば前回のADVTRのblueprint解読時のようなやりとりを自動化できないかと考えたのだが、なぜかumix.umがめちゃくちゃ遅く、実用は難しそうだった。
パスワードの依存関係
レポートにも同様の図が載っているが、パスワードは次のグラフの順序で入手できる。二重線は難易度が高い入手経路である。
howie: Adventure (ADVTR)
前回クリアした。hmonkとyangとknrのパスワードと、810点が手に入る。
ohmega: 2D (CIRCS)
BASICでハックしたアカウントohmegaでは2次元プログラミング言語2Dで遊べる。
データとしてはユニット (), 組 (x,y), 直和 Inl x, Inr y が使える。これを使うと例えば
- 自然数：
Inr ()をゼロ、Inlを後続者ペアノ自然数として- 0:
Inr () - 1:
Inl Inr () - 2:
Inl Inl Inr () - 3:
Inl Inl Inl Inr () - …
- 0:
- リスト：
Inr ()を空リスト、Inl (x,xs)をconsとする- [x,y,z]:
Inl (x, Inl (y, Inl (z, Inr())))
- [x,y,z]:
- 真偽値：例題に出てくるわけじゃないので必要なら自分で定義するのだが、例えば
Inr ()を真、Inl ()を偽とする
という風にデータ構造をエンコードできる。関数型言語でお馴染みの要素があるが、関数は第一級ではないので2D自体は関数型言語ではない（ADVTRのRMLもそうだったが、UMIXの中の言語には第一級関数を持つものがない気がする）。
他の細かい特徴を挙げると、
Inl/Inrで分岐・パターンマッチを行うためのcaseコマンドがある。組に対しては組を分解するためのsplitコマンドがある。- 関数はモジュールと呼ばれ、2つ以下の入力を受け取り一つの出力を受け取る。関数の定義の中で自身を呼び出すことができる。
- 変数、というかワイヤーはそのままでは一箇所でしか消費できないが、sendコマンドを使って増やすと複数箇所で使用できるようになる。
InlやInr、(,)の導入等はsendコマンドで行う。- caseコマンドで分岐させた制御フローを合流させるには、「関数の返り値」を利用するしかない。はず。
最も特徴的なのは見た目で、最初から入っている「足し算をするプログラム」plus.2dはこんな感じである：
,..............................|....................................,
:plus | :
: *==================* | :
-->!send [(W,S),(W,E)]!--------#--------------------+ :
: *==================* | | :
: | | | :
: | v v :
: | *==============* *============* :
: | !case N of S, E!--->!send [(N,E)]!-------
: | *==============* *============* :
: | | :
: | v :
: | *========* *================* :
: +------------------->!use plus!------>!send [(Inl W,E)]!---
: *========* *================* :
,...................................................................,
,..............................................................,
:main :
: :
: *================================================* :
: !send [(Inl Inl Inl Inr (),E),(Inl Inl Inr (),S)]!--+ :
: *================================================* | :
: | v :
: | *========* :
: +--------------------------->!use plus!-----
: *========* :
,..............................................................,
見ての通りアスキーアートで配線する。配線は、変数の役割（値を受けわたす）と制御フローの役割がある。
同等のプログラムをML系言語で書けば次のようになるだろう：
datatype nat = Inl of nat | Inr of unit
-- xが左の入力、yが上の入力とする
fun plus x y = case y of
Inr _ => x
| Inl y' => Inl (plus x y')
val main = plus (Inl (Inl (Inl (Inr ())))) (Inl (Inl (Inr ())))
課題は
- 掛け算 (mult)
- リストの反転 (reverse)
- 0次元（というのか？全てが一直線上にあるやつ）レイトレーシング (raytrace)
- O’Cult（後述）の状態遷移器 (advise)
の4つで、O’Cultはコンテスト終了後に追加されたものである。
掛け算は、例の足し算を使って
datatype nat = Inl of nat | Inr of unit
fun plus x y = case y of
Inl y' => Inl (plus x y')
| Inr () => x
fun mult x y = case y of
Inl y' => plus x (mult x y')
| Inr () => Inr ()
という風なコードを書いてやれば良い。
2Dでの回答例は次のようになる：
,......................|................, :P *=================* | : -->!send[(W,S),(W,E)]!-#---------+ : : *=================* v v : : | *=============* *===========*: : | !case N of S,E!->!send[(N,E)]!- : | *=============* *===========*: : | | : : | v : : | *=====* *===============* : : +--->!use P!->!send[(Inl W,E)]!-- : *=====* *===============* : ,......................................., ,.............|.............................., :mult v : : *=============* *===============*: : !case N of S,E!->!send[(Inr W,E)]!- : *=============* *===============*: : | : : v : : *=================* *========* : ->!send[(W,S),(W,E)]!->!use mult!---+ : : *=================* *========* v : : | *=====* : : +---------------->!use P!------ : *=====* : ,............................................,
採点はverifyコマンドで行い、面積が小さいほど高得点がつく。コードゴルフである。結果さえ出せば誰でも同じ点数を獲得できたINTROやADVTRと異なり、チームごとの得点の差別化要因となっている。
面積は、コード全体を覆う長方形の面積として計算される。行数×最大カラム数という感じ。ファイル転送の際に最後を空行で終えているとそれも行数としてカウントされるので注意。
さっき貼ったコードの面積は1242で、採点すると37点（CIRCS.MUL）がつく。気合を入れてコードを縮めると例えば
,..................|..................,,.....|..................................., :P | *=============* ::mult | *=============* *===============*: --+ +>!case W of S,E!+ :--+ +>!case W of S,E!->!send[(Inr W,E)]!- : v *=============*v :: v *=============* *===============*: :*=================* | *===========*::*=================*| : :!send[(N,S),(N,E)]!---#>!send[(W,E)]!-:!send[(N,S),(N,E)]!#----+ : :*=================* v *===========*::*=================*v v : :++*===============* *=====* :: | *========* *=====* : :+>!send[(Inl W,E)]!->!use P!----------: +-->!use mult!->!use P!------------ : *===============* *=====* :: *========* *=====* : ,.....................................,,.........................................,
という感じになり、これは面積902で、採点すると46点がもらえる。
さて、問題を解くとメールが届く。確認してみると
% mail↵ First unread message: --------------------- Date: Fri, 1 Jan 19100 00:00:00 -0400 From: Cain Gardener <gardener@cbv.net> To: ohmega@cbv.net Subject: Something is wrong... Dear Bill, I hope that you never read this. This is an automated message sent in the event that neither Betty nor I have logged into UMIX for at least 60 days. It has been -6241731 days since one of us last logged on. Something must be wrong; you know that the cult has its enemies. There's probably nothing you can do for us now, except to make sure that our research into programming languages is not lost. I've attached our passwords below... please, if you can, carry on with our research, and make sure the world knows what we've done! Betty's login: bbarker password: plinko My login: gardener password: mathemantica Farewell friend, Cain Gardener
という感じで何やら悲壮な感じである。ともかく、これでbbarkerとgardenerのパスワードが手に入った。
リストの反転は、関数型プログラマーにはお馴染みの
datatype 'a list = Inl of 'a * 'a list | Inr of unit
fun r acc xs = case xs of
Inl (y,ys) => r (Inl (y,acc)) ys
| Inr () => acc
fun rev xs = r (Inr ()) xs
みたいなやつである。筆者の現在のスコアは面積774で46点（CIRCS.REV）である。
問題はレイトレーシングである。一旦解けば1000点以上手に入るが、その分大変である。
筆者は
- SMLで下書きする
- 個々の関数を2Dに変換する：先にiPadでお絵描きしてから手作業でアスキーアートに変換した。例：
- 2Dに変換したそれぞれのプログラムを一つにまとめる：この段階で配置を工夫すれば圧縮につながるかもしれないが、まだそこまではやっていない。
デバッグが大変で、最終的には「一つの関数についていくつかテストケースを与えて実行する」スクリプトを使ってデバッグした。テスト万歳。
筆者の書いたコードは、モジュールの配置を工夫しない状態では面積21960で、得点は1221点（CIRCS.RAY）である。
筆者は完全に手作業で解いたわけだが、自動化するとしたら最後の「2Dに変換したモジュールを2次元上に配置する」部分が筆頭だろう。MLライクなプログラムを2Dにコンパイルする部分を自動化するのは大変そうだ。
2DでO’Cultを実装するやつは気が向いたらやる。元々後付けの課題なのでやらないかもしれない。
hmonk: O’Cult (ADVIS)
項書き換え系である。
Add Z y => y; Add (S x) y => S (Add x y);
という風に規則をいくつか指定できるので、お題を満たす規則集合を書け、というもの。
規則中に同じ変数名が複数出現する場合は、単一化できる場合にマッチする（非線形なパターンってやつ？）。
ただし規則の適用が厄介で、複数箇所に規則がマッチする場合は最もマッチ数（？）が少ない部分にマッチする。マッチ数が同じ場合は全くマッチしない（！）。例えば、先程の規則は
Add (Add (S (S Z)) (S Z)) (Add (S (S (S Z))) (S (S Z)))
という項にはマッチしない。
最初のお題はペアノ算術（足し算 Add と掛け算 Mult）である。
Add Z y => y; Add (S x) y => S (Add x y); Mult Z y => Z; Mult (S x) y => Add y (Mult x y);
普通のシステムなら上記の規則集合でいけるはずだが、O’Cultではうまくいかない。筆者が思いついたのは、MultAddという項を導入し、Add/Mulその他を含む一番外側の項に常に規則が適用されるようにする
Add Z y => y;
Add (S x) y => S (Add x y);
Add (Add x y) z => Add x (Add y z);
Add (Mult x y) z => MultAdd x y z;
Add (MultAdd x y z) w => MultAdd x y (Add z w);
Mult x y => MultAdd x y Z;
{- MultAdd x y z := x * y + z -}
MultAdd Z y z => z;
MultAdd (S x) y z => MultAdd x y (Add y z);
MultAdd (Add x y) z w => MultAdd x z (MultAdd y z w);
MultAdd (Mult x y) z w => MultAdd x (Mult y z) w;
MultAdd (MultAdd x y z) w u => MultAdd x (Mult y w) (MultAdd z w u); {- (x * y + z) * w + u => x * y * w + (z * w + u) -}
Compute x => x;
.
というものである。この他に、他の人の記事を参考にしたのだが、「マーカーとなる項が常に一つだけ存在するようにして、常にマーカーの周囲だけにマッチするようにする」という方法もある。後者の戦略では算術は次のように書ける：
Compute Z => Computed Z; Compute (S x) => S (Compute x); Compute (Add x y) => Add x (Compute y); Compute (Mult x y) => Mult x (Compute y); S (Computed x) => Computed (S x); Add x (Computed y) => Add (Compute x) y; Mult x (Computed y) => Mult (Compute x) y; Add (Computed Z) y => Compute y; Add (Computed (S x)) y => S (Compute (Add x y)); Mult (Computed Z) y => Computed Z; Mult (Computed (S x)) y => Compute (Add y (Mult x y)); Computed x => x; .
獲得できる得点は規則集合が小さければ小さいほど多く、MultAddを使う規則集合は160点（ADVIS.ARH）、マーカーを使うやつは164点を獲得できる。
arithを通すとメールが届く。
Date: Fri, 1 Jan 19100 00:00:00 -0400
From: hmonk@cbv.net
To: hmonk@cbv.net
Subject: O'Cult User Survey
**********************************************************************
TESTING AUTOMATED E-MAIL SURVEY
This should be sent to users after they pass the 'arith' suite---
I only want responses from qualified people.
FIXME: Before going live with this, I need to ask gardener and ohmega
about doing installations in guest accounts---I can't give out their
actual passwords!
**********************************************************************
Dear O'Cult User,
I'm thinking about extending O'Cult with other programming paradigms:
two-dimensional-oriented programming
login: ohmega password: bidirectional
bug-oriented programming
login: gardener password: mathemantica
Since you're such a good O'Cult programmer, I'd welcome your advice
(heh!) on how to do so. Because these languages are not yet publicly
available, you'll have to log in using the above accounts to run the
research prototypes.
-Harmonious
両者のパスワードは既に取得しているので冗長なのだが、冗長なのはいいことである。
もう一つの課題はeXcessively Malleable Language (XML)という謎の木構造を正規形にする問題である。ここでのXMLは
quality ::= Bold | Emph | Maj doc ::= A | B | Seq doc doc | Tag quality doc
という木構造で、正規形（short normal form; SNF）は以下のパターンを含まないもの
Seq (Seq d1 d2) d3 {- -> Seq d1 (Seq d2 d3) になっているべき -}
Tag q (Tag q d) {- -> Tag q d になっているべき -}
Seq (Tag q d1) (Tag q d2) {- -> Tag q (Seq d1 d2) になっているべき -}
かつ、ネストした Tag 式（Tag q1 (Tag q2 d)）について外側のqualityの方が小さい（ただし Bold < Emph < Maj）ようなものである。
筆者の現在の解答は、
- まず、Tagが内側、Seqが外側になるように変形する。この際
Seq (Seq d1 d2) d3みたいなやつも正規化する - 次に、
Seq (Tag q d1) (Tag q d2)を正規化する
という戦略でやっている。これで132点取れている。
この二つの課題で164+132=296点だが、スコアボードを見ると300点以上のチームが多いので、まだ改良の余地があるようだ。スコアボードで最高得点をとっているのは優勝チームで、336点とっている。
yang: Balance (BLNCE)
パスワードのU+262Fは太極図☯YIN YANGである。
変態VMである。このVMは
- サイズ256の、8ビット配列（メモリー）
- Instruction Pointer (IP)
- Instruction Speed (IS)
- 8ビットのレジスター6つ（うち4つは「ソース」、2つは「デスティネーション」）
- 4つの命令
- MATH: 足し算と引き算を同時に行う。
- LOGIC: ビットANDとXORをを同時に行う。
- SCIENCE: 条件によってISを変更する。ISが0ならVMを停止する。
- PHYSICS: レジスターを変更する。
という仕様である。命令は8ビット固定長にコードされる。
ここまでくるとプログラミングというよりはパズルであり、最初の課題4つは「VMを停止せよ」である。
それぞれの課題ではメモリーとレジスターの初期状態および達成すべきメモリーやレジスターの状態が指定される。最初の課題2つのメモリーの初期状態として何故か /etc/passwd が与えられるので、実行後のメモリーダンプを見ることで何人かのパスワード（gardener, ohmega, yang）を入手できる。
筆者が現在までに解いたのは、VMを停止させる問題stop / stop1 / stop127 / stop128である。VMを停止させるにはM[sR[0]]≠0な状態でSCIENCE命令を発行する必要がある。M[sR[0]]の初期値は0で、メモリーの初期値としてはM[0]以外の場所に0じゃないものが転がっているので、PHYSICS命令でsRの値を変更してからSCIENCE命令を発行することになる。
これも例によってコードが短いほど得点が高く、筆者のstop / stop1 / stop127 / stop128に対する解答はいずれも最高得点の10点／10点／20点／15点を獲得した。
Balanceも頑張れば1000点以上獲得できるようなのだが、難しそうだ。
gardener: Antomaton (ANTWO)
セルオートマトンである。盤面上に一匹以上アリがいて、それらのうち少なくとも一匹がエサにたどり着けるようにする必要がある。
アリの動きは規則によって決まっている（例：壁にぶつかった時は右を向く）が、進行方向に何もなかった時の移動後の向きと、他のアリとぶつかりそうになった時の向きをプログラムできる。このプログラムは、NEWSの4種類の文字からなる7文字である。
アリには群れの種類（clan）があって、同じ群れに属するアリはプログラムを共有する。
アリのプログラムと初期マップを与えると、シミュレーターで動かすことができる。初期マップの例は次のようなものだ：
Amusement Park NNNWWWW NNWWEEE NNNSEEE 8 8 o o o # - - - - o o o - - - #1v o o o -2^ # -1< o o o - - $ - # # - - - - - - - - - - - - -0> - - - - - - - - # - - - # - - - -
最初の7文字×3行はアリのプログラムで、次の行はマップのサイズ、それ以降は初期マップである。 o は穴、 # は壁、- は何もない空間、$ はエサで、 ^><v はアリ（矢印の向きは進行方向）を表していて左の番号は群れの番号である。
課題はプログラムの一部と初期マップの一部が欠けた状態で与えられ、アリがうまくエサにたどり着けるように欠けた部分を埋めるのがプレイヤーの役割である。例えば最初の問題は
Puzzle 1: Simple NNNNNNN ******* 8 8 - - - - - - - - -0>0< - - - - - - - - - - # - - - - - - - - - - - - - - - - $ - - - - -0v - - - - * - -0^ - - - - - - - - - - -
で、アスタリスクになっているのが欠けた部分である。この例だと群れ0のプログラムは変更不可、群れ1のプログラムは自在に設定できる。また、マス目のうち一つを好きに設定できる。
初期状態で群れ0のアリは4匹いるが、与えられたプログラムではいずれもこれ以上動けない（消滅もしない）。エサに到達させるには群れ1のアリを配置する必要がある。というわけで、マップの * の位置に群れ1のアリを配置し、次の図の経路で移動させれば良いことがわかる（アリは壁に衝突すると常に右折する）：
- - - - - - - - -0>0< - - - - - - > > > v # - - - ^ - - v - - - - ^ - - > > $ - - ^ - -0v - - - -1^ - -0^ - - - - - - - - - - -
なので、
- 前に何もない状態では向きは変えず（1文字目が
N） - 前に
>がいた場合は右を向き（5文字目がE） - 前に
^がいた場合は左を向く（4文字目がW）
という風にプログラムとなる7文字を組み立てれば良い。puzzle1の解答例は
Puzzle 1: Simple NNNNNNN NEEWEEE 8 8 - - - - - - - - -0>0< - - - - - - - - - - # - - - - - - - - - - - - - - - - $ - - - - -0v - - - -1^ - -0^ - - - - - - - - - - -
となる。
puzzle1の次に簡単なのがコンテスト後に追加されたpuzzle15で、これは巨大な迷路である（迷路の壁でSWITCH YOUR GOGGLESと中央部に書かれている）。アリは1匹しか配置できず、他のアリはいない。アリが壁にぶつかった場合の動作は指定できない（常に右を向く）ので、実質的にプログラムできるのは「前に何もなかった場合の直進後の向き」だけである。
迷路を手動で解いて経路をプログラムすることはできないので、単純なアルゴリズムで迷路を解く必要がある。つまり、「左の壁づたいに動かす」である。直進後に左を向く（1文字目を W にする）ようにすればこのアルゴリズムが実現できる。
「左の壁づたいに動かす」ができれば、壁役を用意することによってpuzzle2も解ける。「左の壁づたいに動くやつと壁役の組み合わせ」は半分の速度で直進するので、これと別の一匹を組み合わせるとpuzzle3が解ける。また、ぶつかった時の動作をゴニョゴニョすればpuzzle5も解ける。
筆者が現在までに解けたのはこの5つで、80点である。
なお、ホームディレクトリーに転がっている.historyを見るとbbarkerのパスワードが入手できる。
Black Knots (BLACK)
あみだくじである。指定された置換を実現しつつ、「左から右への移動」の回数が所定の回数となるようなあみだくじを作る必要がある。
例えば
012 ||| ><| |>< |||
というあみだくじがあったとする。縦棒は縦棒、横棒は >< で表している。0番は上から辿っていくと2番にたどり着き、その際に左から右への移動を2回行う。1番は辿ると0番にたどり着き、左から右への移動は0回である。2番は辿ると1番にたどりつき、左から右への移動は0回である。このことを
0 -> (2,2) 1 -> (0,0) 2 -> (1,0)
と表す。矢印の右側は，行き先と、左から右への移動回数の組である。この組のデータが与えられるので、それを実現するあみだくじを作れ、というのが課題である。例えば課題000は
0 -> (3,4) 1 -> (2,3) 2 -> (0,1) 3 -> (1,1)
という指定で、これを実現するあみだくじの解答例は
><|| |><| ><>< |><| ><>< ><><
となる。
課題の数は全部で9個、課題010は棒の数が10本、課題500は棒の数が500本である。10本ならギリギリ手でもいけるかもしれないが、500とかどう考えても手では解けない。
ちなみに、上記の解答例を採点プログラムに通すと、何故か名前とパスワードの入力を求められる。適当に入れてみると……
% verify↵
Please enter your machine now using the |>< characters.
Terminate with an empty line.
><||
|><|
><><
|><|
><><
><><
[BK] Your machine has the same width as black-knot model 000.
[BK] Checking against that model's spec...
[BK] Your machine successfully replicated black-knot model 000!
High score!
Please enter your name: mod_poppo↵
Please enter your password: damepo↵
===============================
HIGH SCORES
===============================
SCORE NAME PASSWORD
50 howie xyzzy^H^H^H^H^H
40 yang U+262F
10 mod_poppo damepo
0 guest
0 guest
0 yang how do I delete this??
0 guest
0 guest
0 guest
0 guest
0 guest
0 yang please take my password off!
という感じでhowieとyangのパスワードが手に入る。ギャグか？
得点まとめ
筆者が現在までに獲得した得点は次のようになる：
| INTRO | CIRCS | BLNCE | BLACK | BASIC | ANTWO | ADVTR | ADVIS | Total |
| 265 | 1313 | 55 | 10 | 100 | 80 | 810 | 296 | 2929 |
1006点以上の獲得でAssistant Administratorのアカウントが、2006点以上の獲得でAssociate Administratorのアカウントが開放される。するとそれぞれの権限を持つrootとしてログインできるようになり、the Cult of Bound Variables滅亡直前と思しきチャットログが読めるようになる。どうやらCBVはthe Cult of the LValueと呼ばれる勢力からの攻撃（コンピューターウイルス的な？）を受けて滅んだらしい……？権限が高いほどチャットログを最後まで読めるようになるようで、早く3006点に到達したい。
なお、rootのホームディレクトリーにはおまけとして、Universal Machineのリファレンス実装（もちろんUniversal Machine上で動作する）が置かれている。Webサイトで配布されているものと多分同じだ。dumpコマンドは（C7sus4もだったけど）ここで役に立つのか、という感想である。