OCamlのlambda IRをいじる（代数的データ型）

代数型データ型とそれに対するパターンマッチのlambda IRへのコンパイルを見ていく

タグのみ直和型

まずは簡単なタグのみ直和型を見てみる：

type t = A | B | C

let () =
  let x = C in
  match x with
  | A -> print_int 1
  | B -> print_int 2
  | C -> print_int 3

type t = A | B | Cと直和型でタグ以外の型を何も持たせていない。列挙型といってもいいかも（言語によっては列挙型の意味も違うようだが・・・）

-dlambdaでコンパイル：

(seq
  (let
    (*match*/89 =
       (let (x/84 = 2a)
         (switch* x/84
          case int 0: (apply (field 43 (global Stdlib!)) 1)
          case int 1: (apply (field 43 (global Stdlib!)) 2)
          case int 2: (apply (field 43 (global Stdlib!)) 3))))
    0a)
  0a)

レコードの時と同じく、type t = ...の部分は完全にlambda IRでは消えている。

let x = C in ...が(let (x/84 = 2a) ...)になっているので、タグのみ直和型の場合は0a, 1a, 2aのような値にコンパイルされるようだ。

パターンマッチは(switch* ... case int 0: ... case int 1: ... case int 2: ...)のような形になっている。

直和型＆直積型

タグだけではなく、値も持った代数的データ型を定義・使ってみる：

type t =
 | A
 | B of int
 | C of string * bool

let () =
  let x = A in
  let y = B 2 in
  let z = C("hi",true) in
  let f = function
  | A -> print_int 1
  | B n -> print_int n
  | C(s,b) -> print_endline @@ if b then s else "hello"
  in
  f x; f y; f z;

-dlambdaでコンパイル：

(seq
  (let
    (*match*/95 =
       (let
         (x/84 = 0a
          y/85 = [0: 2]
          z/86 = [1: "hi" 1a]
          f/87 =
            (function param/92
              (switch* param/92
               case int 0: (apply (field 43 (global Stdlib!)) 1)
               case tag 0:
                (apply (field 43 (global Stdlib!)) (field 0 param/92))
               case tag 1:
                (apply (field 45 (global Stdlib!))
                  (if (field 1 param/92) (field 0 param/92) "hello")))))
         (seq (apply f/87 x/84) (apply f/87 y/85) (apply f/87 z/86))))
    0a)
  0a)

タグのみのケースは先ほどと同じように0aに、そして値を持つタグは[0: ...]のような（タプルやリスト、レコードと同じ）ブロックにコンパイルされている。

値を持つタグが複数ある場合 [0: ...]、[1: ...]、[2: ...]とブロックの最初の部分であるn:で差別化している。（タプルのコンパイル結果を見たときからの「[0: ...]の0:部分はなんだ？」という疑問がここにきてようやく解ける）

パターンマッチは

• タグのみのケースはcase int 0:
• 値つきのケースはcase tag 0:

のようにコンパイルされており、case tag n:が[n: ...]のブロックと対応するようになっている。

直積型とタグ付きタプル

直積型とタグ付きタプルは、定義の仕方も使い勝手も非常に似ている：

type t =
  A of int * string
  | B of (int * string)

let () =
  let x = A(1,"hi") in
  let y = B(2,"ho") in
  let f = function
    | A(n,s) -> print_int n; print_endline s
    | B(n,s) -> print_int n; print_endline s
  in
  f x; f y

A of int * stringとB of (int * string)という違いだけで、あとはコンストラクタとしての使い方もパターンマッチもまったく同じ記法になっている。

-dlambdaでコンパイルしてみると：

(seq
  (let
    (*match*/95 =
       (let
         (x/83 = [0: 1 "hi"]
          y/84 = [1: [0: 2 "ho"]]
          f/85 =
            (function param/91
              (switch* param/91
               case tag 0:
                (seq (apply (field 43 (global Stdlib!)) (field 0 param/91))
                  (apply (field 45 (global Stdlib!)) (field 1 param/91)))
               case tag 1:
                (let (*match*/93 =a (field 0 param/91))
                  (seq
                    (apply (field 43 (global Stdlib!)) (field 0 *match*/93))
                    (apply (field 45 (global Stdlib!)) (field 1 *match*/93)))))))
         (seq (apply f/85 x/83) (apply f/85 y/84))))
    0a)
  0a)

実装は違っていることがはっきりわかる。

A of int * stringは二つのフィールドのあるブロック、B of (int * string)はそれ自体がブロックである一つのフィールドを持つブロックになっており、パターンマッチに関してもデータの実装の違いが反映されている。

次回

次はミュータブルなrefがどのようにコンパイルされるのか見ていく。