\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 Fundamental Concepts},
            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\\
Fundamental Concepts}
\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 much of this work in
Summer and Fall 2016 from my previous materials.

\begin{itemize}
\item
  Evolving Computer Hardware Affects Programming Languages from my notes
  \emph{Effect of Computing Hardware Evolution on Programming
  Languages}, which were based on a set of unscripted remarks I made in
  the Fall 2014 offering of CSci 450, Organization of Programming
  Languages
\item
  Primary Programming Paradigms from chapter 1 of my \emph{Notes on
  Functional Programming with Haskell}, which I wrote originally in the
  mid-1990s for the Gofer dialect of Haskell but later updated to the
  1998 and 2010 Haskell standards
\item
  Object-Oriented programming paradigm from my notes \emph{Introduction
  to Object Orientation}, which I wrote originally for the first UM
  Java-based class (CSci 211) in 1996 but expanded and adapted for other
  courses.
\item
  History of Programming Languages from my notes \emph{History of
  Programming Languages}, which were based on a set of unscripted
  remarks I made in the Fall 2014 offering of CSci 450, Organization of
  Programming Languages. Those remarks drew on the following:

  \begin{itemize}
  \tightlist
  \item
    \href{http://www.oreillynet.com/pub/a/oreilly/news/languageposter_0504.html}{O'Reilly
    History of Programming Languages poster}
  \item
    Wikipedia article
    \href{http://en.wikipedia.org/wiki/History_of_programming_languages}{History
    of Programming Languages}
  \end{itemize}
\item
  Abstraction from my notes on \emph{Data Abstraction}, which were
  originally written for the first UM Java-based course (CSci 211) in
  1996 but expanded and adapted for subsequent courses and languages
\item
  Motivating Functional Programming from chapter 1 of my \emph{Notes on
  Functional Programming with Haskell}
\item
  Review of Relevant Mathematics from chapter 2 of my \emph{Notes on
  Functional Programming with Haskell}
\end{itemize}

In 2017, I continued 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
  Reorganize to make the chapter more cohesive and coherent.
\item
  Elaborate descriptions of ``other paradigms'' (procedural, modular,
  prototype-based), perhaps adding others (language-oriented,
  concurrent, parallel). Give simple examples for these.
\item
  Focus the object orientation more appropriately a Haskell functional
  programming course.
\item
  Better integrate the discussion of abstraction.
\item
  Expand the discussion of relevant mathematics to conver additional
  mathematical and logical concepts needed in these notes such as those
  used in specification of preconditions, postconditions, invariants,
  and abstract data types.
\item
  Add exercises.
\item
  Update references, terms and concepts
\end{itemize}

\setcounter{section}{0}

\section{Fundamental Concepts}\label{fundamental-concepts}

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

The goal of this chapter is motivate the concept of functional
programming and relate it to other approaches to programming and to the
relevant mathematical concepts.

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

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  describe the evolution of computers and programming languages since
  the 1940's and its impact upon contemporary programming language
  design and implementation
\item
  distinguish among the primary programming paradigms, in particular to
  be able to relate functional programming to their previous knowledge
  of imperative programming
\item
  describe other programming paradigms (such as object-oriented and
  prototype-based) and relate these to the primary paradigms and their
  previous programming experiences
\item
  understand the abstraction and mathematical concepts that underlie the
  functional programming paradigm
\end{enumerate}

Students entering this course should already have sufficient familiarity
with the relevant mathematical concepts from the prerequisite courses.
However, they may need to relate the mathematics with the programming
constructs in functional programming.

Before we look at Haskell programming, let's consider the development of
programming languages over the past 70 years, examine the primary
programming programming paradigms, consider key concepts, and review the
related mathematical concepts.

\subsection{Evolving Computer Hardware Affects Programming
Languages}\label{evolving-computer-hardware-affects-programming-languages}

To put our study in perspective, let's examine the effect of computing
hardware evolution on programming languages by considering a series of
questions.

\emph{When were the first ``modern'' computers developed? That is,
programmable electronic computers.}

Although the mathematical roots of computing go back more than a
thousand years, it is only with the invention of the programmable
electronic digital computer during the World War II era of the 1930s and
1940s that modern computing began to take shape.

One of the first computers was the ENIAC (Electronic Numerical
Integrator and Computer), developed in the mid-1940s at the University
of Pennsylvania. When construction was completed in 1946, the ENIAC cost
about \$500,000. In today's terms, that is nearly \$7,000,000.

It weighed 30 tons, occupied as much space as a small house, and
consumed 160 kilowatts of electric power.

Initially, the ENIAC had no main memory. Instead it had 20 accumulators,
each 10 decimal digits wide. Later 100 \emph{words} of core were added.

Similarly, it had no external memory as we now it today. It could read
and write stacks of punch cards.

The ENIAC was not a stored program computer. It was programmed mostly by
connecting cables in plugboards. It took several days of careful work to
enter one program. The program was only changed every few weeks.

Aside: Many of the early programmers were women. This is quite a
contrast to contemporary programming teams that are mostly male. What
happened?

The ENIAC and most other computers of that era were designed for
military purposes, such as calculating firing tables for artillery or
breaking codes. As a result, many observers viewed the market for such
devices to be quite small. The observers were wrong!

Electronics technology has improved greatly in 70 years. Today, a
computer with the capacity of the ENIAC would be smaller than a coin
from our pockets, would consume little power, and cost just a few
dollars on the mass market.

\emph{How have computer systems and their use evolved over the past 70
years?}

\begin{itemize}
\item
  Contemporary processors are much smaller and faster. They use much
  less power, cost much less money (when mass produced), and operate
  much more reliably.
\item
  Contemporary ``main'' memories are much larger in capacity, smaller in
  physical size, and faster in access speed. They also use much less
  power, cost much less money, and operate much more reliably.
\item
  The number of processors per machine has increased from one to many.
  First, channels and other co-processors were added, then multiple
  CPUs. Today, computer chips for common desktop and mobile applications
  have several processors--cores--on each chip, plus specialized
  processors such as graphics processing units (GPUs) for data
  manipulation and parallel computation. This trend toward
  multiprocessors will likely continue given that physics dictates
  limits on how small and fast we can make computer processors; to
  continue to increase in power means increasing parallelism.
\item
  Contemporary external storage devices are much larger in capacity,
  smaller in size, faster in access time, and cost less.
\item
  The number of computers available per user has increased from much
  less than one to many more than one.
\item
  Early systems were often locked into rooms, with few or no direct
  connections to the external world and just a few kinds of input/output
  devices. Contemporary systems may be on the user's desktop or in the
  user's backpack, be connected to the internet, and have many kinds of
  input/output devices.
\item
  The range of applications has increased from a few specialized
  applications (e.g., code-breaking, artillery firing tables) to almost
  all human activities.
\item
  The cost of the human staff to program, operate, and support computer
  systems has probably increased somewhat (in constant dollars).
\end{itemize}

\emph{How have these changes affected programming practice?}

\begin{itemize}
\item
  In the early days of computing, computers were very expensive and the
  cost of the human workers to use them relatively less. Today, the
  opposite holds. So we need to maximize human productivity.
\item
  In the early days of computing, the slow processor speeds and small
  memory sizes meant that programmers had to control these precious
  resources to be able to carry out most routine computations. Although
  we still need to use efficient algorithms and data structures and use
  good coding practices, programmers can now bring large amounts of
  computing capacity to bear on most problems. We can use more computing
  resources to improve productivity to program development and
  maintenance. The size of the problems we can solve computationally has
  increased beyond what would be possible manually.
\item
  In the early days of computing, multiple applications and users
  usually had to share one computer. Today, we can often apply many
  processors for each user and application if needed. Increasingly,
  applications must be able to use multiple processors effectively.
\item
  Security on early systems meant keeping the computers in locked rooms
  and restricting physical access to those rooms. In contemporary
  networked systems with diverse applications, security has become a
  much more difficult issue with many aspects.
\item
  Currently, industry can devote considerable hardware and software
  resources to the development of production software.
\end{itemize}

The first higher-level programming languages began to appear in the
1950s. IBM released the first compiler for a programming language in
1957--for the scientific programming language Fortran. Although Fortran
has evolved considerably during the past 60 years, it is still in use
today.

\emph{How have the above changes affected programming language design
and implementation over the past 60 years?}

\begin{itemize}
\item
  Contemporary programming languages often use automatic memory
  allocation and deallocation (e.g., garbage collection) to manage a
  program's memory. Although programs in these languages may use more
  memory and processor cycles than hand-optimized programs, they can
  increase programmer productivity and the security and reliability of
  the programs. Think Java, C\#, and Python versus C and C++.
\item
  Contemporary programming languages are often implemented using an
  interpreter instead of a compiler that translates the program to the
  processor's machine code--or be implemented using a compiler to a
  virtual machine instruction set (which is itself interpreted on the
  host processor). Again they use more processor and memory resources to
  increase programmer productivity and the security and reliability of
  the programs. Think Java, C\#, and Python versus C and C++.
\item
  Contemporary programming languages should make the capabilities of
  contemporary multicore systems conveniently and safely available to
  programs and applications. To fail to do so limits the performance and
  scalability of the application. Think Erlang, Scala, and Clojure
  versus C, C++, and Java.
