\PassOptionsToPackage{unicode=true}{hyperref} % options for packages loaded elsewhere
\PassOptionsToPackage{hyphens}{url}
%
\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
  \usepackage{textcomp} % provides euro and other symbols
\else % if luatex or xelatex
  \usepackage{unicode-math}
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage[]{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\usepackage{hyperref}
\hypersetup{
            pdftitle={CSci 658-01: Software Language Engineering Python 3 Reflexive Metaprogramming Chapter 2},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\usepackage{color}
\usepackage{fancyvrb}
\newcommand{\VerbBar}{|}
\newcommand{\VERB}{\Verb[commandchars=\\\{\}]}
\DefineVerbatimEnvironment{Highlighting}{Verbatim}{commandchars=\\\{\}}
% Add ',fontsize=\small' for more characters per line
\newenvironment{Shaded}{}{}
\newcommand{\AlertTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\AnnotationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\AttributeTok}[1]{\textcolor[rgb]{0.49,0.56,0.16}{#1}}
\newcommand{\BaseNTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\BuiltInTok}[1]{#1}
\newcommand{\CharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\CommentTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textit{#1}}}
\newcommand{\CommentVarTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\ConstantTok}[1]{\textcolor[rgb]{0.53,0.00,0.00}{#1}}
\newcommand{\ControlFlowTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\DataTypeTok}[1]{\textcolor[rgb]{0.56,0.13,0.00}{#1}}
\newcommand{\DecValTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\DocumentationTok}[1]{\textcolor[rgb]{0.73,0.13,0.13}{\textit{#1}}}
\newcommand{\ErrorTok}[1]{\textcolor[rgb]{1.00,0.00,0.00}{\textbf{#1}}}
\newcommand{\ExtensionTok}[1]{#1}
\newcommand{\FloatTok}[1]{\textcolor[rgb]{0.25,0.63,0.44}{#1}}
\newcommand{\FunctionTok}[1]{\textcolor[rgb]{0.02,0.16,0.49}{#1}}
\newcommand{\ImportTok}[1]{#1}
\newcommand{\InformationTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\newcommand{\KeywordTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{\textbf{#1}}}
\newcommand{\NormalTok}[1]{#1}
\newcommand{\OperatorTok}[1]{\textcolor[rgb]{0.40,0.40,0.40}{#1}}
\newcommand{\OtherTok}[1]{\textcolor[rgb]{0.00,0.44,0.13}{#1}}
\newcommand{\PreprocessorTok}[1]{\textcolor[rgb]{0.74,0.48,0.00}{#1}}
\newcommand{\RegionMarkerTok}[1]{#1}
\newcommand{\SpecialCharTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\SpecialStringTok}[1]{\textcolor[rgb]{0.73,0.40,0.53}{#1}}
\newcommand{\StringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\VariableTok}[1]{\textcolor[rgb]{0.10,0.09,0.49}{#1}}
\newcommand{\VerbatimStringTok}[1]{\textcolor[rgb]{0.25,0.44,0.63}{#1}}
\newcommand{\WarningTok}[1]{\textcolor[rgb]{0.38,0.63,0.69}{\textbf{\textit{#1}}}}
\usepackage{graphicx,grffile}
\makeatletter
\def\maxwidth{\ifdim\Gin@nat@width>\linewidth\linewidth\else\Gin@nat@width\fi}
\def\maxheight{\ifdim\Gin@nat@height>\textheight\textheight\else\Gin@nat@height\fi}
\makeatother
% Scale images if necessary, so that they will not overflow the page
% margins by default, and it is still possible to overwrite the defaults
% using explicit options in \includegraphics[width, height, ...]{}
\setkeys{Gin}{width=\maxwidth,height=\maxheight,keepaspectratio}
\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 658-01: Software Language Engineering\\
Python 3 Reflexive Metaprogramming\\
Chapter 2}
\author{\textbf{H. Conrad Cunningham}}
\date{\textbf{4 May 2018}}

\begin{document}
\maketitle

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

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

\setcounter{section}{1}
\newpage

\hypertarget{basic-features-supporting-metaprogramming}{%
\section{Basic Features Supporting
Metaprogramming}\label{basic-features-supporting-metaprogramming}}

In this chapter we examine the characteristics and basic features of
Python 3 upon which the reflexive metaprogramming features build.

Python 3 is an \emph{object-oriented} language built on top of an
\emph{object-based}, \emph{imperative} language. The language is
typically \emph{compiled} to a sequence of instructions for a
\emph{virtual machine}, which is then \emph{interpreted}.

TODO: Better introduce the range of content of this chapter

\hypertarget{objects}{%
\subsection{Objects}\label{objects}}

All Python 3 data are treated as \emph{objects}.

A Python 3 object has the following \emph{essential} characteristics of
objects (as described in the
\href{../ProgrammingParadigms.html\#object-oriented}{Programming
Paradigms} notes {[}Cunningham 2018a{]}):

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\item
  a \emph{state} (value) drawn from a set of possible values

  The state may consist of several distinct data attributes. In this
  case, the set of possible values is the Cartesian product of the sets
  of possible values of each attribute.
\item
  a set of \emph{operations} that access and/or mutate the state
\item
  a unique \emph{identity} (e.g., address in memory)
\end{enumerate}

A Python 3 object has one of the two \emph{important but nonessential}
characteristics of objects (as described in the
\href{../ProgrammingParadigms.html\#object-oriented}{Programming
Paradigms} notes {[}Cunningham 2018a{]}). Python 3 does:

\begin{enumerate}
\def\labelenumi{\alph{enumi}.}
\setcounter{enumi}{3}
\item
  \emph{not} enforce \emph{encapsulation} of the state within the
  object, instead relying mostly upon programming conventions to hide
  private information
\item
  exhibit an \emph{independent lifecycle} (i.e., has a different
  lifetime than the code that created it)
\end{enumerate}

As we see in a later section, each object has a distinct dictionary, the
directory, that maps the local names to the data attributes and
operations.

Python 3 typically uses dot notation to access an object's data
attributes and operations.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    obj.data   }\CommentTok{# access data attribute of obj }
\NormalTok{    obj.op     }\CommentTok{# access operation of obj }
\NormalTok{    obj.op()   }\CommentTok{# invoke operation of obj }
\end{Highlighting}
\end{Shaded}

Some objects are immutable and others are mutable. The \emph{state}
(i.e., value) of \emph{immutable} objects (e.g., numbers, booleans,
strings, and tuples) cannot be changed after creation. The state of
\emph{mutable} objects (e.g., lists, dictionaries, and sets) can be
changed in place after creation.

Caveat: We cannot modify a Python 3 tuple's structure after its
creation. However, if the components of a tuple are themselves mutable
objects, they can be changed in-place.

All Python 3 objects have a type. What does type mean?

\hypertarget{type-system-concepts}{%
\subsection{Type System Concepts}\label{type-system-concepts}}

The term ``type'' tends to be used in many different ways in programming
languages.

\hypertarget{types-and-subtypes}{%
\subsubsection{Types and subtypes}\label{types-and-subtypes}}

Conceptually, a \emph{type} is a set of values (i.e., possible states)
and a set of operations defined on the values in that set.

Similarly, a type \texttt{S} is (a behavioral) \emph{subtype} of type
\texttt{T} if the set of values of type \texttt{S} is a ``subset'' of
the values in set \texttt{T} and set of operations of type \texttt{S} is
a ``superset'' of the operations of type \texttt{T}. That is, we can
safely \emph{substitute} elements of subtype \texttt{S} for elements of
type \texttt{T} because \texttt{S}'s operations behave the ``same'' as
\texttt{T}'s operations . This is known as the \emph{Liskov Substitution
Principle} {[}Liskov 1987{]} {[}Wikipedia 2018d{]}.

Consider a type representing all furniture and a type representing all
chairs. In general, we consider the set of chairs to be a subset of the
set of furniture. A chair should have all the general characteristics of
furniture, but it may have additional characteristics specific to
chairs.

If we can perform an operation on furniture in general, we should be
able to perform the same operation on a chair under the same
circumstances and get the same result. Of course, there may be
additional operations we can perform on chairs that are not applicable
to furniture in general.

Thus the type of all chairs is a subtype of the type of all furniture
according to the Liskov Substitution Principle.

\hypertarget{constants-variables-and-expressions}{%
\subsubsection{Constants, variables, and
expressions}\label{constants-variables-and-expressions}}

Now consider the types of the basic program elements.

A \emph{constant} has whatever types it is defined to have in the
context in which it is used. For example, the constant symbol \texttt{1}
might represent an integer, a real number, a complex number, a single
bit, etc., depending upon the context.

A \emph{variable} has whatever types its value has at a particular point
in time.

An \emph{expression} has whatever types its evaluation yields based on
the types of the variables, constants, and operations from which it is
constructed.

\hypertarget{static-and-dynamic}{%
\subsubsection{Static and dynamic}\label{static-and-dynamic}}

In a \emph{statically typed} language, the types of a variable or
expression can be determined from the program source code and checked at
``compile time'' (i.e., during the syntactic and semantic processing in
the front-end of a language processor). Such languages may require at
least some of the types of variables or expressions to be
\emph{declared} explicitly, while others may be \emph{inferred}
implicitly from the context.

Java, Scala, and Haskell are examples of statically typed languages.

In a \emph{dynamically typed language}, the specific types of a variable
or expression cannot be determined at ``compile time'' but can be
checked at runtime.

Lisp, Python, and Lua are examples of dynamically typed languages.

Of course, most languages use a mixture of static and dynamic typing.
For example, Java objects defined within an inheritance hierarchy must
be bound dynamically to the appropriate operations at runtime. Also Java
objects declared of type \texttt{Object} (the root class of all
user-defined classes) often require explicit runtime checks or
coercions.

\hypertarget{nominal-and-structural}{%
\subsubsection{Nominal and structural}\label{nominal-and-structural}}

In a language with \emph{nominal typing}, the type of an object is based
on the type \emph{name} assigned when the object is created. Two objects
have the same type if they have the same type name. A type \texttt{S} is
a subtype of type \texttt{T} only if \texttt{S} is explicitly declared
to be a subtype of \texttt{T}.

For example, Java is primarily a nominally typed language. It assigns
types to an object based on the name of the class from which the object
is instantiated and the superclasses extended and interfaces implemented
by that class.

However, Java does not guarantee that subtypes satisfy the Liskov
Substitution Principle. For example, a subclass might not implement an
operation in a manner that is compatible with the superclass. (The
behavior of subclass objects are this different from the behavior of
superclass objects.) Ensuring that Java subclasses preserve the
Substitution Principle is considered good programming practice in most
circumstances.

In a language with \emph{structural typing}, the type of an object based
on the \emph{structure} of the object. Two objects have the same type if
they have the ``same'' structure; that is, they have the same
\emph{public} data attributes and operations and these are themselves of
compatible types.

In structurally typed languages, a type \texttt{S} is a subtype of type
\texttt{T} only if \texttt{S} has all the public data values and
operations of type \texttt{T} and the data values and operations are
themselves of compatible types. Subtype \texttt{S} may have additional
data values and operations not in \texttt{T}.

Haskell is primarily a structurally typed language.

\hypertarget{python-type-system}{%
\subsection{Python Type System}\label{python-type-system}}

What about Python 3's type system?

In terms of the discussion in the previous sections, all Python 3
objects can be considered as having one or more conceptual types at a
particular point in time. The types may change over time because the
program can change the possible set of data attributes and operations
associated with the object.

A Python 3 variable is bound to an object by an assignment statement or
its equivalent. Python 3 variables are thus dynamically typed, as are
Python expressions.

Although a Python 3 program usually constructs an object within a
particular nominal type hierarchy (e.g., as an instance of a class),
this may not fully describe the type of the object, even initially. And
the ability to dynamically add, remove, and modify attributes (both data
fields and operations) means the type can change as the program
executes.

The type of a Python 3 object is determined by \emph{what it can do} --
what data it can hold and what operations it can perform on that data --
rather than \emph{how it was created}. We sometimes call this
\emph{dynamic, structural typing} approach \emph{duck typing}. (If it
walks like a duck and quacks like a duck, then it is a duck, even if is
declared as a snake.)

For example, we can say that any object is of an \emph{iterable} type if
it implements an \texttt{\_\_iter\_\_} operation that returns a valid
iterator object. An iterator object must implement a
\texttt{\_\_next\_\_} operation that retrieves the next element of the
``collection'' and must raise a \texttt{StopIteration} exception if no
more elements are available.

In Python 3, we sometimes refer to a type like iterable as a
\emph{protocol}. That is, it is a, perhaps informal, \emph{interface}
that objects are expected to satisfy in certain circumstances.

\hypertarget{builtin-types}{%
\subsection{Builtin Types}\label{builtin-types}}

Python 3 provides several built-in types and subtypes, which are named
and implemented in the core language. When displayed, these types are
shown as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
\end{Highlighting}
\end{Shaded}

That is, the value is an instance of a \emph{class} named \texttt{int}.
Python 3 uses the term \emph{class} to describe its nominal types.

We can query the nominal type of an object \texttt{obj} with the
function call \texttt{type(obj)}. In the following discussion, we show
the results from calling this function interactively in Python 3 REPL
(Read-Evaluate-Print Loop) sessions.

For the purpose of our discussion, the primary built-in types include:`

\begin{itemize}
\tightlist
\item
  Singleton types
\item
  Number types
\item
  Sequence types
\item
  Mapping types
\item
  Other types (e.g., set types and callable, class, module, user-defined
  object types)
\end{itemize}

TODO: Probably should elaborate the ``other types'' more than currently.

\hypertarget{singleton-types}{%
\subsubsection{Singleton types}\label{singleton-types}}

Python 3 has single-element types used for special purposes.

\hypertarget{none}{%
\paragraph{\texorpdfstring{\texttt{None}}{None}}\label{none}}

The name \texttt{None} denotes a value of a singleton type. That is, the
type has one element written as \texttt{None}.

Python programs normally use \texttt{None} to mean there is no
meaningful value of another type.

\hypertarget{notimplemented}{%
\paragraph{\texorpdfstring{\texttt{NotImplemented}}{NotImplemented}}\label{notimplemented}}

The name \texttt{NotImplemented} also denotes a value of a singleton
type. Python programs normally ruse his value to mean that an arithmetic
or comparison operation is not implemented.

\hypertarget{number-types}{%
\subsubsection{Number types}\label{number-types}}

Core Python 3 supports four types of numbers:

\begin{itemize}
\tightlist
\item
  integers
\item
  real numbers
\item
  complex numbers
\item
  Booleans
\end{itemize}

\hypertarget{integers-int}{%
\paragraph{\texorpdfstring{Integers
(\texttt{int})}{Integers (int)}}\label{integers-int}}

Type \texttt{int} denotes the set of integers. They are encoded in a
variant of two's complement binary numbers in the underlyng hardware.
They are of unbounded precision, but they are, of course, limited in
size by the available virtual memory.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\DecValTok{1}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\OperatorTok{-}\DecValTok{14}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=} \DecValTok{2}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
\end{Highlighting}
\end{Shaded}

\hypertarget{real-numbers-float}{%
\paragraph{\texorpdfstring{Real numbers
(\texttt{float})}{Real numbers (float)}}\label{real-numbers-float}}

Type \texttt{float} denotes the subset of the real numbers that can be
encoded as double precision floating point numbers in the underlying
hardware.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\FloatTok{1.01}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'float'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\OperatorTok{-}\FloatTok{14.3}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'float'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=} \DecValTok{2} 
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ y }\OperatorTok{=} \FloatTok{2.0}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(y)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'float'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{==}\NormalTok{ y  }\CommentTok{# Note result of equality comparison}
    \VariableTok{True}
\end{Highlighting}
\end{Shaded}

\hypertarget{complex-numbers-complex}{%
\paragraph{\texorpdfstring{Complex numbers
(\texttt{complex})}{Complex numbers (complex)}}\label{complex-numbers-complex}}

Type \texttt{complex} denotes a subset of the complex numbers encoded as
a pair of floats, one for the real part and one for the imaginary part.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{complex}\NormalTok{(}\StringTok{'1+2j'}\NormalTok{)) }\CommentTok{# real part 1, imaginary part 2}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'complex'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{complex}\NormalTok{(}\StringTok{'1'}\NormalTok{) }\OperatorTok{==} \FloatTok{1.0}   \CommentTok{# Note result of comparison}
    \VariableTok{True} 
    \OperatorTok{>>>} \BuiltInTok{complex}\NormalTok{(}\StringTok{'1'}\NormalTok{) }\OperatorTok{==} \DecValTok{1}     \CommentTok{# Note result of comparison}
    \VariableTok{True} 
\end{Highlighting}
\end{Shaded}

\hypertarget{booleans-bool}{%
\paragraph{\texorpdfstring{Booleans
(\texttt{bool})}{Booleans (bool)}}\label{booleans-bool}}

Type \texttt{bool} denotes the set of Boolean values \texttt{False} and
\texttt{True}; in Python, this is a subtype of \texttt{int} with
\texttt{False} and \texttt{True} having the values 0 and 1,
respectively.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\VariableTok{False}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'bool'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\VariableTok{True}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'bool'}\OperatorTok{>}
    \OperatorTok{>>>} \VariableTok{True} \OperatorTok{==} \DecValTok{1}
    \VariableTok{True}
\end{Highlighting}
\end{Shaded}

Making \texttt{bool} a subtype of \texttt{int} is an unfortunate legacy
design choice from the early days of Python. It is better not to rely on
this feature in Python 3 programs.

\hypertarget{truthy-and-falsy-values}{%
\paragraph{Truthy and falsy values}\label{truthy-and-falsy-values}}

Python 3 programs can test any object as if it was a Boolean
(e.g.~within the condition of an \texttt{if} or \texttt{while} statement
or as an operand of a Boolean operation).

An object is \emph{falsy} (i.e.~considered as \texttt{False}) if its
class defines

\begin{itemize}
\item
  a special method \texttt{\_\_bool\_\_()} that, when called with the
  object, returns \texttt{False}
\item
  a special method \texttt{\_\_len\_\_()} that returns \texttt{0}
\end{itemize}

Note: We discuss special methods in a later section.

Otherwise, the object is \emph{truthy} (i.e.~considered as
\texttt{True}).

The singleton value \texttt{NotImplemented} is explicitly defined as
truthy.

Falsy built-in values include:

\begin{itemize}
\item
  constants \texttt{False} and \texttt{None}
\item
  numeric values of zero such as \texttt{0}, \texttt{0.0}, and
  \texttt{0j}
\item
  empty sequences and collections such as
  \texttt{\textquotesingle{}\textquotesingle{}}, \texttt{()},
  \texttt{{[}{]}}, and \texttt{\{\}} (defined below)
\end{itemize}

Unless otherwise documented, any function expected to return a Boolean
result should return \texttt{False} or \texttt{0} for false and
\texttt{True} or \texttt{1} for true. However, the Boolean operations
\texttt{or} and \texttt{and} should always return one of their operands.

\hypertarget{sequence-types}{%
\subsubsection{Sequence types}\label{sequence-types}}

A \emph{sequence} denotes a serially ordered collection of zero or more
objects. An object may occur more than once in a sequence.

Python 3 supports a number of core sequence types. Some sequences have
immutable structures and some have mutable.

\hypertarget{immutable-sequences}{%
\paragraph{Immutable sequences}\label{immutable-sequences}}

An immutable sequence is a sequence in which the structure cannot be
changed after initialization.

\hypertarget{str}{%
\subparagraph{\texorpdfstring{\texttt{str}}{str}}\label{str}}

Type \texttt{str} (string) denotes sequences of text characters -- that
is, of Unicode code points in Python 3. We can express strings
syntactically by putting the characters between single, double, or
triple quotes. The latter supports multi-line strings.

Python does not have a separate character type; a characer is a
single-element \texttt{str}.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\StringTok{'Hello world'}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'str'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\StringTok{"Hi Earth"}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'str'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\StringTok{'''}
\StringTok{    ... Can have embedded newlines}
\StringTok{    ... '''}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'str'}\OperatorTok{>}
\end{Highlighting}
\end{Shaded}

\hypertarget{tuple}{%
\subparagraph{\texorpdfstring{\texttt{tuple}}{tuple}}\label{tuple}}

Type \texttt{tuple} denotes fixed length, heterogeneous sequences of
objects. We can express tuples syntactically as sequences of
comma-separated expressions in parentheses.

The tuple itself is immutable, but the objects in the sequence might be
mutable.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(())    }\CommentTok{# empty tuple}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'tuple'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{((}\DecValTok{1}\NormalTok{,))  }\CommentTok{# one-element tuple}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'tuple'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=}\NormalTok{ (}\DecValTok{1}\NormalTok{,}\StringTok{'Ole Miss'}\NormalTok{)  }\CommentTok{# mixed elements}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'tuple'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x[}\DecValTok{0}\NormalTok{]        }\CommentTok{# access element with index 0}
    \DecValTok{1}
    \OperatorTok{>>>}\NormalTok{ x[}\DecValTok{1}\NormalTok{]        }\CommentTok{# access element with index 1}
    \CommentTok{'Ole Miss'}
\end{Highlighting}
\end{Shaded}

\hypertarget{bytes}{%
\subparagraph{\texorpdfstring{\texttt{bytes}}{bytes}}\label{bytes}}

Type \texttt{bytes} denotes sequences of 8-bit bytes. We can express
these syntactically as ASCII character strings prefixed by a
``\texttt{b}''.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(b}\StringTok{'Hello}\CharTok{\textbackslash{}n}\StringTok{   World!'}\NormalTok{) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'bytes>}
\end{Highlighting}
\end{Shaded}

\hypertarget{mutable-sequences}{%
\paragraph{Mutable sequences}\label{mutable-sequences}}

A mutable sequence is a sequence in which the structure can be changed
after initialization.

\hypertarget{list}{%
\subparagraph{\texorpdfstring{\texttt{list}}{list}}\label{list}}

Type \texttt{list} denotes variable-length, heterogeneous sequences of
objects. We can express lists syntactically as comma-separated sequence
of expressions between square brackets.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{([])}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'list'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{([}\DecValTok{3}\NormalTok{])}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'list'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=}\NormalTok{ [}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{] }\OperatorTok{+}\NormalTok{ [}\StringTok{'four'}\NormalTok{,}\StringTok{'five'}\NormalTok{] }\CommentTok{# concatenation}
    \OperatorTok{>>>}\NormalTok{ x}
\NormalTok{    [}\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\StringTok{'four'}\NormalTok{, }\StringTok{'five'}\NormalTok{]}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'list'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ y }\OperatorTok{=}\NormalTok{ x[}\DecValTok{1}\NormalTok{:}\DecValTok{3}\NormalTok{] }\CommentTok{# get slice of list}
    \OperatorTok{>>>}\NormalTok{ y}
\NormalTok{    [}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{]}
    \OperatorTok{>>>}\NormalTok{ y[}\DecValTok{0}\NormalTok{] }\OperatorTok{=} \DecValTok{3}   \CommentTok{# assign to list index 0}
\NormalTok{    [}\DecValTok{3}\NormalTok{, }\DecValTok{3}\NormalTok{]}
\end{Highlighting}
\end{Shaded}

\hypertarget{bytearray}{%
\subparagraph{\texorpdfstring{\texttt{bytearray}}{bytearray}}\label{bytearray}}

Type \texttt{bytearray} denotes mutable sequences of 8-bit bytes, that
is otherwise like type \texttt{bytes}. They are constructed by calling
the function \texttt{bytearray()}.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{bytearray}\NormalTok{(b}\StringTok{'Hello}\CharTok{\textbackslash{}n}\StringTok{   World!'}\NormalTok{)) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'bytes>}
\end{Highlighting}
\end{Shaded}

\hypertarget{mapping-types}{%
\subsubsection{Mapping types}\label{mapping-types}}

Type \texttt{dict} (dictionary) denotes mutable finite sets of key-value
pairs, where the \emph{key} is an index into the set for the value with
which it is paired.

The key must be an immutable object to enable use of hashing. However,
the associated value objects may be mutable and the membership in the
set may change.

We can express dictionaries syntactically in various ways such as
comma-separated lists of key-value pairs with braces.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=}\NormalTok{ \{ }\DecValTok{1}\NormalTok{ : }\StringTok{"one"}\NormalTok{ \}}
    \OperatorTok{>>>}\NormalTok{ x}
\NormalTok{    \{}\DecValTok{1}\NormalTok{: }\StringTok{'one'}\NormalTok{\}}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'dict'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x[}\DecValTok{1}\NormalTok{]}
    \CommentTok{'one'}
    \OperatorTok{>>>}\NormalTok{ x.update(\{ }\DecValTok{2}\NormalTok{ : }\StringTok{"two"}\NormalTok{ \}) }\CommentTok{# add to dictionary}
    \OperatorTok{>>>}\NormalTok{ x}
\NormalTok{    \{}\DecValTok{1}\NormalTok{: }\StringTok{'one'}\NormalTok{, }\DecValTok{2}\NormalTok{: }\StringTok{'two'}\NormalTok{\}}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'dict'}\OperatorTok{>}
    \OperatorTok{>>>} \KeywordTok{del}\NormalTok{ x[}\DecValTok{1}\NormalTok{]  }\CommentTok{# delete element with key}
    \OperatorTok{>>>}\NormalTok{ x}
\NormalTok{    \{}\DecValTok{2}\NormalTok{: }\StringTok{'two'}\NormalTok{\}}
\end{Highlighting}
\end{Shaded}

\hypertarget{other-object-types}{%
\subsubsection{Other object types}\label{other-object-types}}

We discuss callable objects (e.g.~functions), class objects, module
objects, and user-defined types (classes) below.

We do not discuss the set types here.

TODO: Probably should add some discussion of sets here

\hypertarget{statements}{%
\subsection{Statements}\label{statements}}

The basic building blocks of Python 3 programs include statements,
functions, classes, and modules. We discuss those in this and the
following subsections.

Python 3 \emph{statements} consist primarily of assignment statements
and other mutator operation and constructs to control the order in which
those are executed.

Statements execute in the order defined in the program text (as shown
below). Each statement executes in an \emph{environment} that assigns
values to the names (e.g., of variables and functions) that occur in the
statement.

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    statement1}
\NormalTok{    statement2}
\NormalTok{    statement3}
\NormalTok{    ...}
\end{Highlighting}
\end{Shaded}

TODO: Do I need to say more here about kinds of statements? Give a
reference? an example?

\hypertarget{functions}{%
\subsection{Functions}\label{functions}}

Python 3 \emph{functions} are program units that take zero or more
\emph{arguments} and \emph{return} a corresponding value.

The code below shows the general structure of a function definition.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ my_func(x, y, z):}
\NormalTok{        statement1}
\NormalTok{        statement2}
\NormalTok{        statement3}
        \ControlFlowTok{return}\NormalTok{ my_loc_var}
\end{Highlighting}
\end{Shaded}

If a function does not explicitly return a value, it implicitly returns
the singleton object \texttt{None}.

When a program \emph{calls} a function, it passes a \emph{reference}
(pointer) to each \emph{argument} object. These references are
\emph{bound} to the corresponding \emph{parameter} names, which are
\emph{local} variables of the function.

If we assign a new object to the parameter variable in the called
function, then the variable binds to the new object. This new binding is
\emph{not visible} to the calling program.

However, if we apply a mutator or destructor to the parameter and the
argument object is mutable, we can modify the actual argument object.
The modified value is \emph{visible} to the calling program.

Of course, if the argument object is not mutable, we cannot modify it's
value.

Functions in Python 3 are \emph{first-class objects}. That is, they are
(callable) objects of type \texttt{function} and, hence, can be stored
in data structures, passed as arguments to functions, and returned as
the value of a functions. Like other objects, they can have associated
data attributes.

To see this, consider the function \texttt{add2} and the following
series of commands in the Python REPL.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \KeywordTok{def}\NormalTok{ add3(x, y, z):}
\NormalTok{    ...     }\ControlFlowTok{return}\NormalTok{ x }\OperatorTok{+}\NormalTok{ y }\OperatorTok{+}\NormalTok{ z}
\NormalTok{    ...}
    \OperatorTok{>>>}\NormalTok{ add3(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{)}
    \DecValTok{6}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(add3)}
    \OperatorTok{<}\KeywordTok{class}\NormalTok{ `function`}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=}\NormalTok{ [add3,}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{,}\DecValTok{6}\NormalTok{]  }\CommentTok{# store function object in list}
    \OperatorTok{>>>}\NormalTok{ x}
\NormalTok{    [}\OperatorTok{<}\NormalTok{function add3 at }\BaseNTok{0x10bf65ea0}\OperatorTok{>}\NormalTok{, }\DecValTok{1}\NormalTok{, }\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{, }\DecValTok{6}\NormalTok{]}
    \OperatorTok{>>>}\NormalTok{ add3.author }\OperatorTok{=} \StringTok{'Cunningham'}  \CommentTok{# set attribute author}
    \OperatorTok{>>>}\NormalTok{ add3.author                 }\CommentTok{# get attribute author}
    \CommentTok{'Cunningham'}
\end{Highlighting}
\end{Shaded}

We call a function a \emph{higher-order function} if it takes another
function as its parameter and/or returns a function as its return value.

\hypertarget{classes}{%
\subsection{Classes}\label{classes}}

A Python 3 \emph{class} is a program construct that defines a new
nominal \emph{type} consisting of data attributes and the operations on
them. When we call a class as a function, it creates a new
\emph{instance} (i.e.~an object) of the associated type.

We define an operation with a method bound to the class. A \emph{method}
is a function that takes an instance (by convention named \texttt{self})
as its first argument. It can access and modify the data attributes of
the instance. The method is also an attribute of the instance.

The code below shows the general structure of a class definition. The
class calls the special method \texttt{\_\_init\_\_} (if present) to
initialize a newly allocated instance of the class.

Note: The special method \texttt{\_\_new\_\_} allocates memory,
constructs a new instance, and then returns it. The interpretrer passes
the new instance to \texttt{\_\_init\_\_}. which initizlizes the new
object's instance variables.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ P: }
        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{): }
            \VariableTok{self}\NormalTok{.my_loc_var }\OperatorTok{=} \VariableTok{None} 
        \KeywordTok{def}\NormalTok{ method1(}\VariableTok{self}\NormalTok{, args): }
\NormalTok{            statement11 }
\NormalTok{            statement12 }
            \ControlFlowTok{return}\NormalTok{ some_value }
        \KeywordTok{def}\NormalTok{ method2(}\VariableTok{self}\NormalTok{, args): }
\NormalTok{            statement21 }
\NormalTok{            statement22 }
            \ControlFlowTok{return}\NormalTok{ some_other_value }
\end{Highlighting}
\end{Shaded}

A class instance defines an environment with local variable and method
names and their values.

In addition to being factories for creating and initializing instances,
Python 3 classes are themselves objects.

Consider the following simple example.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ P:}
        \ControlFlowTok{pass}

    \OperatorTok{>>>}\NormalTok{ x }\OperatorTok{=}\NormalTok{ P()}
    \OperatorTok{>>>}\NormalTok{ x}
    \OperatorTok{<}\NormalTok{__main__.P }\BuiltInTok{object}\NormalTok{ at }\BaseNTok{0x1011a10b8}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(x)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'__main__.P'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(x,P)}
    \VariableTok{True}
    \OperatorTok{>>>}\NormalTok{ P}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'__main__.P'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(P)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(P,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{int}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'int'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{int}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(}\BuiltInTok{int}\NormalTok{,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{True}
\end{Highlighting}
\end{Shaded}

We observe the following:

\begin{itemize}
\item
  Variable \texttt{x} holds a value that is an object of type
  \texttt{P}; the object is an instance of class \texttt{P}.
\item
  Class \texttt{P} is an object of a built-in type named \texttt{type};
  the object is an instance of class \texttt{type}.
\item
  Built-in type \texttt{int} is also an object of the type named
  \texttt{type}.
\end{itemize}

We call a class object like \texttt{P} a \emph{metaobject} because it is
a constructor of ordinary objects {[}Kiczales 1991; Forman 1999{]}.

We call a special class object like \texttt{type} a \emph{metaclass}
because it is a constructor for metaobjects (i.e., class objects)
{[}Kiczales 1991; Forman 1999{]}.

We will look more deeply into these relationships later when we examine
inheritance.

\hypertarget{modules}{%
\subsection{Modules}\label{modules}}

A Python 3 \emph{module} is a file that contains a sequence of
\emph{global} variable, function, and class definitions and executable
statements. If the name of the file is \texttt{mymod.py}, then the
module's name is \texttt{mymod}.

A Python 3 \emph{package} is a directory of Python 3 modules.

A module collects the names and values of its global variables,
functions, and classes into its own private \emph{namespace}
(i.e.~environment). This becomes the global environment for all
definitions and executable statements in the module.

When we execute a module as a script from the Python 3 REPL, the
interpreter executes all the top-level statements in the module's
namespace. If the module contains function or class definitions, then
the interpreter checks those for syntactic correctness and stores the
definitions in the namespace for use later during execution.

\hypertarget{using-import}{%
\subsubsection{\texorpdfstring{Using
\texttt{import}}{Using import}}\label{using-import}}

Suppose we have the following Python 3 code in a file named
\texttt{test.py}.

\begin{Shaded}
\begin{Highlighting}[]
    \CommentTok{# This is module "testmod" in file "testmod.py"}
\NormalTok{    testvar }\OperatorTok{=} \DecValTok{-1}
    
    \KeywordTok{def}\NormalTok{ test(x):}
        \ControlFlowTok{return}\NormalTok{ x}
\end{Highlighting}
\end{Shaded}

We can execute this code in a Python 3 REPL session as follows.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \ImportTok{import}\NormalTok{ testmod   }\CommentTok{# import module in file "testmod.py"}
    \OperatorTok{>>>}\NormalTok{ testmod.testvar  }\CommentTok{# access module's variable "testvar"}
    \DecValTok{-1}
    \OperatorTok{>>>}\NormalTok{ testmod.testvar }\OperatorTok{=} \DecValTok{-2}  \CommentTok{# set variable to new value}
    \OperatorTok{>>>}\NormalTok{ testmod.testvar}
    \DecValTok{-2}
    \OperatorTok{>>>}\NormalTok{ testmod.test(}\DecValTok{23}\NormalTok{) }\CommentTok{# call module's function "test"}
    \DecValTok{23}
    \OperatorTok{>>>}\NormalTok{ test(}\DecValTok{2}\NormalTok{)          }\CommentTok{# must use module prefix "test"}
\NormalTok{    Traceback (most recent call last):}
\NormalTok{      File }\StringTok{"<stdin>"}\NormalTok{, line }\DecValTok{1}\NormalTok{, }\KeywordTok{in} \OperatorTok{<}\NormalTok{module}\OperatorTok{>}
    \PreprocessorTok{TypeError}\NormalTok{: }\StringTok{'module'} \BuiltInTok{object} \KeywordTok{is} \KeywordTok{not} \BuiltInTok{callable}
    \OperatorTok{>>>}\NormalTok{ testmod          }\CommentTok{# below PATH = directory path }
    \OperatorTok{<}\NormalTok{module }\StringTok{'testmod'} \ImportTok{from} \StringTok{'PATH/testmod.py'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(testmod)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'module'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ testmod.}\VariableTok{__name__}
    \CommentTok{'testmod'} 
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{type}\NormalTok{(testmod))}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
\end{Highlighting}
\end{Shaded}

The \texttt{import} statement causes the interpreter to execute all the
top-level statements from the module file and makes the namespace
available for use in the script or another module. In the above, the
imported namespace includes the variable \texttt{testvar} and the
function definition \texttt{test}.

A name from one module (e.g., \texttt{testmod}) can be directly accessed
from an imported module by prefixing the name by the module name using
the dot notation. For example, \texttt{testmod.testvar} accesses
variable \texttt{testvar} in module \texttt{testmod} and
\texttt{testmod.test()} calls function \texttt{test} in module
\texttt{testmod}.

We also see that the imported module \texttt{testmod} is an object of
type (class) \texttt{module}.

\hypertarget{using-from-import}{%
\subsubsection{\texorpdfstring{Using
\texttt{from\ import}}{Using from import}}\label{using-from-import}}

We can also \emph{import} names selectively. In this case, the
definitions of the selected features are copied into the module.

Consider the module \texttt{testimp} below.

\begin{Shaded}
\begin{Highlighting}[]
    \CommentTok{# This is module "testimp" in file "testimp.py"}
    \ImportTok{from}\NormalTok{ testmod }\ImportTok{import}\NormalTok{ testvar, test}

\NormalTok{    myvar }\OperatorTok{=} \DecValTok{10}

    \KeywordTok{def}\NormalTok{ myfun(x, y, z):}
\NormalTok{        mylocvar }\OperatorTok{=}\NormalTok{ myvar }\OperatorTok{+}\NormalTok{ testvar}
        \ControlFlowTok{return}\NormalTok{ mylocvar}
    
    \KeywordTok{class}\NormalTok{ P:}
        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{): }
            \VariableTok{self}\NormalTok{.my_loc_var }\OperatorTok{=} \VariableTok{None} 

        \KeywordTok{def}\NormalTok{ meth1(}\VariableTok{self}\NormalTok{, arg): }
            \ControlFlowTok{return}\NormalTok{ test(arg)}

        \KeywordTok{def}\NormalTok{ meth2(}\VariableTok{self}\NormalTok{, arg): }
            \ControlFlowTok{if}\NormalTok{ arg }\OperatorTok{==} \VariableTok{None}\NormalTok{:}
                \ControlFlowTok{return} \VariableTok{None}
            \ControlFlowTok{else}\NormalTok{:}
\NormalTok{                my_loc_var}\OperatorTok{=}\NormalTok{ arg}
                \ControlFlowTok{return}\NormalTok{ arg}
\end{Highlighting}
\end{Shaded}

The definitions of variable \texttt{testvar} and function \texttt{test}
are copied from module \texttt{testmod} into module \texttt{testimp}'s
namespace. Module \texttt{testimp} can thus access these without prefix
\texttt{testmod}.

Module \texttt{testimp} could import all of the definitions from module
\texttt{testmod} by using the wildcard \texttt{*} instead of the
explicit list.

We can execute the above code in a Python 3 REPL session as follows.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \ImportTok{import}\NormalTok{ testimp}
    \OperatorTok{>>>}\NormalTok{ testimp.myvar}
    \DecValTok{10}
    \OperatorTok{>>>}\NormalTok{ testimp.myfun(}\DecValTok{1}\NormalTok{,}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{)}
    \DecValTok{9}
    \OperatorTok{>>>}\NormalTok{ pp }\OperatorTok{=}\NormalTok{ testimp.P()}
    \OperatorTok{>>>}\NormalTok{ pp.meth1(}\DecValTok{23}\NormalTok{)}
    \DecValTok{23}
    \OperatorTok{>>>}\NormalTok{ pp.meth2(}\DecValTok{14}\NormalTok{)}
    \DecValTok{14}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(pp)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'testimp.P'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(testimp.testmod) }
\NormalTok{    Traceback (most recent call last): }
\NormalTok{      File }\StringTok{"<stdin>"}\NormalTok{, line }\DecValTok{1}\NormalTok{, }\KeywordTok{in} \OperatorTok{<}\NormalTok{module}\OperatorTok{>}
    \PreprocessorTok{NameError}\NormalTok{: name }\StringTok{'testmod'} \KeywordTok{is} \KeywordTok{not}\NormalTok{ defined}
\end{Highlighting}
\end{Shaded}

Note that the \texttt{from\ testmod\ import} statement does not create
an object \texttt{testmod}.

\hypertarget{programming-conventions}{%
\subsubsection{Programming conventions}\label{programming-conventions}}

Python 3 programs typically observe the following conventions:

\begin{itemize}
\item
  All module \texttt{import} and \texttt{import\ from} statements should
  appear at the beginning of the importing module.
\item
  All \texttt{from\ import} statements should specify the imported names
  explicitly rather than using the wildcard \texttt{*} to import all
  names. This avoids polluting the importing module's namespace with
  unneeded names. It also makes the dependencies explicit.
\item
  Any definition whose name begins with an \texttt{\_} (underscore)
  should be kept private to a module and thus should not be imported
  into or accessed directly from other modules.
\end{itemize}

\hypertarget{using-importlib-directly}{%
\subsubsection{\texorpdfstring{Using \texttt{importlib}
directly}{Using importlib directly}}\label{using-importlib-directly}}

TODO: Perhaps move the discussion below of the \texttt{importlib}, a
metaprogramming feature, to a later chapter.

The Python 3 core module \texttt{importlib} exposes the functionality
underlying the \texttt{import} statement to Python 3 programs. In
particular, we can use the function call

\begin{Shaded}
\begin{Highlighting}[]
\NormalTok{    importlib.import_module(}\StringTok{'modname'}\NormalTok{) }\CommentTok{# argument is string}
\end{Highlighting}
\end{Shaded}

to find and import a module from the file named \texttt{modname.py}.
Below we see that this works like an explicit \texttt{import}.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \ImportTok{from}\NormalTok{ importlib }\ImportTok{import}\NormalTok{ import_module}
    \OperatorTok{>>>}\NormalTok{ tm }\OperatorTok{=}\NormalTok{ import_module(}\StringTok{'testmod'}\NormalTok{)}
    \OperatorTok{>>>}\NormalTok{ tm          }\CommentTok{# below PATH = directory path }
    \OperatorTok{<}\NormalTok{module }\StringTok{'testmod'} \ImportTok{from} \StringTok{'PATH/testmod.py'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(tm)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'module'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{type}\NormalTok{(tm))}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
\end{Highlighting}
\end{Shaded}

\hypertarget{statement-execution-and-variable-scope}{%
\subsection{Statement Execution and Variable
Scope}\label{statement-execution-and-variable-scope}}

Statements perform the work of the program -- computing the values of
expressions and assigning the computed values to variables or parts of
data structures.

Statements execute in two scopes: global and local.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  As described above, the \emph{global} scope is the enclosing module's
  environment (a dictionary), as extended by imports of other modules.
\item
  As described above, the \emph{local} scope is the enclosing function's
  dictionary (if the statement is in a function).

  If \texttt{statement} is a string holding a Python 3 statement, then
  we can execute the statement dynamically using the \texttt{exec}
  library function. By default, the statement is executed in the current
  global and local environment, but these environments can be passed in
  explicitly.

  \begin{quote}
  \texttt{exec(statement} {[}\texttt{,} globals {[}\texttt{,} locals{]}
  \texttt{)}
  \end{quote}
\end{enumerate}

Inside a function, variables that are:

\begin{itemize}
\item
  referenced but not assigned a value are assumed to be global
\item
  assigned a value are assumed to be local
\end{itemize}

In the latter case, we can explicitly declare the variable
\texttt{global}. if the desired target variable is defined in the global
scope.

\hypertarget{function-calling-conventions}{%
\subsection{Function Calling
Conventions}\label{function-calling-conventions}}

Consider a module-level function. A function may include a combination
of:

\begin{itemize}
\item
  positional parameters
\item
  keyword parameters
\end{itemize}

There are several different ways we can specify the arguments of
function calls described below.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Using \emph{positional arguments}

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ myfunc(x, y, z): }
\NormalTok{        statement1 }
\NormalTok{        statement2 }
\NormalTok{        ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{, }\DecValTok{30}\NormalTok{)}
\end{Highlighting}
\end{Shaded}
\item
  Using \emph{keyword} arguments

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ myfunc(x, y, z): }
\NormalTok{        statement1 }
\NormalTok{        statement2 }
\NormalTok{        ... }
\NormalTok{    myfunc(z}\OperatorTok{=}\DecValTok{30}\NormalTok{, x}\OperatorTok{=}\DecValTok{10}\NormalTok{, y}\OperatorTok{=}\DecValTok{20}\NormalTok{)}
    \CommentTok{# note different order than in signature}
\end{Highlighting}
\end{Shaded}
\item
  Using \emph{default arguments} set at definition time -- using only
  immutable values (e.g., \texttt{False}, \texttt{None}, string, tuple)
  for defaults

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ myfunc(x, trace }\OperatorTok{=} \VariableTok{False}\NormalTok{, }\BuiltInTok{vars} \OperatorTok{=} \VariableTok{None}\NormalTok{): }
        \ControlFlowTok{if} \BuiltInTok{vars} \KeywordTok{is} \VariableTok{None}\NormalTok{: }
            \BuiltInTok{vars} \OperatorTok{=}\NormalTok{ [] }
\NormalTok{        ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{)}
        \CommentTok{# x=10, trace=False, vars=None}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\BuiltInTok{vars}\OperatorTok{=}\NormalTok{[}\StringTok{'x'}\NormalTok{, }\StringTok{'y'}\NormalTok{])}
        \CommentTok{# x=10, trace=False, vars=['x', 'y'])}
\end{Highlighting}
\end{Shaded}
\item
  Using required positional and \emph{variadic positional} arguments

\begin{Shaded}
\begin{Highlighting}[]
   \KeywordTok{def}\NormalTok{ myfunc(x, }\OperatorTok{*}\NormalTok{args):}
       \CommentTok{# x is a required argument in position 1}
       \CommentTok{# args is tuple of variadic positional args}
       \CommentTok{# name "args" is just convention}
\NormalTok{       ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{, }\DecValTok{30}\NormalTok{)}
        \CommentTok{# x = 10}
        \CommentTok{# args = (20, 30)}
\end{Highlighting}
\end{Shaded}
\item
  Using required positional, variadic positional, and keyword arguments

\begin{Shaded}
\begin{Highlighting}[]
   \KeywordTok{def}\NormalTok{ myfunc(x, }\OperatorTok{*}\NormalTok{args, y):}
       \CommentTok{# x is a required argument in position 1}
       \CommentTok{# args is tuple of variadic positional args}
       \CommentTok{# y is keyword argument (occurs after variadic positional)}
\NormalTok{       ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{, }\DecValTok{30}\NormalTok{, y }\OperatorTok{=} \DecValTok{40}\NormalTok{)}
        \CommentTok{# x = 10}
        \CommentTok{# args = (20, 30)}
        \CommentTok{# y = 40}
\end{Highlighting}
\end{Shaded}
\item
  Using required positional, variadic positional, keyword, and
  \emph{variadic keyword} arguments

\begin{Shaded}
\begin{Highlighting}[]
   \KeywordTok{def}\NormalTok{ myfunc(x, }\OperatorTok{*}\NormalTok{args, y }\OperatorTok{=} \DecValTok{40}\NormalTok{, }\OperatorTok{**}\NormalTok{kwargs):}
        \CommentTok{# x is a required argument in position 1}
        \CommentTok{# args is tuple of variadic positional args}
        \CommentTok{# y is a regular keyword argument with default}
        \CommentTok{# kwargs is a dictionary of variadic keyword args}
        \CommentTok{# names 'args' and 'kwargs' are conventions}
\NormalTok{        ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{, }\DecValTok{30}\NormalTok{, y }\OperatorTok{=} \DecValTok{40}\NormalTok{, r }\OperatorTok{=} \DecValTok{50}\NormalTok{, s }\OperatorTok{=} \DecValTok{60}\NormalTok{, t }\OperatorTok{=} \DecValTok{70}\NormalTok{)}
        \CommentTok{# x = 10}
        \CommentTok{# args = (20, 30)}
        \CommentTok{# y = 40}
        \CommentTok{# kwargs = \{ 'r': 50, 's': 60, 't': 70 \}}
\end{Highlighting}
\end{Shaded}
\item
  Using required positional and keyword arguments -- where named
  arguments appearing after \texttt{*} can only be passed by keyword

\begin{Shaded}
\begin{Highlighting}[]
   \KeywordTok{def}\NormalTok{ myfunc(x, }\OperatorTok{*}\NormalTok{, y, }\OperatorTok{**}\NormalTok{kwargs):}
       \CommentTok{# x is a required argument in position 1}
       \CommentTok{# y is a regular keyword argument}
       \CommentTok{# kwargs is a dictionary of keyword args}
\NormalTok{      ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, y }\OperatorTok{=} \DecValTok{40}\NormalTok{, r }\OperatorTok{=} \DecValTok{50}\NormalTok{, s }\OperatorTok{=} \DecValTok{60}\NormalTok{, t }\OperatorTok{=} \DecValTok{70}\NormalTok{)}
        \CommentTok{# x = 10}
        \CommentTok{# y = 40}
        \CommentTok{# kwargs = \{ 'r': 50, 's': 60, 't': 70 \}}
\end{Highlighting}
\end{Shaded}
\item
  Using a fully variadic general signature

\begin{Shaded}
\begin{Highlighting}[]
   \KeywordTok{def}\NormalTok{ myfunc(}\OperatorTok{*}\NormalTok{args, }\OperatorTok{**}\NormalTok{kwargs):}
        \CommentTok{# args is tuple of all positional args}
        \CommentTok{# kwargs is a dictionary of all keyword args}
\NormalTok{        ...}
\NormalTok{    myfunc(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{, y }\OperatorTok{=} \DecValTok{40}\NormalTok{, }\DecValTok{30}\NormalTok{, r }\OperatorTok{=} \DecValTok{50}\NormalTok{, s }\OperatorTok{=} \DecValTok{60}\NormalTok{, t }\OperatorTok{=} \DecValTok{70}\NormalTok{)}
        \CommentTok{# args = (10, 20, 30)}
        \CommentTok{# kwargs = \{ 'y': 40, 'r': 50, 's': 60, 't': 70 \}}
\end{Highlighting}
\end{Shaded}
\end{enumerate}

\hypertarget{nested-function-definitions}{%
\subsection{Nested Function
Definitions}\label{nested-function-definitions}}

Above we only considered module-level function definitions and instance
method definitions defined within classes.

Python 3 allows function definitions to be nested within other function
definitions. Nested functions have several characteristics:

\begin{itemize}
\item
  \emph{Encapsulation}. The outer function hides the inner function
  definitions from the global scope. The inner functions can only be
  called from within the outer function.

  In contrast, Python 3 classes and modules do not provide airtight
  encapsulation. Their hiding of information is mostly by convention,
  with some support from the language.
\item
  \emph{Abstraction}. The inner function is a procedural abstraction
  that is named and separated from the outer function's code. This
  enables the inner function to be used several times within the outer
  function. The abstraction can enable the algorithm to be simplified
  and understood more easily.

  Of course, modules and classes also support abstraction, but not in
  combination with encapsulation.
\item
  \emph{Closure construction}. The outer function can take one or more
  functions as arguments, combine them in various ways (perhaps with
  inner function definitions), and construct and return a specialized
  function as a \emph{closure}. The closure can bind in parameters and
  other local variables of the outer function.

  Closures enable functional programming techniques such as currying,
  partial evaluation, function composition, construction of combinators,
  etc.

  We discuss closures in more depth in a later section of this chapter.

  Closure are powerful mechanisms that can be used to implement
  metaprogramming solutions (e.g., Python 3's decorators). We discuss
  those in later chapters.
\end{itemize}

As an example of use of nested function definitions to promote
encapsulation and abstraction, consider a recursive function
\texttt{sqrt(x)} to compute the square root of nonnegative number
\texttt{x} using Newton's Method. (This is adapted from section 1.1.7 of
{[}Abelson 1996{]}.)

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ sqrt(x):}
        \KeywordTok{def}\NormalTok{ square(x): }
            \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ x }
        \KeywordTok{def}\NormalTok{ good_enough(guess,x):}
            \ControlFlowTok{return} \BuiltInTok{abs}\NormalTok{(square(guess) }\OperatorTok{-}\NormalTok{ x) }\OperatorTok{<} \FloatTok{0.001}
        \KeywordTok{def}\NormalTok{ average(x,y):}
            \ControlFlowTok{return}\NormalTok{ (x }\OperatorTok{+}\NormalTok{ y) }\OperatorTok{/} \DecValTok{2}
        \KeywordTok{def}\NormalTok{ improve(guess,x):}
            \ControlFlowTok{return}\NormalTok{ average(guess,x}\OperatorTok{/}\NormalTok{guess)}
        \KeywordTok{def}\NormalTok{ sqrt_iter(guess,x):  }\CommentTok{# recursive version}
            \ControlFlowTok{if}\NormalTok{ good_enough(guess,x):}
                \ControlFlowTok{return}\NormalTok{ guess}
            \ControlFlowTok{else}\NormalTok{:}
                \ControlFlowTok{return}\NormalTok{ sqrt_iter(improve(guess,x),x)}
        \ControlFlowTok{if}\NormalTok{ x }\OperatorTok{>=} \DecValTok{0}\NormalTok{:}
            \ControlFlowTok{return}\NormalTok{ sqrt_iter(}\DecValTok{1}\NormalTok{, x)}
        \ControlFlowTok{else}\NormalTok{:}
            \BuiltInTok{print}\NormalTok{(}
                \SpecialStringTok{f'Cannot compute square root of negative number }\SpecialCharTok{\{x\}}\SpecialStringTok{'}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

A more ``Pythonic'' implementation of the \texttt{sqrt\_iter} function
would use a loop as follows:

\begin{Shaded}
\begin{Highlighting}[]
        \KeywordTok{def}\NormalTok{ sqrt_iter(guess,x):  }\CommentTok{# looping version}
            \ControlFlowTok{while} \KeywordTok{not}\NormalTok{ good_enough(guess,x):}
\NormalTok{                guess }\OperatorTok{=}\NormalTok{ improve(guess,x)}
            \ControlFlowTok{return}\NormalTok{ guess}
\end{Highlighting}
\end{Shaded}

Note: The Python 3.6+ source code for the recursive version of
\texttt{sqrt} is available at \href{code/sqrt1.py}{this link} and the
looping version at \href{code/sqrt2.py}{another link}.

\hypertarget{lexical-scope}{%
\subsection{Lexical Scope}\label{lexical-scope}}

Nested function definitions introduce a third category of variables --
local variables of outer functions -- in addition to the
(function-level) local and (module-level) global scopes we have
discussed so far.

Python 3 searches \emph{lexical scope} (also called \emph{static scope})
of a function for variable accesses.

Inside a function, variables that are:

\begin{itemize}
\item
  referenced but not assigned a value are assumed to be either defined
  in an outer function scope or in the global scope.

  The Python 3 interpreter first searches for the nearest enclosing
  function scope with a definition. If there is none, it then searches
  the global scope.
\item
  assigned a value are assumed to be local
\end{itemize}

In the latter case, we can explicitly declare the variable as
\texttt{nonlocal} if the desired variable to be assigned is defined in
an enclosing function scope or as \texttt{global} if it is defined in
the global scope.

Suppose we want to add an iteration counter \texttt{c} to the
\texttt{sqrt} function above. We can create and initialize variable
\texttt{c} in the outer function \texttt{sqrt}, but we must increment it
in nested function \texttt{sqrt\_iter}. For the nested function to
change an outer function variable, we must declare the variable as
\texttt{nonlocal} in the nested function's scope.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ sqrt(x):}
\NormalTok{        c }\OperatorTok{=} \DecValTok{0}                   \CommentTok{# create c in outer function}
        \CommentTok{# same definitions of square, good_enough, average, improve}
        \KeywordTok{def}\NormalTok{ sqrt_iter(guess,x): }\CommentTok{# new local x, hide outer x}
            \KeywordTok{nonlocal}\NormalTok{ c          }\CommentTok{# declare c nonlocal}
            \ControlFlowTok{while} \KeywordTok{not}\NormalTok{ good_enough(guess,x):}
\NormalTok{                c }\OperatorTok{+=} \DecValTok{1}          \CommentTok{# increment c}
\NormalTok{                guess }\OperatorTok{=}\NormalTok{ improve(guess,x)}
            \ControlFlowTok{return}\NormalTok{ (guess,c)    }\CommentTok{# return c}
        \ControlFlowTok{if}\NormalTok{ x }\OperatorTok{>=} \DecValTok{0}\NormalTok{: }
            \ControlFlowTok{return}\NormalTok{ sqrt_iter(}\DecValTok{1}\NormalTok{, x)}
        \ControlFlowTok{else}\NormalTok{:}
            \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Cannot compute square root of negative number }\SpecialCharTok{\{x\}}\SpecialStringTok{'}\NormalTok{)}
\end{Highlighting}
\end{Shaded}

Note: The Python 3.6+ source code for this version of \texttt{sqrt} is
available at \href{code/sqrt3.py}{this link}.

\hypertarget{closures}{%
\subsection{Closures}\label{closures}}

As discussed in a previous section, Python 3 function definitions can be
nested inside other functions. Among other capabilities, this enables a
Python 3 function to create and return a closure.

A \emph{closure} is a function object plus a reference to the enclosing
environment.

For example, consider the following:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ make_multiplier(x, y):}
        \KeywordTok{def}\NormalTok{ mul():}
           \ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ y}
        \ControlFlowTok{return}\NormalTok{ mul}
\end{Highlighting}
\end{Shaded}

If we call this function interactively from the Python 3 REPL, we see
that the values of the local variables \texttt{x} and \texttt{y} are
captured by the function returned.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ amul }\OperatorTok{=}\NormalTok{ make_multiplier(}\DecValTok{2}\NormalTok{, }\DecValTok{3}\NormalTok{)}
    \OperatorTok{>>>}\NormalTok{ bmul }\OperatorTok{=}\NormalTok{ make_multiplier(}\DecValTok{10}\NormalTok{, }\DecValTok{20}\NormalTok{) }
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(amul)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'function'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ amul()}
    \DecValTok{6}
    \OperatorTok{>>>}\NormalTok{ bmul()}
    \DecValTok{200}
\end{Highlighting}
\end{Shaded}

Function \texttt{make\_multiplier} is a \emph{higher order function}
because it returns a function (or closure) as its return value. Higher
order functions may also take functions (or closures) as parameters.

We can compose two conforming single argument functions using the
following \texttt{compose2} function. Function \texttt{comp} captures
the two arguments of \texttt{compose2} in a closure {[}Larose 2013{]}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ compose2(f, g):}
        \KeywordTok{def}\NormalTok{ comp(x):}
            \ControlFlowTok{return}\NormalTok{ f(g(x))}
        \ControlFlowTok{return}\NormalTok{ comp}
\end{Highlighting}
\end{Shaded}

Given that \texttt{f(g(x))} is a simple expression without side effects,
we can replace the \texttt{comp} function with an anonymous
\texttt{lambda} function as follows:

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{def}\NormalTok{ compose2(f, g): }
        \ControlFlowTok{return} \KeywordTok{lambda}\NormalTok{ x: f(g(x))}
\end{Highlighting}
\end{Shaded}

If we call this function from the Python 3 REPL, we see that the values
of the local variables \texttt{x} and \texttt{y} are captured by the
function returned.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>} \KeywordTok{def}\NormalTok{ square(x):}
\NormalTok{    ...     }\ControlFlowTok{return}\NormalTok{ x }\OperatorTok{*}\NormalTok{ x}
\NormalTok{    ...}
    \OperatorTok{>>>} \KeywordTok{def}\NormalTok{ inc(x):}
\NormalTok{    ...     }\ControlFlowTok{return}\NormalTok{ x }\OperatorTok{+} \DecValTok{1}
\NormalTok{    ...}
    \OperatorTok{>>>}\NormalTok{ inc_then_square }\OperatorTok{=}\NormalTok{ compose2(square, inc)}
    \OperatorTok{>>>}\NormalTok{ inc_then_square(}\DecValTok{10}\NormalTok{)}
    \DecValTok{121}
\end{Highlighting}
\end{Shaded}

Note: The Python 3.6+ source code for \texttt{compose2} is available at
\href{code/compose.py}{this link}.

\hypertarget{class-and-instance-attributes}{%
\subsection{Class and Instance
Attributes}\label{class-and-instance-attributes}}

As we noted above, classes are objects. The class objects can have
attributes. Instances of the class are also objects with their own
attributes.

Consider the following class \texttt{Dummy} which has a class-level
variable \texttt{r}. This attribute exists even if no instance has been
created.

Instances of \texttt{Dummy} have instance variables \texttt{s} and
\texttt{t} and an instance method \texttt{in\_meth}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ Dummy:}
\NormalTok{        r }\OperatorTok{=} \DecValTok{1} 
        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{, s, t): }
            \VariableTok{self}\NormalTok{.s }\OperatorTok{=}\NormalTok{ s}
            \VariableTok{self}\NormalTok{.t }\OperatorTok{=}\NormalTok{ t }
       \KeywordTok{def}\NormalTok{ in_meth(}\VariableTok{self}\NormalTok{):}
            \BuiltInTok{print}\NormalTok{(}\StringTok{'In instance method in_meth'}\NormalTok{) }
\end{Highlighting}
\end{Shaded}

Now consider the following Python 3 REPL session with the above
definition.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ Dummy.r}
    \DecValTok{1} 
    \OperatorTok{>>>}\NormalTok{ d }\OperatorTok{=}\NormalTok{ Dummy(}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{) }
    \OperatorTok{>>>}\NormalTok{ d.s }
    \DecValTok{2} 
    \OperatorTok{>>>}\NormalTok{ d.in_meth() }
    \OperatorTok{>>>}\NormalTok{ In instance method method }
\end{Highlighting}
\end{Shaded}

In the above, we see that:

\begin{itemize}
\item
  \texttt{Dummy.r} accesses the value of class variable \texttt{r} of
  the class object for the class \texttt{Dummy}.
\item
  \texttt{d.s} accesses the value of instance variable \texttt{s} of an
  instance object created by the constructor call and assignment
  \texttt{d\ =\ Dummy(2)}.
\item
  \texttt{d.in\_meth()} calls instance method \texttt{in\_meth} of
  instance object \texttt{d}.
\end{itemize}

These usages are similar to those of other object-oriented languages
such as Java.

A class can have three different kinds of methods in Python 3
{[}StackOverflow 2012{]}:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  An \emph{instance method} is a function associated with an instance of
  the class. It requires a reference to an instance object to be passed
  as the first non-optional argument, which is by convention named
  \texttt{self}. If that reference is missing, the call results in a
  \texttt{TypeError}.

  It can access the values of any of the instance's attributes (via the
  \texttt{self} argument) as well as the class's attributes.

  Note \texttt{in\_meth} in the \texttt{Dummy} code below.
\item
  A \emph{class method} is a function associated with a class object. It
  requires a reference to the class object to be passed as the first
  non-optional argument, which is by convention named \texttt{cls}. If
  that reference is missing, the call results in a \texttt{TypeError}.

  It can access the values of any of the class's attributes (via the
  \texttt{cls} argument). For example, \texttt{cls()} can create a new
  instance of the class. However, it cannot access the attributes of any
  of the class's instances.

  Note \texttt{cl\_meth} in the \texttt{Dummy} code below.

  Class methods can be overriden in subclasses.

  Because Python 3 does not support method overloading, class methods
  are useful in circumstances where overloading might be used in a
  language like Java. For example, we can use class methods to implement
  factory methods as alternative constructors for instances of the
  class.
\item
  A \emph{static method} is a function associated with the class object,
  but it does not require any non-optional argument to be passed

  A static method is just a function attached to the class's namespace.
  It cannot access any of the attributes of the class or instances
  except in a way that any function in the program can (e.g., by using
  the name of the class explicitly, by being passed an object as an
  argument, etc.)

  Note \texttt{s\_meth} in the \texttt{Dummy} code below.

  Static methods cannot be overrides in subclasses.
\end{enumerate}

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ Dummy:  }\CommentTok{# extended definition}
\NormalTok{        r }\OperatorTok{=} \DecValTok{1} 

        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{, s, t): }
            \VariableTok{self}\NormalTok{.s }\OperatorTok{=}\NormalTok{ s }
            \VariableTok{self}\NormalTok{.t }\OperatorTok{=}\NormalTok{ t }

        \KeywordTok{def}\NormalTok{ in_meth(}\VariableTok{self}\NormalTok{):}
            \BuiltInTok{print}\NormalTok{(}\StringTok{'In instance method in_meth'}\NormalTok{) }

        \AttributeTok{@classmethod} 
        \KeywordTok{def}\NormalTok{ cl_meth(cls): }
            \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'In class method cl_meth for }\SpecialCharTok{\{}\NormalTok{cls}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{) }

        \AttributeTok{@staticmethod}
        \KeywordTok{def}\NormalTok{ st_meth(): }
            \BuiltInTok{print}\NormalTok{(}\StringTok{'In static method st_meth'}\NormalTok{) }
\end{Highlighting}
\end{Shaded}

In the example, the \emph{decorators} \texttt{@classmethod} and
\texttt{@staticmethod} transform the attached functions into class and
static methods, respectively. We will discuss decorators in a later
section.

Now consider a Python 3 REPL session with the extended definition.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ d }\OperatorTok{=}\NormalTok{ Dummy(}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{) }
    \OperatorTok{>>>}\NormalTok{ d.in_meth()}
\NormalTok{    In instance method in_meth }
    \OperatorTok{>>>}\NormalTok{ d.r }
    \DecValTok{1} 
    \OperatorTok{>>>}\NormalTok{ Dummy.cl_meth()}
\NormalTok{    In }\KeywordTok{class}\NormalTok{ method cl_meth }\ControlFlowTok{for}\NormalTok{ Dummy}
    \OperatorTok{>>>}\NormalTok{ Dummy.st_meth() }
\NormalTok{    In static method st_meth}
    \OperatorTok{>>>}\NormalTok{ Dummy.in_meth()}
\NormalTok{    Traceback (most recent call last):}
\NormalTok{    ...}
    \PreprocessorTok{TypeError}\NormalTok{: in_meth() missing }\DecValTok{1}\NormalTok{ required positional argument: }\StringTok{'self'}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(d.in_meth)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'method'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(Dummy.cl_meth)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'method'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(Dummy.st_meth)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'function'}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ din }\OperatorTok{=}\NormalTok{ d.in_meth  }\CommentTok{# get method object, store in variable din}
    \OperatorTok{>>>}\NormalTok{ din()            }\CommentTok{# call method object in din}
\NormalTok{    In instance method in_meth}
    \VariableTok{None}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(din)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'method'}\OperatorTok{>}    
\end{Highlighting}
\end{Shaded}

Note that the types of the references \texttt{d.in\_meth} and
\texttt{Dummy.cl\_meth} are both \texttt{method}. A \texttt{method}
object is essentially a function that binds in a reference to the
required first positional argument. A method object is, of course, a
first-class object that can be stored and invoked later as illustrated
by variable \texttt{din} above.

However, note that \texttt{Dummy.st\_meth} has type \texttt{function}.

Note: The Python 3.6+ source code for the class \texttt{Dummy} is
available at \href{code/dummy1.py}{this link}.

\hypertarget{object-dictionaries}{%
\subsection{Object Dictionaries}\label{object-dictionaries}}

As we noted earlier, each Python 3 object has a distinct dictionary that
maps the local names to the data attributes and operations (i.e., its
environment). Each object's attribute \texttt{\_\_dict\_\_} holds its
dictionary. Python 3 programs can access this dictionary directly.

Again consider the \texttt{Dummy} class we examined the previous
section. Let's look at dictionary for this class and an instance in the
Python 3 REPL.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ d }\OperatorTok{=}\NormalTok{ Dummy(}\DecValTok{2}\NormalTok{,}\DecValTok{3}\NormalTok{)}
    \OperatorTok{>>>}\NormalTok{ d.__dict__ }
\NormalTok{    \{}\StringTok{'s'}\NormalTok{: }\DecValTok{2}\NormalTok{, }\StringTok{'t'}\NormalTok{: }\DecValTok{3}\NormalTok{\}}
    \OperatorTok{>>>}\NormalTok{ Dummy.__dict__[}\StringTok{"r"}\NormalTok{]}
    \DecValTok{1}
    \OperatorTok{>>>}\NormalTok{ Dummy.__dict__[}\StringTok{"in_meth"}\NormalTok{]}
    \OperatorTok{<}\NormalTok{function Dummy.in_meth at }\BaseNTok{0x10191abf8}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ Dummy.__dict__[}\StringTok{"cl_meth"}\NormalTok{]}
    \OperatorTok{<}\BuiltInTok{classmethod} \BuiltInTok{object}\NormalTok{ at }\BaseNTok{0x101928c50}\OperatorTok{>}
    \OperatorTok{>>>}\NormalTok{ Dummy.__dict__[}\StringTok{"st_meth"}\NormalTok{]}
    \OperatorTok{<}\BuiltInTok{staticmethod} \BuiltInTok{object}\NormalTok{ at }\BaseNTok{0x101928c88}\OperatorTok{>}    
\end{Highlighting}
\end{Shaded}

TODO: Investigate and explain last two types returned above?

\hypertarget{special-methods-and-operator-overloading}{%
\subsection{Special Methods and Operator
Overloading}\label{special-methods-and-operator-overloading}}

Almost everything about the behavior of Python 3 classes and instances
can be customized. A key way to do this is by defining or redefining
\emph{special methods} (sometimes called \emph{magic} methods).

Python 3 uses special methods to provide an \emph{operator overloading}
capability. There are special methods associated with certain operations
that are invoked by builtin operators (such as arithmetic and comparison
operators, subscripting) and with other functionality (such as
initializing newly class instance).

The names of special methods both begin and end with double underscores
\texttt{\_\_} (and thus are sometimes called ``dunder'' methods). For
example, in an earlier subsection, we defined the special method
\texttt{\_\_init\_\_} to specify how a newly created instance is
initialized. In other class-based examples, we have defined the
\texttt{\_\_str\_\_} special method to implement a custom string
conversion for an instance's state.

Consider the class \texttt{Dum} that overrides the definition of the
addition operator to do the same operation as multiplication.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ Dum:}
        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{,x):}
           \VariableTok{self}\NormalTok{.x }\OperatorTok{=}\NormalTok{ x}
        \KeywordTok{def} \FunctionTok{__add__}\NormalTok{(a,b):}
            \ControlFlowTok{return}\NormalTok{ a.x }\OperatorTok{*}\NormalTok{ b.x}
\end{Highlighting}
\end{Shaded}

Now let's see how \texttt{Dum} works.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ y }\OperatorTok{=}\NormalTok{ Dum(}\DecValTok{2}\NormalTok{) }
    \OperatorTok{>>>}\NormalTok{ z }\OperatorTok{=}\NormalTok{ Dum(}\DecValTok{4}\NormalTok{)}
    \OperatorTok{>>>}\NormalTok{ y }\OperatorTok{+}\NormalTok{ z}
    \DecValTok{8}
\end{Highlighting}
\end{Shaded}

Consider the rudimentary \texttt{SparseArray} collection below. It uses
the special methods \texttt{\_\_init\_\_}, \texttt{\_\_str\_\_},
\texttt{\_\_getitem\_\_}, \texttt{\_\_setitem\_\_},
\texttt{\_\_delitem\_\_}, and \texttt{\_\_contains\_\_} to tie this new
collection into the standard access mechanisms. (This example stores the
sparse array in a dictionary internally, but ``hides'' that from the
user.)

The Boolean \texttt{\_\_contains\_\_} functionality searches the
\texttt{SparseArray} instance for an item. The class also provides a
separate Boolean method \texttt{has\_index} to check wether an index has
a corresponding value. Alternatively, we could have tied the
\texttt{\_\_contains\_\_} functionality to the latter and provided a
\texttt{has\_item} method for the former.

In addition, the method \texttt{from\_assoc} loads an ``association
list'' into a sparse array instance. Here, the term \emph{association
list} refers to any iterable object yielding a finite sequence of
index-value pairs.

Similarly, the method \texttt{to\_assoc} unloads the entire sparse array
into a sorted list of index-value pairs (which is an iterable object).

For simplicity, the implementation below just prints error messages. It
probably should raise exception instead.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ SparseArray:}

        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{, assoc}\OperatorTok{=}\VariableTok{None}\NormalTok{):}
            \VariableTok{self}\NormalTok{._arr }\OperatorTok{=}\NormalTok{ \{\}}
            \ControlFlowTok{if}\NormalTok{ assoc }\KeywordTok{is} \KeywordTok{not} \VariableTok{None}\NormalTok{:}
                \VariableTok{self}\NormalTok{.from_assoc(assoc)}

        \KeywordTok{def}\NormalTok{ from_assoc(}\VariableTok{self}\NormalTok{,assoc):}
            \ControlFlowTok{for}\NormalTok{ p }\KeywordTok{in}\NormalTok{ assoc:}
                \ControlFlowTok{if} \BuiltInTok{len}\NormalTok{(p) }\OperatorTok{==} \DecValTok{2}\NormalTok{:}
\NormalTok{                    (i,v) }\OperatorTok{=}\NormalTok{ p}
                    \ControlFlowTok{if} \BuiltInTok{type}\NormalTok{(i) }\KeywordTok{is} \BuiltInTok{int}\NormalTok{:}
                        \VariableTok{self}\NormalTok{._arr[i] }\OperatorTok{=}\NormalTok{ v}
                    \ControlFlowTok{else}\NormalTok{:}
                        \BuiltInTok{print}\NormalTok{(}
                            \SpecialStringTok{f'Index not int in assoc list: }\SpecialCharTok{\{}\BuiltInTok{str}\NormalTok{(i)}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{)}
                \ControlFlowTok{else}\NormalTok{:}
                    \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Invalid pair in assoc list: }\SpecialCharTok{\{}\BuiltInTok{str}\NormalTok{(p)}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{)}

        \KeywordTok{def}\NormalTok{ has_index(}\VariableTok{self}\NormalTok{, index):}
            \ControlFlowTok{if} \BuiltInTok{type}\NormalTok{(index) }\KeywordTok{is} \BuiltInTok{int}\NormalTok{:}
                \ControlFlowTok{return}\NormalTok{ index }\KeywordTok{in} \VariableTok{self}\NormalTok{._arr}
            \ControlFlowTok{else}\NormalTok{:}
                \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Warning: Index not int: }\SpecialCharTok{\{}\NormalTok{index}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{) }
                \ControlFlowTok{return} \VariableTok{False}

        \KeywordTok{def} \FunctionTok{__getitem__}\NormalTok{(}\VariableTok{self}\NormalTok{, index):        }\CommentTok{# arr[index]}
            \ControlFlowTok{if} \BuiltInTok{type}\NormalTok{(index) }\KeywordTok{is} \BuiltInTok{int}\NormalTok{:}
                \ControlFlowTok{return} \VariableTok{self}\NormalTok{._arr[index]}
            \ControlFlowTok{else}\NormalTok{:}
                \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Index not int: }\SpecialCharTok{\{}\NormalTok{index}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{) }

        \KeywordTok{def} \FunctionTok{__setitem__}\NormalTok{(}\VariableTok{self}\NormalTok{, index, value): }\CommentTok{# arr[index] = value}
            \ControlFlowTok{if} \BuiltInTok{type}\NormalTok{(index) }\KeywordTok{is} \BuiltInTok{int}\NormalTok{:}
                \VariableTok{self}\NormalTok{._arr[index] }\OperatorTok{=}\NormalTok{ value}
            \ControlFlowTok{else}\NormalTok{:}
                \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Index not int: }\SpecialCharTok{\{}\NormalTok{index}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{)}

        \KeywordTok{def} \FunctionTok{__delitem__}\NormalTok{(}\VariableTok{self}\NormalTok{, index):        }\CommentTok{# del arr[index]}
            \ControlFlowTok{if} \BuiltInTok{type}\NormalTok{(index) }\KeywordTok{is} \BuiltInTok{int}\NormalTok{:}
                \KeywordTok{del} \VariableTok{self}\NormalTok{._arr[index]}
            \ControlFlowTok{else}\NormalTok{:}
                \BuiltInTok{print}\NormalTok{(}\SpecialStringTok{f'Index not int: }\SpecialCharTok{\{}\NormalTok{index}\SpecialCharTok{\}}\SpecialStringTok{'}\NormalTok{)}

        \KeywordTok{def} \FunctionTok{__contains__}\NormalTok{(}\VariableTok{self}\NormalTok{, item):        }\CommentTok{# item (is value) in arr}
            \ControlFlowTok{return}\NormalTok{ item }\KeywordTok{in} \VariableTok{self}\NormalTok{._arr.values()}

        \KeywordTok{def}\NormalTok{ to_assoc(}\VariableTok{self}\NormalTok{):}
            \ControlFlowTok{return} \BuiltInTok{sorted}\NormalTok{(}\VariableTok{self}\NormalTok{._arr.items())}
    
        \KeywordTok{def} \FunctionTok{__str__}\NormalTok{(}\VariableTok{self}\NormalTok{):}
            \ControlFlowTok{return} \BuiltInTok{str}\NormalTok{(}\VariableTok{self}\NormalTok{.to_assoc())}
\end{Highlighting}
\end{Shaded}

Now consider a Python 3 REPL session with the above class definition.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ arr }\OperatorTok{=}\NormalTok{ SparseArray()}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(arr)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'__main__.SparseArray'}\OperatorTok{>}  
    \OperatorTok{>>>}\NormalTok{ arr}
\NormalTok{    []}
    \OperatorTok{>>>}\NormalTok{ arr[}\DecValTok{1}\NormalTok{] }\OperatorTok{=} \StringTok{"one"}
    \OperatorTok{>>>}\NormalTok{ arr}
\NormalTok{    [(}\DecValTok{1}\NormalTok{, `one`)]}
    \OperatorTok{>>>}\NormalTok{ arr.has_index(}\DecValTok{1}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>}\NormalTok{ arr.has_index(}\DecValTok{2}\NormalTok{)}
    \VariableTok{False}
    \OperatorTok{>>>}\NormalTok{ arr.from_assoc([(}\DecValTok{2}\NormalTok{,}\StringTok{"two"}\NormalTok{),(}\DecValTok{3}\NormalTok{,}\StringTok{"three"}\NormalTok{)])}
\NormalTok{    \{}\DecValTok{1}\NormalTok{: }\StringTok{'one'}\NormalTok{, }\DecValTok{2}\NormalTok{: }\StringTok{'two'}\NormalTok{, }\DecValTok{3}\NormalTok{: }\StringTok{'three'}\NormalTok{\}}
    \OperatorTok{>>>}
    \OperatorTok{>>>}\NormalTok{ arr[}\DecValTok{10}\NormalTok{] }\OperatorTok{=} \StringTok{"ten"}
    \OperatorTok{>>>}\NormalTok{ arr}
\NormalTok{    [(}\DecValTok{1}\NormalTok{,}\StringTok{'one'}\NormalTok{), (}\DecValTok{2}\NormalTok{, }\StringTok{'two'}\NormalTok{), (}\DecValTok{3}\NormalTok{, }\StringTok{'three'}\NormalTok{), (}\DecValTok{10}\NormalTok{, }\StringTok{'ten'}\NormalTok{)]}
    \OperatorTok{>>>} \KeywordTok{del}\NormalTok{ arr[}\DecValTok{3}\NormalTok{]}
    \OperatorTok{>>>}\NormalTok{ arr}
\NormalTok{    [(}\DecValTok{1}\NormalTok{,}\StringTok{'one'}\NormalTok{), (}\DecValTok{2}\NormalTok{, }\StringTok{'two'}\NormalTok{), (}\DecValTok{10}\NormalTok{, }\StringTok{'ten'}\NormalTok{)]}
    \OperatorTok{>>>} \StringTok{'ten'} \KeywordTok{in}\NormalTok{ arr}
    \VariableTok{True}
\end{Highlighting}
\end{Shaded}

Note: The Python 3.6+ source code for the class \texttt{SparseArray} is
available at \href{code/sparse_array1.py}{this line}.

\hypertarget{object-orientation}{%
\subsection{Object Orientation}\label{object-orientation}}

The \href{../ProgrammingParadigms.html\#object-oriented}{Programming
Paradigms} notes {[}Cunningham 2018a{]} discuss object orientation in
terms of a general object model. The general \emph{object model}
includes four basic components:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  objects
\item
  classes
\item
  inheritance
\item
  subtype polymorphism
\end{enumerate}

We discuss Python 3's objects and classes above. Now let's consider the
other two components of the general object model in relation to Python
3.

\hypertarget{inheritance}{%
\subsubsection{Inheritance}\label{inheritance}}

In programming languages in general, inheritance involves defining
hierarchical relationships among classes. From a \emph{pure}
perspective, a class \texttt{C} \emph{inherits} from class \texttt{P} if
\texttt{C}'s objects form a \emph{subset} of \texttt{P}'s objects in the
following sense:

\begin{itemize}
\item
  Class \texttt{C}'s objects must support all of class \texttt{P}'s
  operations (but perhaps are carried out in a special way).

  We can say that a \texttt{C} object \emph{is a} \texttt{P} object or
  that a class \texttt{C} object can be \emph{substituted} for a class
  \texttt{P} object whenever the latter is required.
\item
  Class \texttt{C} may support additional operations and an extended
  state (i.e., more data attributes fields).
\end{itemize}

We use the following terminology.

\begin{itemize}
\item
  Class \texttt{C} is called a \emph{subclass} or a \emph{child} or
  \emph{derived class}.
\item
  Class \texttt{P} is called a \emph{superclass} or a \emph{parent} or
  \emph{base} class.
\item
  Class \texttt{P} is sometimes called a \emph{generalization} of class
  \texttt{C}; class \texttt{C} is a \emph{specialization} of class
  \texttt{P}.
\end{itemize}

In terms of the discussion in the Type System Concepts section, the
parent class \texttt{P} defines a conceptual type and child class
\texttt{C} defines a behavioral subtype of \texttt{P}'s type. The
subtype satisfies the Liskov Substitution Principle.

Even in a statically typed language like Java, the language does not
enforce this subtype relationship. It is possible to create subclasses
that are not subtypes. However, using inheritance to define subtype
relationships is considered good object-oriented programming practice in
most circumstances.

In a dynamically typed like Python 3, there are fewer supports than in
statically typed languages. But using classes to define subtype
relationships is still a good practice.

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 parent classes and shared
among the child classes.

The following code fragment shows how to define a single inheritance
relationship among classes in Python 3. Instance method \texttt{process}
is defined in the parent class \texttt{P} and \emph{overridden} (i.e.,
redefined) in child class \texttt{C} but not overriden in child class
\texttt{D}. In turn, \texttt{C}'s instance method \texttt{process} is
overridden in its child class \texttt{G}.

\begin{Shaded}
\begin{Highlighting}[]
    \KeywordTok{class}\NormalTok{ P:}
        \KeywordTok{def} \FunctionTok{__init__}\NormalTok{(}\VariableTok{self}\NormalTok{,name}\OperatorTok{=}\VariableTok{None}\NormalTok{): }
            \VariableTok{self}\NormalTok{.name }\OperatorTok{=}\NormalTok{ name }
        \KeywordTok{def}\NormalTok{ process(}\VariableTok{self}\NormalTok{):}
            \ControlFlowTok{return} \SpecialStringTok{f'Process at parent P level'}

    \KeywordTok{class}\NormalTok{ C(P):   }\CommentTok{# class C inherits from class P}
        \KeywordTok{def}\NormalTok{ process(}\VariableTok{self}\NormalTok{):}
\NormalTok{            result }\OperatorTok{=} \SpecialStringTok{f'Process at child C level'}
            \CommentTok{# Call method in parent class}
            \ControlFlowTok{return} \SpecialStringTok{f'}\SpecialCharTok{\{}\NormalTok{result}\SpecialCharTok{\}}\SpecialStringTok{ }\CharTok{\textbackslash{}n}\SpecialStringTok{  }\SpecialCharTok{\{}\BuiltInTok{super}\NormalTok{()}\SpecialCharTok{.}\NormalTok{process()}\SpecialCharTok{\}}\SpecialStringTok{'}
            
    \KeywordTok{class}\NormalTok{ D(P):   }\CommentTok{# class D inherits from class P}
        \ControlFlowTok{pass}

    \KeywordTok{class}\NormalTok{ G(C):   }\CommentTok{# class G inherits from class C}
        \KeywordTok{def}\NormalTok{ process(}\VariableTok{self}\NormalTok{):}
            \ControlFlowTok{return} \SpecialStringTok{f'Process at grandchild G level'}
\end{Highlighting}
\end{Shaded}

Now consider a (lengthy) Python 3 REPL session with the above class
definition.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ p1 }\OperatorTok{=}\NormalTok{ P()}
    \OperatorTok{>>>}\NormalTok{ c1 }\OperatorTok{=}\NormalTok{ C()}
    \OperatorTok{>>>}\NormalTok{ d1 }\OperatorTok{=}\NormalTok{ D()}
    \OperatorTok{>>>}\NormalTok{ g1 }\OperatorTok{=}\NormalTok{ G()}
    \OperatorTok{>>>}\NormalTok{ p1.process()}
    \CommentTok{'Process at parent P level'}
    \OperatorTok{>>>}\NormalTok{ c1.process()}
    \CommentTok{'Process at child C level'}
    \CommentTok{'Process at parent P level'}
    \OperatorTok{>>>}\NormalTok{ d1.process()}
    \CommentTok{'Process at parent P level'} 
    \OperatorTok{>>>}\NormalTok{ g1.process()}
    \CommentTok{'Process at grandchild G level'}
    \CommentTok{#}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(P) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(C) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(G) }
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(P,}\BuiltInTok{object}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(C,P)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(G,C)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(G,P)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(G,}\BuiltInTok{object}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(C,G)}
    \VariableTok{False}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(G,D)}
    \VariableTok{False}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(P,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{False}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(P,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(C,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(G,}\BuiltInTok{type}\NormalTok{) }
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{type}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(}\BuiltInTok{type}\NormalTok{,}\BuiltInTok{object}\NormalTok{)}
    \VariableTok{True}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(}\BuiltInTok{type}\NormalTok{,}\BuiltInTok{type}\NormalTok{) }
    \VariableTok{True} 
    \OperatorTok{>>>} \BuiltInTok{type}\NormalTok{(}\BuiltInTok{object}\NormalTok{)}
    \OperatorTok{<}\KeywordTok{class} \StringTok{'type'}\OperatorTok{>}
    \OperatorTok{>>>} \BuiltInTok{isinstance}\NormalTok{(}\BuiltInTok{object}\NormalTok{,}\BuiltInTok{type}\NormalTok{) }
    \VariableTok{True} 
    \OperatorTok{>>>} \BuiltInTok{issubclass}\NormalTok{(}\BuiltInTok{object}\NormalTok{,}\BuiltInTok{type}\NormalTok{)}
    \VariableTok{False}
\end{Highlighting}
\end{Shaded}

\texttt{Note:\ The\ Python\ 3.6+\ source\ code\ for\ the\ above\ version\ of\ the}P`
class hierarchy is available at \href{code/inherit1.py}{this link}.

\hypertarget{understanding-relationships-among-classes}{%
\paragraph{Understanding relationships among
classes}\label{understanding-relationships-among-classes}}

By examining the REPL session above, we can observe the following:

\begin{itemize}
\item
  Top-level user-defined classes like \texttt{P} implicitly inherit from
  the \texttt{object} root class. They have the \texttt{issubclass}
  relationship with \texttt{object}.
\item
  A user-defined subclass like \texttt{C} inherits explicitly from its
  superclass \texttt{P}, which inherits implicitly from root class
  \texttt{object}. Class \texttt{C} thus has \texttt{issubclass}
  relationships with both \texttt{P} and \texttt{object}.
\item
  By default, all Python 3 classes (including subclasses) are instances
  of the root metaclass \texttt{type} (or one of its subtypes as we see
  later). But non-class objects are not instances of \texttt{type}.
\end{itemize}

As we noted in a previous section, we call class objects
\emph{metaobjects}; they are constructors for ordinary objects
{[}Kiczales 1991; Forman 1999{]}.

Also as we noted in a previous section, we call special class objects
like \texttt{type} \emph{metaclasses}; they are constructors for
metaobjects (i.e., class objects) {[}Kiczales 1991; Forman 1999{]}.

Note that classes \texttt{object} and \texttt{type} have special --
almost ``magical'' -- relationships with one another {[}Ramalho 2015,
pp.~593-5{]}.

\begin{itemize}
\item
  Class \texttt{object} is an instance of class \texttt{type} (i.e.~it
  is a Python class object).
\item
  Class \texttt{type} is an instance of itself (i.e.~it is a Python
  class object) and a subclass of class \texttt{object}.
\end{itemize}

The diagram in Figure 1 shows the relationships among user-definfed
class \texttt{P} and built-in classes \texttt{int}, \texttt{object}, and
\texttt{type}. Solid lines denote subclass relationships; dashed lines
denote ``instance of'' relationships.

\begin{figure}
\centering
\includegraphics{Py3_Class_Model.png}
\caption{\textbf{Figure 1: Python 3 Class Model}}
\end{figure}

\hypertarget{replacement-and-refinement}{%
\paragraph{Replacement and
refinement}\label{replacement-and-refinement}}

There are two general approaches for overriding methods in subclasses.

\begin{itemize}
\item
  \emph{Replacement}, in which the child class method totally replaces
  the parent class method

  This is the usual approach in most ``American school'' object-oriented
  languages in use today -- Smalltalk (where it originated), Java, C++,
  C\#, and Python 3.
\item
  \emph{Refinement}, in which the language merges the behaviors of the
  parent and child classes to form a new behavior

  This is the approach taken in Simula 67 (the first object-oriented
  language) and its successors in the ``Scandinavian school'' of
  object-oriented languages. In these languages, the child class method
  typically wraps around a call to the parent class method.
\end{itemize}

The refinement approach supports the implementation of pure subtyping
relationships better than replacement does. The replacement approach is
more flexible than refinement.

A language that takes the replacement approach usually provides a
mechanism for using refinement. For example in the Python 3 class
hierarchy example above, the expression \texttt{super().process()} in
subclass \texttt{C} calls the \texttt{process} method of its superclass
\texttt{P}.

\hypertarget{subtype-polymorphism}{%
\subsubsection{Subtype polymorphism}\label{subtype-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. Here we
examine one form.

In the Python 3 class hierarchy example above, the method
\texttt{process} forms part of the common interface for this hierarchy.
Parent class \texttt{P} defines the method, child class \texttt{C}
overrides \texttt{P}'s definition by refinement, and grandchild class
\texttt{G} overrides \texttt{C}'s definition by replacement. However,
child class \texttt{D} does not override \texttt{P}'s definition.

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

This form of polymorphism is usually carried out at run time. Such an
implementation is called \emph{dynamic binding}.

In general, given an object (i.e., class instance) to which an operation
is applied, the runtime system first searches for an implementation of
the operation associated with the object's class. If no implementation
is found, the system checks the parent class, and so forth up the
hierarchy until it finds an implementation and then invokes it.
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.

In a statically typed language like Java, we declare a variable of some
ancestor class type. We can then store any descendant class instance in
that variable. Polymorphism allows the program to apply any of the
ancestor class operations to the instance.

Because of dynamically typed variables, polymorphism is even more
flexible in Python 3 than in Java.

In Python 3, an instance object may also have its own implementation of
a method, so the runtime system searches the instance before searching
upward in the class hierarchy.

Also (as we noted in an earlier section) Python 3 uses duck typing.
Objects can have a common interface even if they do not have common
ancestors in a class hierarchy. If the runtime system can find an
compatible operation associated with an instance, it can execute it.

Thus Python 3's approach to subtype polymorphism gives considerable
flexibility in structuring programs. However, unlike statically typed
languages, the compiler provides little help in ensuring the
compatibility of method implementations.

Again consider the simple inheritance hierarchy above in the following
Python 3 REPL session.

\begin{Shaded}
\begin{Highlighting}[]
    \OperatorTok{>>>}\NormalTok{ d1 }\OperatorTok{=}\NormalTok{ D()}
    \OperatorTok{>>>}\NormalTok{ g1 }\OperatorTok{=}\NormalTok{ G()}
    \OperatorTok{>>>}\NormalTok{ obj }\OperatorTok{=}\NormalTok{ d1     }\CommentTok{# variables support polymorphism}
    \OperatorTok{>>>}\NormalTok{ obj.process()}
    \CommentTok{'Process at parent P level'} 
    \OperatorTok{>>>}\NormalTok{ obj }\OperatorTok{=}\NormalTok{ g1     }\CommentTok{# variables support polymorphism}
    \OperatorTok{>>>}\NormalTok{ obj.process()}
    \CommentTok{'Process at grandchild G level'} 
\end{Highlighting}
\end{Shaded}

\hypertarget{multiple-inheritance}{%
\subsubsection{Multiple Inheritance}\label{multiple-inheritance}}

TODO: Decide whether discussion of multiple inheritance is needed here?
or later? Issues include the diamond problem, Python syntax and
semantics, and method resolution order.

\hypertarget{chapter-summary}{%
\subsection{Chapter Summary}\label{chapter-summary}}

TODO: Write this

In the next chapter, we explore a case study to motivate the concept and
use of decorators and metaclasses in Python 3.

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

TODO: Decide whether any are needed.

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

I developed these notes in Spring 2018 for use in CSci 658 Software
Language Engineering. The Spring 2018 version used Python 3.6.

The overall set of notes on Python 3 Reflexive Metaprogramming is
inspired by David Beazley's \href{http://www.dabeaz.com/py3meta}{Python
3 Metaprogramming tutorial} from PyCon'2013 {[}Beazley 2013a{]}. In
particular, some chapters adapt Beazley's examples. Beazley's tutorial
draws on material from his and Brian K. Jones' book \emph{Python
Cookbook} {[}Beazley 2013b{]}.

In particular, this chapter adapts and extends some aspects of the
introductory section of {[}Beazley 2013a{]}.

The notes also adapt some material from the Programming Paradigms
{[}Cunningham 2018a{]} notes.

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

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

\begin{description}
\tightlist
\item[{[}Abelson 1996{]}:]
Harold Abelson, Gerald Jay Sussman, and Julie Sussman. \emph{Structure
and Interpretation of Computer Programs (2nd Edition)}, MIT Press, 1996.
\item[{[}Beazley 2013a{]}:]
David Beazley. \href{http://www.dabeaz.com/py3meta/}{Python 3
Metaprogramming (Tutorial)}, \emph{PyCon'2013}, 14 March 2013.
\item[{[}Beazley 2013b{]}:]
David Beazley and Brian K. Jones. \emph{Python Cookbook, 3rd Edition},
O'Reilly Media, May 2013.
\item[{[}Cunningham 2018a{]}:]
H. Conrad Cunningham.
\href{../ProgrammingParadigms.html\#object-oriented}{Programming
Paradigms, Object-Oriented} section, revised 17 February 2018.
\item[{[}Forman 1999{]}:]
Ira R. Forman and Scott Danforth. \emph{Putting Metaclasses to Work},
Addison Wesley Longman, 1999.
\item[{[}Kiczales 1991{]}:]
Gregor Kiczales, Jim des Rivieres; Daniel G. Bobrow. \emph{The Art of
the Metaobject Protocol}, The MIT Press, 1991.
\item[{[}Larose 2013{]}:]
Mathieu Larose.
\href{https://mathieularose.com/function-composition-in-python/}{Function
Composition in Python}, Blog post. January 2013.
\item[{[}Liskov 1987{]}:]
Barbara Liskov. Keynote Address -- Data Abstraction and Hierarchy, In
the Addendum to the \emph{Proceedings on Object-Oriented Programming
Systems, Languages, and Applications (OOPSLA '87)}, Leigh Power and Zvi
Weiss, Editors, ACM, 1987.
\item[{[}Ramalho 2015{]}:]
Luciano Ramalho. \emph{Fluent Python: Clear, Concise, and Effective
Programming}, O'Reilly Media, May 2015.
\item[{[}Scott 2016{]}:]
Michael L. Scott. \emph{Programming Language Pragmatics}, Fourth
Edition, Morgan Kaufmann, 2016. MAY NOT BE CITED
\item[{[}StackOverflow 2012{]}:]
StackOverflow.
\href{https://stackoverflow.com/questions/12179271/meaning-of-classmethod-and-staticmethod-for-beginner}{Meaning
of @classmethod and @staticmethod-for beginner?}, first post 12 August
2012.
\item[{[}Wikipedia 2018d{]}:]
Wikipedia,
\href{https://en.wikipedia.org/wiki/Liskov_substitution_principle}{Liskov
Substitution Principle}, accessed 25 April 2018.
\end{description}

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

TODO

\end{document}
