\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={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{Expression Tree Calculator Case Study}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{13 September 2018}}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
\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{Browser Advisory}: The HTML version of this document requires
use of a browser that supports the display of MathML. A good choice as
of September 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
\VERB|\DecValTok{1}\FunctionTok{+}\DecValTok{2}| and
\VERB|\NormalTok{(x}\FunctionTok{+}\NormalTok{x)}\FunctionTok{+}\NormalTok{(}\DecValTok{7}\FunctionTok{+}\NormalTok{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 \VERB|\DataTypeTok{Add}| represents addition of two
subexpressions, \VERB|\DataTypeTok{Var}| represents a variable with a
name, and \VERB|\DataTypeTok{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
\VERB|\NormalTok{x}\FunctionTok{+}\DecValTok{1}| might be evaluated in
an environment that associates the value \VERB|\DecValTok{5}| with the
variable \VERB|\NormalTok{x}|, written
\texttt{\{\ x\ -\textgreater{}\ 5\ \}}. This evaluation yields the value
\VERB|\DecValTok{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
\VERB|\DataTypeTok{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 \VERB|\NormalTok{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 \VERB|\DataTypeTok{Maybe}|, returning a \VERB|\DataTypeTok{Just}|
if the key is found or returns a \VERB|\DataTypeTok{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 \VERB|\NormalTok{main}| function that
performs several operations on the expression
\VERB|\NormalTok{(x}\FunctionTok{+}\NormalTok{x)}\FunctionTok{+}\NormalTok{(}\DecValTok{7}\FunctionTok{+}\NormalTok{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 \VERB|\NormalTok{x}| and then to
\VERB|\NormalTok{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 \VERB|\DataTypeTok{ExprTree}| definition and the
  \VERB|\NormalTok{eval}| function to add the following new kinds of
  nodes: \VERB|\DataTypeTok{Sub}|,\VERB|\DataTypeTok{Mul}|, and
  \VERB|\DataTypeTok{Div}| for subtraction, multiplication, and division
  of values, respectively; \VERB|\DataTypeTok{Neg}| for negating a
  value, and \VERB|\DataTypeTok{Sin}| and \VERB|\DataTypeTok{Cos}| for
  the sine and cosine trigonometric functions, respectively.
\item
  Extend function \VERB|\NormalTok{derive}| to support the operators in
  the previous exercise.
\item
  Extend the \VERB|\NormalTok{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
  (\VERB|\NormalTok{(x }\FunctionTok{+}\NormalTok{ y) }\FunctionTok{+}\NormalTok{ z }\FunctionTok{=}\NormalTok{ x }\FunctionTok{+}\NormalTok{ (y }\FunctionTok{+}\NormalTok{ z)}|)
  and commutativity
  (\VERB|\NormalTok{x }\FunctionTok{+} \DecValTok{1} \FunctionTok{=} \DecValTok{1} \FunctionTok{+}\NormalTok{ x}|).
\item
  Write an object-oriented program (e.g.~in Java, Scala, or Python

  \begin{enumerate}
  \def\labelenumii{\arabic{enumii})}
  \setcounter{enumii}{2}
  \tightlist
  \item
    to carry out the same functionality using a class hierarchy and the
    message-passing style.
  \end{enumerate}
\end{enumerate}

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

For the Haskell-based CSci 556 course in Spring 2017, I converted the
Expression Tree Calculator case study from Scala to Haskell and adapted
this document from my
\href{../../ScalaForJava/ScalaForJava.html}{\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}{\emph{Scala
for Java Programmers}} by Michel Schinz and Phillipp Haller.

Later in Spring 2017, I expanded this case study into an assignment for
CSci 556. In 2017 and 2018, I further expanded it into chapters of the
textbook now titled
\href{https://www.cs.olemiss.edu/~hcc/csci450/ELIFP/ExploringLanguages.html}{\emph{Exploring
Languages with Interpreters and Functional Programming}}. 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.

\hypertarget{references}{%
\subsection{References}\label{references}}

TODO: Add

\hypertarget{concepts}{%
\subsection{Concepts}\label{concepts}}

TODO: Add

\end{document}