\item
  Contemporary programming languages increasingly incorporate
  declarative features (higher order functions, recursion, immutable
  data structures, generators, etc.). These features offer the potential
  of increasing programming productivity, increasing the security and
  reliability of programs, and more conveniently and safely providing
  access to multicore processor capabilities. Think Scala, Clojure, and
  Java 8 and beyond versus C, C++, and older Java.
\item
  etc.
\end{itemize}

As we study programming and programming languages in this and other
courses, we need to keep the nature of the contemporary programming
scene in mind.

Now let's consider the concept of programming paradigm and the major
paradigms.

\subsection{Primary Programming
Paradigms}\label{primary-programming-paradigms}

According to Timothy Budd, a \emph{programming paradigm} is ``a way of
conceptualizing what it means to perform computation, of structuring and
organizing how tasks are to be carried out on a computer.'' {[}from:
Timothy A. Budd. \emph{Multiparadigm Programming in Leda},
Addison-Wesley, 1995, page 3{]}

Historically, computer scientists have classified programming
\emph{languages} into one of two primary paradigms: \emph{imperative}
and \emph{declarative}.

In recent years, many imperative languages have added more declarative
features, so the distinction between languages has become blurred.
However, the concept of \emph{programming} paradigm is still meaningful.

\subsubsection{Imperative paradigm}\label{imperative-paradigm}

A program in the imperative paradigm has an \emph{implicit state} (i.e.,
values of variables, program counters, etc.) that is modified (i.e.,
side-effected or mutated) by \emph{constructs} (i.e., commands) in the
source language.

As a result, such languages generally have an explicit notion of
\emph{sequencing} (of the commands) to permit precise and deterministic
control of the state changes.

Imperative programs thus express \emph{how} something is to be computed.

Consider the following fragment of Java code:

\begin{verbatim}
    int count =  0;
    int maxc  = 10;
    while (count <= maxc) {
        System.out.println(count) ;
        count = count + 1
    }
\end{verbatim}

In this fragment, the program's \emph{state} includes at least the
values of the variables \texttt{count} and \texttt{maxc}, the sequence
of output lines that have been printed, and an indicator of which
statement to execute next (i.e., location or program counter).

The assignment statement changes the value of \texttt{count} and the
\texttt{println} statement adds a new line to the output sequence. These
are \emph{side effects} of the execution.

Similarly, Java executes these commands in sequence, causing a change in
which statement will be executed next. The purpose of the \texttt{while}
statement is to cause the statements between the braces to be executed
zero or more times. The number of times depends upon the values of
\texttt{count} and \texttt{maxc} and how the values change within the
\texttt{while} loop.

We call this state \emph{implicit} because the aspects of the state used
by a particular statement are not explicitly specified; the state is
assumed from the context of the statement. Sometimes a statement can
modify aspects of the state that are not evident from examining the code
fragment itself.

The Java variable \texttt{count} is \emph{mutable} because its value can
change. After the declaration, \texttt{count} has the value 0. At the
end of the first iteration of the \texttt{while} loop, it has value 1.
After the \texttt{while} loop exits, it has a value 10. So a reference
to \texttt{count} yields different values depending upon the state of
the program at that point.

The Java variable \texttt{maxc} is also \texttt{mutable}, but this code
fragment does not change its value.

Imperative languages are the ``conventional'' or ``von Neumann
languages'' discussed by John Backus in his 1977 Turing Award address.
(See the section with excerpts from that address.) They are well suited
to traditional computer architectures.

Most of the languages in existence today are primarily imperative in
nature. These include Fortran, C, C++, Java, C\#, Python, Lua, and
JavaScript.

\subsubsection{Declarative paradigm}\label{declarative-paradigm}

A program in the declarative paradigm has \emph{no implicit} state. Any
needed state information must be handled explicitly.

A program is made up of \emph{expressions} (or terms) that are
\emph{evaluated} rather than commands that are executed.

Repetitive execution is accomplished by \emph{recursion} rather than by
sequencing.

Declarative programs express \emph{what} is to be computed (rather than
how it is to be computed).

The declarative paradigm is often divided into two types:
\emph{functional} (or applicative) and \emph{relational} (or logic).

\paragraph{Functional paradigm}\label{functional-paradigm}

In the functional paradigm the underlying model of computation is the
mathematical concept of a \emph{function}.

In a computation, a function is applied to zero or more arguments to
compute a single result; that is, the result is deterministic (or
predictable).

Consider the following Haskell code. (Don't worry about the details of
the language for now. We study the syntax and semantics of Haskell in an
upcoming chapter.)

\begin{verbatim}
    counter :: Int -> Int -> String 
    counter count maxc 
        | count <= maxc = show count ++ "\n" ++ counter (count+1) maxc 
        | otherwise     = ""
\end{verbatim}

This fragment is similar to the Java fragment above. This Haskell code
defines a function \texttt{counter} that takes two integer arguments,
\texttt{count} and \texttt{maxc}, and returns a string consisting of a
sequence of lines with the integers from \texttt{count} to \texttt{maxc}
such that each would be printed on a separate line. (It does not print
the string, but it inserts newline character at the end of each line.)

In the execution of a function call, \texttt{counter} references the
\emph{values} of \texttt{count} and \texttt{maxc} corresponding to the
explicit arguments of the function call. These values are not changed
within the execution of that function call. However, the values of the
arguments can be changed as needed for a subsequent \emph{recursive}
call of \texttt{counter}.

We call the state of \texttt{counter} \emph{explicit} because it is
passed in arguments of the function call. These parameters are
\emph{immutable} (i.e., their values cannot change) within the body of
the function. That is, any reference to \texttt{count} or \texttt{maxc}
within a call gets the same value.

In a pure functional language like Haskell, the names like
\texttt{count} and \texttt{maxc} are said to be \emph{referentially
transparent}. In the same context (such as the body of the function),
they always have the same value. A name must be defined before it is
used, but otherwise the order of the execution of the expressions within
a function body does not matter.

There are no ``loops''. The functional paradigm uses recursive calls to
carry out a task repeatedly.

In most programming languages that support functional programming,
functions are treated as \emph{first class} values. That is, like other
data types, functions can be stored in data structures, passed as
arguments to functions, and returned as the results of functions. (The
implementation technique for first-order functions usually involves
creation of a \emph{lexical closure} holding the function and its
environment.)

A function that can take functions as arguments or return functions in
the result is called a \emph{higher-order function}. A function that
does not take or return functions is thus a \emph{first-order function}.
Most imperative languages do not fully support higher-order functions.

The higher-order functions in functional programming languages enable
regular and powerful abstractions and operations to be constructed. By
taking advantage of a library of higher-order functions that capture
common patterns of computation, we can quickly construct concise, yet
powerful, programs.

Purely functional languages include Haskell, Idris, Miranda, Hope, Elm,
and Backus' FP.

Hybrid functional languages with significant functional subsets include
Scala, F\#, OCaml, SML, Erlang, Elixir, Lisp, Clojure, and Scheme.

Mainstream imperative languages such as Java (beginning with version 8),
C\#, Python, Ruby, Groovy, Rust, and Swift have recent feature
extensions that make them hybrid languages as well.

\paragraph{Relational (or logic)
paradigm}\label{relational-or-logic-paradigm}

In the relational (logic) paradigm, the underlying model of computation
is the mathematical concept of a \emph{relation} (or a
\emph{predicate}).

A computation is the (nondeterministic) association of a group of
values---with backtracking to resolve additional values.

Consider the following SWI-Prolog code. (Don't worry about the details
of the language.)

\begin{verbatim}
    counter(X,Y,S) :- count(X,Y,R), atomics_to_string(R,'\n',S).

    count(X,X,[X]). 
    count(X,Y,[])     :- X  > Y. 
    count(X,Y,[X|Rs]) :- X < Y, NX is X+1, count(NX,Y,Rs).
\end{verbatim}

This fragment is somewhat similar to the Java and Haskell fragments
above. It can be used to generate a string with the integers from
\texttt{X} to \texttt{Y} where each integer would be printed on a
separate line. (As with the Haskell fragment, it does not print the
string.)

This program fragment defines a \emph{database} consisting of four
\emph{clauses}.

The clause

\begin{verbatim}
    count(X,X,[X]).
\end{verbatim}

defines a \emph{fact}. For any \emph{variable} value \texttt{X} and list
\texttt{{[}X{]}} consisting of the single value \texttt{X},
\texttt{count(X,X,{[}X{]})} is asserted to be true.

The other three clauses are \emph{rules}. The left-hand-side of
\texttt{:-} is true if the right-hand-side is also true. For example,

\begin{verbatim}
    count(X,Y,[]) :- X > Y.
\end{verbatim}

asserts that

\begin{verbatim}
    count(X,Y,[])
\end{verbatim}

is true when \texttt{X\ \textgreater{}\ Y}. The empty brackets denote an
empty list of values.

As a logic or relational language, we can \emph{query} the database for
any missing components. For example,

\begin{verbatim}
    count(1,1,Z).
\end{verbatim}

yields the value \texttt{Z\ =\ {[}1{]}}. However,

\begin{verbatim}
    count(X,1,[1]).
\end{verbatim}

