JavaScriptによる型推論器の実装： let と let rec
再帰関数の型推論
以下は、階乗を求める関数 fac の定義です。
let rec fac = fun n -> if n = 0 then 1 else n * fac (n - 1)
このように、Ibis で再帰関数を定義する際は let ではなく let rec を使います。これは OCaml に倣ったものです。この二つの違いは何か、型推論の観点から説明します。
再帰関数と型変数
上の fac の場合、関数本体の型推論をする際、そこに fac 自身が現れます。そのため、あらかじめ fac の型を仮に決めておかなくてはなりません。そこで型変数が登場します。let と let rec の型推論のコードを見比べてみましょう。
47: case "Let": 48: var inferredType = infer(ctxt, env, variants, expr.valueExpr); 49: var typeSchema = createPolyType(inferredType); 50: Env.add(ctxt, expr.varName, typeSchema); 51: return createAlphaEquivalent(typeSchema).bodyType; 52: case "LetRec": 53: var varType = Type.createVar(null); 54: var newCtxt = Env.createLocal({}, ctxt); 55: Env.add(newCtxt, expr.varName, Type.createTypeSchema([], varType)); 56: var inferredType = infer(newCtxt, env, variants, expr.valueExpr); 57: unify(varType, inferredType); 58: var typeSchema = createPolyType(inferredType); 59: Env.add(ctxt, expr.varName, typeSchema); 60: return createAlphaEquivalent(typeSchema).bodyType;src/inferer.js
let rec のほうには varType という変数があり、そこに型変数が代入されています。これが仮決定した fac の型です。fac の型を varType とした新しい環境 newCtxt で、関数本体の式を推論します。仮決定した型 varType と推論結果 inferredType は一致していなくてはなりませんから、この二つを単一化します。後は、let の場合と同様です。
このように、Ibis において let と let rec では推論の手順がわずかに異なります。もし let rec がなければ再帰関数は定義できません。
