deliverables/report/sem.tex

   1 \section{Semantic analysis}\label{sec:sem}
   2 %The grammar used to parse
   3 %SPL
   4 %, if it is di erent from the given grammar.
   5 %{
   6 %The scoping rules you use and check in your compiler.
   7 %{
   8 %The typing rules used for
   9 %SPL
  10 %.
  11 %{
  12 %A brief guide telling what each of the examples tests (see next point).
  13 %{
  14 %A concise but precise description of how the work was divided amongst the
  15 %members of
  16 %the team.
  17
  18 The semantic analysis phase asses if a -grammatically correct- program is also
  19 semantically correct and decorates the program with extra information it
  20 finds during this checking. The input of the semantic analysis is an \AST/ of
  21 the
  22 parsed program, its output is either a semantically correct and completely typed
  23 \AST/ plus the environment in which it was typed (for debug purposes), or it is
  24 an error describing the problem with the \AST/.
  25
  26 During this analysis \SPLC checks four properties of the program:
  27 \begin{enumerate}
  28         \item That no functions are declared with the same name
  29         \item That \tt{main} is of type \tt{(-> Void)}
  30         \item That the program includes a main function
  31         \item That the program is correctly typed
  32 \end{enumerate}
  33 The first three steps are simple sanity checks which are coded in slightly over
  34 two dozen lines of Clean code. The last step is a Hindley Milner type inference
  35 algorithm, which is a magnitude more complex. This last step also decorates the
  36 \AST/ with inferred type information.
  37
  38 \subsection{Sanity checks}
  39 The sanity checks are defined as simple recursive functions over the function
  40 declarations in the AST. We will very shortly describe them here.
  41
  42 \begin{description}
  43         \item [No duplicate functions] This function checks that the program does
  44                 not contain top level functions sharing the same name. Formally:
  45                 $ \forall f \in \textrm{functions} \ldotp \neg
  46                         \exists g \in \textrm{functions} \setminus \{f\} \ldotp
  47                         f.\textrm{name} = g.\textrm{name}$
  48         \item [\tt{main} should have type \tt{->Void}] Our semantics of \SPL{}
  49                 require the main function to take no arguments and to not return a
  50                 value. Formally: $\forall f \in \textrm{functions} \ldotp
  51                         f.\textrm{name} = \textrm{'main'} \Rightarrow
  52                         \textit{typeof}\textrm{(main)} = \rightarrow\textrm{Void} $
  53         \item [The program should have a main function] $\exists f \in
  54                 \textrm{functions} \ldotp f.\textrm{name} = \textrm{'main'}$
  55 \end{description}