yields the value \texttt{X\ =\ 1}. If more than one answer is possible,
the program can generate all of them in some nondeterministic order.

So, in some sense, where imperative and functional languages only run a
computation in one direction and give a single answer, Prolog can
potentially run a computation in multiple directions and give multiple
answers.

Example relational languages include Prolog, Parlog, and miniKanren.

Most Prolog implementations have imperative features such as the cut and
the ability to assert and retract clauses.

\subsection{Other Programming
Paradigms}\label{other-programming-paradigms}

The imperative-declarative taxonomy described above divides programming
styles and language features on how they handle state and how they are
executed.

The computing community often speaks of other paradigms -- procedural,
modular, object-oriented, concurrent, parallel, language-oriented,
scripting, reactive, and so forth. The definitions of these
``paradigms'' may be quite fuzzy and vary significantly from one writer
to another. Sometimes a term is chosen for ``marketing'' reasons -- to
associate a language with some trend even though the language may be
quite different from others in that paradigm -- or to make a language
seem different and new even though it may not be significantly
different.

These paradigms tend to divide up programming styles and language
features along different dimensions than the primary taxonomy above.
Often the languages we are speaking of are subsets of the imperative
paradigm.

\subsubsection{Procedural}\label{procedural}

\emph{Procedural} languages, for example, are imperative languages built
around the concept of subprograms -- procedures and functions.
Programmers divide a program's behavior into these program units that
call each other. Subprograms may be nested inside of other subprograms
to control the range of the program where the name of the subprogram is
known.

Languages like C, Fortran, Pascal, Lua, and Python are primarily
procedural languages, although most have evolved to support other
styles.

\subsubsection{Modular}\label{modular}

\emph{Modular programming} refers more to a design method for programs
and program libraries than to languages.

It means to decompose a program into packages of functionality that can
be developed separately. Key design and implementation details are
hidden inside the module -- the principle of \emph{information hiding}.
The interactions among modules is kept at a minimum -- exhibit a low
degree of coupling.

A language that provides constructs for defining modules, packages,
namespaces, or separate compilation units can assist in writing modular
programs.

\subsubsection{Object oriented}\label{object-oriented}

The dominant paradigm since the early 1990s has been the
\emph{object-oriented paradigm}. Because this paradigm is likely
familiar with most readers, let's examine it in more detail.

We discuss object orientation in terms of an object model. Our
\emph{object model} includes four basic components:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  objects (i.e., abstract data structures)
\item
  classes (i.e., abstract data types)
\item
  inheritance (hierarchical relationships among abstract data types)
\item
  subtype polymorphism
\end{enumerate}

Note: Some writers consider \emph{dynamic binding} a basic component of
object orientation. Here we consider it an implementation technique for
subtype polymorphism.

\paragraph{Objects}\label{objects}

An \emph{object} is a characterized by three essential characteristics:

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\tightlist
\item
  state
\item
  operations
\item
  identity
\end{enumerate}

An object is a separately identifiable entity that has a set of
operations and a state that records the effects of the operations. An
object is typically a \emph{first class} entity that can be stored in
variables and passed to or returned from subprograms.

The \emph{state} is the collection of information held (i.e., stored) by
the object.

\begin{itemize}
\tightlist
\item
  It can change over time.
\item
  It can change as the result of an operation performed on the object.
\item
  It cannot change spontaneously.
\end{itemize}

The various components of the state are sometimes called the
\emph{attributes} of the object.

An \emph{operation} is a procedure that takes the state of the object
and zero or more arguments and changes the state and/or returns one or
more values. Objects permit certain operations and not others.

If an object is \emph{mutable}, then an operation may change the stored
state so that a subsequent operation on that object acts upon the
modified state; the language is thus imperative.

If an object is \emph{immutable}, then an operation cannot change the
stored state; instead it returns a new object with the modified state.

\emph{Identity} means we can distinguish between two distinct objects
(even if they have the same state and operations).

As an example, consider an object for a student desk in a simulation of
a classroom. Student desks are distinct from each other. The relevant
\emph{state} might be attributes like location, orientation, person
using, items in the basket, items on top, etc. The relevant
\emph{operations} might be state-changing operations (called
\emph{mutator}, setter, or command operations) such as ``move the
desk'', ``seat student'', or ``remove from basket'' or might be
state-observing operations (called \emph{accessor}, getter, observer, or
query operations) such as ``is occupied'' or ``report items on
desktop''.

A language is \emph{object-based} if it supports objects as a language
feature.

Object-based languages include Ada, Modula, Clu, C++, Java, Scala, C\#,
and Smalltalk. Pascal (without module extensions), Algol, Fortran. and C
are not inherently object-based.

Some writers require that an object have additional characteristics, but
these notes consider these as important but \emph{non-essential}
characteristics of objects:

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\setcounter{enumi}{3}
\tightlist
\item
  encapsulation
\item
  independent lifecycle
\end{enumerate}

The state may be \emph{encapsulated} within the object -- that is, not
be directly visible or accessible from outside the object.

The object may also have an \emph{independent lifecycle} -- that is, the
object may exist independently from the program unit that created it.

We do not include these as essential characteristics because they do not
seem required by the object metaphor. There are languages that use a
modularization feature to enforce encapsulation separately from the
object (or class) feature. Also, there are languages that may have local
``objects'' within a function or procedure.

\paragraph{Classes}\label{classes}

A \emph{class} is a template or factory for creating objects.

\begin{itemize}
\item
  A class describes a collection of related objects (i.e.,
  \emph{instances} of the class).
\item
  Objects of the same class have common operations and a common set of
  possible states.
\item
  The concept of class is closely related to the concept of \emph{type}.
\end{itemize}

A class description includes definitions of:

\begin{itemize}
\tightlist
\item
  operations on objects of the class
\item
  the possible set of states
\end{itemize}

As an example, again consider a simulation of a classroom. There might
be a class \texttt{StudentDesk} from which specific instances can be
created as needed.

An object-based language is \emph{class-based} if the concept of class
occurs as a language feature and every object has a class.

Class-based languages include Clu, C++, Java, Scala, C\#, Smalltalk,
Ruby, and Ada 95. Ada 83 and Modula are not class-based.

At their core, JavaScript and Lua are object-based but not class-based.

In statically typed, class-based languages such as Java, Scala, C++, and
C\# classes are treated as types. Instances of the same class have the
same type.

However, some dynamically typed languages may have a more general
concept of type: If two objects have the same set of operations, then
they have the same type regardless of how the object was created.
Languages such as Smalltalk and Ruby have this characteristic --
sometimes informally called \emph{duck typing}. (If it walks like a duck
and quacks like a duck, then it is a duck.)

\paragraph{Inheritance}\label{inheritance}

A class C \emph{inherits} from class P if C's objects form a subset of
P's objects.

\begin{itemize}
\item
  Class C's objects must support all of the class P's operations (but
  perhaps are carried out in a special way).
\item
  Class C may support additional operations and an extended state (i.e.,
  more information fields).
\item
  Class C is called a \emph{subclass} or a \emph{child} or \emph{derived
  class}.
\item
  Class P is called a \emph{superclass} or a \emph{parent} or
  \emph{base} class.
\item
  Class P is sometimes called a \emph{generalization} of class C; class
  C is a \emph{specialization} of class P.
\end{itemize}

The importance of inheritance is that it encourages sharing and reuse of
both design information and program code. The shared state and
operations can be described and implemented in base classes and shared
among the subclasses.

As an example, again consider the student desks in a simulation of a
classroom. The \texttt{StudentDesk} class might be derived (i.e.,
inherit) from a class \texttt{Desk}, which in turn might be derived from
a class \texttt{Furniture}. In diagrams, it is the convention to draw
arrows (e.g., \(\longleftarrow\)) from the subclass to the superclass.

\begin{quote}
\texttt{Furniture}\(\longleftarrow\) \texttt{Desk} \(\longleftarrow\)
\texttt{StudentDesk}
\end{quote}

The simulation might also include a \texttt{ComputerDesk} class that
also derives from \texttt{Desk}.

\begin{quote}
\texttt{Furniture} \(\longleftarrow\) \texttt{Desk} \(\longleftarrow\)
\texttt{ComputerDesk}
\end{quote}

In Java and Scala, we can express the above inheritance relationships
using the \texttt{extends} keyword as follows.

\begin{verbatim}
    class Furniture  // extends cosmic root class for references
    {   ...   }      // (java.lang.Object, scala.AnyRef)



    class Desk extends Furniture
    {   ...   }

    class StudentDesk extends Desk
    {   ...   }

    class ComputerDesk extends Desk
    {   ...   }
\end{verbatim}

Both \texttt{StudentDesk} and \texttt{ComputerDesk} objects will need
operations to simulate a \texttt{move} of the entity in physical space.
The \texttt{move} operation can thus be implemented in the \texttt{Desk}
class and shared by objects of both classes. Invocation of operations to
\texttt{move} either a \texttt{StudentDesk} or a \texttt{ComputerDesk}
will be bound to the general \texttt{move} in the \texttt{Desk} class.

The \texttt{StudentDesk} class might inherit from a \texttt{Chair} class
as well as the \texttt{Desk} class.

