% -*- mode: Noweb; noweb-code-mode: caml-mode -*-
% $Id: symbol.nw,v 1.5 2004-06-05 15:35:49 govereau Exp $
% ---------------------------------------------------------------------------
\section{Symbols}
\label{sec:symbols}
The [[Symbol]] module provides the representation of symbols and an
implementation of symbol tables.

% ---------------------------------------------------------------------------
\subsection{Basic Symbols}
% ---------------------------------------------------------------------------
Symbols are created from strings found in the source program. The
interface to symbols is given below. A new symbol can be created from
a string. The [[new_symbol]] function ensures that the newly created
symbol is unique.
<<symbol.mli>>=
type symbol

val uid        : symbol -> int
val name       : symbol -> string
val symbol     : string -> symbol
val new_symbol : string -> symbol
@
Symbols are implemented as stamped strings---a pair containing a
string and an int. The integer is used to identify the symbol. All
symbols are held in a hash-table implemented by the standard library
[[Hashtbl]] module.
<<symbol.ml>>=
type symbol = string * int

let nextsym = ref 0
let hashtable = Hashtbl.create 128

let name = fst
let uid  = snd

let symbol name =
  try let s = Hashtbl.find hashtable name in (name,s)
  with Not_found ->
    incr nextsym; Hashtbl.add hashtable name !nextsym;
    (name, !nextsym)

let new_symbol s = symbol (Printf.sprintf "%s_%d" s !nextsym)
@ 
% ---------------------------------------------------------------------------
\subsection{Symbol Tables}
% ---------------------------------------------------------------------------
A symbol table is a mapping from symbols to values. In addition,
symbol tables support ``scoping'' in that each table has a parent
table. If a symbol is not found in the a table, then the parent table
will be consulted---each child table hide the definitions of its
parent.

A symbol table is created with a list of key-value pairs for the
initial table. Symbols can be inserted and queried up with the
[[enter]] and [[look]] functions, and a nested scope can be created
with the [[new_scope]] function.
<<symbol.mli>>=
type 'a table

val enter  : 'a table -> symbol -> 'a -> unit
val look   : 'a table -> symbol -> 'a
val mem    : 'a table -> symbol -> bool
val create : (string * 'a) list -> 'a table

val new_scope : 'a table -> 'a table
@
The [[iter]] and [[fold]] functions perform the usual iteration and
folding over a symbol table and its parents. The first parameter to
the supplied functions gives to nesting level in which the current
symbol-value pair lives. The outermost level is 0.
<<symbol.mli>>=
val iter : (int -> symbol -> 'a -> unit) -> 'a table -> unit
val fold : (int -> symbol -> 'a -> 'b -> 'b) -> 'a table -> 'b -> 'b
@
Symbol tables are implemented using the standard library [[Hashtbl]]
module. Duplicate entries in the same table are disallowed.
<<symbol.ml>>=
type 'a table = {
    level  : int;
    tbl    : (symbol, 'a) Hashtbl.t;
    parent : 'a table option
  }

let enter env s v =
  if Hashtbl.mem env.tbl s
  then failwith "Compiler error: symbol table duplicate entry"
  else Hashtbl.add env.tbl s v
@
If a symbol is not found in a given symbol table, then its parent
table is checked. If there is no parent table, then [[Not_found]] is
raised.
<<symbol.ml>>=
let rec look env s =
  try Hashtbl.find env.tbl s
  with Not_found -> match env.parent with
    None -> raise Not_found
  | Some e -> look e s
@
The [[mem]] function can be used to determine if a symbol is defined
in the current nesting level.
<<symbol.ml>>=
let mem env = Hashtbl.mem env.tbl
@
Symbol tables are created from a list of initial mappings. All symbol
tables are created with an initial nesting level of zero. As new
nested scopes are created the level increases by one for each level.
<<symbol.ml>>=        
let create l =
  let env = {
    level = 0;
    tbl = Hashtbl.create 20;
    parent = None
  } in
  List.iter (fun (key, data) -> enter env (symbol key) data) l;
  env

let new_scope env = { level = env.level + 1;
                      tbl = Hashtbl.create 20;
                      parent = Some env }
@
Both [[iter]] and [[fold]] are implemented by lifting the
corresponding [[Hashtbl]] functions up to our representation of symbol
tables.
<<symbol.ml>>=
let rec iter f env =
  Hashtbl.iter (f env.level) env.tbl;
  match env.parent with
    None -> ()
  | Some e -> iter f e

let rec fold f env init =
  let fold_fun = f env.level in
  let result = Hashtbl.fold (f env.level) env.tbl init in
  match env.parent with
    None -> result
  | Some e -> fold f e result
@