OCamlのlambda IRをいじる（再帰関数）

再帰関数のことを忘れていた！

というわけで幕間的な記事。

Factorial

再帰で階乗なコード：

let () =
  let rec f x = if x = 0 then 1 else x * (f (x-1)) in
  print_int @@ f 5

-dlambdaでコンパイル：

(seq
  (let
    (*match*/83 =
       (letrec
         (f/80
            (function x/81[int] : int
              (if (== x/81 0) 1 (* x/81 (apply f/80 (- x/81 1))))))
         (apply (field 43 (global Stdlib!)) (apply f/80 5))))
    0a)
  0a)

再帰関数だとインライン化はできない（当然といえば当然）。それ以外では(let (... = ...) ...)という構文が(letrec (... ...) ...)になったくらいの違いだ。（なぜletで=を使っていてletrecでは使っていないのかは少し謎だが・・・ =[int]のようにboxing関連の型情報を伝える必要がないからか？）

(function ... )の部分は本当にまったく非再帰的な関数と同じで、この部分だけ見ると再帰しているかどうかはわからない。

相互再帰的なodd/even

相互再帰も見ていく。

let () =
  let rec odd x = if x = 0 then false else even (x-1)
  and even x = if x = 0 then true else odd (x-1)
  in
  print_int @@ if odd 5 then 1 else 2

-dlambdaでコンパイル：

(seq
  (let
    (*match*/85 =
       (letrec
         (odd/80
            (function x/82[int]
              (if (== x/82 0) 0a (apply even/81 (- x/82 1))))
           even/81
             (function x/83[int]
               (if (== x/83 0) 1a (apply odd/80 (- x/83 1)))))
         (apply (field 43 (global Stdlib!)) (if (apply odd/80 5) 1 2))))
    0a)
  0a)

およそ期待どおりといったところか。(letrec (.. ..) ..)の中のカッコに相互再帰な関数を入れていくだけ。

モジュールレベルでodd/even

相互再帰関数をローカルではなくモジュールのトップレベルで定義してみる：

let rec odd x = if x = 0 then false else even (x-1)
and even x = if x = 0 then true else odd (x-1)

let () = print_int @@ if odd 5 then 1 else 2

-dlambdaでコンパイル：

(seq
  (letrec
    (odd/80
       (function x/82[int] (if (== x/82 0) 0a (apply even/81 (- x/82 1))))
      even/81
        (function x/83[int] (if (== x/83 0) 1a (apply odd/80 (- x/83 1)))))
    (seq (setfield_ptr(root-init) 0 (global Rec1!) odd/80)
      (setfield_ptr(root-init) 1 (global Rec1!) even/81)))
  (let
    (*match*/87 =
       (apply (field 43 (global Stdlib!))
         (if (apply (field 0 (global Rec1!)) 5) 1 2)))
    0a)
  0a)

(letrec (X ... Y ...) (seq (setfield_ptr ... X) (setfield_ptr ... Y)))という形にコンパイルされる。つまり相互再帰的な部分がすべて定義された後で、それらを一つずつモジュールに保存していく流れになっている。

次回

これでようやくデータ型に移れる。まずはタプルから。