\begin{quote}
\texttt{Furniture} \(\longleftarrow\) \texttt{Chair} \(\longleftarrow\)
\texttt{StudentDesk}
\end{quote}

Some languages support \emph{multiple inheritance} as shown above for
\texttt{StudentDesk} (e.g., C++, Eiffel). Other languages only support a
single inheritance hierarchy.

Because multiple inheritance is both difficult to use correctly and to
implement in a compiler, the designers of Java and Scala did not include
multiple inheritance of classes as features. Java has a single
inheritance hierarchy with a top-level class named \texttt{Object} from
which all other classes derive (directly or indirectly). Scala is
similar, with the corresponding top-level class named \texttt{AnyRef}.

\begin{verbatim}
    class StudentDesk extends Desk, Chair  // NOT VALID in Java
    {   ...   }
\end{verbatim}

To see some of the problems in implementing multiple inheritance,
consider the above example. Class \texttt{StudentDesk} inherits from
class \texttt{Furniture} through two different paths. Do the data fields
of the class \texttt{Furniture} occur once or twice? What happens if the
intermediate classes \texttt{Desk} and \texttt{Chair} have conflicting
definitions for a data field or operation with the same name?

The difficulties with multiple inheritance are greatly decreased if we
restrict ourselves to inheritance of class \emph{interfaces} (i.e., the
signatures of a set of operations) rather than a supporting the
inheritance of the class \emph{implementations} (i.e., the instance data
fields and operation implementations). Since interface inheritance can
be very useful in design and programming, the Java designers introduced
a separate mechanism for that type of inheritance.

The Java \texttt{interface} construct can be used to define an interface
for classes separately from the classes themselves. A Java
\texttt{interface} may inherit from (i.e., \texttt{extend}) zero or more
other \texttt{interface} definitions.

\begin{verbatim}
    interface Location3D
    {   ...   }

    interface HumanHolder
    {   ...   }

    interface Seat extends Location3D, HumanHolder
    {   ...   }
\end{verbatim}

A Java \texttt{class} may inherit from (i.e., \texttt{implement}) zero
or more interfaces as well as inherit from (i.e., \texttt{extend})
exactly one other \texttt{class}.

\begin{verbatim}
    interface BookHolder
    {   ...   }

    interface BookBasket extends Location3D, BookHolder
    {   ...   }

    class StudentDesk extends Desk implements Seat, BookBasket
    {   ...   }
\end{verbatim}

This definition requires the \texttt{StudentDesk} class to provide
actual implementations for all the operations from the
\texttt{Location3D}, \texttt{HumanHolder}, \texttt{BookHolder},
\texttt{Seat}, and \texttt{BookBasket} interfaces. The
\texttt{Location3D} operations will, of course, need to be implemented
in such a way that they make sense as part of both the
\texttt{HumanHolder} and \texttt{BookHolder} abstractions.

The Scala \texttt{trait} provides a more powerful, and more complex,
mechanism than Java's original \texttt{interface}. In addition to
signatures, a \texttt{trait} can define method implementations and data
fields. These traits can be added to a class in a controlled, linearized
manner to avoid the semantic and implementation problems associated with
multiple inheritance of classes. This is called \emph{mixin}
inheritance.

Java 8 generalized interfaces to allow default implementations of
methods.

Most statically typed languages treat subclasses as \emph{subtypes}.
That is, if \texttt{C} is a subclass of \texttt{P}, then the objects of
type \texttt{C} are also of type \texttt{P}. We can \emph{substitute} a
\texttt{C} object for a \texttt{P} object in all cases.

However, the inheritance mechanism in languages in most class-based
languages (e.g., Java) does not automatically preserve substitutability.
For example, a subclass can change an operation in the subclass to do
something totally different from the corresponding operation in the
parent class.

\paragraph{Polymorphism}\label{polymorphism}

The concept of \emph{polymorphism} (literally ``many forms'') means the
ability to hide different implementations behind a common interface.
Polymorphism appears in several forms in programming languages. We will
discuss these more later.

\emph{Subtype polymorphism} (sometimes called \emph{polymorphism by
inheritance}, \emph{inclusion polymorphism}, or \emph{subtyping}) means
the association of an operation invocation (i.e., procedure or function
call) with the appropriate operation implementation in an inheritance
(subtype) hierarchy.

This form of polymorphism is usually carried out at run time. That
implementation is called \emph{dynamic binding}. Given an object (i.e.,
class instance) to which an operation is applied, the system will first
search for an implementation of the operation associated with the
object's class. If no implementation is found in that class, the system
will check the superclass, and so forth up the hierarchy until an
appropriate implementation is found. Implementations of the operation
may appear at several levels of the hierarchy.

The combination of dynamic binding with a well-chosen inheritance
hierarchy allows the possibility of an instance of one subclass being
substituted for an instance of a different subclass during execution. Of
course, this can only be done when none of the extended operations of
the subclass are being used.

As an example, again consider the simulation of a classroom. As in our
discussion of inheritance, suppose that the \texttt{StudentDesk} and
\texttt{ComputerDesk} classes are derived from the \texttt{Desk} class
and that a general \texttt{move} operation is implemented as a part of
the \texttt{Desk} class. This could be expressed in Java as follows:

\begin{verbatim}
    class Desk extends Furniture
    {   ...
        public void move(...)
        ...
    }

    class StudentDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }

    class ComputerDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }
\end{verbatim}

As we noted before, invocation of operations to \texttt{move} either a
\texttt{StudentDesk} or a \texttt{ComputerDesk} instance will be bound
to the general \texttt{move} in the \texttt{Desk} class.

Extending the example, suppose that we need a special version of the
\texttt{move} operation for \texttt{ComputerDesk} objects. For instance,
we need to make sure that the computer is shut down and the power is
disconnected before the entity is moved.

To do this, we can define this special version of the \texttt{move}
operation and associate it with the \texttt{ComputerDesk} class. Now a
call to \texttt{move} a \texttt{ComputerDesk} object will be bound to
the special \texttt{move} operation, but a call to \texttt{move} a
\texttt{StudentDesk} object will still be bound to the general
\texttt{move} operation in the \texttt{Desk} class.

The definition of \texttt{move} in the \texttt{ComputerDesk} class is
said to \emph{override} the definition in the \texttt{Desk} class.

In Java, this can be expressed as follows:

\begin{verbatim}
    class Desk extends Furniture
    {   ...
        public void move(...)
        ...
    }

    class StudentDesk extends Desk
    {   ...
        // no move(...) operation here
        ...
    }

    class ComputerDesk extends Desk
    {   ...
        public void move(...)
        ...
    }
\end{verbatim}

A class-based language is \emph{object-oriented} if class hierarchies
can be incrementally defined by an inheritance mechanism and the
language supports polymorphism by inheritance along these class
hierarchies.

Object-oriented languages include C++, Java, Scala, C\#, Smalltalk, and
Ada 95. The language Clu is class-based, but it does not include an
inheritance facility.

Other object-oriented languages include Objective C, Object Pascal,
Eiffel, and Oberon 2.

\subsubsection{Prototype based}\label{prototype-based}

Classes and inheritance are not the only way to support relationships
among objects in object-based languages. Another approach of growing
importance is the use of \emph{prototypes}.

A \emph{prototype-based} language does not have the concept of class as
defined above. It just has objects. Instead of using a class to
instantiate a new object, a program copies (or clones) an existing
object -- the \emph{prototype} -- and modifies the copy to have the
needed attributes and operations.

Each prototype consists of a collection of \emph{slots}. Each slot is
filled with either a data attribute or an operation

This cloning approach is more flexible than the class-based approach.

In a class-based language, we need to define a new class or subclass to
create a variation of an existing type. For example, we may have a
\texttt{Student} class. If we want to have students who play chess, then
we would need to create a new class, say \texttt{ChessPlayingStudent},
to add the needed data attributes and operations.

In a class-based language, the boundaries among categories of objects
specified by classes should be \emph{crisply defined}. That is, an
object is in a particular class or it is not. Sometimes this crispness
may be unnatural.

In a prototype-based language, we simply clone a student object and add
new slots for the added data and operations. This new object can be a
prototype for further objects.

In a prototype-based language, the boundaries between categories of
objects created by cloning may be fuzzy. One category of objects may
tend to blend into others. Sometimes this fuzziness may be more natural.

Consider categories of people associated with a university. These
categories may include \texttt{Faculty}, \texttt{Staff},
\texttt{Student}, and \texttt{Alumnus}. Consider a \emph{student} who
gets a BSCS degree, then accepts a \emph{staff} position as a programmer
and stays a student by starting an MS program part-time, and then later
teaches a course as a graduate student. The same person who started as a
student thus evolves into someone who is in several categories later.
And he or she may also be a chess player.

Instead of static, class-based inheritance and polymorphism, some
languages exhibit prototype-based \emph{delegation}. If the appropriate
operation cannot be found on the current object, the operation can be
delegated to its prototype, or perhaps to some other related, object.
This allows dynamic relationships along several dimensions. It also
means that the ``copying'' or ``cloning'' may be partly logical rather
than physical.

Prototypes and delegation are more basic mechanisms than inheritance and
polymorphism. The latter can often be implemented (or perhaps
``simulated'') using the former.

