tiger book読書記録 chapter 5

Oct 9, 2018
chapter 5本文を読む.symbol table, binding, type checkが書いてある.chap 4でASTを作った後のstepである.本文はこうすれば意味解析が実装できると書いてある.プログラム演習はそれに沿って実装することになる.chap4の結果からfileをcopyして準備した.明日から意味解析を実装する.smlに慣れていないと実装が大変そうなsymbol table, binding tableは提供されているので素直に残りを埋めるだけか.

Oct 10, 2018
translate.sml. これは本文中に載っているものそのまま.後の章で実装する為のものでからの実装.

signature TRANSLATE =
sig
    type exp;
end

structure Translate : TRANSLATE =
struct
    type exp = unit;
end

env.sml.本文にsignatureが載っているのでstructureを実装する.type accessを何に使うか不明.取り敢えずtype access = intとしておいた.必要になったら変更しよう.

signature ENV =
sig
    type access;
    type ty;

    datatype enventry = VarEntry of {ty: ty}
                      | FunEntry of {formals: ty list, result: ty};

    val base_tenv : ty Symbol.table;
    val base_venv : enventry Symbol.table;
end;

structure Env :> ENV =
struct

    structure A = Absyn;
    structure T = Types;

    type access = int; (* ??? *)
    type ty = T.ty;

    datatype enventry = VarEntry of {ty: ty}
                      | FunEntry of {formals: ty list, result: ty};

    type venv = enventry Symbol.table;
    type tenv = ty Symbol.table;
    type expty = {exp: Translate.exp, ty: T.ty};

    val predefined_types = [("int", T.INT),
                            ("nil", T.NIL),
                            ("string", T.STRING),
                            ("unit", T.UNIT)];
    val predefined_funs = [
        ("print", [T.INT], T.UNIT),
        ("flush", nil : ty list, T.UNIT),
        ("getchar", nil : ty list, T.STRING),
        ("ord", [T.STRING], T.INT),
        ("chr", [T.INT], T.STRING),
        ("size", [T.STRING], T.INT),
        ("substring", [T.INT, T.INT, T.STRING], T.STRING),
        ("concat", [T.STRING, T.STRING], T.STRING),
        ("not", [T.INT], T.INT),
        ("exit", [T.INT], T.UNIT)];

    fun enter_type ((name, type_ty), table) =
        Symbol.enter (table, Symbol.symbol name, type_ty);
    fun enter_fun ((name, formals, result), table) =
        Symbol.enter (table, Symbol.symbol name,
                      FunEntry {formals=formals, result=result});

    val base_tenv : ty Symbol.table =
        foldl enter_type Symbol.empty predefined_types;
    val base_venv : enventry Symbol.table =
        foldl enter_fun Symbol.empty predefined_funs;
end;

明日からはSemant moduleの実装に入る.

Oct 15, 2018
semant.smlの実装を開始する.本文中のadviseに従って素直に実装することにする.まずはabsyn.smlに従ってpattern matchを用意する.中身の実装はこれから.特に難しいことはないよな.素直に埋めていけばいい筈.

structure A = Absyn;

signature SEMANT =
sig
    type venv;
    type tenv;
    type expty;

    val transProg: A.exp -> unit;

    val transVar: venv * tenv * A.var -> expty;
    val transExp: venv * tenv * A.exp -> expty;
    val transDec: venv * tenv * A.dec -> {venv: venv, tenv: tenv};
    val transTy: tenv * A.ty -> Types.ty;
end;

