Created
November 18, 2022 12:42
-
-
Save Guest0x0/bb69e917e3f238fdec8ed3516bf42544 to your computer and use it in GitHub Desktop.
ANF transformation with joint point for branching, using higher order reference cell
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| module Src = struct | |
| type expr = | |
| | Int of int | |
| | Var of string | |
| | Op of string * expr * expr | |
| | Let of string * expr * expr | |
| | If of expr * expr * expr | |
| end | |
| module IR = struct | |
| type variable = int | |
| let var_seed = ref 0 | |
| let fresh_var () = incr var_seed; !var_seed | |
| type label = int | |
| let label_seed = ref 0 | |
| let fresh_label () = incr label_seed; !label_seed | |
| type value = | |
| | Int of int | |
| | Var of variable | |
| type expr = | |
| | Val of value | |
| | Op of string * value * value | |
| type program = | |
| | Ret of value | |
| | Jmp of label * value | |
| | Blk of (label * variable * program) * program | |
| | Let of variable * expr * program | |
| | If of value * program * program | |
| end | |
| module Env = Map.Make(String) | |
| type hole = IR.program -> IR.program | |
| let compose_hole h_outer h_inner = fun p -> h_outer (h_inner p) | |
| let rec anf env hole expr = | |
| match expr with | |
| | Src.Int i -> IR.Int i | |
| | Src.Var v -> Env.find v env | |
| | Src.Op(op, l, r) -> | |
| let var = IR.fresh_var () in | |
| let lv = anf env hole l in | |
| let rv = anf env hole r in | |
| hole := compose_hole !hole (fun p -> IR.Let(var, IR.Op(op, lv, rv), p)); | |
| IR.Var var | |
| | Src.Let(name, rhs, body) -> | |
| let rhsv = anf env hole rhs in | |
| let var = IR.fresh_var () in | |
| hole := compose_hole !hole (fun p -> IR.Let(var, IR.Val rhsv, p)); | |
| anf (Env.add name (IR.Var var) env) hole body | |
| | Src.If(cond, conseq, alter) -> | |
| let condv = anf env hole cond in | |
| let label = IR.fresh_label () in | |
| let param = IR.fresh_var () in | |
| let conseq_prog = | |
| let conseq_hole = ref Fun.id in | |
| let result = anf env conseq_hole conseq in | |
| !conseq_hole (IR.Jmp(label, result)) | |
| in | |
| let alter_prog = | |
| let alter_hole = ref Fun.id in | |
| let result = anf env alter_hole conseq in | |
| !alter_hole (IR.Jmp(label, result)) | |
| in | |
| (* previous hole: H[] | |
| * new hole: H[let label param = [] in if condv conseq_prog alter_prog] *) | |
| hole := compose_hole !hole | |
| (fun p -> IR.Blk( (label, param, p) | |
| , IR.If(condv, conseq_prog, alter_prog) )); | |
| IR.Var param | |
| let test expr = | |
| let hole = ref Fun.id in | |
| let value = anf Env.empty hole expr in | |
| !hole (IR.Ret value) | |
| let test1 = | |
| let open Src in | |
| Op("add", Int 1, Op("mul", Int 2, Int 3)) | |
| let test2 = | |
| let open Src in | |
| Let( "x", Op("add", Int 1, Int 2) | |
| , Let( "y", Op("mul", Int 3, Int 4) | |
| , Op("mul", Var "x", Op("add", Var "y", Var "y") ))) | |
| let test3 = | |
| let open Src in | |
| Op("add", Int 1 | |
| , If( Int 0 | |
| , Op("mul", Int 2, Int 3) | |
| , Op("mul", Int 4, Int 5) )) | |
| let test4 = | |
| let open Src in | |
| If( Int 0 | |
| , Op("mul", Int 2, Int 3) | |
| , Op("mul", Int 4, Int 5) ) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment