ICFP Contest 2013

例年のようにicfpのコンテストに @khibino @plaster @dekosuke @Lost_dog_ @m2ym Kee -san達と参加。

ルール等の詳細はhttp://icfpc2013.cloudapp.net/

去年まではSchemeとC++を使っていた人々がふたりともHaskell派になったおかげで、一人でScala書いてた。

dekosukeさんが乱択アルゴリズムに進むようだったので、こちらは小さい問題を全列挙で解いた。

1日目

とりあえずさくっと \BV の eval を実装。

case class Literal(val value: Long) extends Expression {
  val ops = 0
}
object Zero extends Literal(0)
object One extends Literal(1)
case class Id(id: String) extends Expression {
  val ops = 0
}
case class If0(e: Expression, t: Expression, f: Expression) extends Expression {
  val ops = BV.OPS.OP_If0 | e.ops | t.ops | f.ops
}
case class Fold(e: Expression, acc: Expression, l: FoldLambda) extends Expression {
  val ops = BV.OPS.OP_Fold | e.ops | acc.ops | l.exp.ops
}
case class FoldLambda(e: Id, acc: Id, exp: Expression)

object BV {
  def eval(prog: Program, x: Long): Long = {
    eval(prog.e, Env(Map(prog.arg.id -> x), None))
  }

  def eval(exp: Expression, env: IEnv): Long = exp match {
    case v: Literal => v.value
    case Id(id) => env(id)
    case Op1Exp(t, e) =>
      {
        import Op1._
        t match {
          case Not => ~eval(e, env)
          case ShiftL1 => eval(e, env) << 1
          case ShiftR1 => eval(e, env) >>> 1
          case ShiftR4 => eval(e, env) >>> 4
          case ShiftR16 => eval(e, env) >>> 16
        }
      }
...
  }

トレーニングでチェックした範囲では問題なさそう。

次はサイズとoperatorsから合法な全ての構文木を生成。

