ICFP Programming Contest 2006 “The Cult of Bound Variable” に挑戦してみる

ICFPプログラミングコンテスト2006に今更ながら挑戦しようとしている。

目次

どういうコンテストなのか

遺跡から発掘された古代文明の計算機(のプログラム)を実行・解析しよう、みたいなお話。

VMの仕様とその上で動く動作するバイナリーが与えられるので、VMを実装してバイナリーを動かして(動かすとUMIXなる謎のシステムが動作する)publicationと呼ばれる特定の文字列を回収するのが目的である。

当時リアルタイムで参加した方々の日記へのリンクを貼っておく:

2006年当時の筆者は中学生で、参加者の日記を読んですごいな〜〜と思いつつ自分でもある程度挑戦してみた(adventureの最初のエリアを抜けるくらいまではやったはず)。しかし、実力不足でクリア(?)には至らなかった。

15年経った今、やっぱり忘れられないので再挑戦してみることにした。流石に中学生の時分よりは知識も経験も積んだはずだ。少なくとも、 (\b.bb)(\v.vv) という文字列を見て「ラムダ計算の停止しない項だな」と分かる程度の知識はついた。

15年前のコンテストにネタバレとか言っても仕方がないと思うので、適宜ネタバレを含む解説を書いていく。実況と呼んで良いかもしれない。

自分の書いたコード類は

に置いておくことにする。

なお、配布されるバイナリーのソースコードやそれをコンパイルするためのコンパイラー(SMLで書かれている、humlockというやつ)のコードは http://boundvariable.org/code.shtml で配布されている。付属しているMakefileが現在のMLtonに対して正しく動作しない(当時はMLtonが.cmを解釈したのか?)のが、VMの仕様もSMLという言語も変わらない中で唯一15年という時の経過を感じさせる要素である。humlockがセルフホストしていればまさに不朽だったかもしれないが、それは望みすぎか。

The Universal Machine

まずは課題のページ(から読めるum-spec.txt)で仕様が与えられるVM、”the Universal Machine” を実装する。課題は全部この上で動作するので、なるべく高速なVMを書くことが望ましい。

VMは8個のレジスターとヒープ(と言って良いのか?Arrayと呼ばれる)を持つ。ワード幅は32ビットで、命令も32ビット固定長である。大半の命令は0個〜3個のレジスターに対する操作で、RISCっぽさがある。しかし「calloc/freeに相当する命令がある」「putchar/getcharに相当する命令がある」あたりはやっぱりVMなのだと思わされる。

ヒープにある配列は32ビットのIDっぽいもので識別される。アドレス幅が32ビットなマシンならcallocが返すポインターをそのままIDとして使うこともできる(筆者が中学生の頃に書いたVMはそのようにした記憶がある)が、昨今は64ビットが一般的なので、確保するアドレスを特定の4GBに押し込める工夫でもしない限りは0から始まる連番をIDとして使うことになるだろう。

プログラム自身も配列として扱われ、そのIDは0である。この「0番配列」にも書き込みができるし、別の配列を「0番配列」として置き換えることもできる。

命令は14個ある。

  • #0. Conditional Move
    • 指定されたレジスターCの値が0でなかったらレジスターBの値をレジスターAに代入する。
  • #1. Array Index
    • 配列の値を参照する。
  • #2. Array Amendment
    • 配列の値を更新する。
  • #3. Addition
    • modulo 2^32で足し算を行う。
  • #4. Multiplication
    • modulo 2^32で掛け算を行う。
    • チューリング完全を目指すだけなら掛け算は必要ない(実際、RISC-Vの最小構成では乗算を省いている)が、実用上の理由(速度)で命令セットに入れていると考えられる。
  • #5. Division
    • 符号なし32ビット整数の割り算を行う。
    • 入っている理由は乗算と同じ。
    • 【追記】UMIX上で動作するプログラミング言語で、除算命令を持つものはほとんどない(C7sus4くらい?)。この命令はもっぱらビットシフトに使われているのではないだろうか。
  • #6. Not-And
    • ビットごとのNANDを取る。
    • NANDがあればなんでもできる。入力オペランドを同じに設定すれば単なるbitwise notになるし、複数組み合わせればANDやORも作れる。
    • 0が入ったレジスターを入力にすればbitwise notを使って-1 (0xffffffff)を作れるし、それを掛け算すれば符号の反転ができる。さらに足し算を使えば引き算が実装できる。
  • #7. Halt
    • VMを終了させる。
  • #8. Allocation
    • 新しい配列を確保する。要はcalloc。
  • #9. Abandonment
    • 指定された配列を放棄する。要はfree。
  • #10. Output
    • 1文字出力する。要はputchar。
  • #11. Input
    • 1文字入力する。要はgetchar。
    • getchar の前に fflush(stdout) を実行しておくべきだろう。
  • #12. Load Program
    • この命令セットの中で一番面白いやつ。
    • レジスターBの値をIDに持つ配列を複製し、それを0番配列(プログラム)として置き換える。
    • 新しいプログラムカウンターはレジスターCの値が使用される。
    • 大抵の場合はレジスターBの値は0で、その場合この命令は単なるジャンプと等価となる。仕様のコメントにはわざわざ「レジスターBの値が0である場合に対して最適化しとけよ(意訳)」と書かれている。
  • #13. Orthography
    • 25ビットの即値を指定されたレジスターに代入する。

幾つかの動作は「未定義動作」として扱って良い。配列のIDが無効だとか、配列の範囲外アクセスとか、ゼロ除算とか。

さて、この命令セットではLoad Program命令に値が0なレジスターを渡してジャンプを行う。値が0なレジスターはもちろんOrthography命令で作れるわけだが、その度に「潰しても良い」レジスターを用意するのは鬱陶しい。そうすると、この命令セットをターゲットとして出力するコンパイラーとしては特定のレジスターを「ゼロレジスター」、つまり常に0が格納されたレジスターとして扱うという戦略が考えられる。

現代の命令セットを見ると、AArch64やRISC-Vは31個の汎用レジスターを用意しているが、32というキリのいい数ではないのは「ゼロレジスター」を提供するためである。

というわけで調べたところ、UMIXについては6番レジスター(0から数える)がゼロレジスターとして使用されているようである。このことはコンパイラー(humlock)のソースコードからも確認できる。残念ながらsandmark.umzでは6番レジスターにも0でない値が代入されることがあるようだ(self checkの一環だろうか)。

まあ6番レジスターがゼロレジスターだからどうしたという話なのだが。JITに活用できるかはわからない。

VMのベンチマークとしては、公式から配布されているsandmark.umzが使える。VMが遅くてsandmark.umzのフルの実行に時間がかかって嫌だという場合は、ソースコード中にfastmarkというライト版のソースコードが含まれているので、(humlockを使って)自分でビルドすれば良い。ビルドが面倒な人用に筆者のリポジトリーの中にfastmark.umzを入れておいた。

VMの実装

まずはディスパッチにswitchを使う普通のインタープリターを書いてみた:

なんの変哲もない。assert満載だが、最近のコンパイラーとCPUは賢いので分岐予測がアレしてassertのコストは実質タダ、誤差の範囲だと思って良いだろう。

筆者の手元ではsandmark.umzの実行にかかる時間は

  • Apple M1: 16秒
  • Core i7-3770なデスクトップ:25.5秒
    • 2013年ごろに組んだマシン。
  • Ice Lake(2GHz, Core i5)搭載MacBook Pro:30秒
    • 2020年のマシン。

という結果だった。デスクトップ vs ノートPCという違いはあるが、2020年のコンピューターが2013年のマシンに負けるのは悔しい。

VMの高速化についてdirect threaded VMというものを聞いたことがあったので

などを参考に組んでみたところ、

  • Apple M1: 14秒
  • Core i7-3770: 16秒
  • Ice Lake搭載MacBook Pro: 27秒

という結果だった。

言語処理系Slackで聞いてみたところ、κeen氏に「LLVMは普通のVMをThreaded VMと同等のコードに最適化してくれる」

と教えていただいた。

当初、配列の確保で空いているIDを線形探索する実装を使っていたが、それだとめちゃくちゃ遅い。Apple M1でsandmarkが12分ほどかかっていた。自前でfreelistを管理するようにしたらめちゃくちゃ高速化した。