Self, JavaScript, and Lua are prototype-based languages.

\subsection{History of Programming
Languages}\label{history-of-programming-languages}

From the instructor's perspective, key languages and milestones in the
history of programming languages include the following.

1950's

\begin{itemize}
\item
  Fortran, 1957; imperative, first compiler, math-like language for
  scientific programming, developed at IBM by John Backus, influenced
  most subsequent languages, enhanced versions still in use today (first
  language learned by the instructor in 1974)
\item
  Lisp, 1958; mix of imperative and functional features, code and data
  have same format (i.e., the language is \emph{homoiconic}), related to
  Church's lambda calculus theory, recursion, syntactic macros,
  automatic storage management, higher order functions, developed at MIT
  by John McCarthy, influenced most subsequent languages/research,
  enhanced versions still in use today
\item
  Algol, 1958, 1960; imperative, nested block structure, lexical
  scoping, BNF invented to define syntax, call by name parameter
  passing, developed by an international team from Europe and the USA,
  influenced most subsequent languages
\item
  COBOL, 1959; imperative, key designer Grace Hopper,
  business/accounting programming, still in use today (third language
  learned by instructor in late 1975)
\end{itemize}

1960's

\begin{itemize}
\item
  Simula; 1962, 1967; imperative, original purpose for discrete-event
  simulation, developed in Norway by Ole-Johan Dahl and Kristen Nygaard,
  first object-oriented language (in Scandinavian school of
  object-oriented languages), influenced subsequent object-oriented
  languages
\item
  Snobol, 1962; string processing, patterns as first class data,
  backtracking on failure, developed at AT\&T Bell Laboratories by David
  J. Farber, Ralph E. Griswold and Ivan P. Polonsky
\item
  PL/I, 1964; IBM-designed language to merge scientific (Fortran),
  business (COBOL), and systems programming (second language learned by
  the instructor in early 1975)
\item
  BASIC, 1964; interactive computing in early timesharing and
  microcomputers environments, developed at Dartmouth College by John G.
  Kemeny and Thomas E. Kurtz
\item
  Algol 68, 1968; ambitious and rigorously defined successor to Algol
  60, greatly influenced computing science theory and subsequent
  language designs, not widely implemented because of its complexity
\end{itemize}

1970's

\begin{itemize}
\item
  Pascal, 1970; simplified Algol family language designed by Niklaus
  Wirth (Switzerland) because of frustration with complexity of Algol
  68, structured programming, one-pass compiler, important for teaching
  in 1980s and 1990s, Pascal-P System virtual machine implemented on
  many early microcomputers (Pascal used by UM CIS in CS1 and CS2 until
  1999)
\item
  Prolog, 1972; first and most widely used logic (relational)
  programming language, originally developed by a team headed by Alain
  Colmerauer (France), rooted in first-order logic, most modern Prolog
  implementations based on the Edinburgh dialect (which ran on the
  Warren Abstract Machine), used extensively for artificial intelligence
  research in Europe, influenced subsequent logic languages and also
  Erlang
\item
  C, 1972; systems programming language for Unix operating system,
  widely used today, developed by Dennis Ritchie at AT\&T Bell Labs,
  influenced many subsequent languages
\item
  Smalltalk, 1972; ground-up object-oriented programming language,
  message-passing between objects (in American school of object-oriented
  languages), developed by Alan Kay and others at Xerox PARC, influenced
  many subsequent object-oriented languages
\item
  ML, 1973; mostly functional, polymorphic type system on top of
  Lisp-like language, pioneering statically typed functional
  programming, algebraic data types, developed by Robin Milner at the
  University of Edinburgh, influenced subsequent functional programming
  languages
\item
  Scheme, 1975; minimalist dialect of Lisp with lexical scoping, tail
  call optimization, first-class continuations, developed by Guy Steele
  and Gerald Jay Sussman at MIT, influenced subsequent
  languages/research
\item
  Icon, 1977; structured programming successor to Snobol, developed by a
  team led by Ralph Griswold at the University of Arizona, uses
  goal-directed execution based on success or failure of expressions
\end{itemize}

1980's

\begin{itemize}
\item
  C++, 1980; C with Simula-like classes, developed by Bjarne Stroustrup
  (Denmark)
\item
  Ada, 1983; designed by US DoD-funded committee as standard language
  for military applications, design led by Jean Ichbiah and a team in
  France, statically typed, block structured, modular, synchronous
  message passing, object-oriented extensions in 1995 (instructor
  studied this language while working in the military aerospace industry
  1980-83)
\item
  Eiffel, 1985; object-oriented language designed with strong emphasis
  on software engineering concepts such as design by contract and
  command-query separation, developed by Bertrand Meyer (France)
\item
  Objective C, 1986; C with Smalltalk-like messaging, developed by Brad
  Cox and Tom Love at Stepstone, selected by Steve Jobs' NeXT systems,
  picked up by Apple when NeXT absorbed, key language for OS X and iOS
\item
  Erlang, 1986; message-passing concurrency on functional programming
  base (actors), fault-tolerant/real-time systems, dynamic typing,
  virtual machine, originally used in telephone switches, developed by
  Joe Armstrong, Robert Virding and Mike Williams at Ericsson (Sweden)
\item
  Self, 1986; dialect of Smalltalk, developed by David Ungar and Randall
  Smith while at Xerox PARC, Stanford University, and Sun Microsystems,
  first prototype-based object-oriented language (which influenced
  JavaScript, Lua), used virtual machine with just-in-time compilation
  (JIT) which influenced Java HotSpot
\item
  Perl, 1987; dynamic programming language originally focused on
  providing powerful text-processing facilities based around regular
  expressions, developed by Larry Wall
\end{itemize}

1990's

\begin{itemize}
\item
  Haskell, 1990; purely functional language with non-strict semantics
  (i.e., lazy evaluation) and strong static typing, developed by an
  international committee of functional programming researchers, widely
  used in research community
\item
  Python, 1991; dynamically typed, multiparadigm language, developed by
  Guido van Rossum (Netherlands), increasing in use
\item
  Ruby, 1993; dynamically typed, object-oriented, supports
  reflective/metaprogramming and internal domain-specific languages,
  developed by Yukihiro ``Matz'' Matsumoto (Japan), popularized by Ruby
  on Rails web framework, influenced subsequent languages
\item
  Lua, 1993; minimalistic language designed for embedding in any
  environment supporting standard C, developed by Roberto Ierusalimschy,
  Luiz Henrique de Figueiredo, and Waldemar Celes (Brazil), dynamic
  typing, lexical scoping, first-class functions, garbage collection,
  tail recursion optimization, pervasive table/metatable data structure,
  facilities for prototype object-oriented programming, coroutines, used
  as scripting language in games, etc.
\item
  R, 1993; statistical computing and graphics, open-source
  implementation of the language S, developed by Ross Ihaka and Robert
  Gentleman (New Zealand)
\item
  Java, 1995; class-based object-oriented programming, statically typed,
  virtual machine, version 8 has functional programming features (higher
  order functions, streams); developed by Sun Microsystems, now Oracle
\item
  JavaScript, 1995 (standardized as ECMAScript); designed for embedding
  in web pages, developed by Brendan Eich at Netscape in 12 days to meet
  a deadline, internals influenced by Scheme and Self but using a
  Java-like syntax, dynamic typing, first-class functions,
  prototype-based object-oriented programming, became popular quickly
  before language design made clean
\item
  PHP, 1995; originally developed by Rasmus Lerdorf (Canada), evolved
  organically, server-side scripting language for dynamic web
  applications,
\item
  OCaml (originally Objective Caml), 1996; a dialect of ML that adds
  object-oriented constructs, focusing on performance and practical use,
  developed by a team lead by Xavier Leroy (France)
\end{itemize}

2000's

\begin{itemize}
\item
  C\#, 2001; class-based object-oriented programming, statically typed,
  mostly imperative, language that runs on Microsoft's Common Language
  Infrastructure (in some sense, Microsoft's response to Sun's Java)
\item
  F\#, 2002; OCaml re-envisioned for Microsoft's Common Language
  Infrastructure (.Net), developed by a team led by Don Syme at
  Microsoft Research in the UK, replaces OCaml's object and module
  systems with .Net concepts,
\item
  Scala, 2003; hybrid functional and object-oriented language that runs
  on the Java Virtual Machine, developed by Martin Odersky's team at
  EPFL in Switzerland
\item
  Groovy, 2003; dynamically typed, object-oriented ``scripting''
  language that runs on the Java Virtual Machine, originally proposed by
  James Strachan
\item
  miniKanren, 2005; a family of relational programming languages,
  developed by Dan Friedman's team at Indiana University, implemented as
  an extension to other languages (originally in Scheme, most popular
  current usage probably in Clojure)
\item
  Clojure, 2007; Lisp dialect developed by Rich Hickey, runs on Java
  Virtual Machine, Microsoft Common Language Runtime, and JavaSript
  platform, emphasis on functional programming, concurrency (e.g.,
  software transactional memory), and immutable data structures
\end{itemize}

2010's

\begin{itemize}
\item
  Idris, 2011 (1.0 release planned 2017); eagerly evaluated,
  Haskell-like functional language with dependent types, incorporating
  ideas from proof assistants, intended for practical programming,
  developed by Edwin Brady (UK)
