\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}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \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
}{}
\PassOptionsToPackage{hyphens}{url} % url is loaded by hyperref
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={CSci 450: Org. of Programming Languages Evaluation and Efficiency},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{longtable,booktabs}
% Fix footnotes in tables (requires footnote package)
\IfFileExists{footnote.sty}{\usepackage{footnote}\makesavenoteenv{long table}}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{5}
% 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 450: Org. of Programming Languages\\
Evaluation and Efficiency}
\author{H. Conrad Cunningham}
\date{16 September 2017}

\begin{document}
\maketitle

{
\setcounter{tocdepth}{4}
\tableofcontents
}
Copyright (C) 2016, 2017, H. Conrad Cunningham

\textbf{Acknowledgements:} I adapted and revised this chapter from my
previous materials in Summer and Fall 2016.

\begin{itemize}
\item
  Evaluation of Functional Programs from parts of chapters 1 and 13 of
  my \emph{Notes on Functional Programming with Haskell} and from my
  notes on \emph{Recursion Concepts and Terminology} (Scala version)
\item
  three sections on recursion from my notes on \emph{Recursion Concepts
  and Terminology} (Scala, Elixir, and Lua versions)
\item
  the Haskell factorial, Fibonacci number, and exponentiation functions
  from my previous examples in Haskell, Elixir, Scala, Lua, and Elm,
  which, in turn, were adapted from the Scheme programs in Abelson and
  Sussman's classic, Scheme-based textbook
  \href{http://mitpress.mit.edu/sicp/}{SICP} {[}Abelson-Sussman 1996{]}.
\end{itemize}

In 2017, I continue to develop this chapter.

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.

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

TODO:

\begin{itemize}
\tightlist
\item
  Review discussion of termination, preconditions, and postconditions
  for consistency with later discussion of those topics
\item
  Add Java implementations of the \texttt{expt3} exponentiation function
\item
  Add new examples?
\item
  Update and add new exercises
\end{itemize}

\setcounter{section}{2}

\section{Evaluation and Efficiency}\label{evaluation-and-efficiency}

\subsection{Chapter Introduction}\label{chapter-introduction}

This chapter introduces an evaluation model and basic recursive
programming styles and techniques applicable to Haskell programs. As in
the previous chapter (Basic Haskell Functional Programming), it focuses
on use of first-order functions and primitive data types.

The goals of the chapter are for the students to be able to

\begin{itemize}
\item
  analyze Haskell functions to determine under what conditions they
  terminate normally and how efficient they are
\item
  develop recursive Haskell programs that terminate and are efficient in
  both time and space usage
\end{itemize}

Upon successful completion of this chapter, students should be able to:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  explain the substitution model
\item
  use the substitution model informally to analyze Haskell programs to
  determine under what conditions they terminate normally and abnormally
\item
  use the substitution model informally to analyze Haskell programs to
  determine the time and space complexities of their execution
\item
  compare different implementations of the same functionality for
  termination and efficiency
\item
  use the appropriate programming techniques to develop Haskell programs
  that terminate and execute efficiently
\item
  compare basic functional programming syntax and semantics of Haskell
  to that in other programming languages
\end{enumerate}

The Haskell code for this chapter is in file
\href{code03/EvalEff.hs}{\texttt{EvalEff.hs}}.

\subsection{Evaluation of Functional
Programs}\label{evaluation-of-functional-programs}

How can we evaluate (i.e., execute) an expression that ``calls'' a
function like the \texttt{fact1} function in a previous chapter?

We do this by rewriting expressions using a substitution model, as we
see below. This process depends upon a property of functional languages
called referential transparency.

\subsubsection{Referential transparency}\label{referential-transparency}

\emph{Referential transparency} is probably the most important property
of modern functional programming languages.

Referential transparency means that, within some well-defined context
(e.g., a function or module definition), a variable (or other symbol)
\emph{always} represents the \emph{same value}.

Because a variable always has the same value, we can replace the
variable in an expression by its value or vice versa. Similarly, if two
subexpressions have equal values, we can replace one subexpression by
the other. That is, ``equals can be replaced by equals''.

Pure functional programming languages thus use the same concept of a
variable that mathematics uses.

However, in most imperative programming languages, a variable represents
an address or ``container'' in which values may be stored. A program may
change the value stored in a variable by executing an assignment
statement. Thus these mutable variables break the property of
referential transparency.

Because of referential transparency, we can construct, reason about, and
manipulate functional programs in much the same way we can any other
mathematical expressions. Many of the familiar ``laws'' from high school
algebra still hold; new laws can be defined and proved for less familiar
primitives and even user-defined operators. This enables a relatively
natural equational style of reasoning using the actual expressions of
the language.

In contrast, to reason about imperative programs, we usually need to go
outside the language itself and use notation that represents the
semantics of the language.

For our purposes here, referential transparency underlies the
substitution model for evaluation of expressions in functional programs.

\subsubsection{Substitution model}\label{substitution-model}

The \emph{substitution model} (or \emph{reduction model}) involves
rewriting (or reducing) an expression to a ``simpler'' equivalent form.
It involves two kinds of replacements:

\begin{itemize}
\item
  replacing a subexpression that satisfies the left-hand side of an
  equation by the right-hand side with appropriate substitution of
  arguments for parameters
\item
  replacing a primitive application (e.g., \texttt{+} or \texttt{*}) by
  its value
\end{itemize}

The term \emph{redex} refers to a subexpression that can be reduced.

Redexes can be selected for reduction in several ways. For instance, the
redex can be selected based on its position within the expression:

\begin{itemize}
\item
  \emph{leftmost redex first}, where the leftmost reducible
  subexpression in the expression text is reduced before any other
  subexpressions are reduced
\item
  \emph{rightmost redex first}, where the rightmost reducible
  subexpression in the expression text is reduced before any other
  subexpressions are reduced
\end{itemize}

The redex can also be selected based on whether or not it is contained
within another redex:

\begin{itemize}
\item
  \emph{outermost redex first}, where a reducible subexpression that is
  not contained within any other reducible subexpression is reduced
  before one that is contained within another
\item
  \emph{innermost redex first}, where a reducible subexpression that
  contains no other reducible subexpression is reduced before one that
  contains others
\end{itemize}

We will explore these more fully later in these notes. In most
circumstances, Haskell uses a \emph{leftmost outermost redex first}
approach.

In a previous chapter, we defined factorial function \texttt{fact1} as
follows:

\begin{verbatim}
    fact1 :: Int -> Int 
    fact1 n = if n == 0 then 
                  1 
              else 
                  n * fact1 (n-1) 
\end{verbatim}

Consider the expression from \texttt{else} clause in \texttt{fact1} with
\texttt{n} having the value \texttt{2}:

\begin{verbatim}
    2 * fact1 (2-1)
\end{verbatim}

This has two redexes: subexpressions \texttt{2-1} and
\texttt{fact1\ (2-1)}.

The multiplication cannot be reduced because it requires both of its
arguments to be evaluated.

A function parameter is said to be \emph{strict} if the value of that
argument is always required. Thus, multiplication is strict in both its
arguments. If the value of an argument is not always required, then it
is \emph{nonstrict}.

The first redex \texttt{2-1} is an innermost redex. Since it is the only
innermost redex, it is both leftmost and rightmost.

The second redex \texttt{fact1\ (2-1)} is an outermost redex. Since it
is the only outermost redex, it is both leftmost and rightmost.

Now consider the complete evaluation of the expression \texttt{fact1\ 2}
using leftmost outermost reduction steps. Below we denote the steps with
\(\Longrightarrow\) and give the substitution performed between braces.

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{fact1\ 2}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ 2} using definition
\}\tabularnewline
&
\texttt{if\ 2\ ==\ 0\ then\ 1\ else\ 2\ *\ fact1\ (2-1)}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2\ ==\ 0} in condition
\}\tabularnewline
& \texttt{if\ False\ then\ 1\ else\ 2\ *\ fact1\ (2-1)}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ fact1\ (2-1)}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ (2-1)} using definition,
add implicit parentheses \}\tabularnewline
&
\texttt{2\ *\ (if\ (2-1)\ ==\ 0\ then\ 1\ else\ (2-1)\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2-1} in condition
\}\tabularnewline
&
\texttt{2\ *\ (if\ 1\ ==\ 0\ then\ 1\ else\ (2-1)\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1\ ==\ 0} in condition
\}\tabularnewline
&
\texttt{2\ *\ (if\ False\ then\ 1\ else\ (2-1)\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ ((2-1)\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate leftmost \texttt{2-1}
\}\tabularnewline
& \texttt{2\ *\ (1\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ ((2-1)-1)} using
definition, add implicit parentheses \}\tabularnewline
& \texttt{2\ *\ (1\ *\ (if\ ((2-1)-1)\ ==\ 0\ then\ 1}\tabularnewline
& \texttt{else\ ((2-1)-1)\ *\ fact1\ ((2-1)-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2-1} in condition
\}\tabularnewline
& \texttt{2\ *\ (1\ *\ (if\ (1-1)\ ==\ 0\ then\ 1}\tabularnewline
& \texttt{else\ ((2-1)-1)\ *\ fact1\ ((2-1)-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1-1} in condition
\}\tabularnewline
& \texttt{2\ *\ (1\ *\ (if\ 0\ ==\ 0\ then\ 1}\tabularnewline
& \texttt{else\ ((2-1)-1)\ *\ fact1\ ((2-1)-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{0\ ==\ 0} \}\tabularnewline
& \texttt{2\ *\ (1\ *\ (if\ True\ then\ 1}\tabularnewline
& \texttt{else\ ((2-1)-1)\ *\ fact1\ ((2-1)-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ (1\ *\ 1)}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1\ *\ 1} \}\tabularnewline
& \texttt{2\ *\ 1}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2\ *\ 1} \}\tabularnewline
& \texttt{2}\tabularnewline
\bottomrule
\end{longtable}

The rewriting model we have been using so far can be called \emph{string
reduction} because our model involves the textual replacement of one
string by an equivalent string.

A more efficient alternative is \emph{graph reduction}. In this
technique, the expressions are represented as (directed acyclic)
expression graphs rather than text strings. The repeated subexpressions
of an expression are represented as shared components of the expression
graph. Once a shared component has been evaluated once, it need not be
evaluated again.

In the example above, subexpression \texttt{2-1} is reduced three times.
However, all of those subexpressions come from the initial replacement
of \texttt{fact1\ 2}. Using graph reduction, only the first of those
reductions is necessary.

\begin{longtable}[]{@{}ll@{}}
\toprule
& \texttt{fact1\ 2}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ 2} using definition
\}\tabularnewline
&
\texttt{if\ 2\ ==\ 0\ then\ 1\ else\ 2\ *\ fact1\ (2-1)}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2\ ==\ 0} in condition
\}\tabularnewline
& \texttt{if\ False\ then\ 1\ else\ 2\ *\ fact1\ (2-1)}
\}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ fact1\ (2-1)}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ (2-1)} using definition,
add implicit parentheses \}\tabularnewline
&
\texttt{2\ *\ (if\ (2-1)\ ==\ 0\ then\ 1\ else\ (2-1)\ *\ fact1\ ((2-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2-1} because of condition (3
occurrences in graph) \}\tabularnewline
&
\texttt{2\ *\ (if\ 1\ ==\ 0\ then\ 1\ else\ 1\ *\ fact1\ (1-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1\ ==\ 0} \}\tabularnewline
&
\texttt{2\ *\ (if\ False\ then\ 1\ else\ 1\ *\ fact1\ (1-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ (1\ *\ fact1\ (1-1))}\tabularnewline
\(\Longrightarrow\) & \{ replace \texttt{fact1\ ((1-1)} using
definition, add implicit parentheses \}\tabularnewline
&
\texttt{2\ *\ (1\ *\ (if\ (1-1)\ ==\ 0\ then\ 1\ else\ (1-1)\ *\ fact1\ ((1-1)-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1-1} because of condition (3
occurrences in graph) \}\tabularnewline
&
\texttt{2\ *\ (1\ *\ (if\ 0\ ==\ 0\ then\ 1\ else\ 0\ *\ fact1\ (0-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{0\ ==\ 0} \}\tabularnewline
&
\texttt{2\ *\ (1\ *\ (if\ True\ then\ 1\ else\ \ 0\ *\ fact1\ (0-1))}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{if} \}\tabularnewline
& \texttt{2\ *\ (1\ *\ 1)}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{1\ *\ 1} \}\tabularnewline
& \texttt{2\ *\ 1}\tabularnewline
\(\Longrightarrow\) & \{ evaluate \texttt{2\ *\ 1} \}\tabularnewline
& \texttt{2}\tabularnewline
\bottomrule
\end{longtable}

In general, the Haskell compiler or interpreter uses a leftmost
outermost graph reduction technique. However, if the value of a
function's argument is always needed for a computation, then an
innermost reduction can be triggered for that argument. Either the
programmer can explicitly require this or the compiler can detect the
situation and automatically trigger the innermost reduction order.

Haskell exhibits \emph{lazy evaluation}. That is, an expression is not
evaluated until its value is needed, if ever. An outermost reduction
corresponds to this evaluation strategy.

Other functional languages such as Scala and F\# exhibit \emph{eager
evaluation}. That is, an expression is evaluated as soon as possible. An
innermost reduction corresponds to this evaluation strategy.

\subsubsection{Time and space
complexity}\label{time-and-space-complexity}

We state efficiency (i.e., time complexity or space complexity) of
programs in terms of the ``Big-O'' notation and asymptotic analysis.

For example, consider the leftmost outermost graph reduction of function
\texttt{fact1} above. The number of reduction steps required to evaluate
\texttt{fact1\ n} is \texttt{5n\ +\ 3}.

We let the number of steps in a graph reduction be our measure of time.
Thus, the \emph{time complexity} of \texttt{fact1\ n} is O(\texttt{n}),
which means that the time to evaluate \texttt{fact1\ n} is bounded above
by some (mathematical) function that is proportional to the value of
\texttt{n}.

Of course, this result is easy to see in this case. The algorithm is
dominated by the \texttt{n} multiplications it must carry out.
Alternatively, we see that evaluation requires on the order of
\texttt{n} recursive calls.

We let the number of \emph{arguments} in an expression graph be our
measure of the \emph{size} of an expression. Then the \emph{space
complexity} is the maximum size needed for the evaluation in terms of
the input.

This size measure is an indication of the maximum size of the
unevaluated expression that is held at a particular point in the
evaluation process. This is a bit different from the way we normally
think of space complexity in imperative algorithms, that is, the number
of ``words'' required to store the program's data.

However, this is not as strange as it may at first appear. As we see
later in these notes, the data structures in functional languages like
Haskell are themselves \emph{expressions} built by applying constructors
to simpler data.

In the case of the graph reduction of \texttt{fact1\ n}, the size of the
largest expression is \texttt{2n\ +\ 16}. This is a multiplication for
each integer in the range from 1 to \texttt{n} plus 16 for the full
\texttt{if} statement. Thus the space complexity is O(\texttt{n}).

The Big-O analysis is an asymptotic analysis. That is, it estimates the
order of magnitude of the evaluation time or space as the size of the
input approaches infinity (gets large). We often do worst case analyses
of time and space. Such analyses are usually easier to do than
average-case analyses.

The time complexity of \texttt{fact1\ n} is similar to that of a loop in
an imperative program. However, the space complexity of the imperative
loop algorithm is O(1). So \texttt{fact1} is not space efficient
compared to the imperative loop.

We examine techniques for improving the efficiency of functions below.
Later in these notes, we examine reduction techniques more fully.

\subsubsection{Termination}\label{termination}

A recursive function has one or more recursive cases and one or more
base (nonrecursive) cases. It may also be undefined for some cases.

To show that evaluation of a recursive function terminates, we must show
that each recursive application \emph{always} gets closer to a
termination condition represented by a base case.

Again consider \texttt{fact1} defined above.

If \texttt{fact1} is called with argument \texttt{n} greater than 0, the
argument of the recursive application in the \texttt{else} clause always
decreases to \texttt{n\ -\ 1}. Because the argument always decreases in
integer steps, it must eventually reach 0 and, hence, terminate in the
first leg of the definition.

If we call \texttt{fact1} with argument 0, the function terminates
immediately.

What if we call \texttt{fact1} with its argument less than 0? We
consider this issue below.

\subsubsection{Preconditions and
postconditions}\label{preconditions-and-postconditions}

The \emph{precondition} of a function is what the caller (i.e., the
client of the function) must ensure holds when calling the function. A
precondition may specify the valid combinations of values of the
arguments. It may also record any constraints on the values of
``global'' data structures that the function access or modifies.

If the precondition holds, the supplier (i.e., developer) of the
function must ensure that the function terminates with the
\emph{postcondition} satisfied. That is, the function returns the
required values and/or alters the ``global'' data structures in the
required manner.

Functions \texttt{fact1}, \texttt{fact2}, and \texttt{fact3} require
that argument \texttt{n} be a natural number (nonnegative integer)
value. If they are applied to a negative value for \texttt{n}, then the
evaluation does not terminate. Operationally, they go into an ``infinite
loop'' and likely will terminate when the runtime stack overflows.

If function \texttt{fact4} is called with a negative argument, then all
guards and pattern matches fail. Thus the function aborts with a
standard error message.

Thus to ensure normal termination, we impose the precondition

\begin{verbatim}
    n >= 0
\end{verbatim}

on these factorial functions.

The postcondition of all five factorial functions is that the result
returned is the correct mathematical value of \texttt{n} factorial. For
\texttt{fact4}, that is:

\begin{quote}
\texttt{fact4\ n\ =} \emph{fact'(n)}
\end{quote}

None of the five factorial functions access or modify any global data
structures, so we do not include other items in the precondition or
postcondition.

Function \texttt{fact5} is defined to be 1 for all arguments less than
zero. So, if this is the desired result, we can weaken the precondition
to allow all integer values, for example,

\begin{verbatim}
    True
\end{verbatim}

and strengthen the postcondition to give the results for negative
arguments, for example:

\begin{quote}
\texttt{fact5\ n\ =\ if\ n\ \textgreater{}=\ 0\ then}
\emph{fact'}\texttt{(n)\ else\ 1}
\end{quote}

In the discussion of data abstraction in a previous chapter, we
introduced the concept of \emph{invariant}. In that context, an
invariant is a postcondition of all constructor functions in the public
interface. It is both a precondition and postcondition of all functions
that access or update an ``object''. If there destructor functions that
explicitly release the resources of an an object, the invariant must be
a precondition.

\subsection{Linear and Nonlinear
Recursion}\label{linear-and-nonlinear-recursion}

Given the substitution model, we can now consider efficiency and
termination in the design of recursive Haskell functions.

In this section, we examine the concepts of linear and nonlinear
recursion. The following two sections examine other styles.

The Haskell code for this chapter is in file
\href{code03/EvalEff.hs}{\texttt{EvalEff.hs}}.

\subsubsection{Linear recursion}\label{linear-recursion}

A function definition is \emph{linear recursive} if at most one
recursive application of the function occurs in any leg of the
definition (i.e., along any path from an entry to a return). The various
argument patterns and guards and the branches of the conditional
expression \texttt{if} introduce paths.

The definition of the function \texttt{fact4} repeated below is linear
recursive because the expression in the second leg of the definition
(i.e., \texttt{n\ *\ fact4\ (n-1)}) involves a single recursive
application. The other leg is nonrecursive; it is the base case of the
recursive definition.

\begin{verbatim}
    fact4 :: Int -> Int 
    fact4 n 
        | n == 0 =  1 
        | n >= 1 =  n * fact4 (n-1)
\end{verbatim}

What are the precondition and postcondition for \texttt{fact4\ n}?

As noted above, we must require a precondition of
\texttt{n\ \textgreater{}=\ 0} to avoid abnormal termination. When the
precondition holds, the result is:

\begin{quote}
\texttt{fact4\ n\ =} \emph{fact'(n)}
\end{quote}

What are the time and space complexities of \texttt{fact4\ n}?

Function \texttt{fact4} recurses to a depth of \texttt{n}. As we saw
earlier for \texttt{fact1}, it has \emph{time complexity} O(\texttt{n}),
if we count either the recursive calls or the multiplication at each
level. The \emph{space complexity} is also O(\texttt{n}) because a new
runtime stack frame is needed for each recursive call.

How do we know that function \texttt{fact4\ n} terminates?

For a call \texttt{fact4\ n} with \texttt{n\ \textgreater{}\ 0}, the
argument of the recursive application always decreases to
\texttt{n\ -\ 1}. Because the argument always decreases in integer
steps, it must eventually reach 0 and, hence, terminate in the first leg
of the definition.

\subsubsection{Nonlinear recursion}\label{nonlinear-recursion}

A \emph{nonlinear recursion} is a recursive function in which the
evaluation of some leg requires more than one recursive application. For
example, the naive Fibonacci number function \texttt{fib} shown below
has two recursive applications in its third leg. When we apply this
function to a nonnegative integer argument greater than 1, we generate a
pattern of recursive applications that has the ``shape'' of a binary
tree. Some call this a \emph{tree recursion}.

\begin{verbatim}
    fib :: Int -> Int
    fib 0          = 0
    fib 1          = 1 
    fib n | n >= 2 = fib (n-1) + fib (n-2)
\end{verbatim}

What are the precondition and postcondition for \texttt{fib\ n}?

For \texttt{fib\ n}, the precondition \texttt{n\ \textgreater{}=\ 0} to
ensure that the function is defined. When called with the precondition
satisfied, the postcondition is:

\begin{quote}
\texttt{fib\ n} \emph{= Fibonacci}\texttt{(n)}
\end{quote}

How do we know that \texttt{fib\ n} terminates?

For the recursive case \texttt{n\ \textgreater{}=\ 2}. the two recursive
calls have arguments that are 1 or 2 less than \texttt{n}. Thus every
call gets closer to one of the two base cases.

What are the time and space complexities of \texttt{fib\ n}?

Function \texttt{fib} is combinatorially explosive, having a time
complexity O(\texttt{fib\ n}). The space complexity is O(\texttt{n})
because a new runtime stack frame is needed for each recursive call and
the calls recurse to a depth of \texttt{n}.

An advantage of a linear recursion over a nonlinear one is that a linear
recursion can be compiled into a \emph{loop} in a straightforward
manner. Converting a nonlinear recursion to a loop is, in general,
difficult.

\subsection{Backward and Forward
Recursion}\label{backward-and-forward-recursion}

In this section, we examine the concepts of backward and forward
recursion.

\subsubsection{Backward recursion}\label{backward-recursion}

A function definition is \emph{backward recursive} if the recursive
application is embedded within another expression. During execution, the
program must complete the evaluation of the expression after the
recursive call returns. Thus, the program must preserve sufficient
information from the outer call's environment to complete the
evaluation.

The definition for the function \texttt{fact4} above is backward
recursive because the recursive application \texttt{fact4\ (n-1)} in the
second leg is \emph{embedded within the expression}
\texttt{n\ *\ fact4\ (n-1)}. During execution, the multiplication must
be done after return. The program must ``remember'' (at least) the value
of parameter \texttt{n} for that call.

A compiler can translate a backward linear recursion into a loop, but
the translation may require the use of a stack to store the program's
\emph{state} (i.e., the values of the variables and execution location)
needed to complete the evaluation of the expression.

Often when we design an algorithm, the first functions we come up with
are backward recursive. They often correspond directly to a convenient
recurrence relation. It is often useful to convert the function into an
equivalent one that evaluates more efficiently.

\subsubsection{Forward recursion}\label{forward-recursion}

A function definition is \emph{forward recursive} if the recursive
application is \emph{not embedded within another expression}. That is,
the \emph{outermost expression is the recursive application} and any
other subexpressions appear in the argument lists. During execution,
significant work is done as the recursive calls are made (e.g., in the
argument list of the recursive call).

The definition for the auxiliary function \texttt{factIter} below has
two integer arguments. The first argument is the number whose factorial
is to be computed. The second argument accumulates the product
incrementally as recursive calls are made.

The recursive application \texttt{factIter\ (n-1)\ (n*r)} in the second
leg is on the outside of the expression evaluated for return. The other
leg of \texttt{factIter} and \texttt{fact6} itself are nonrecursive.

\begin{verbatim}
    fact6 :: Int -> Int
    fact6 n = factIter n 1

    factIter :: Int -> Int -> Int
    factIter 0 r         = r
    factIter n r | n > 0 = factIter (n-1) (n*r)
 
\end{verbatim}

What are the precondition and postcondition for \texttt{factIter\ n\ r}?

To avoid termination, \texttt{factIter\ n\ r} requires
\texttt{n\ \textgreater{}=\ 0}. Its postcondition is that:

\begin{quote}
\texttt{factIter\ n\ r\ =\ r\ *} \emph{fact}\texttt{(n)}
\end{quote}

How do we know that \texttt{factIter\ n\ r} terminates?

Argument \texttt{n} of the recursive leg is at least 1 and decreases by
1 on each recursive call.

What is the time and space complexity of \texttt{factIter\ n\ r}?

Function \texttt{factIter\ n\ r} has a time complexity O(\texttt{n}).
But, if the compiler converts the \texttt{factIter} recursion to a loop,
the time complexity's constant factor should be smaller than that of
\texttt{fact4}.

As shown, \texttt{factIter\ n\ r} has space complexity of O(\texttt{n}).
But, if the compiler does an innermost reduction on the second argument
(because its value will always be needed), then the space complexity of
\texttt{factIter} becomes O(1).

\subsubsection{Tail recursion}\label{tail-recursion}

A function definition is \emph{tail recursive} if it is \emph{both
forward recursive and linear recursive}. In a tail recursion, the last
action performed before the return is a recursive call.

The definition of the function \texttt{factIter} above is thus tail
recursive.

Tail recursive definitions are relatively straightforward to compile
into efficient loops. There is no need to save the states of unevaluated
expressions for higher level calls; the result of a recursive call can
be returned directly as the caller's result. This is sometimes called
\emph{tail call optimization} (or ``tail call elimination'' or ``proper
tail calls'').

In converting the backward recursive function \texttt{fact4} to a tail
recursive auxiliary function, we added the parameter \texttt{r} to
\texttt{factIter}. This parameter is sometimes called an
\emph{accumulating parameter} (or just an \emph{accumulator}).

We typically use an accumulating parameter to ``accumulate'' the result
of the computation incrementally for return when the recursion
terminates. In \texttt{factIter}, this ``state'' passed from one
``iteration'' to the next enables us to convert a backward recursive
function to an ``equivalent'' tail recursive one.

Function \texttt{factIter} defines a more general function than
\texttt{fact4}. It computes a factorial when we initialize the
accumulator to 1, but it can compute some multiple of the factorial if
we initialize the accumulator to another value. However, the application
of \texttt{factIter} in \texttt{fact6} gives the initial value of 1
needed for factorial.

Consider auxiliary function \texttt{fibIter} used by function
\texttt{fib2} below. This function adds two ``accumulating parameters''
to the backward nonlinear recursive function \texttt{fib} to convert the
nonlinear (tree) recursion into a tail recursion. This technique works
for Fibonacci numbers, but the same technique will not work in all
cases.

\begin{verbatim}
    fib2 :: Int -> Int
    fib2 n | n >= 0 = fibIter n 0 1 
        where 
            fibIter 0 p q         = p
            fibIter m p q | m > 0 = fibIter (m-1) q (p+q)
\end{verbatim}

Here we use \emph{type inference} for \texttt{fibIter}. Function
\texttt{fibIter} could be declared

\begin{verbatim}
    fibIter :: Int -> Int -> Int -> Int 
\end{verbatim}

but it was not necessary because Haskell can infer the type from the
types involved in its defining expressions.

What are the precondition and postcondition for
\texttt{fibIter\ n\ p\ q}?

To avoid termination, \texttt{fibIter\ n\ p\ q} requires
\texttt{n\ \textgreater{}=\ 0}. When the precondition holds, its
postcondition is:

\begin{quote}
\texttt{fibIter\ n\ p\ q\ =}
\emph{Fibonacci}\texttt{(n)\ +\ (p\ +\ q\ -\ 1)}
\end{quote}

If called with \texttt{p} and \texttt{q} set to 0 and 1, respectively,
then \texttt{fibIter} returns:

\begin{quote}
\emph{Fibonacci}\texttt{(n)}
\end{quote}

How do we know that \texttt{fibIter\ n\ p\ q} terminates?

The recursive leg of \texttt{fibIter\ n\ p\ q} is only evaluated when
\texttt{n\ \textgreater{}\ 0}. On the recursive call, that argument
decreases by 1. So eventually the computation reaches the base case.

What are the time and space complexities of \texttt{fibIter}?

Function \texttt{fibIter} has a time complexity of O(\texttt{n}) in
contrast to O(\texttt{fib(n)}) for \texttt{fib}. This algorithmic
speedup results from the replacement of the very expensive operation
\texttt{fib(n-1)\ +\ fib(n-2)} at each level in \texttt{fib} by the
inexpensive operation \texttt{p\ +\ q} (i.e., addition of two numbers)
in \texttt{fibIter}.

Without tail call optimization, \texttt{fibIter\ n\ p\ q} has space
complexity of O(\texttt{n}). However, tail call optimization (including
an innermost reduction on the \texttt{q} argument) can convert the
recursion to a loop, giving O(1) space complexity.

When combined with tail-call optimization and innermost reduction of
strict arguments, a tail recursive function may be more efficient than
the equivalent backward recursive function. However, the backward
recursive function is often easier to understand and, as we see in a
later chapter, to reason about.

\subsection{Logarithmic Recursion}\label{logarithmic-recursion}

We can define the exponentiation operation \texttt{\^{}} in terms of
multiplication as follows for integers \texttt{b} and
\texttt{n\ \textgreater{}=\ 0}:

\begin{quote}
\texttt{b\^{}n\ =} \(\prod_{i=1}^{i=n} b\)
\end{quote}

In this subsection, we develop Haskell functions for exponentiation, but
we also briefly examine how to code similar recursive functions in other
programming languages.

\subsubsection{Haskell}\label{haskell}

A backward recursive exponentiation function \texttt{expt}, shown below
in Haskell, raises a number to a nonnegative integer power.

\begin{verbatim}
    expt :: Integer -> Integer -> Integer
    expt b 0        = 1
    expt b n 
        | n > 0     = b * expt b (n-1)  -- backward rec
        | otherwise = error (
                        "expt not defined for negative exponent " 
                        ++ show n )
\end{verbatim}

Here we use the unbounded integer type \texttt{Integer} for the
parameters and return value.

Note that the recursive call of \texttt{expt} does not change the value
of the parameter \texttt{b}.

Consider the following questions relative to \texttt{expt}.

\begin{itemize}
\item
  What are the precondition and postcondition for \texttt{expt\ b\ n}?
\item
  How do we know that \texttt{expt\ b\ n} terminates?
\item
  What are the time and space complexities of \texttt{expt\ b\ n}
  (ignoring any additional costs of processing the unbounded integer
  type)?
\end{itemize}

We can define a tail recursive auxiliary function \texttt{exptIter} by
adding a new parameter to accumulate the value of the exponentiation
incrementally. We can define \texttt{exptIter} within a function
\texttt{expt2}, taking advantage of the fact that the base \texttt{b}
does not change. This is shown below.

\begin{verbatim}
    expt2 :: Integer -> Integer -> Integer
    expt2 b n | n < 0 = error (
                          "expt2 not defined for negative exponent
    " 
                          ++ show n )
    expt2 b n         = exptIter n 1
        where exptIter 0 p = p
              exptIter m p = exptIter (m-1) (b*p) -- tail rec
\end{verbatim}

Consider the following questions relative to \texttt{expt2}.

\begin{itemize}
\item
  What are the precondition and postcondition for
  \texttt{exptIter\ n\ p}?
\item
  How do we know that \texttt{exptIter\ n\ p} terminates?
\item
  What are the time and space complexities of \texttt{exptIter\ n\ p}?
\end{itemize}

The exponentiation function can be made computationally more efficient
by squaring the intermediate values instead of iteratively multiplying.
We observe that:

\begin{verbatim}
    b^n = b^(n/2)^2   if n is even
    b^n = b * b^(n-1) if n is odd
\end{verbatim}

Function \texttt{expt3} below incorporates this observation into an
improved algorithm. Its time complexity is O(\texttt{log(n)}) and space
complexity is O(\texttt{log(n)}).

\begin{verbatim}
    expt3 :: Integer -> Integer -> Integer
    expt3 _ n | n < 0 = error (
                        "expt3 not defined for negative exponent "
                        ++ show n )
    expt3 b n         = exptAux n
        where exptAux 0 = 1
              exptAux n
                | even n    = let exp = exptAux (n `div` 2) in 
                                  exp * exp      -- backward rec
                | otherwise = b * exptAux (n-1)  -- backward rec
\end{verbatim}

Here we are use two features of Haskell we have not used in the previous
examples.

\begin{itemize}
\item
  Boolean function \texttt{even} returns \texttt{True} if and only if
  its integer argument is an even number. Similarly, \texttt{odd}
  returns \texttt{True} when its argument is an odd number.
\item
  The \texttt{let} clause introduces \texttt{exp} as a local definition
  within the expression following \texttt{in} keyword, that is, within
  \texttt{exp\ *\ exp}.

  The \texttt{let} feature allows us to introduce new definitions in a
  bottom-up manner--first defining a symbol and then using it.
\end{itemize}

Consider the following questions relative to \texttt{expt3}.

\begin{itemize}
\item
  What are the precondition and postcondition \texttt{expt3\ b\ n}?
\item
  How do we know that \texttt{exptAux\ n} terminates?
\item
  What are the time and space complexities of \texttt{exptAux\ n}?
\end{itemize}

We express the functions in this chapter in Haskell, but they are
adapted from the classic textbook \emph{Structure and Interpretation of
Computer Programs} (SICP) by Abelman and Sussman, which used Scheme.

Now let's look at what the \texttt{expt3} function looks like in Scheme
and other languages.

\subsubsection{Scheme}\label{scheme}

Below is the Scheme language program for exponentiation similar to to
\texttt{expt3} (called \texttt{fast-expt} in SICP). Scheme, a dialect of
Lisp, is an impure, eagerly evaluated functional language with dynamic
typing.

\begin{verbatim}
    (define (expt3 b n)
      (cond 
        ((< n 0) (error `expt3 "Called with negative exponent"))
        (else (expt_aux b n))))

    (define (expt_aux b n)
      (cond 
        ((= n 0) 1)
        ((even? n) (square (expt3 b (/ n 2))))
        (else (* b (expt3 b (- n 1))))))
            
    (define (square x) (* x x))
     
    (define (even? n) (= (remainder n 2) 0))
\end{verbatim}

Scheme (and Lisp) represents both data and programs as s-expressions
(nested list structures) enclosed in balanced parentheses. In the case
of executable expressions, the first element of the list may be
operator. For example, consider:

\begin{verbatim}
    (define (square x) (* x x))
\end{verbatim}

The \texttt{define} operator takes two arguments:

\begin{itemize}
\item
  a symbol being defined, in this case a function signature
  \texttt{(square\ x)} for a function named \texttt{square} with one
  formal parameter named \texttt{x}
\item
  an expression defining the value of the symbol, in this case the
  expression \texttt{(*\ x\ x)} that multiplies formal parameter
  \texttt{x} by itself and returns the result
\end{itemize}

The \texttt{define} operator has the side effect of adding the
definition of the symbol to the environment. That is, \texttt{square} is
introduced as a one argument function with the value denoted by the
expression \texttt{(*\ x\ x)}.

The conditional expression \texttt{cond} gives an if-then-elseif
expression that evaluates a sequence of predicates until one evaluates
to ``true'' value and then returns the paired expression. The
\texttt{else} at the end always evaluates to ``true''.

The above Scheme code defines the functions \texttt{square}, the
exponentiation function \texttt{expt3}, and the logical predicate
\texttt{even?}. It uses the primitive Scheme functions \texttt{-},
\texttt{*}, \texttt{/}, \texttt{remainder}, and \texttt{=} (equality).

We can evaluate the Scheme expression \texttt{(expt\ 2\ 10)} using a
Scheme interpreter (as I did using DrRacket) and get the value
\texttt{1024}.

Although Haskell and Scheme are different in many ways -- algebraic
versus s-expression syntax, static versus dynamic typing, lazy versus
eager evaluation (by default), always pure versus sometimes impure
functions, etc. -- the fundamental techniques we have examined in
Haskell still apply to Scheme and other languages. We can use a
substitution model, consider preconditions and termination, use tail
recursion, and take advantage of first-class and higher-order functions.

Of course, each language offers a unique combination of features that
can be exploited in our programs. For example, Scheme programmers can
leverage its runtime flexibility and powerful macro system; Haskell
programmers can build on its safe type system, algebraic data types,
pattern matching, and other features.

Let's now consider other languages.

The Racket Scheme code for this subsection is in file
\href{code03/expt3.rkt}{\texttt{expt3.rkt}}.

\subsubsection{Elixir}\label{elixir}

The language Elixir is a relatively new language that executes on the
Erlang platform (called the Erlang Virtual Machine or BEAM). Elixir is
an eagerly evaluated functional language with strong support for
message-passing concurrent programming. It is dynamically typed and is
mostly pure except for input/output. It has pattern-matching features
similar to Haskell.

We can render the \texttt{expt3} program into a sequential Elixir
program as follows.

\begin{verbatim}
    def expt3(b,n) when is_number(b) and is_integer(n)
                        and n >= 0 do
      exptAux(b,n)
    end

    defp exptAux(_,0) do 1 end

    defp exptAux(b,n) do
      if rem(n,2) == 0  do  #  i.e. even
        exp = exptAux(b,div(n,2))
        exp * exp           #  backward rec
      else                  #  i.e. odd
        b * exptAux(b,n-1)  #  backward rec
      end
    end
\end{verbatim}

This code occurs within an Elixir module. The \texttt{def} statement
defines a function that is exported from the module while \texttt{defp}
defines a function that is private to the module (i.e., not exported).

A definition allows the addition of guard clauses following
\texttt{when} (although they cannot include user-defined function calls
because of restrictions of the Erlang VM). In function \texttt{expt3},
we use guards to do some type checking in this dynamically typed
language and to ensure that the exponent is nonnegative.

Private function \texttt{exptAux} has two functions bodies. As in
Haskell, the body is selected using pattern matching proceeding from top
to bottom in the module. The first function body with the header
\texttt{exptAux(\_,0)} matches all cases in which the second argument is
\texttt{0}. All other situations match the second header
\texttt{exptAux(b,n)} binding parameters \texttt{b} and \texttt{n} to
the argument values.

The functions \texttt{div} and \texttt{rem} denote integer division and
remainder, respectively.

The Elixir \texttt{=} operator is not an assignment as in imperative
languages. It is a pattern-match statement with an effect similar to
\texttt{let} in the Haskell function.

Above the expression \texttt{exp\ =\ exptAux(b,div(n,2))} evaluates the
recursive call and then binds the result to new local variable named
\texttt{exp}. This value is used in the next statement to compute the
return value \texttt{exp\ *\ exp}.

Again, although there are significant differences between Haskell and
Elixir, the basic thinking and programming styles learned for Haskell
are also useful in Elixir (or Erlang). These styles are also key to use
of their concurrent programming features.

The Elixir code for this subsection is in file
\href{code03/expt.ex}{\texttt{expt.ex}}.

\subsubsection{Scala}\label{scala}

The language Scala is a hybrid functional/object-oriented language that
executes on the Java platform (i.e., on the Java Virtual Machine or
JVM). Scala is an eagerly evaluated language. It allows functions to be
written in a mostly pure manner, but it allows intermixing of
functional, imperative, and object-oriented features. It has a
relatively complex static type system similar to Java, but it supports
type inference (although weaker than that of Haskell). It interoperates
with Java and other languages on the JVM.

We can render the exponentiation function \texttt{expt3} into a
functional Scala program as shown below. This uses the Java/Scala
extended integer type \texttt{BigInt} for the base and return values.

\begin{verbatim}
    def expt3(b: BigInt, n: Int): BigInt = {

      def exptAux(n1: Int): BigInt = // b known from outer
        n1 match {
          case 0                 => 1
          case m if (m % 2 == 0) =>  // i.e. even
            val exp = exptAux(m/2)
            exp * exp                // backward rec
          case m                 =>  // i.e. odd
            b * exptAux(m-1)         // backward rec
        }

      if (n >= 0)
        exptAux(n)
      else
        sys.error ("Cannot raise to negative power " + n )
    }
\end{verbatim}

The body of function \texttt{expt3} uses an \texttt{if-else} expression
to ensure that the exponent is non-negative and then calls
\texttt{exptAux} to do the work.

Function \texttt{expt3} encloses auxiliary function \texttt{exptAux}.
For the latter, the parameters of \texttt{expt3} are in scope. For
example, \texttt{exptAux} uses \texttt{b} from \texttt{expt3} as a
constant.

Scala supports pattern matching using an explicit \texttt{match}
operator in the form:

\begin{quote}
\emph{selector} \texttt{match\ \{} \emph{alternatives} \texttt{\}}
\end{quote}

It evaluates the \emph{selector} expression and then choses the first
\emph{alternative} pattern that matches this value, proceedings top to
botton, left to right. We write the alternative as

\begin{quote}
\texttt{case} \emph{pattern} \texttt{=\textgreater{}} \emph{expression}
\end{quote}

or with a guard as:

\begin{quote}
\texttt{case} \emph{pattern} \texttt{if} \emph{boolean\_expression}
\texttt{=\textgreater{}} \emph{expression}
\end{quote}

The \emph{expression} may be a sequence of expressions. The value
returned is the value of the last expression evaluated.

In this example, the \texttt{match} in \texttt{exptAux} could easily be
replaced by an \texttt{if} - \texttt{else\ if} - \texttt{else}
expression because it does not depend upon complex pattern matching.

In Haskell, functions are automatically curried. In Scala, we could
alternatively define \texttt{expt3} in curried form using two argument
lists as follows:

\begin{verbatim}
    def expt3(b: BigInt)(n: Int): BigInt = ...
\end{verbatim}

Again, we can use most of the functional programming methods we learn
for Haskell in Scala. Scala has a few advantages over Haskell such as
the ability to program in a multiparadigm style and interoperate with
Java. However, Scala tends to be more complex and verbose than Haskell.
Some features such as type inference and tail recursion are limited by
Scala's need to operate on the JVM.

The Scala code for this subsection is in file
\href{code03/exptBigInt2.scala}{\texttt{exptBigInt2.scala}}.

\subsubsection{Lua}\label{lua}

Lua is a minimalistic, dynamically typed, imperative language designed
to be embedded as a scripting language in other programs, such as
computer games. It interoperates well with standard C and C++ programs.

We can render the exponentiation function \texttt{expt3} into a
functional Lua program as shown below.

\begin{verbatim}
    local function expt3(b,n)

      local function expt_aux(n)   -- b known from outer
        if n == 0 then
          return 1
        elseif n % 2 == 0 then     -- i.e. even
          local exp = expt_aux(n/2)
          return exp * exp         -- backward recursion
        else                       -- i.e. odd
          return b * expt_aux(n-1) -- backward recursion
        end
      end

      if type(b) == "number" and type(n) == "number" and n >= 0 and 
          n == math.floor(n) then
        return expt_aux(n,1)
      else
        error("Invalid arguments to expt: " .. 
              tostring(b) .. "^" .. tostring(n))
      end
    end
\end{verbatim}

Like the Scala version, we define the auxiliary function
\texttt{expt\_aux} inside of function \texttt{expt3}, limiting its scope
to the outer function.

This function uses with Lua version 5.2. In this and earlier versions,
the only numbers are IEEE standard floating point. As in the Elixir
version, we make sure the arguments are numbers with the exponent
argument being nonnegative. Given that the numbers are floating point,
the function also ensures that the exponent is an integer.

Auxiliary function \texttt{expt\_aux} does the computational work. It
differentiates among the three cases using an \texttt{if} -
\texttt{elseif} - \texttt{else} structure. Lua does not have a switch
statement or pattern matching capability.

Lua is not normally considered a functional language, but it has a
number of features that support functional programming -- in particular,
first-class and higher order functions and tail call optimization.

In many ways, Lua is semantically similar to Scheme, but instead of
having the Lisp-like hierarchical list as its central data structure,
Lua provides an efficient, mutable, associative data structure called a
table (somewhat like a hash table or map in other languages). Lua does
not support Scheme-style macros in the standard language.

Unlike Haskell, Elixir, and Scala, Lua does not have builtin immutable
data structures or pattern matching. Lua programs tend to be relatively
verbose. So some of the usual programming idioms from functional
languages do not fit Lua well.

The Lua code for this subsection is in file
\href{code03/expt.lua}{\texttt{expt.lua}}.

\subsubsection{Elm}\label{elm}

Elm is a new functional language intended primarily for client-side Web
programming. It is currently compiled into JavaScript, so some aspects
are limited by the target execution environment. For example, Elm's
basic types are those of JavaScript. So integers are actually
implemented as floating point numbers.

Elm has a syntax and semantics that is similar to, but simpler than,
Haskell. It has a Haskell-like \texttt{let} construct for local
definitions but not a \texttt{where} construct. It also limits pattern
matching to structured types.

Below is an Elm implementation of an exponentiation function similar to
the Haskell \texttt{expt3} function, except it is limited to the
standard integers \texttt{Int}. Operator \texttt{//} denotes the integer
division operation and \texttt{\%} is remainder operator.

\begin{verbatim}
    expt3 : Int -> Int -> Int
    expt3 b n =
        let
            exptAux m =
                if m == 0 then
                    1
                else if m % 2 == 0 then 
                    let
                        exp = exptAux (m // 2)
                    in
                        exp * exp  -- backward rec
                else 
                    b  * exptAux (m-1)  -- backward rec
        in
            if n < 0 then
                0 -- error?
            else
                exptAux n
\end{verbatim}

One semantic difference between Elm and Haskell is that Elm functions
must be total--that is, return a result for every possible input. Thus,
this simple function extends the definition of \texttt{expt3} to return
0 for a negative power. An alternative would be to have \texttt{expt3}
return a \texttt{Maybe\ Int} type instead of \texttt{Int}. We will
examine this feature in Haskell later.

The Elm code for this subsection is in file
\href{code03/expt.elm}{\texttt{expt.elm}}.

\subsection{Conclusion}\label{conclusion}

As we have seen in this chapter, we can develop efficient programs using
functional programming and the Haskell language. These may require use
to think about problems and programming a bit differently than we might
in an imperative or object-oriented language. However, the techniques we
learn for Haskell are usually applicable whenever we use the functional
paradigm in any language. The functional way of thinking can also
improve our programming in more traditional imperative and
object-oriented languages.

\subsection{Exercises}\label{exercises}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Show the reduction of the expression \texttt{fib\ 4} using the
  substitution model.
\item
  Show the reduction of the expression \texttt{expt\ 4\ 3} using the
  substitution model.
\item
  Answer the questions (precondition, postcondition, termination, time
  complexity, space complexity) in the subsection about \texttt{expt}.
\item
  Answer the questions in the subsection about \texttt{exptAux}
\item
  Answer the questions in the subsection about \texttt{expt}.
\item
  Develop a recursive function in Java, C\#, Python, or C++ that has the
  same functionality as \texttt{expt3}.
\end{enumerate}

For each of the following exercises, develop a Haskell program. For each
function, informally argue that it terminates and give Big-O time and
space complexities. Also identify any preconditions necessary to
guarantee correct operation. Take care that special cases and error
conditions are handled in a reasonable way.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\setcounter{enumi}{6}
\item
  Develop a backward recursive function \texttt{sumTo} such that
  \texttt{sumTo\ n} computes the sum of the integers from 1 to
  \texttt{n} for \texttt{n\ \textgreater{}=\ 0}.
\item
  Develop a tail recursive function \texttt{sumTo\textquotesingle{}}
  such that \texttt{sumTo\textquotesingle{}\ n} computes the sum of the
  integers from 1 to \texttt{n} for \texttt{n\ \textgreater{}=\ 0}.
\item
  Develop a backward recursive function \texttt{sumFromTo} such that
  \texttt{sumFromTo\ m\ n} computs the sum of the integers from
  \texttt{m} to \texttt{n} for \texttt{m\ \textless{}=\ n}.
\item
  Develop a tail recursive function \texttt{sumFromTo\textquotesingle{}}
  such that \texttt{sumFromTo\textquotesingle{}\ m\ n} computes the sum
  of the integers from \texttt{m} to \texttt{n} for
  \texttt{m\ \textless{}=\ n}.
\item
  Suppose we have functions \texttt{succ} (successor) and \texttt{pred}
  (predecessor) defined as follows:

\begin{verbatim}
succ, pred :: Int -> Int
succ n = n + 1
pred n = n - 1
\end{verbatim}

  Develop a function \texttt{add} such that \texttt{add\ m\ n} computes
  \texttt{m\ +\ n}. Function \texttt{add} cannot use the integer
  addition or subtraction operations but can use the \texttt{succ} ad
  \texttt{pred} functions above.
\item
  Develop a function \texttt{acker} to compute Ackermann's function,
  which is function \(A\) defined as follows:

  \begin{longtable}[]{@{}llll@{}}
  \toprule
  \(A(m,n)\) & \(=\) & \(n+1,\) & if \(m = 0\)\tabularnewline
  \(A(m,n)\) & \(=\) & \(A(m-1,1),\) & if \(m > 0\) and
  \(n = 0\)\tabularnewline
  \(A(m,n)\) & \(=\) & \(A(m-1,A(m,m-1)),\) & if \(m > 0\) and
  \(n > 0\)\tabularnewline
  \bottomrule
  \end{longtable}
\item
  Develop a function \texttt{hailstone} to implement the following
  function:

  \begin{longtable}[]{@{}llll@{}}
  \toprule
  \(hailstone(n)\) & \(=\) & \(1\), & if \(n = 1\)\tabularnewline
  \(hailstone(n)\) & \(=\) & \(hailstone(n/2)\), & if \(n > 1\), even
  \(n\)\tabularnewline
  \(hailstone(n)\) & \(=\) & \(hailstone(3*n+1)\), & if \(n > 1\), odd
  \(n\)\tabularnewline
  \bottomrule
  \end{longtable}

  Note that an application of the \texttt{hailstone} function to the
  argument \texttt{3} would result in the following ``sequence'' of
  ``calls'' and would ultimately return the result \texttt{1}.

\begin{verbatim}
hailstone 3
  hailstone 10
    hailstone 5
      hailstone 16
        hailstone 8
          hailstone 4
            hailstone 2
              hailstone 1
\end{verbatim}

  For further thought: What is the domain of the \emph{hailstone}
  function?
\item
  Develop the exponentiation function \texttt{expt4} that is similar to
  \texttt{expt3} but is tail recursive.
\item
  Develop the following group of functions.

  \begin{itemize}
  \item
    \texttt{test} such that \texttt{test\ a\ b\ c} is \texttt{True} if
    and only if \texttt{a\ \textless{}=\ b} and no integer is the range
    from \texttt{a} to \texttt{b} inclusive is divisible by \texttt{c}.
  \item
    \texttt{prime} such that \texttt{prime\ n} is \texttt{True} if and
    only if \texttt{n} is a prime integer.
  \item
    \texttt{nextPrime} such that \texttt{nextPrime\ n} returns the next
    prime integer greater than \texttt{n}
  \end{itemize}
\item
  Develop function \texttt{binom} to compute \emph{binomial
  coefficients}. That is, \texttt{binom\ n\ k} returns \(\binom{n}{k}\)
  for integers \texttt{n\ \textgreater{}=\ 0} and
  \texttt{0\ \textless{}=\ k\ \textless{}=\ n}.
\end{enumerate}

TODO: Add more exercises for the techniques and features introduced in
this section.

\subsection{References}\label{references}

\begin{description}
\tightlist
\item[{[}Abelson-Sussman 1996{]}]
Harold Abelson and Gerald Jay Sussman. \emph{Structure and
Interpretation of Computer Programs}
(\href{http://mitpress.mit.edu/sicp/}{SICP}), Second Edition, MIT Press,
1996.
\item[{[}Bird-Wadler 1998{]}]
Richard Bird and Philip Wadler. \emph{Introduction to Functional
Programming}, Second Edition, Addison Wesley, 1998.
{[}\href{https://usi-pl.github.io/lc/sp-2015/doc/Bird_Wadler.\%20Introduction\%20to\%20Functional\%20Programming.1ed.pdf}{First
Edition, 1988}{]}
\item[{[}Cunningham 2014{]}]
H. Conrad Cunningham.
\href{https://john.cs.olemiss.edu/~hcc/csci450/notes/haskell_notes.pdf}{\emph{Notes
on Functional Programming with Haskell}}, 1994-2014.
\item[{[}Thompson 2011{]}]
Simon Thompon. \emph{Haskell: The Craft of Programming, Third Edition},
Pearson, 2011.
\end{description}

\subsection{Terms and Concepts}\label{terms-and-concepts}

Referential transparency, redex, reduction strategies (leftmost
vs.~rightmost, innermost vs.~outermost), string and graph reduction
models, time and space complexity, termination. preconditions,
postconditions, recursion styles (linear vs.~nonlinear, backward
vs.~forward, tail, and logarithmic), correctness (precondition,
postcondition, and termination), efficiency estimation (time and space
complexity), transformations to improve efficiency (auxiliary function,
accumulator)

\end{document}