switchベースと比べてdirect threaded VMで若干高速化はしたが、これ以上の速度向上を目指すにはJITをやることになる。筆者の手元にある最強のマシンはApple M1搭載Mac miniなので、ターゲットとなる命令セットはAArch64となる。

ググって見つけた、UMをJITで実装した先人へのリンクを貼っておく:

JITの実装は大変そうなので次回以降に回し、今回は最初に書いたswitchベースのVMを使っていく。

codex.umzからumix.umの入手

課題のページからcodex.umzをダウンロードする。VMがうまく実装できていれば

self-check succeeded!
enter decryption key:

というメッセージと共に入力待ちの状態になる。ここで復号鍵 (\b.bb)(\v.vv)06FHPVboundvarHRAk を入力すれば、

decrypting...
ok
LOADING: 9876543210

 == CBV ARCHIVE ==
    VOLUME ID 9

 Choose a command:

 p) dump UM data
 x) exit

? 

という画面になる。p を入力すれば

UM program follows colon:<バイナリーのダンプ>

が標準出力に吐き出される。コロンの次以降の出力をファイルに保存すればUMIXのバイナリー(ここでは umix.um と呼ぶ)の出来上がりなわけだが、量が多いしバイナリーなのでリダイレクトを使って適宜保存しよう。Windowsの人は改行コードがアレかもしれないのでWSLで作業した方が良いかもしれない。

コロン以下を切り出すのはシェル芸でもできるのかもしれないが、筆者はLuaで適当に書いた。筆者のリポジトリーのMakefileとextract.luaを参照。

UMIXの起動 — INTRO

umix.um をVMで実行すると

<空行の連続>
12:00:00 1/1/19100
Welcome to Universal Machine IX (UMIX).

This machine is a shared resource. Please do not log
in to multiple simultaneous UMIX servers. No game playing
is allowed.

Please log in (use 'guest' for visitor access).
;login: 

と出力されて入力待ちになる。まずは guest でログインしよう。パスワードは求められない。

logged in as guest
INTRO.LOG=200@999999|ホニャララ


You have new mail. Type 'mail' to view.
% 

INTRO.LOG=200@999999|ホニャララ という文字列(ホニャララは実際には英数字列)はゲームの目的であるpublicationの一つである。@の前の数字が点数っぽくて、これは200点である。

メールが来ているようなので mail と打ち込む。

First unread message:
---------------------

Date: Fri, 1 Jan 19100 00:00:00 -0400
From: Administrator <root@localhost>
To: guest@cbv.net
Subject: guest account misuse

To whom it may concern:

Guest access is provided as a courtesy to the community. We have
recently observed an increase in abuse using the guest account. For
example, the following sequence of commands obviously represents an
attempt to gain unauthorized access to the account "howie":

  cd code
  /bin/umodem hack.bas STOP
  /bin/qbasic hack.bas
  ls /home
  ./hack.exe howie
  
Moreover, the file that you uploaded with umodem appears to be 
corrupted and did not compile.

Please have respect for your fellow users,
Admin

% 

どうやらguestアカウントを悪用してアカウントをハックしようとするならず者がいるようだ。我々もそのならず者に倣ってアカウントをハックする。

…の前に。もう一度 mail を実行する。するともう一つメールが来ているのがわかる。

% mail↵
No unread messages.

---------------------------------------------------------------------
INBOX:

Message  Read?  Sender                                Subject
-------  -----  ------                                -------
      0    Yes  Administrator <root@localhost>        guest account misuse
      1    Yes  Donald Nut <dnut@clv.net>             Yours loan is approved 7l0l

---------------------------------------------------------------------

Which message would you like to read?
Type a number from '0' to '1'.
Or type 'q' to quit.
1↵

Date: Fri, 1 Jan 19100 00:00:00 -0400
From: Donald Nut <dnut@clv.net>
X-Organization: First Projection On-Line: So Easy to Use, No Wonder It's #1!
To: guest@cbv.net
Subject: Yours loan is approved 7l0l

Dear Homeowner

You have been approved for a 

INTRO.MUA=5@999999|ホニャララ

