\section{The Abstract Syntax Tree}
\label{sec:ast}

In functional programming languages it is trivial to create new types. A
formally defined syntax as we have seen for While in \autoref{sec:intro:while}
translates almost directly to a type definition:

\lstinputlisting[firstline=12,lastline=24]{While/WhileCommon.dcl}
\lstinputlisting[firstline=6,lastline=10]{While/Simple.dcl}

Note that we have added common binary operators like \CI{Lt} that did not exist
in the grammar of \autoref{sec:intro:while}. These operators could also be
constructed from other boolean expressions. We have also added \CI{Div} for
integer division. It is a useful addition in this example, as it will force us
to implement error handling in the evaluation of arithmetic expressions when we
divide by zero.

As an example, the example program from \autoref{sec:intro:while} would be
stored in the AST as follows:

\begin{lstlisting}
Compose
	(Ass "x" (Var "y"))
	(While
		(Not (Comp (Var "x") Le (Lit 0)))
		(Compose
			(Ass "x" (Op (Var "x") Sub (Lit 2)))
			(Ass "y" (Op (Var "y") Sub (Lit 1)))
		)
	)
\end{lstlisting}