% -*- mode: Noweb; noweb-code-mode: caml-mode -*-
% $Id: environment.nw,v 1.5 2004-06-05 15:35:46 govereau Exp $
% ---------------------------------------------------------------------------
\section{Environments}
\label{sec:environments}
% ---------------------------------------------------------------------------
The [[Environment]] module provides the environment structure that is
used during type checking (Section~\ref{sec:semantics}). For each
Tiger function, there is an associated environment containing variable
definitions, function definitions, and other information. An
environment is made up of: a table of type definitions, a table of
variable names and their defined types, the list of defined
exceptions, the current procedure stack frame, the current break
label, and the current exception handler label.
<<envtype>>=
type 'a t = {
    tenv        : 'a Symbol.table;
    venv        : 'a enventry Symbol.table;
    xenv        : int Symbol.table;
    frame       : Frame.frame;
    break_label : Tree.label option;
    exn_label   : Tree.label option
  }
@
The environment type [['a t]] is polymorphic---any Ocaml~type can be
used to represent Tiger types. The type variable [['a]] is
instantiated with the representation of Tiger types defined in
Section~\ref{sec:types}.

A name can be bound to either a variable or a function in the
environment. For variables, we keep information about the location in
the current stack frame and the type. For functions, we keep the
function name, an optional calling convention, the stack frame, the
parameter types, and the return type.
<<enventry>>=
type 'a enventry =
    VarEntry of (Frame.access * 'a)
  | FunEntry of (Symbol.symbol * string option * Frame.frame * 'a list * 'a)
@ 
% ---------------------------------------------------------------------------
\subsection{Interface to the Environment}
% ---------------------------------------------------------------------------
The environment is a mostly functional data structure. However, the
symbol tables representing type definitions and variable types are
mutated in place. Therefore, most operations return a new environment,
but adding new type definitions and variable bindings do not.

The environment types are exposed in the interface.
<<environment.mli>>=
<<enventry>>
<<envtype>>
@ 
An initial environment can be generated using the [[new_env]]
function. The new environment will be populated with an initial set of
type definitions and functions. All new environments are automatically
given a new stack frame.
<<environment.mli>>=
val new_env : (string * 'a) list ->
              (string * string option * 'a list * 'a) list -> 'a t
@ 
There are three functions for manipulating the variable scope and the
current stack frame. Creating a new stack frame automatically creates
a new variable scope.
<<environment.mli>>=
val new_scope : 'a t -> 'a t
val frame     : 'a t -> Frame.frame
val new_frame : 'a t -> Symbol.symbol -> 'a t
@ 
The environment provides functions for looking up types, values and
exception identifiers. Calling a lookup function for a symbol that
does not exist indicates that the original source has an error (use of
undefined symbol). Each lookup function takes an [[Ast.pos]] argument
that is used to report errors.
<<environment.mli>>=
val lookup_type  : 'a t -> Symbol.symbol -> Ast.pos -> 'a
val lookup_value : 'a t -> Symbol.symbol -> Ast.pos -> 'a enventry
val lookup_exn   : 'a t -> Symbol.symbol -> Ast.pos -> int
@ 
New types, values, and exceptions can be added to an environment using
the enter functions. There are five functions for entering type
definitions, exceptions, function definitions, formal parameters, and
local variables. Both [[enter_param]] and [[enter_local]] take a
boolean parameter that is true if the new local or parameter will hold
a pointer value.
<<environment.mli>>=
val enter_type  : 'a t -> Symbol.symbol -> 'a -> unit
val enter_exn   : 'a t -> Symbol.symbol -> unit
val enter_fun   : 'a t -> Symbol.symbol -> string option ->
                  'a list -> 'a  -> 'a t
val enter_param : 'a t -> Symbol.symbol -> 'a -> bool -> unit
val enter_local : 'a t -> Symbol.symbol -> 'a -> bool -> Frame.access
@ 
The environment is used to track the current break label for exiting
from loops. The [[break_label]] function will raise [[Not_Found]] if
there is no current break label.
<<environment.mli>>=
val break_label     : 'a t -> Tree.label
val new_break_label : 'a t -> 'a t
@ 
Similar to the break label, the environment also tracks the current
exception label. The exception label can be [[None]] indicating that
there is no current exception handler.
<<environment.mli>>=
val exn_label     : 'a t -> Tree.label option
val new_exn_label : 'a t -> 'a t
@ 
% ---------------------------------------------------------------------------
\subsection{Implementation of Environments}
% ---------------------------------------------------------------------------
<<environment.ml>>=
module E = Error
module S = Symbol
module F = Frame
module T = Tree
<<enventry>>
<<envtype>>
@ 
To create a new environment, we construct a record that contains the
initial types and functions, and a base frame.
<<environment.ml>>=
let new_env types funs =
  let mkfe (n,cc,a,r) = (n, FunEntry(S.symbol n,cc,F.base_frame,a,r))
  in { tenv        = Symbol.create types;
       venv        = Symbol.create (List.map mkfe funs);
       xenv        = Symbol.create [];
       frame       = F.new_frame (S.symbol "tiger_main") F.base_frame;
       break_label = None;
       exn_label   = None }
@ 
To create a new variable scope, we update the symbol tables.
<<environment.ml>>=
let new_scope env = { env with
                      tenv = S.new_scope env.tenv;
                      venv = S.new_scope env.venv }
@
Creating a new frame requires updating the frame and removing the
current exception label in addition to updating the symbol tables.
<<environment.ml>>=
let frame env = env.frame
let new_frame env sym = { env with
                          tenv = S.new_scope env.tenv;
                          venv = S.new_scope env.venv;
                          frame = Frame.new_frame sym env.frame;
                          exn_label = None }
@ 
The lookup functions use the symbol table (Section~\ref{sec:symbols})
implementation to lookup values in the various tables. If a symbol is
not found, then we raise an undefined symbol error.
<<environment.ml>>=
let lookup env sym pos =
  try S.look env sym
  with Not_found ->
    raise(E.Error(E.Undefined_symbol (S.name sym), pos))

let lookup_type  env = lookup env.tenv
let lookup_value env = lookup env.venv
let lookup_exn   env = lookup env.xenv
@
Entering new types, exceptions, and values into the environment is
also implemented with the symbol table functions. In this case, we may
raise a duplicate symbol error if a name is defined twice in a source
file.
<<environment.ml>>=
let enter tbl sym v =
  if S.mem tbl sym
  then raise(E.Error(E.Duplicate_symbol (S.name sym), 0))
  else S.enter tbl sym v

let enter_type env = enter env.tenv
@ 
For exceptions, we need to generate a unique identifier for each
exception. For this, we just use the unique identifier associated with
the symbol.
<<environment.ml>>=
let enter_exn env sym = enter env.xenv sym (S.uid sym)
@ 
For function definitions, we generate a fresh label based on the
function name, and a new environment for the function parameters and
local variables. After entering the function definition in the
environment, we return the new function environment to the caller.
<<environment.ml>>=
let enter_fun env sym cc args result =
  let lbl = S.new_symbol (S.name sym) in
  let fenv = new_frame env lbl in
  let fe = FunEntry (lbl, cc, fenv.frame, args, result) in
  enter env.venv sym fe;
  fenv
@ 
When a formal function parameter is entered in to the environment, a
new slot is allocated in the current frame to hold the parameter.
<<environment.ml>>=
let enter_param env sym typ ptr =
  let acc = F.alloc_param env.frame sym ptr in
  enter env.venv sym (VarEntry(acc,typ))
@
When a new local variable is entered into the environment, we first
allocate space in the current frame to hold a new temporary and then
enter it into the value table.
<<environment.ml>>=
let enter_local env sym typ ptr =
  let acc = F.alloc_local env.frame sym ptr in
  enter env.venv sym (VarEntry(acc, typ));
  acc
@
To create a new break label, we generate a new label and store it in
the environment. When the break label is requested, the
[[break_label]] function will raise [[Not_Found]] if there is no
current label.
<<environment.ml>>=
let break_label env =
  match env.break_label with
    None      -> raise Not_found
  | Some(lbl) -> lbl

let new_break_label env =
  { env with break_label = Some(T.new_label "loop_end") }
@
The implementation for exception labels is similar. However, the
[[exn_label]] function will not raise an exception if there is no
current exception label. Instead, this function returns an option
type.
<<environment.ml>>=
let exn_label     env = env.exn_label
let new_exn_label env =
  { env with exn_label = Some(T.new_label "exn") }
@