house loan.  This offer is being presented to you right now!. 
Your credit history is in no way a factor.  To take advantage 
of this Limited Time Opportunity, please take a minute and 
confirm your curiosity or intention to accept this loan.

Best Regards
Don Nut
Loan Manager

Press Enter to continue...
↵

---------------------------------------------------------------------
INBOX:

Message  Read?  Sender                                Subject
-------  -----  ------                                -------
      0    Yes  Administrator <root@localhost>        guest account misuse
      1    Yes  Donald Nut <dnut@clv.net>             Yours loan is approved 7l0l

---------------------------------------------------------------------

Which message would you like to read?
Type a number from '0' to '1'.
Or type 'q' to quit.
q↵
Goodbye!
% 

というわけでINTRO.MUAの5点獲得。

ls してみると、 code/ の他に a.out という実行ファイルがあるのがわかる。実行してみるとセグフォを起こす。

% ls↵
code/
a.out*
% ./a.out↵
segmentation fault (core dumped)

UMIXの世界におけるcore dumpとは……と思いながらもう一度 ls するとファイルが増えている。中を見てみると……

% ls↵
core
code/
a.out*
% cat core↵
INTRO.OUT=5@999999|ホニャララ

というわけでINTRO.OUT/5点獲得。

help を実行すると実行可能なコマンドが見られる。

% help↵
For information on a specific command, type
  help cmd
UMIX Commands:
  ls
  rm
  cat
  more
  cdup
  mkdir
  cd
  run
  pwd
  dump
  logout
  telnet

Also, try running programs with no arguments for usage instructions.

すでに使った lscat の他、UNIXでお馴染みのものがいくつか見られる。dump コマンドは実行可能ファイルには使えなさそうなポンコツである(今後使う場面があるのだろうか?)。

そして一番後ろには telnet がある。こんなgetcharとputcharでしか世界と繋がれないVMの上でtelnetとかw と思うのだが、localhostくらいは使えるかもしれない。もしかしたら80番ポートでWebサーバーが動いてるかも……?

% telnet localhost 80↵
GET / HTTP/1.0↵
↵
HTTP/1.1 200 OK
Date: Sun, 1 Jan 19100 00:00:00 UCT
Server: CultWeb/1.0 (UMIX)
Connection: close
Publication: INTRO.WEB=15@999999|ホニャララ
Content-Length: 1616
Content-Type: text/html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>CultWeb Home</title>
<link rel="shortcut icon" href="favicon.ico" type="image/x-icon" />
</head>
<body>
<img style="float:right" src="cbv.gif" alt="CBV logo" />
<h1>Welcome to CultWeb!</h1>


<img alt="under construction" src="under_construction.gif" /> <b>This web site is under construction!</b>

<hr style="background:url(rainbow.gif); height:8px; width:100%; border:none" />
<a href="/index.html"><img src="home.gif" alt="home" /></a> <img src="links.gif" alt="links" /> <img src="contact.gif" alt="contact us" />

<p>Welcome to the home web of the Cult of the Bound Variable. This web
site is currently under construction, so please bear with us as we
improve our Home Page. Here you will find all sorts of things such as
information about our Organization, our collection of Links and Bookmarks, 
and recipes.</p>

<div style="margin-left:auto;margin-right:auto;width:81px"><img alt="space ship" src="sship.gif" /></div>

<h2>Level 2 Header</h2>

<h3>Level 3 Header</h3>
<ul>
  <li>Bulleted list</li>
  <li><a href="http://boundvariable.org/">http://boundvariable.org/</a></li>
  <li><a href="http://example.com/">http://example.com/</a></li>
</ul>


This home site has been visited <img src="0.gif" alt="0"><img src="0.gif" alt="0"><img src="0.gif" alt="0"><img src="0.gif" alt="0"><img src="0.gif" alt="0"><img src="0.gif" alt="0"><img src="5.gif" alt="5"> times since 13 July 19099.

<p><p>
<hr style="background:url(rainbow.gif); height:8px; width:100%; border:none" />
<i>Last updated: 13 July 19099. by Webmaster</i>
</body>
</html>

というわけで、INTRO.WEB/15点獲得である。HTMLがこんな古代から存在したなんて……(棒)

