F#でインタープリタ : クロージャの実装

• https://gist.github.com/4578600/687544edff499c54d4e5ea6fd2208244cdce1c1f

やっとクロージャが実装できました。

    def counter (c) {
      fun () { c = c + 1 }
    }
    c1 = counter(0)
    c2 = counter(0)
    c1()
    c1()
    c2()
    c1()

上のコードを実行すると3が返ってきます。

関数呼び出しを評価するコードを抜粋。ごちゃごちゃしているけど現時点では満足です。クロージャを表現するのに、スコープチェーンのようなデータ構造を入れないと無理かなーと思いつつ、永続データ型のMapでなんとかなったのがうれしい。

    | PrimaryExpr(expr, arguments) ->
      match arguments with
      | Some(arguments) -> (* 引数があったら関数呼び出し *)
        eval env expr (fun exprEnv expr ->
        eval exprEnv arguments (fun argsEnv arguments ->
          match expr, arguments with
          | Var(id, Fun(parameters, block, funEnv)), Args(args) -> (* パラメータ、ブロック、静的スコープを取り出す *)
            eval argsEnv parameters (fun paramsEnv -> function
              | Params(``params``) ->
                let rec loop paramsEnv list = 
                  match list with
                  | [] -> (* 関数ブロックの処理*)
                    (* 関数ブロックのための環境を作成 *)
                    let blockEnv = (Map.toList funEnv) @ (Map.toList paramsEnv) |> Map.ofList
                    (* 関数ブロックを評価*)
                    eval blockEnv block (fun resultEnv result -> 
                      (* 自由変数だけを含んだ環境を作成 *)
                      let freeEnv = resultEnv |> Map.filter (fun key _ -> funEnv |> Map.containsKey key)
                      (* クロージャとして使えるように関数が保持する環境を更新 *)
                      let f = Fun(parameters, block, (Map.toList funEnv) @ (Map.toList freeEnv) |> Map.ofList)
                      (* 関数の束縛だけを変更した新しい環境を作成 *)
                      let newEnv = Map.add id f exprEnv
                      (* 関数の呼び出し終了。関数の束縛だけを変更した環境で後続処理。 *)
                      cont newEnv result)
                  | (param, arg) :: xs -> (* パラメータに引数を割り当て *)
                    assign paramsEnv param arg (fun paramsEnv _ -> loop paramsEnv xs)
                (* パラメータと引数の組のリストを再帰で処理 *)
                loop paramsEnv (List.zip ``params`` args)
              | _ -> failwith (sprintf "parameters %A is not found" parameters))
          | _ -> failwith (sprintf "function %A is not found" expr)))
      | _ -> (* 引数がなかったら式の評価 *)
        eval env expr cont

今回は素のMapでがんばりましたが、環境に相当する型を作ればもっとすっきり書けるはず。