\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 658-01: Software Language Engineering Expression Tree Calculator Case Study},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi

% set default figure placement to htbp
\makeatletter
\def\fps@figure{htbp}
\makeatother

\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 658-01: Software Language Engineering\\
Expression Tree Calculator Case Study}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{17 February 2018}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2018, \href{http://www.cs.olemiss.edu/~hcc}{H. Conrad
Cunningham}\\
Professor of \href{https://www.cs.olemiss.edu}{Computer and Information
Science}\\
\href{http://www.olemiss.edu}{University of Mississippi}\\
211 Weir Hall\\
P.O. Box 1848\\
University, MS 38677\\
(662) 915-5358

\textbf{Advisory}: The HTML version of this document requires use of a
browser that supports the display of MathML. A good choice as of
February 2018 is a recent version of Firefox from Mozilla.

\hypertarget{expression-tree-calculator-case-study}{%
\section{Expression Tree Calculator Case
Study}\label{expression-tree-calculator-case-study}}

\hypertarget{problem-description}{%
\subsection{Problem Description}\label{problem-description}}

In programming, we often use trees and other hierarchical data
structures.

We can illustrate how to implement a tree in Haskell using a small
calculator program for simple arithmetic expressions composed of
addition operations, integer constants, and variables. Examples of such
expressions in infix form area \texttt{1+2} and \texttt{(x+x)+(7+y)}.

We can represent expressions naturally with a tree, where nodes are
operations (e.g., addition) and leaves are values (e.g., constants or
variables). This representation is called the \emph{abstract syntax
tree} for the expression.

In Haskell, we can represent these expression trees using algebraic data
types. Such types often enable us to express programs concisely by using
pattern matching.

For the calculator program, we introduce the following types to describe
the expression tree.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{type} \DataTypeTok{Name} \FunctionTok{=} \DataTypeTok{String}

    \KeywordTok{data} \DataTypeTok{ExprTree} \FunctionTok{=} \DataTypeTok{Add} \DataTypeTok{ExprTree} \DataTypeTok{ExprTree} \FunctionTok{|} 
                    \DataTypeTok{Var} \DataTypeTok{Name} \FunctionTok{|} 
                    \DataTypeTok{Val} \DataTypeTok{Int}
                    \KeywordTok{deriving} \DataTypeTok{Show}
\end{Highlighting}
\end{Shaded}

Above \texttt{Add} represents addition of two subexpressions,
\texttt{Var} represents a variable with a name, and \texttt{Val}
represents a constant value.

Consider a function to evaluate an expression in some
\emph{environment}. The purpose of an environment is to associate values
with variables.

For example, the expression \texttt{x+1} might be evaluated in an
environment that associates the value \texttt{5} with the variable
\texttt{x}, written \texttt{\{\ x\ -\textgreater{}\ 5\ \}}. This
evaluation yields the value \texttt{6}.

An environment associates a variable name with a value. The environment
\texttt{\{\ x\ -\textgreater{}\ 5\ \}} given above can be expressed in
Haskell in a number of ways. Here we choose to represent it as an
\emph{association list}, that is, as a list of pairs where the variable
is the first component and its value is the second:

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    [(}\StringTok{"x"}\NormalTok{,}\DecValTok{5}\NormalTok{)]}
\end{Highlighting}
\end{Shaded}

To simplify our evaluation program, we define the type synonym
\texttt{Env} as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{type} \DataTypeTok{Env} \FunctionTok{=}\NormalTok{ [(}\DataTypeTok{Name}\NormalTok{,}\DataTypeTok{Int}\NormalTok{)]}
\end{Highlighting}
\end{Shaded}

We can use the Prelude function \texttt{lookup} to search association
lists. It takes a \texttt{key} and an association list and returns the
value associated with the key, if any. It wraps the result in a
\texttt{Maybe}, returning a \texttt{Just} if the key is found or returns
a \texttt{Nothing} if it does not occur in the list.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    lookup ::}\NormalTok{ (}\DataTypeTok{Eq}\NormalTok{ a) }\OtherTok{=>}\NormalTok{ a }\OtherTok{->}\NormalTok{ [(a,b)] }\OtherTok{->} \DataTypeTok{Maybe}\NormalTok{ b}
\NormalTok{    lookup _   []   }\FunctionTok{=}  \DataTypeTok{Nothing}
\NormalTok{    lookup key ((x,y)}\FunctionTok{:}\NormalTok{xys)}
        \FunctionTok{|}\NormalTok{ key }\FunctionTok{==}\NormalTok{ x  }\FunctionTok{=}  \DataTypeTok{Just}\NormalTok{ y}
        \FunctionTok{|}\NormalTok{ otherwise }\FunctionTok{=}\NormalTok{  lookup key xys}