【追記】ちなみに、複数回アクセスするとアクセスカウンターの部分がご丁寧に更新される。

ここまでのINTROで225点獲得した。今後INTRO.UMDとINTRO.QBCで10点ずつ獲得するので、INTROでは最低245点獲得できることになる。しかしスコアボードを見るとINTROの点数は230点が上限だ。これは

  • INTRO.WEBが後付け要素である(コンテストの途中または終了後に追加された)
  • 誰もコンテスト中にINTRO.WEBに気づかなかった(まさか!)

のどちらだろう?codexにはコンテスト終了後にeaster eggが追加されている旨がboundvariable.orgのトップページに書かれているのでそれだろうか。

QVICKBASIC: アカウントハック

本題に戻ろう。コンテストを進めるには、guest以外のアカウントのパスワードを知る必要がある。Adminからのメールにある手順に従ってアカウントハックを目指す。とりあえずhack.basの中身を見てみよう。

% cd code↵
% cat hack.bas↵
V        REM  +------------------------------------------------+
X        REM  | HACK.BAS      (c) 19100   fr33 v4r14bl3z       |
XV       REM  |                                                |
XX       REM  | Brute-forces passwords on UM vIX.0 systems.    |
XXV      REM  | Compile with Qvickbasic VII.0 or later:        |
XXX      REM  |    /bin/qbasic hack.bas                        |
XXXV     REM  | Then run:                                      |
XL       REM  |   ./hack.exe username                          |
XLV      REM  |                                                |
L        REM  | This program is for educational purposes only! |
LV       REM  +------------------------------------------------+
LX       REM
LXV      IF ARGS() > I THEN GOTO LXXXV
LXX      PRINT "usage: ./hack.exe username"
LXXV     PRINT CHR(X)
LXXX     END
LXXXV    REM
XC       REM  get username from command line
XCV      DIM username AS STRING
C        username = ARG(II)
CV       REM  common words used in passwords
CX       DIM pwdcount AS INTEGER
CXV      pwdcount = LIII
CXX      DIM words(pwdcount) AS STRING
CXXV     words(I) = "airplane"
CXXX     words(II) = "alphabet"
CXXXV    words(III) = "aviator"
CXL      words(IV) = "bidirectional"
CXLV     words(V) = "changeme"
CL       words(VI) = "creosote"
CLV      words(VII) = "cyclone"
CLX      words(VIII) = "december"
CLXV     words(IX) = "dolphin"
CLXX     words(X) = "elephant"
CLXXV    words(XI) = "ersatz"
CLXXX    words(XII) = "falderal"
CLXXXV   words(XIII) = "functional"
CXC      words(XIV) = "future"
CXCV     words(XV) = "guitar"
CC       words(XVI) = "gymnast"
CCV      words(XVII) = "hello"
CCX      words(XVIII) = "imbroglio"
CCXV     words(XIX) = "january"
CCXX     words(XX) = "joshua"
CCXXV    words(XXI) = "kernel"
CCXXX    words(XXII) = "kingfish"
CCXXXV   words(XXIII) = "(\b.bb)(\v.vv)"
CCXL     words(XXIV) = "millennium"
CCXLV    words(XXV) = "monday"
CCL      words(XXVI) = "nemesis"
CCLV     words(XXVII) = "oatmeal"
CCLX     words(XXVIII) = "october"
CCLXV    words(XXIX) = "paladin"
CCLXX    words(XXX) = "pass"
CCLXXV   words(XXXI) = "password"
CCLXXX   words(XXXII) = "penguin"
CCLXXXV  words(XXXIII) = "polynomial"
CCXC     words(XXXIV) = "popcorn"
CCXCV    words(XXXV) = "qwerty"
CCC      words(XXXVI) = "sailor"
CCCV     words(XXXVII) = "swordfish"
CCCX     words(XXXVIII) = "symmetry"
CCCXV    words(XXXIX) = "system"
CCCXX    words(XL) = "tattoo"
CCCXXV   words(XLI) = "thursday"
CCCXXX   words(XLII) = "tinman"
CCCXXXV  words(XLIII) = "topography"
CCCXL    words(XLIV) = "unicorn"
CCCXLV   words(XLV) = "vader"
CCCL     words(XLVI) = "vampire"
CCCLV    words(XLVII) = "viper"
CCCLX    words(XLVIII) = "warez"
CCCLXV   words(XLIX) = "xanadu"
CCCLXX   words(L) = "xyzzy"
CCCLXXV  words(LI) = "zephyr"
CCCLXXX  words(LII) = "zeppelin"
CCCLXXXV words(LIII) = "zxcvbnm"
CCCXC    REM try each password
CCCXCV   PRINT "attempting hack with " + pwdcount + " passwords " + CHR(X)
CD       DIM i AS INTEGER
CDV      i = I
CDX      IF CHECKPASS(username, words(i)) THEN GOTO CDXXX
CDXV     i = i + I
CDXX     IF i > pwdcount THEN GOTO CDXLV
CDXXV    GOTO CDX
CDXXX    PRINT "found match!! for user " + username + CHR(X)
CDXXXV   PRINT "password: " + words(i) + CHR(X)
CDXL     END
CDXLV    PRINT "no simple matches for user " + username + CHR(X)
CDL      REM
CDLV     REM  the above code will probably crack passwords for many
CDLX     REM  users so I always try it first. when it fails, I try the
CDLXV    REM  more expensive method below.
CDLXX    REM
CDLXXV   REM  passwords often take the form
CDLXXX   REM    dictwordDD
CDLXXXV  REM  where DD is a two-digit decimal number. try these next:
CDXC     i = I
CDXCV    DIM j AS INTEGER
D        IF i >  ~3U$p;JS*X?:8< MRc<1 ,,,)/zWWWWWWWWWWW


