バックパッチしようぜ

みんなバックパッチ(backpatch)って知ってる?
ほらコンパイラとかでジャンプとかを作るときに使うやつだよ。gotoでもいいけどさ。

	a;
	b;
	goto LABEL; // <- ここを生成しているときは、LABELのアドレスが分からない
	c;
	d;
LABEL:  // <- ここでLABELのアドレスが決定する
	e;

これを関数型言語でやろうと思ったら、結構大変だったんだ。どれくらい大変だったかというと、ゴールデンウィーク中ずっとこのことを考えてるぐらい大変だった。
1パスでやりたいとか、たいれたことは考えてなくて、拡張がしやすくて見た目がシンプルな実装がしたかっただけなんだけど、結構むつかしい。
結局、http://www.itpl.co.jp/ocaml-nagoya/index.php?%A5%CD%A5%BF%B5%AD%CF%BF%B8%CB%2FHaskellを参考にしてそれらしいものができたので、貼っておきますね。

type t = Int of int | Label of string | Ref of string

(* val conv : int -> t list -> ((string * int) list -> int list) * (string * int) list = <fun> *)
let rec conv i =
  function
      [] ->
	(fun _ -> []),[]
    | (Int x)::xs ->
	let ys, map =
	  conv (i+1) xs in
	  (fun m -> x::ys m), map
    | (Ref x)::xs ->
	let ys, map =
	  conv (i+1) xs in
	  (fun m -> ((List.assoc x m) - i)::ys m),map
    | (Label x)::xs ->
	let ys,map =
	  conv (i+1) xs in
	  ys,(x,i)::map

(*  val backpatch : t list -> int list = <fun> *)
let backpatch xs =
  let xs,map =
    conv 0 xs in
    xs map

# backpatch [Int 1;Ref "foo"; Int 2; Int 3;Label "foo";Int 4];;
- : int list = [1; 3; 2; 3; 4]