  def genExpression(size: Int, availables: Int, rests: Int, par: Boolean = false): GenSeq[Expression] = {
    var results: List[Expression] = Nil
    if (canched) throw new InterruptedException
    if (size == 1) {
      return toPar(
        (if (contains(availables, OP_Fold) || contains(availables, OP_TFold))
          List(Zero, One, Id("x"), Id("y"), Id("z"))
        else
          List(Zero, One, Id("x"))), par)
    }
    if (size >= 2) {
      for (
        op <- toPar(flagToList(availables & MASK_OP1), par);
        e <- genExpression(size - 1, availables, unset(rests, op.asInstanceOf[OpOp1].op.id))
      ) {
        val exp = Op1Exp(op.asInstanceOf[OpOp1].op, e)
        if (contains(exp.ops, rests)) {
          results = exp :: results
        }
      }
    }
  ...

全てオンメモリで処理するのでサイズ12程度でOOMEくらう。

サイズ9の問題で全部で1万個ほどプログラムが生成されて、evalからもらった256入出力を満たすかのチェックだけだと200個あって解けなそうと判断。

ライトニングディビジョンに参加するか迷うも全員力尽きて翌日に持ち越し。

2日目

生成したプログラムをそれぞれ簡約化して等価なものを取り除くようにする。

  def simplify(e: Op2Exp): Expression = e match {
    //const
    case Op2Exp(op, Literal(_), Literal(_)) =>
      new Literal(BV.eval(e, Env(Map(), None)))
    // x | 0
    case Op2Exp(Or, Literal(0), other) =>
      other
    case Op2Exp(Or, other, Literal(0)) =>
      other
    // x | ~0
    case Op2Exp(Or, l @ Literal(0xffffffffffffffffL), _) =>
      simplify(l)
    case Op2Exp(Or, _, l @ Literal(0xffffffffffffffffL)) =>
      simplify(l)
    ...
  }

  def simplify(e: If0): Expression = e match {
    //const
    case If0(l: Literal, t, f) =>
      val v = BV.eval(l, Env(Map(), None))
      if (v == 0L)
        t
      else
        f
    case If0(c, t, f) if t == f =>
      t

    ...
  }

のような感じで。これでサイズ10くらいまでは256入出力のペアがあれば、5択〜20択くらいまで候補を絞り込めるようになったのでポチポチと手動でサブミット。
ほぼ、1発で成功していて、簡約化できていないことが判明するも
(and 1 x) == (and 1 (shr1 (shl1 x))) のように値域・定義域の判定まで必要なケースで解くには問題ないのであきらめる。

3日目

サイズ11のトレーニングデータで試すと流石に可能なケース全てを一旦生成して処理するのは不可能だったので、生成しつつ評価していくことに。

  def genExpression(size: Int, availables: Int, rests: Int, par: Boolean = false)(cb: Expression => Unit): Unit = {
    if (size == 1) {
      val es =
        if (contains(availables, OP_Fold) || contains(availables, OP_TFold)) {
          cb(Zero)
          cb(One)
          cb(Id("x"))
          cb(Id("y"))
          cb(Id("z"))
        } else {
          cb(Zero)
          cb(One)
          cb(Id("x"))
        }
      return
    }
    if (size >= 2) {
      for (
        op <- flagToList(availables & MASK_OP1)
      ) {
        genExpression(size - 1, availables, unset(rests, op.asInstanceOf[OpOp1].op.id)) { e =>
          {
            val exp = Op1Exp(op.asInstanceOf[OpOp1].op, e)
              cb(exp)
          }
        }

      }
    }
...

これで、size<=11の問題とsize<=14のtfoldまでは解けるように。

サイズ20前後の通常問題は乱択アルゴリズム班が頑張ってるようだったので、\BVの最適化をしつつボーナス問題の検討を開始するも(if0 a b c)で仮にbを正解に固定しても時間ないに解けない。

しかしその際のBV.eval()とプログラム生成の最適化でsize<=13の問題とsize<=16のtfoldは時間内に解けるようになってた。

4日目

結局残ったままになっていたボーナス問題をダメ元で全探索の順序をランダムに変えつつ試してみるも解けず会社へ。


初日は全員集合してノートで開発していたけれどメモリ4Gの32bit WindowsだとScala IDE走らせつつ、探索問題とくのは厳しく、二日目以降はリモート参加してた。

延々Scalaを書いてたけれど、やはり並列コレクションのparはとりあえずマルチコアを使うのには楽だけどCPUを使い切り続けるのにはつらい。
caseクラスやパターンマッチやラムダ式は便利だけどプロファイリングしたときに意外な所でコストかかってたりする。もちろんそれらがあるお陰で構造的な改良はやりやすいのでトレードオフ関係はあるんだけど。

後知恵だけどある程度のサイズの式の集合は予め生成しておいて、入出力から逆算するようなDP的なやり方でもう1サイズ分ぐらいは稼げたかもしれない。

Cygwin/X + IME

内部コードをkinput2仕様のオレオレwcharからUCSに変更したので、ハングルや中国語も入力できているようにみえる。

http://zakki.github.io/xserver/

頂いたコードに言うのもなんだけど、いい加減K&RのやX11R5以前の事情を引き継いでるkinput2ベースじゃなくてuim-xim実装とかその辺に実装移すべきなんじゃなかろうか。
mozcのおかげで別にWindowsのIME使わなくてもそれなりに幸せなんで実際にやるかどうかは未定です。

TypeScript 勉強会

トップゲートさんで開催されたTypeScript勉強会でしゃべってきた。
予め喋る内容決めとかないと準備不足でグダグダだ。

TypeScriptの処理系概要 http://prezi.com/56-dvutxh0un/typescript/

  • 喋りつつ思ったけど、AST の構築や TypeCheck は処理の流れをトップダウンで追うより、末端の最小要素からボトムアップで説明する方が分かりやすそう。
  • Language Services もなんかミニマムなサンプル入れとけばよかった。
  • ひたすら文字ばっかりなのも適宜構造を図示出来ればよかったけどめんどい。

他の方の資料

Emacs + typescript-tools + auto-complete + flymake

引き続き TypeScript の環境整備。

普通に flymake を使うと毎回 node tsc.js が走ってしまうのと取れるエラーの数に制限がかかっているのを解消するために typescript-tools からエラーをとれるようにして flymake に流しこむ。

普通に flymake の初期化を定義するとプロセス起動しかできないので、初期化関数では nil を返しておいて処理をスキップしてタイマーで実際のエラー取得をするようにした。(flymake側でプロセス呼んで標準入力読む以外の方法対応しないかなぁ)

  (defun flymake-typescript-init ()
    (run-at-time 0.1 nil 'flymake-typescript-check-error)
    nil)
  
  (add-to-list 'flymake-allowed-file-name-masks
               '("\\.ts\\'" flymake-typescript-init))

(defun flymake-typescript-check-error ()
  "Show syntax errors."
  (interactive)
  (setq flymake-last-change-time nil)
  (setq flymake-check-start-time (flymake-float-time))
  ...
  (setq flymake-new-err-info
		(flymake-parse-err-lines
		 flymake-new-err-info lines))
  (flymake-post-syntax-check 0 "tss")
  (setq flymake-is-running nil))

typescript-tools でスクリプトの編集結果を読み込めるようにしたり、コンパイルエラーをとれるようにしたりしていたら、同時期にどちらも公式側で対応されてた……。LanguageService の API を出しているだけで大差なかったのは幸いか。 clausreinke さん働き過ぎ。

https://github.com/zakki/auto-complete-ts/tree/typescript-tools

Emacs で TypeScript を auto-complete 使ってコード補完

Services.TypeScriptServicesFactory() 経由で補完情報を取れたのでそれを auto-complete につなげた。
公式の TypeScript.el だと (typescript-mode-hook) のフックが無いのでそっちも更新。

今のところ同一ファイルか lib.d.ts で定義されたメンバーだけ使ってる。
https://github.com/zakki/auto-complete-ts


補完のたびに node を起動して JSON で情報を取得しているけど、本来は処理系に差分更新モードがあるっぽいので Vim でやってるところのようにサーバーモードで動作するほうがいいのかも。
http://vividcode.hatenablog.com/entry/ts/how-to-completion

$ node.exe isense.js --line 4 --col 23 --libdir $(cygpath -m ~/ts/typescript/typings) test/getCompletionsAtPosition1.ts|sed 's/},/\n/g'|head
{"pos":83,"signature":null,"member":{"maybeInaccurate":false,"isMemberCompletion
":true,"entries":[{"name":"pubMeth","type":"() => void","kind":"method","kindMod
ifiers":"public"
{"name":"pubProp","type":"any","kind":"property","kindModifiers":"public"
{"name":"privMeth","type":"() => void","kind":"method","kindModifiers":"private"

{"name":"privProp","type":"string","kind":"property","kindModifiers":"private"}]

"nomember":{"maybeInaccurate":false,"isMemberCompletion":false,"entries":[{"name
":"toString","type":"() => string","kind":"method","kindModifiers":"declare"
{"name":"PropertyDescriptor","type":"PropertyDescriptor","kind":"interface","kin


js_of_ocaml

ハマったところ幾つかメモ。Js.Unsafeは名前の通りUnsafeだった。

Js.Unsafe.variable

Js.Unsafe.variableはごく普通にjs_of_ocamlが生成する関数内のスコープでが展開される。
何が起こるかというと、js_of_ocamlが生成する変数と名前の衝突が起こり、本当に見たかった変数が隠されてしまう。

let index_of array value from_index =
  Unsafe.meth_call
    (Unsafe.variable "$") "inArray"
    [|Unsafe.inject value;
      Unsafe.inject array;
      Unsafe.inject from_index|];;

で、$が隠されて意図した動作をしなかった。
厄介なことに -pretty の有無で変数名が変わるのでしばらく発覚していなかった。

let index_of array value from_index =
  Unsafe.meth_call
    (Unsafe.variable "jQuery") "inArray"

に変更して対処。
別名がない3文字程度までの外部の変数を参照する必要がある場合は、一端長い名前の別名をJavaScript側で定義するのが安全だと思う。

Js.Unsafe.fun_call

JavaScriptの関数呼び出しで

function js_foo(a) {
  return doA(a);
}

let foo: a -> b =
  Unsafe.variable "js_foo"

ignore (foo bar);;

としていた。

これがライブラリのバージョンアップで

function js_foo(a, b) {
  if (typeof a === "undefined") {
    return doA(a);
  } else {
    return doAB(a, b);
  }
}

となっていた。これはJavaScriptでは合法。
だけどOCaml側では foo a; が js_foo への部分適用の状態になるので、b -> cが帰る。
さらに戻り値がメソッドチェーン用で使わないのでignoreしてたのも事態をややこしくしてた。

ここは面倒くさがらずに Unsafe.fun_call を使うようにする。

let foo a =
  Unsafe.fun_call (Unsafe.variable "foo") [| Unsafe.inject a |];;

js_of_ocaml tips

make

js_of_ocamlではグローバルな名前空間に関数が置かれてしまう。
また、外部の型付けの弱いライブラリを呼び出すときには、OCamlの型をつけることも難しく、Js.Unsafe.eval_stringも若干冗長。

そこでOCamlで記述する範囲とは別にJavaScriptを書いて

intro.js
var foo;
if (!foo) foo = {};

(function(){
outro.js
})();
xx_.js
function hoge() {
}
xx.ml
open Js

let hoge x = ...


そうしておいて最終的にmakeでまとめる。

Makefile
%.js: %.byte
	$(COMP) -noruntime $(JSFILES) $< $(OPTIONS) -o tmp.js
	cat intro.js $*_.js tmp.js outro.js > $@

デバッグ

ブラウザ依存部分を切り離しトップレベルやユニットテストでデバッグすることもできるけれど、どうしても最終的にはブラウザ上でJavaScriptのデバッグが必要になることもある。そこで出力JavaScriptにデバッグ情報を埋めるパッチを作った。
https://gist.github.com/3634430