#9a[ESC[^@^@^@

       f3#$A3 jn^^CARRIER DROPPED

これを書いたのは fr33 v4r14bl3z なる結社(?)の人のようである。leet speakは古代から存在した!

御託はともかく、最後のゴミを取り除けばそのまま実行できそうである。UMIXではシェルのリダイレクトは使えなさそう(なので cat > foo.bas はできない)なので、ファイルの書き込みには /bin/umodem を使う。ゴミを取り除いたものを hack2.bas として保存して(すると INTRO.UMD=10@999999 がもらえる)、 /bin/qbasic hack2.bas を実行すると hack2.exe ができる(さらに INTRO.QBC=10@999999 がもらえる)。

これで、単純なブルートフォースのプログラムができた。ターゲット一覧を得るために ls /home して、適当に仕掛けてみる。

% ls /home↵
ftd/
knr/
guest/
gardener/
ohmega/
yang/
howie/
hmonk/
bbarker/
% ./hack2.exe ftd↵
attempting hack with LIII passwords 
no simple matches for user ftd

結論を書くと、このプログラム(hack2.bas)では ohmega と howie のパスワードを割り出すことができる。

  • ohmega: bidirectional
  • howie: xyzzy

それぞれのアカウントでログインするとそれぞれの課題が得られるが、ここでは残りのアカウントに対してもう少し真面目にハックを仕掛けよう。

hack.basの末尾の切れている部分のコメントには「<単語><十進2桁> の形のパスワードを試すと良いかも」というようなことが書かれている。これを実装しよう。

shinh氏が書いているように、このQVICKBASICでは文字列に数字をくっつけるとローマ数字に変換される。今欲しいのは十進の数字なので words(i) + j ではうまくいかない。

このQVICKBASICには割り算や剰余のような高級な命令はない。なので words(i) + CHR(48 + j / 10) + CHR(48 + j REM 10) というようなコードは書けない。書けたとしてもローマ数字の世界に0という数は存在しないのでうまくいかない。

なので、48≤j<58(ASCIIコードの0から9), 48≤k<58 についてループを書いて words(i) + CHR(j) + CHR(k) という風にしてやる必要がある。筆者の実装は hack3.bas に置いた。

この hack3.bas を使うと新たにftdのパスワードが取れる。残りのknr, gardener, yang, hmonk, bbarkerはこのプログラムでは取れない。

  • ftd: falderal90

ls /home した時に「パスワードが取れる」 ftd が一番上に出てくるのは出題者の作為的なものを感じる。