\end{Highlighting}
\end{Shaded}

We can now define the evaluation function in Haskell as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    eval ::} \DataTypeTok{ExprTree} \OtherTok{->} \DataTypeTok{Env} \OtherTok{->} \DataTypeTok{Int}
\NormalTok{    eval (}\DataTypeTok{Add}\NormalTok{ l r) env }\FunctionTok{=}\NormalTok{ eval l env }\FunctionTok{+}\NormalTok{ eval r env}
\NormalTok{    eval (}\DataTypeTok{Var}\NormalTok{ n)   env }\FunctionTok{=}
        \KeywordTok{case}\NormalTok{ (lookup n env) }\KeywordTok{of}
            \DataTypeTok{Just}\NormalTok{ i  }\OtherTok{->}\NormalTok{ i}
            \DataTypeTok{Nothing} \OtherTok{->}\NormalTok{ error (}\StringTok{"Undefined variable "} \FunctionTok{++}\NormalTok{ show n)}
\NormalTok{    eval (}\DataTypeTok{Val}\NormalTok{ v)   _   }\FunctionTok{=}\NormalTok{ v}
\end{Highlighting}
\end{Shaded}

To explore algebraic data types and pattern matching further, consider
another operation on arithmetic expressions: symbolic derivation.
Looking back at our calculus class, we see the following rules for
differentiation:

\begin{itemize}
\item
  The derivative of a sum is the sum of the derivatives.
\item
  The derivative of some variable \texttt{v} is 1 if \texttt{v} is the
  variable relative to which the derivation takes place, and is 0
  otherwise.
\item
  The derivative of a constant is 0.
\end{itemize}

We can directly translate these rules into a Haskell function that uses
the above data types as follows:

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    derive ::} \DataTypeTok{ExprTree} \OtherTok{->} \DataTypeTok{Name} \OtherTok{->} \DataTypeTok{ExprTree}
\NormalTok{    derive (}\DataTypeTok{Add}\NormalTok{ l r) v }\FunctionTok{=} \DataTypeTok{Add}\NormalTok{ (derive l v) (derive r v)}
\NormalTok{    derive (}\DataTypeTok{Var}\NormalTok{ n)   v}
        \FunctionTok{|}\NormalTok{ v }\FunctionTok{==}\NormalTok{ n       }\FunctionTok{=} \DataTypeTok{Val} \DecValTok{1}
\NormalTok{    derive _         _ }\FunctionTok{=} \DataTypeTok{Val} \DecValTok{0}
\end{Highlighting}
\end{Shaded}

Consider an example with a simple \texttt{main} function that performs
several operations on the expression \texttt{(x+x)+(7+y)}.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    main }\FunctionTok{=} \KeywordTok{do}
        \KeywordTok{let}\NormalTok{ exp }\FunctionTok{=} \DataTypeTok{Add}\NormalTok{ (}\DataTypeTok{Add}\NormalTok{ (}\DataTypeTok{Var} \StringTok{"x"}\NormalTok{) (}\DataTypeTok{Var} \StringTok{"x"}\NormalTok{)) }
\NormalTok{                      (}\DataTypeTok{Add}\NormalTok{ (}\DataTypeTok{Val} \DecValTok{7}\NormalTok{) (}\DataTypeTok{Var} \StringTok{"y"}\NormalTok{))}
        \KeywordTok{let}\NormalTok{ env }\FunctionTok{=}\NormalTok{ [(}\StringTok{"x"}\NormalTok{,}\DecValTok{5}\NormalTok{), (}\StringTok{"y"}\NormalTok{,}\DecValTok{7}\NormalTok{)]}
\NormalTok{        putStrLn (}\StringTok{"Expression: "} \FunctionTok{++}\NormalTok{ show exp) }
\NormalTok{        putStrLn (}\StringTok{"Evaluation with x=5, y=7: "} \FunctionTok{++}
\NormalTok{                  show (eval exp env))}
\NormalTok{        putStrLn (}\StringTok{"Derivative relative to x:\textbackslash{}n "} \FunctionTok{++} 
\NormalTok{            show (derive exp }\StringTok{"x"}\NormalTok{))}
\NormalTok{        putStrLn (}\StringTok{"Derivative relative to y:\textbackslash{}n "} \FunctionTok{++} 
\NormalTok{                  show (derive exp }\StringTok{"y"}\NormalTok{))}
\end{Highlighting}
\end{Shaded}