\item
  Julia, 2012; dynamic programming language designed to address
  high-performance numerical and scientific programming
\item
  Elixir, 2012 (1.0 release 2014); functional concurrent programming
  language, dynamic strong typing, metaprogramming, protocols, Erlang
  actors, runs on Erlang Virtual Machine, influenced by Erlang, Ruby,
  and Clojure, developed by a team led by Jose Valim (Brazil)
\item
  Elm, 2012 (0.18 release November 2016); simplified, eagerly evaluated
  Haskell-like functional programming language that compiles to
  JavaScript, intended primarily for user-interface programming in a
  browser, supports reactive-style programming, developed by Evan
  Czaplicki (original version for his senior thesis at Harvard)
\item
  Rust, 2012 (1.0 release 2015); systems programming language that
  incorporates contemporary language concepts and focuses on safety and
  performance, meant to replace C and C++, developed originally at
  Mozilla Research by Graydon Hoare
\item
  PureScript, 2013 (0.10.6 release February 2017); an eagerly evaluated
  functional programming language otherwise similar to Haskell,
  primarily compiles to human-readable JavaScript, originally developed
  by Phil Freeman
\item
  Swift, 2014; Apple's replacement for Objective C that incorporates
  contemporary language concepts and focuses on program safety;
  ``Objective C without the C''
\item
  etc.
\end{itemize}

\subsection{Abstraction}\label{abstraction}

As computing scientists and computer programmers, we should remember the
maxim:

\begin{quote}
\emph{Simplicity is good; complexity is bad.}
\end{quote}

The most effective weapon that we have in the fight against complexity
is \emph{abstraction}. What is abstraction?

Abstraction is \emph{concentrating on the essentials and ignoring the
details.}

Sometimes abstraction is described as \emph{remembering the ``what'' and
ignoring the ``how''}.

\subsubsection{Kinds of abstraction}\label{kinds-of-abstraction}

Large complex systems can only be made understandable by decomposing
them into modules. When viewed from the outside, from the standpoints of
users, each \emph{module} should be simple, with the complexity hidden
inside.

We strive for modules that have simple interfaces that can be used
without knowing the implementations. Here we use \emph{interface} to
mean any information about the module that other modules must assume to
be able to do their work correctly.

Two kinds of abstraction are of interest to computing scientists:
\emph{procedural abstraction} and \emph{data abstraction}.

\begin{description}
\tightlist
\item[Procedural abstraction:]
the separation of the logical properties of an \emph{action} from the
details of how the action is implemented.
\item[Data abstraction:]
the separation of the logical properties of \emph{data} from the details
of how the data are represented.
\end{description}

When we develop an algorithm following the top-down approach, we are
practicing procedural abstraction. At a high level, we break the problem
up into several tasks. We give each task a name and state its
requirements, but we do not worry about how the task is to be
accomplished until we expand it at a lower level of our design.

When we code a task in a programming language, we will typically make
each task a subprogram (procedure, function, subroutine, method, etc.).
Any other program component that calls the subprogram needs to know its
interface (name, parameters, return value, assumptions, etc.) but does
not need to know the subprogram's internal implementation details. The
internal implementation can be changed without affecting the caller.

In data abstraction, the focus is on the problem's data rather than the
tasks to be carried out.

\subsubsection{Procedures and functions}\label{procedures-and-functions}

Generally we make the following distinctions among subprograms:

\begin{itemize}
\item
  A \emph{procedure} is (in its pure form) a subprogram that takes zero
  or more arguments but does not return a value. It is executed for its
  effects, such as changing values in a data structure within the
  program, modifying its reference or value-result arguments, or causing
  some effect outside the program (e.g., displaying text on the screen
  or reading from a file).
\item
  A \emph{function} is (in its pure form) a subprogram that takes zero
  or more arguments and returns a value but that does not have other
  effects.
\item
  A \emph{method} is a procedure or function associated with an object
  or class in an object-oriented program. Some object-oriented languages
  use the metaphor of message-passing. A method is the feature of an
  object that receives a message. In an implementation, a method is
  typically a procedure or function associated with the object; the
  object may be in implicit parameter of the method.
\end{itemize}

Of course, the features of various programming languages and usual
practices for their use may not follow the above pure distinctions. For
example, a language may not distinguish between procedures and
functions. One term or another may be used for all subprograms.
Procedures may return values. Functions may have side effects. Functions
may return multiple values. The same subprogram can sometimes be called
either as a function or procedure.

Nevertheless, it is good practice to maintain the distinction between
functions and procedures for most cases in software design and
programming.

In Haskell, the primary unit of procedural abstraction is the pure
function. Haskell also groups functions and other declarations into a
program unit called a \texttt{module}. A \texttt{module} explicitly
exports selected functions and keep others hidden.

\subsection{Motivating Functional Programming: John
Backus}\label{motivating-functional-programming-john-backus}

John W. Backus (December 3, 1924 -- March 17, 2007) was a pioneer in
research and development of programming languages. He was the primary
developer of Fortran while a developer at IBM in the mid-1950s. Fortran
is the first widely used high-level language. Backus was also a
participant in the international team that designed the influential
languages Algol 58 and Algol 60 a few years later. The notation used to
describe the Algol 58 language syntax--Backus-Naur Form (BNF)--bears his
name. This notation continues to be used to this day.

In 1977, ACM bestowed its Turing Award on Backus in recognition of his
career of accomplishments. (This award is sometimes described as the
``Nobel Prize for computer science''.) The annual recipient of the award
gives an address to a major computer science conference. Backus's
address was titled ``Can Programming Be Liberated from the von Neumann
Style? A Functional Style and Its Algebra of Programs''.

Although functional languages like Lisp go back to the late 1950's,
Backus's address did much to stimulate research community's interest in
functional programming languages and functional programming over the
past 40 years.

The next subsection gives excerpts from Backus' Turing Award address
published as the article ``Can Programming Be Liberated from the von
Neumann Style? A Functional Style and Its Algebra of Programs''
(\emph{Communications of the ACM}, Vol.~21, No.~8, pages 613--41, August
1978).

\subsubsection{Excerpts from Backus's Turing Award
Address}\label{excerpts-from-backuss-turing-award-address}

Programming languages appear to be in trouble. Each successive language
incorporates, with little cleaning up, all the features of its
predecessors plus a few more. Some languages have manuals exceeding 500
pages; others cram a complex description into shorter manuals by using
dense formalisms. \ldots{} Each new language claims new and fashionable
features, such as strong typing or structured control statements, but
the plain fact is that few languages make programming sufficiently
cheaper or more reliable to justify the cost of producing and learning
to use them.