structure Semant : SEMANT =
struct
    structure T = Types;

    type venv = Env.enventry Symbol.table;
    type tenv = Env.ty Symbol.table;
    type expty = {exp: Translate.exp, ty: T.ty};

    exception Semant;

    fun transProg (exp: A.exp): unit =
        let
            val _ = transExp exp;
        in
            ()
        end

    fun checkInt ({exp, ty}, pos) = ();

    (* fun transExp (venv: venv, tenv: tenv, exp: A.exp): expty = *)
    fun transExp (venv, tenv, A.VarExp (var)) =
        transVar (venv, tenv, var)
      | transExp (venv, tenv, NilExp) = {exp=(), ty=T.NIL}
      | transExp (venv, tenv, A.IntExp (i)) = {exp=(), ty=T.INT}
      | transExp (venv, tenv, A.StringExp(str)) = {exp=(), ty=T.STRING}
      | transExp (venv, tenv, A.CallExp{func=sym, args=explist, pos=pos}) =
        let
            val func_sym_opt = lookup (tenv, func);
            val func_sym =
                case func_sym_opt of
                    NONE => raise Semant "undefined function: " ^ (A.name sym)
                  | SOME func_sym => func_sym;
            val fun_result =
                case func_sym of
                    VarEntry{ty=ty} => raise Semant "var is used as fun: " ^ (A.name sym)
                  | FunEntry{result=ty, ...} => ty;
        in
            expty {exp=(), ty=ty}
        end
      | transExp (venv, tenv,
                  A.OpExp {left=left, oper=oper, right=right, pos=pos}) =
        let
        in
            {exp=(), ty=}
        end
      | transExp transExp (
            venv, tenv, A.RecordExp {fiedls=fields_list, typ=sym, pos=pos}) =
        let
        in
            {exp=(), ty=}
        end
      | transExp (venv, tenv, A.SeqExp (seq_list)) =
        let
        in
            {exp=(), ty}
        end
      | transExp (venv, tenv, A.AssignExp {var=var, exp=exp, pos=pos}) =
        let
        in
            {exp=(), ty}
        end
      | transExp (venv, tenv,
                  A.IfExp {test=test_exp, then'=then_exp,
                           else'=NONE, pos=pos}) =
        let
        in
            {exp=(), ty=T.UNIT}
        end
      | transExp (venv, tenv,
                  A.IfExp {test=test_exp, then'=then_exp,
                           else'=SOME else_exp, pos=pos}) =
        let
        in
            {exp=(), ty=}
        end
      | transExp (venv, tenv,
                  A.WhileExp {test=test_exp, body=body_exp, pos=pos})=
        let
        in
            {exp=(), ty=T.UNIT}
        end
      | transExp (venv, tenv,
                  A.ForExp {var=sym, escape=ref esc,
                            lo=lo_exp, hi=hi_exp, body=body_exp, pos=pos}) =
        let
        in
        end
      | transExp (venv, tenv, A.BreakExp (pos)) =
        let
        in
            {exp=(), ty=T.UNIT}
        end
      | transExp (venv, tenv,
                  A.LetExp {desc=desc_list, body=body_exp, pos=pos}) =
        let
        in
            {exp=(), ty=}
        end
      | transExp (venv, tenv,
                  A.ArrayExp {typ=sym, size=size_exp, init=init_exp,
                              pos=pos}) =
        let
        in
            {exp=(), ty=T.UNIT}
        end
    and transVar (venv, tenv, A.SimpleVar (sym, pos)) =
        let
        in
            {exp=(), ty=}
        end
      | transVar (venv, tenv, A.FieldVar (var, sym, pos)) =
        let
        in
            {exp=(), ty=}
        end
      | transVar (venv, tenv, SubscriptVar (var, exp, pos)) =
        let
        in
            {exp=(), ty=}
        end
    and transDec (venv: venv, tenv: tenv, dec: A.dec): {venv: venv, tenv: tenv} = ();
    and transDec (venv, tenv, A.FunctionDec (fundec_list)) =
        let
        in
            {exp=(), ty=}
        end
      | transDec (venv, tenv,
                  A.VarDec {name=sym, escape=ref esc, typ: typ,
                            init=init_exp, pos=pos}) =
        let
        in
        end
      | transDec (venv, tenv, A.TypeDec (ty_list)) =
        let
        in
        end
    and transTy  (tenv, A.NameTy (sym, pos)) =
        let
        in
        end
      | transTy (tenv, A.RecordTy (field_list)) =
        let
        in
        end
      | transTy (tenv, A.ArrayTy (sym, pos)) =
        let
        in
        end;
end;