しかし、割り算もない癖に CHECKPASS 関数は持っているBASICとは何なのか。誰がどういう目的で設置したのか。パスワードをハックする用にしか見えない(メタ的には実際そうなんだけど)。

ftd

BASICで割り出したパスワードを使って ftd にログインしてみよう。

% ls↵
TODO
README
ml19100.exe*
icfp.exe*
% cat README↵

ml19100.exe: An implementation of the next version of ML


icfp.exe: Instant Checker For Publications

I'm so sick of the reviewers rejecting my perfectly good publications
for no reason at all.  I reverse-engineered and automated their review
process falderal: if you run this program on your publications, it will
tell you whether or not they'll be accepted.

And, with the time the TRB is taking to review tenure cases these days,
our new administrators won't get their credentials until who knows when.
So this program will grant administrative privileges if it decides that
your publication record has enough gravitas.

% ./ml19100.exe↵
Uncaught exception: Unimplemented
BASIC.MLC=100@999999|ホニャララ
% cat TODO↵
* Water plants.

* Feed cats.

* Make sure this advice nonsense does not get adopted---it's the most
  anti-modular programming language I've ever seen!  Write up a detailed
  critique using the implementation:
  login: hmonk
  password: COMEFROM

というわけで、BASIC.MLCの100点と、hmonkのパスワードがもらえる。icfp.exeは採点ツールで、実行して入手済みのpublication文字列を入力すると

Enter one publication per line; terminate with an empty line:
INTRO.LOG=200@999999|ホニャララ↵
INTRO.UMD=10@999999|ホニャララ↵
INTRO.QBC=10@999999|ホニャララ↵
INTRO.OUT=5@999999|ホニャララ↵
INTRO.WEB=15@999999|ホニャララ↵
INTRO.MUA=5@999999|ホニャララ↵
BASIC.MLC=100@999999|ホニャララ↵
↵
------------------------------------------------------------

Assessing your best accepted publications:

	Your CV's weight is 345.
	Your current rank is Lecture Administrator.
	To use your administrative privileges: 
		login:   	guest
		password:	

------------------------------------------------------------

The CBV Tenure Review Board's promotion guidelines:

To attain the rank of   		Your CV must weigh at least
*********************   		***************************
Lecture Administrator			0
Assistant Administrator			1006
Associate Administrator			2006
Full Administrator			3006

という感じに合計スコア(今は345点)を表示してくれる。1006点、2006点、3006点を突破すると昇進(?)して特権ユーザーのアカウントを貰えたりするのか……?

今回のまとめ・次回に向けて

今回は

  • ftd: falderal90
  • ohmega: bidirectional
  • howie: xyzzy
  • hmonk: COMEFROM

の4つのアカウントのパスワードを入手し、

  • INTRO.LOG…200点
  • INTRO.MUA…5点
  • INTRO.OUT…5点
  • INTRO.WEB…15点
  • INTRO.UMD…10点
  • INTRO.QBC…10点
  • BASIC.MLC…100点

の合計345点を獲得した。今回は触れなかったが、ftd以外のホームディレクトリー以下には

  • ohmega
    • 2d
  • howie
    • adventure
  • hmonk
    • advise

なる物体が保管されている。これは次回以降遊んでいくことになる。

さっき書いたように、筆者の当初のUM実装はめちゃくちゃ遅かった。例えばadventureの起動には死ぬほど時間がかかった。これの改善にはJITコンパイルしかないと思い込んでJITについて色々調べたり実験したりし始めたのだが、実は命令ディスパッチではなく配列の確保がボトルネックだったことが判明した。配列の確保を改善した後はadventureもすぐに起動するようになったのでぶっちゃけJITの必要性は薄くなったのだが、乗りかかった船なので次回はJITコンパイルに挑戦したい。

【追記】書いた:

Spread the love

ICFP Programming Contest 2006 “The Cult of Bound Variable” に挑戦してみる」への2件のフィードバック

  1. ピンバック: 2021年振り返りと来年に向けて | 雑記帳

  2. ピンバック: AArch64でJITしてみる | 雑記帳

コメントは停止中です。