\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.

As an example, the 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}