Arantium Maestum

プログラミング、囲碁、読書の話題

OCamlのlambda IRをいじる(リスト)

リストとパターンマッチ、Listモジュール使用のコンパイルを見ていく。

簡単なパターンマッチ

簡単なリストを作り、リストのコンストラクタ2つに対しての素直なパターンマッチをする:

let () =
  let xs = [1;2] in
  match xs with
  | [] -> print_endline "hello"
  | n::_ -> print_int n

-dlambdaコンパイル

(seq
  (let
    (*match*/85 =
       (let (xs/80 = [0: 1 [0: 2 0a]])
         (if xs/80 (apply (field 43 (global Stdlib!)) (field 0 xs/80))
           (apply (field 45 (global Stdlib!)) "hello"))))
    0a)
  0a)

OCaml[1; 2]がlambda IRでは[0: 1 [0: 2 0a]]になっている。[]つまりnil0aで表現され(ちなみにユニット型()やブール型のfalseも同じ表現にコンパイルされていた)、cons a b[0: a b]つまり2要素のタプルと同じ形で表現されている。

パターンマッチに関しては、ただのifに変換されている。空リストとfalseがどちらも0aで表現されることを利用してなのか、リスト自体をifの条件にして、もしリストが真(つまり空リストじゃないなら)なら(field 0 xs/80)`とフィールドアクセスしている。

-drawlambdaコンパイルすると:

(seq
  (let
    (*match*/85 =
       (let (xs/80 = [0: 1 [0: 2 0a]])
         (if xs/80
           (let (*match*/82 =a (field 1 xs/80) n/81 =a (field 0 xs/80))
             (apply (field 43 (global Stdlib!)) n/81))
           (apply (field 45 (global Stdlib!)) "hello"))))
    0a)
  0a)

パターンマッチはやはりifに変換されているが、その後| n::_ -> ...の部分に対応する変数束縛が残っている。let () = ...と同じく、_への束縛は(let (*match*/xx =...) ...)という形に変換されるようだ。そしてタプルの記事の追記で@camloeba さんに教えていただいたと書いたとおり、-drawlambdaコンパイルしたlambda IRに出てくるlet (... =a ...)がaliasとして-dlambdaコンパイルされた形ではインライン化されている。

複雑なケースのあるパターンマッチ

パターンマッチのケースわけをもう少し複雑にしてみる。[x] -> ...と、リストに一つだけ要素が含まれている特殊ケースのパターンを追加:

let () =
  let xs = [1;2] in
  match xs with
  | [] -> print_endline "hello"
  | [n] -> print_int n
  | n::_ -> print_int (n + 1)

-dlambdaコンパイル

(seq
  (let
    (*match*/88 =
       (let (xs/80 = [0: 1 [0: 2 0a]])
         (if xs/80
           (let (n/81 =a (field 0 xs/80))
             (if (field 1 xs/80)
               (apply (field 43 (global Stdlib!)) (+ n/81 1))
               (apply (field 43 (global Stdlib!)) n/81)))
           (apply (field 45 (global Stdlib!)) "hello"))))
    0a)
  0a)

ネストしたifになっている。

-drawlambdaコンパイル

(seq
  (let
    (*match*/88 =
       (let (xs/80 = [0: 1 [0: 2 0a]])
         (if xs/80
           (let (n/81 =a (field 0 xs/80))
             (catch
               (let (*match*/83 =a (field 1 xs/80))
                 (if *match*/83 (exit 1)
                   (apply (field 43 (global Stdlib!)) n/81)))
              with (1)
               (let (n/82 =a n/81 *match*/84 =a (field 1 xs/80))
                 (apply (field 43 (global Stdlib!)) (+ n/82 1)))))
           (apply (field 45 (global Stdlib!)) "hello"))))
    0a)
  0a)

分岐に例外を使っている!

[n] -> ...n::_ -> ...の処理の分岐で、リストのcdr部分が0aでなければ(exit 1)で例外を投げて、(catch ... with (1) ...)の後者の処理に回るようになっている。

この例だと正直なぜこんなややこしいことをするのかわからない。(exit 1)のところにwith (1) ...の部分にある処理を書けばいいのでは?と思うが、より複雑なパターンマッチなどではこの方が書きやすいのかもしれない。さらにこういった例外処理を-drawlambdaから-dlambdaの間のステップでただのネストしたifコンパイルしているのも面白い&ぱっと見大変そう・・・

Listモジュール内の関数を使ってみる

最後にOCamlの標準ライブラリに含まれているListモジュールを使ったコードを見てみる:

let () =
  let xs = [1;2] in
  print_int @@ List.fold_left (+) 0 xs

-dlambdaコンパイル

(seq
  (let
    (*match*/145 =
       (let (xs/80 = [0: 1 [0: 2 0a]])
         (apply (field 43 (global Stdlib!))
           (apply (field 22 (global Stdlib__list!))
             (function prim/143 prim/142 stub (+ prim/143 prim/142)) 0 xs/80))))
    0a)
  0a)

List.fold_left(field 22 (global Stdlib__list!))に変換されているのは比較的わかりやすい。

(+)(function prim/143 prim/142 stub (+ prim/143 prim/142))になっているのが面白いところで、(+)は標準ライブラリにあるわけではなくその場で関数が作成されるらしい。

この中に出てくるstubというのがどういう意味を持つのかいまいちわからない・・・

次回

次はレコードの定義と利用を見てみる。