リージョン推論

SMLで書いてあったリージョン推論をOCamlに移植した物です。

original SML code: https://gist.github.com/pasberth/311b81324bba06b023b27a08386d4ee4

構文

x ::=                     識別子
      ('a'|...|'z'|'A'|...|'Z') ('a'|...|'z'|'A'|...|'Z'|'0'|...|'9'|'_')*
e ::=                     式
    | x                     変数
    | e e                   関数適用
    | ^ x : t . e           λ抽象
    | let x : t := e in e   let式
    | ( e )                 括弧式
t ::=                     型
    | int                   整数
    | t -> t                関数
    | ( t )                 括弧式

r ::= x
    | ^ x . r at t
    | r r
    | letregion x* r

例1

let one : (int -> int) -> int -> int
        := ^x : int -> int. ^y : int. x y in
let two : (int -> int) -> int -> int
        := ^x : int -> int. ^y : int. x (x y) in
one

(letregion r21 (
  (^one.(
    letregion r20 r19 r17 r14 (
      (^two.one at r14)
      (^x.(^y.(x (x y)) at r19) at r20))) at r21)
  (^x.(^y.(x y) at r26) at r27)
))

let one : int -> int :=
  ^x : int. x
in
one

(letregion r3 (
  (^one.one at r3)
  (^x.x at r5)
))

Reference

A Region Inference Algorithm - Martin Elsman http://www.elsman.com/mlkit/pdf/toplas98.pdf

hsk/region_infer

リージョン推論

Reference