It first computes its value in the environment
\texttt{\{\ x\ -\textgreater{}\ 5,\ y\ -\textgreater{}\ 7\ \}} and then
computes its derivative relative to \texttt{x} and then to \texttt{y}.

Executing this program, we get the expected output:

\begin{verbatim}
    Expression: Add (Add (Var "x") (Var "x")) (Add (Val 7) (Var "y"))
    Evaluation with x=5, y=7: 24
    Derivative relative to x:
        Add (Add (Val 1) (Val 1)) (Add (Val 0) (Val 0))
    Derivative relative to y:
        Add (Add (Val 0) (Val 0)) (Add (Val 0) (Val 1))
\end{verbatim}

The result of the derivative is complex. It should be simplified before
printing. Defining a basic simplification function using pattern
matching is an interesting (but surprisingly tricky) problem.

Here is an skeleton function that simplifies the expression by
evaluating constant subexpressions and accounting for identity elements.

\begin{Shaded}
\begin{Highlighting}[]
\OtherTok{    simplify ::} \DataTypeTok{ExprTree} \OtherTok{->} \DataTypeTok{ExprTree}
\NormalTok{    simplify t}\FunctionTok{@}\NormalTok{(}\DataTypeTok{Val}\NormalTok{ _)               }\FunctionTok{=}\NormalTok{ t}
\NormalTok{    simplify t}\FunctionTok{@}\NormalTok{(}\DataTypeTok{Var}\NormalTok{ _)               }\FunctionTok{=}\NormalTok{ t}
\NormalTok{    simplify (}\DataTypeTok{Add}\NormalTok{ (}\DataTypeTok{Val} \DecValTok{0}\NormalTok{) r        ) }\FunctionTok{=}\NormalTok{ simplify r}
\NormalTok{    simplify (}\DataTypeTok{Add}\NormalTok{ l         (}\DataTypeTok{Val} \DecValTok{0}\NormalTok{)) }\FunctionTok{=}\NormalTok{ simplify l}
\NormalTok{    simplify (}\DataTypeTok{Add}\NormalTok{ (}\DataTypeTok{Val}\NormalTok{ x) (}\DataTypeTok{Val}\NormalTok{ y))   }\FunctionTok{=} \DataTypeTok{Val}\NormalTok{ (x}\FunctionTok{+}\NormalTok{y)}
\end{Highlighting}
\end{Shaded}

The source code for the above skeleton
\href{ExprTreeCalculator.hs}{expression tree calculator program} is
available.

\hypertarget{exercises}{%
\subsection{Exercises}\label{exercises}}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Extend the data type \texttt{ExprTree} definition and the
  \texttt{eval} function to add the following new kinds of nodes:
  \texttt{Sub},\texttt{Mul}, and \texttt{Div} for subtraction,
  multiplication, and division of values, respectively; \texttt{Neg} for
  negating a value, and \texttt{Sin} and \texttt{Cos} for the sine and
  cosine trigonometric functions, respectively.
\item
  Extend function \texttt{derive} to support the operators in the
  previous exercise.
\item
  Extend the \texttt{simplify} function to support the new operators in
  the previous exercises. This function should simplify the tree by
  evaluating all subexpressions involving only constants (not evaluating
  variables) and handling special values like identity and zero
  elements.
\item
  Extend the simplifications in other ways. For example, you could take
  advantage of mathematical properties such as associativity
  (\texttt{(x\ +\ y)\ +\ z\ =\ x\ +\ (y\ +\ z)}and commutativity ( x + 1
  = 1 + x`).
\item
  Write an object-oriented program to carry out the same functionality
  using a class hierarchy and the message-passing style.
\end{enumerate}

\hypertarget{acknowledgements}{%
\subsection{Acknowledgements}\label{acknowledgements}}

In Spring 2017 for the Haskell-based CSci 556 course, I converted the
Expression Tree Calculator case study from Scala to Haskell and adapted
this document from my \emph{Notes on Scala for Java Programmers}, which
is itself adapted from the tutorial
\href{http://docs.scala-lang.org/tutorials/scala-for-java-programmers.html}{Scala
for Java Programmers}.

Later in 2017, I expanded this case study into an expanded assignment
for CSci 556 and further into the ``Expression Language'' chapter of the
evolving CSci 450 textbook. But, for now, I am keeping this as a
separate document.

I maintain these notes as text in Pandoc's dialect of Markdown using
embedded LaTeX markup for the mathematical formulas and then translate
the notes to HTML, PDF, and other forms as needed.

\end{document}