Since large increases in size bring only small increases in power,
smaller, more elegant languages such as Pascal continue to be popular.
But there is a desperate need for a powerful methodology to help us
think about programs, and no conventional language even begins to meet
that need. In fact, conventional languages create unnecessary confusion
in the way we think about programs. \ldots{} In order to understand the
problems of conventional programming languages, we must first examine
their intellectual parent, the von Neumann computer. What is a von
Neumann computer? When von Neumann and others conceived of it \ldots{}
{[}in the 1940's{]}, it was an elegant, practical, and unifying idea
that simplified a number of engineering and programming problems that
existed then. Although the conditions that produced its architecture
have changed radically, we nevertheless still identify the notion of
``computer'' with this \ldots{} concept.

In its simplest form a von Neumann computer has three parts: a central
processing unit (or CPU), a store, and a connecting tube that can
transmit a single word between the CPU and the store (and send an
address to the store). I propose to call this tube the \emph{von Neumann
bottleneck}. The task of a program is to change the contents of the
store in some major way; when one considers that this task must be
accomplished entirely by pumping single words back and forth through the
von Neumann bottleneck, the reason for its name becomes clear.

Ironically, a large part of the traffic in the bottleneck is not useful
data but merely names of data, as well as operations and data used only
to compute such names. Before a word can be sent through the tube its
address must be in the CPU; hence it must either be sent through the
tube from the store or be generated by some CPU operation. If the
address is sent form the store, then its address must either have been
sent from the store or generated in the CPU, and so on. If, on the other
hand, the address is generated in the CPU, it must either be generated
by a fixed rule (e.g., ``add 1 to the program counter'') or by an
instruction that was sent through the tube, in which case its address
must have been sent, and so on.

Surely there must be a less primitive way of making big changes in the
store than by pushing vast numbers of words back and forth through the
von Neumann bottleneck. Not only is this tube a literal bottleneck for
the data traffic of a problem, but, more importantly, it is an
intellectual bottleneck that has kept us tied to word-at-a-time thinking
instead of encouraging us to think in terms of the larger conceptual
units of the task at hand. \ldots{}

Conventional programming languages are basically high level, complex
versions of the von Neumann computer. Our \ldots{} old belief that there
is only one kind of computer is the basis our our belief that there is
only one kind of programming language, the conventional--von
Neumann--language. The differences between Fortran and Algol 68,
although considerable, are less significant than the fact that both are
based on the programming style of the von Neumann computer. Although I
refer to conventional languages as ``von Neumann languages'' to take
note of their origin and style, I do not, of course, blame the great
mathematician for their complexity. In fact, some might say that I bear
some responsibility for that problem.

Von Neumann programming languages use variables to imitate the
computer's storage cells; control statements elaborate its jump and test
instructions; and assignment statements imitate its fetching, storing,
and arithmetic. The assignment statement is the von Neumann bottleneck
of programming languages and keeps us thinking in word-at-at-time terms
in much the same way the computer's bottleneck does.

Consider a typical program; at its center are a number of assignment
statements containing some subscripted variables. Each assignment
statement produces a one-word result. The program must cause these
statements to be executed many times, while altering subscript values,
in order to make the desired overall change in the store, since it must
be done one word at a time. The programmer is thus concerned with the
flow of words through the assignment bottleneck as he designs the nest
of control statements to cause the necessary repetitions.

Moreover, the assignment statement splits programming into two worlds.
The first world comprises the right sides of assignment statements. This
is an orderly world of expressions, a world that has useful algebraic
properties (except that those properties are often destroyed by side
effects). It is the world in which most useful computation takes place.

The second world of conventional programming languages is the world of
statements. The primary statement in that world is the assignment
statement itself. All the other statements in the language exist in
order to make it possible to perform a computation that must be based on
this primitive construct: the assignment statement.

This world of statements is a disorderly one, with few useful
mathematical properties. Structured programming can be seen as a modest
effort to introduce some order into this chaotic world, but it
accomplishes little in attacking the fundamental problems created by the
word-at-a-time von Neumann style of programming, with its primitive use
of loops, subscripts, and branching flow of control.

Our fixation on von Neumann languages has continued the primacy of the
von Neumann computer, and our dependency on \emph{it} has made non-von
Neumann languages uneconomical and has limited their development. The
absence of full scale, effective programming styles founded on non-von
Neumann principles has deprived designers of an intellectual foundation
for new computer architectures. \ldots{}

\subsubsection{Aside on the disorderly world of
statements}\label{aside-on-the-disorderly-world-of-statements}

Backus states that ``the world of statements is a disorderly one, with
few mathematical properties''. Even in 1977 this was a bit overstated
since Dijkstra's work on the weakest precondition (\emph{wp}) calculus
and other work on axiomatic semantics had already appeared.

However, because of the referential transparency property of purely
functional languages, reasoning can often be done in an equational
manner within the context of the language itself. We examine this
convenient approach later in these notes.

In contrast, the \emph{wp}-calculus and other axiomatic semantic
approaches must project the problem from the world of programming
language statements into the world of predicate calculus, which is much
more orderly. We leave this study to other courses (such as CSci 550,
Program Semantics and Derivation).

\subsubsection{Perspective from four decades
later}\label{perspective-from-four-decades-later}

In his Turing Award Address, Backus went on to describe FP, his proposal
for a functional programming language. He argued that languages like FP
would allow programmers to break out of the von Neumann bottleneck and
find new ways of thinking about programming.

FP itself did not catch on, but the widespread attention given to
Backus' address and paper stimulated new interest in functional
programming to develop by researchers around the world. Modern languages
like Haskell developed partly from the interest generated.

In the 21st Century, the software industry has become more interested in
functional programming. Some functional programming features now appear
in most mainstream programming languages (e.g., in Java 8). This
interest seems to driven primarily by two concerns:

\begin{itemize}
\tightlist
\item
  managing the complexity of large software systems effectively
\item
  exploiting multicore processors conveniently and safely
\end{itemize}

The functional programming paradigm is able to address these concerns
because of such properties such as referential transparency, immutable
data structures, and composability of components. We look at these
aspects later in these notes.

\subsection{Review of Relevant
Mathematics}\label{review-of-relevant-mathematics}

This section reviews the mathematical concepts of functions and a few
other mathematical concepts used in these notes. The concept of function
in functional programming corresponds closely to the mathematical
concept of function.

\subsubsection{Natural numbers and
ordering}\label{natural-numbers-and-ordering}

Several of the examples in these notes use natural numbers.

For this study, we consider the set of \emph{natural numbers} \(N\) to
consist of 0 and the positive integers.

Inductively, \(n \in N\) if and only if one of the following holds

\begin{itemize}
\tightlist
\item
  \(n = 0\)
\item
  There exists \(m \in N\) such that \(m = S(n)\)
\end{itemize}

where \(S\) is the \emph{successor} function, which returns the next
element.

Furthermore,

\begin{itemize}
\tightlist
\item
  No element is the successor of more one other natural number.
\item
  0 is not the successor of any natural number. That is, it is the least
  (base) element.
\end{itemize}

The natural numbers thus form a \emph{totally ordered} set in
conjunction with the binary relation \(\leq\) (less or equal). That is,
the relation \(\leq\) satisfies the following properties on set \(N\):

\begin{itemize}
\tightlist
\item
  \(n \leq n\) for all \(n \in N\) (\emph{reflexivity})
\item
  \(m \leq n\) and \(n \leq m\) implies \(m = n\) (\emph{antisymmetry})
\item
  \(m \leq n\) and \(n \leq p\) implies \(m \leq p\)
  (\emph{transitivity})
\item
  Either \(m \leq n\) or \(n \leq m\) for all \(m,n \in N\)
  (\emph{trichotomy})
\end{itemize}

It is also a \emph{partial ordering} because it satisfies the first
three properties above.

For all \(m,n \in N\), we can define the other ordering relations in
terms of \(=\), \(\neq\), and \(\leq\) as follows:

\begin{itemize}
\tightlist
\item
  \(m < n\) (less) to mean \(m \leq n\) and \(m \neq n\). We say that
  \(m\) is smaller (or simpler) than \(n\).
\item
  \(m > n\) (greater) to mean \(n \leq m\) and \(n \neq m\). We say that
  \(m\) is larger (or more complex) than \(n\).
\item
  \(m \geq n\) (greater or equal) to mean the same as \(n \leq m\)
\end{itemize}

\subsubsection{Functions}\label{functions}

As we have studied in mathematics courses, a \emph{function} is a
mapping from a set \(A\) into a set \(B\) such that each element of
\(A\) is mapped into a unique element of \(B\).

\begin{itemize}
\tightlist
\item
  The set \(A\) (on which \(f\) is defined) is called the \emph{domain}
  of \(f\).
\item
  The set of all elements of \(B\) into which \(f\) maps elements of
  \(A\) is called the \emph{range} (or \emph{codomain}) of \(f\), and is
  denoted by \(f(A)\).
\end{itemize}

If \(f\) is a function from \(A\) into \(B\), then we write:

\begin{quote}
\(f : A \rightarrow B\)
\end{quote}

We also write the equation

\begin{quote}
\(f(a) = b\)
\end{quote}

to mean that the \emph{value} (or \emph{result}) from \emph{applying}
function \(f\) to an element \(a \in A\) is an element \(b \in B\).

If a function

\begin{quote}
\(f : A \rightarrow B\)
\end{quote}

and \(A \subseteq A'\), then we say that \(f\) is a \emph{partial
function} from \(A'\) to \(B\) and a \emph{total function} from \(A\) to
\(B\). That is, there are some elements of \(A'\) on which \(f\) may be
undefined.

\subsubsection{Recursive functions}\label{recursive-functions}

Informally, a \emph{recursive function} is a function defined using
recursion.

In computing science, \emph{recursion} is a method in which an
``object'' is defined in terms of smaller (or simpler) ``objects'' of
the same type. A recursion is usually defined in terms of a recurrence
relation.

A \emph{recurrence relation} defines an ``object'' \(x_{n}\) as some
combination of zero or more other ``objects'' \(x_{i}\) for \(i < n\).
Here \(i < n\) means that \(i\) is smaller (or simpler) than \(n\). If
there is no smaller object, then \(n\) is a base object.

For example, consider a recursive function to compute the sum \(s\) of
the first \(n\) natural numbers.

We can define a recurrence relation for \(s\) with the following
equations:

\begin{quote}
\emph{\(s(n) = 0\), if \(n = 0\)}\\
\emph{\(s(n) = n + s(n-1)\), if \(n \geq 1\)}
\end{quote}

For example, consider \(s(3)\),

\begin{quote}
\(s(3) = 3 + s(2) = 3 + (2 + s(1)) = 3 + (2 + (1 + s(0))) = 3 + (2 + (1 + 0)) = 6\)
\end{quote}

\subsubsection{Mathematical induction on natural
numbers}\label{mathematical-induction-on-natural-numbers}

We can give two mathematical definitions of factorial, \emph{fact} and
\emph{fact'}, that are equivalent for all natural number arguments.

We can define \emph{fact} using the product operator as follows:

\begin{quote}
\emph{fact\((n) = \prod_{i=1}^{i=n}\,i\)}
\end{quote}

We can also define the factorial function \emph{fact'} with a
\emph{recursive} definition (or\\
\emph{recurrence relation}) as follows:

\begin{quote}
\emph{fact'\((n) = 1\), if \(n = 0\)}\\
\emph{fact'\((n) = n \times\) fact'\((n-1)\), if \(n \geq 1\)}
\end{quote}

It is, of course, easy to see that the recurrence relation definition is
equivalent to the previous definition. But how can we prove it?

To prove that the above definitions of the factorial function are
equivalent, we can use \emph{mathematical induction} over the natural
numbers.

\emph{Mathematical induction:} To prove a logical proposition \(P(n)\)
holds for any natural number \(n\), we must show two things:

\begin{itemize}
\tightlist
\item
  For the \emph{base case} \(n = 0\), show that \(P(0)\) holds.
\item
  For the \emph{inductive case} \(n = m + 1\), show that, if \(P(m)\)
  holds for some natural number \(m\), then \(P(m+1)\) also holds.
\end{itemize}

The \(P(m)\) assumption is called the \emph{induction hypothesis}.

Now let's prove that the two definitions \emph{fact} and \emph{fact'}
are equivalent.

\textbf{Prove} For all natural numbers \(n\), \emph{fact}\((n) =\)
\emph{fact'}\((n)\).

\textbf{Base case \(n = 0\).}

\begin{longtable}[]{@{}ll@{}}
\toprule
& \emph{fact}\((0)\)\tabularnewline
\(=\) & \{ definition of \emph{fact} (left to right) \}\tabularnewline
& \((\Pi i : 1 \leq i \leq 0 : i)\)\tabularnewline
\(=\) & \{ empty range for \(\Pi\), 1 is the identity element of
\(\times\) \}\tabularnewline
& \(1\)\tabularnewline
\(=\) & \{ definition of \emph{fact'} (first leg, right to left)
\}\tabularnewline
& \emph{fact'}\((0)\)\tabularnewline
\bottomrule
\end{longtable}

\textbf{Inductive case \(n = m+1\).}\\
Given induction hypothesis \emph{fact}\((m) =\) \emph{fact'}\((m)\),
prove \emph{fact}\((m+1) =\)\emph{fact'}\((m+1)\).

\begin{longtable}[]{@{}ll@{}}
\toprule
& \emph{fact'\((m+1)\)}\tabularnewline
\(=\) & \{ definition of \emph{fact} (left to right) \}\tabularnewline
& \((\Pi i : 1 \leq i \leq m+1 : i)\)\tabularnewline
\(=\) & \{ \(m+1 > 0\), so \(m+1\) term exists, split it out
\}\tabularnewline
& \((m+1) \times (\Pi i : 1 \leq i \leq m : i)\)\tabularnewline
\(=\) & \{ definition of \emph{fact} (right to left) \}\tabularnewline
& \((m+1) \times\) \emph{fact}\((m)\)\tabularnewline
\(=\) & \{ induction hypothesis \}\tabularnewline
& \((m+1) \times\) \emph{fact'}\((m)\)\tabularnewline
\(=\) & \{ \(m+1 > 0\), definition of \emph{fact'} (second leg, right to
left) \}\tabularnewline
& \emph{fact'}\((m+1)\)\tabularnewline
\bottomrule
\end{longtable}

Therefore, we have proved \emph{fact}\((n) =\) \emph{fact'}\((n)\) for
all natural numbers \(n\). QED

In the inductive step above, we explicitly state the induction
hypothesis and assertion we wish to prove in terms of a different
variable name (\(m\) instead of \(n\)) than the original statement. This
helps to avoid the confusion in use of the induction hypothesis that
sometimes arises.

We use an equational style of reasoning. To prove that an equation
holds, we begin with one side and prove that it is equal to the other
side. We repeatedly ``substitute equals for equal'' until we get the
other expression.

Each transformational step is justified by a definition, a known
property of arithmetic, or the induction hypothesis.

The structure of this inductive argument closely matches the structure
of the recursive definition of \emph{fact'}.

What does this have to do with functional programming? Many of the
functions we will define in these notes have a recursive structure
similar to \emph{fact'}. The proofs and program derivations that we do
will resemble the inductive argument above.

Recursion, induction, and iteration are all manifestations of the same
phenomenon.

\subsubsection{Operations}\label{operations}

A function

\begin{quote}
\(\oplus : (A \times A) \rightarrow A\)
\end{quote}

is called a \emph{binary operation on} \(A\). We usually write binary
operations in \emph{infix} form:

\begin{quote}
\emph{a \(\oplus\) a'}
\end{quote}

We often call a two-argument function of the form

\begin{quote}
\(\oplus : (A \times B) \rightarrow C\)
\end{quote}

a binary operation as well. We can write this two argument function in
the equivalent \emph{curried} form:

\begin{quote}
\(\oplus : A \rightarrow (B \rightarrow C)\)
\end{quote}

The curried form shows a multiple-paramenter function in a form where
the function takes the arguments one at a time, returning the resulting
function with one fewer arguments.

Let \(\oplus\) be a binary operation on some set \(A\) and \(x\), \(y\),
and \(z\) be elements of \(A\). We can define the following kinds of
properties.

\begin{itemize}
\item
  Operation \(\oplus\) is \emph{closed} on \(A\) if and only if
  \(x \oplus y \in A\) for any \(x,y \in A\). That is, the operation is
  a total function on its domain.
\item
  Operation \(\oplus\) is \emph{associative} if and only if
  \((x \oplus y) \oplus z = x \oplus (y \oplus z)\) for \(x,y,z \in A\).
\item
  Operation \(\oplus\) is \emph{commutative} (also called
  \emph{symmetric}) if and only if \(x \oplus y = y \oplus x\) for
  \(x,y \in A\).
\item
  An element \(e\) of set \(A\) is

  \begin{itemize}
  \tightlist
  \item
    a \emph{left identity} of \(\oplus\) if and only if
    \(e \oplus x = x\) for any \(x \in A\)
  \item
    a \emph{right identity} of \(\oplus\) if and only if
    \(x \oplus e = x\) for any \(x \in A\)
  \item
    an \emph{identity} of \(\oplus\) if and only if it is both a left
    and a right identity.
  \end{itemize}

  An identity of an operation is called a \emph{unit} of the operation.
\item
  An element \(z\) of set \(A\) is

  \begin{itemize}
  \tightlist
  \item
    a \emph{left zero} of \(\oplus\) if and only if \(z \oplus x = z\)
    for any \(x \in A\)
  \item
    a \emph{right zero} of \(\oplus\) if and only if \(x \oplus z = z\)
    for any \(x \in A\)
  \item
    a \emph{zero} of \(\oplus\) if and only if it is both a right and a
    left zero
  \end{itemize}
\item
  If \(e\) is the identity of \(\oplus\) and \(x \oplus y = e\) for some
  \(x\) and \(y\), then

  \begin{itemize}
  \tightlist
  \item
    \(x\) is a \emph{left inverse} of \(y\)
  \item
    \(y\) is a \emph{right inverse} of \(x\).
  \end{itemize}

  Elements \(x\) and \(y\) are inverses of each other if
  \(x \oplus y = e = y \oplus x\).
\end{itemize}

For example, the addition operation \texttt{+} on natural numbers is
closed, associative, and commutative and has the identity element 0. It
has neither a left or right zero element and the only element with a
left or right inverse is 0. If we consider the set of all integers, then
all elements also have inverses.

Also, the multiplication operation \texttt{*} on natural numbers (or on
all integers) is closed, associative, and commutative and has identity
element 1 and zero element 0. Only value 1 has a left or right inverse.

However, the subtraction operation on natural numbers is not closed,
associative, or commutative and has neither a left nor right zero. The
value 0 is subtraction's right identity, but subtraction has no left
identity. Each element is its own right and left inverse. If we consider
all integers, then the operation is also closed.

\subsubsection{Algebraic structures}\label{algebraic-structures}

We can also define \emph{algebraic structures} for binary operations on
a set with certain properties.

\begin{itemize}
\item
  If \(\oplus\) is an \emph{associative} operation closed on \emph{A},
  then \(\oplus\) and \emph{A} are said to form a \emph{semigroup}.
\item
  A semigroup that also has an \emph{identity} element is called a
  \emph{monoid}.
\item
  A monoid that is also \emph{commutative} is a \emph{commutative
  monoid}.
\item
  If every element of a monoid has an inverse then the monoid is called
  a \emph{group}.
\item
  If a monoid or group is also commutative, then it is said to be
  \emph{Abelian}.
\end{itemize}

For example, addition on natural numbers forms a commutative monoid and
on integers forms an Abelian group.

\subsection{Exercises}\label{exercises}

TODO: Add

\subsection{References}\label{references}

TODO: Complete and update

\begin{description}
\tightlist
\item[{[}Craig 2007{]}]
Iain D. Craig. \emph{Object-Oriented Programming Languages}, Springer
2007. (Especially chapter 1 ``Introduction'' and chapter 3 ``Prototype
and Actor Languages'')
\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[{[}Horstmann 1995{]}]
Cay S. Horstmann. \emph{Mastering Object-Oriented Design in C++}, Wiley,
1995. (Especially chapters 3-6 on ``Implementing Classes'',
``Interfaces'', ``Object-Oriented Design'', and ``Invariants'')
\item[{[}Wikipedia 2017{]}]
Wikipedia article on
\href{http://en.wikipedia.org/wiki/History_of_programming_languages}{``History
of Programming Languages''}
\end{description}

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

TODO: Complete and update

Programming language paradigms (imperative, declarative, functional,
relational or logic language), program state, implicit versus explicit
state, execution of commands versus evaluation of expressions,
abstraction, procedural abstraction, data abstraction, procedure,
function, method

\end{document}
