\documentclass[]{article}
\usepackage{lmodern}
\usepackage{amssymb,amsmath}
\usepackage{ifxetex,ifluatex}
\usepackage{fixltx2e} % provides \textsubscript
\ifnum 0\ifxetex 1\fi\ifluatex 1\fi=0 % if pdftex
  \usepackage[T1]{fontenc}
  \usepackage[utf8]{inputenc}
\else % if luatex or xelatex
  \ifxetex
    \usepackage{mathspec}
  \else
    \usepackage{fontspec}
  \fi
  \defaultfontfeatures{Ligatures=TeX,Scale=MatchLowercase}
\fi
% use upquote if available, for straight quotes in verbatim environments
\IfFileExists{upquote.sty}{\usepackage{upquote}}{}
% use microtype if available
\IfFileExists{microtype.sty}{%
\usepackage{microtype}
\UseMicrotypeSet[protrusion]{basicmath} % disable protrusion for tt fonts
}{}
\usepackage[unicode=true]{hyperref}
\hypersetup{
            pdftitle={CSci 450: Organization of Programming Languages Using Data Abstraction in Lua},
            pdfauthor={H. Conrad Cunningham},
            pdfborder={0 0 0},
            breaklinks=true}
\urlstyle{same}  % don't use monospace font for urls
\IfFileExists{parskip.sty}{%
\usepackage{parskip}
}{% else
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}
}
\setlength{\emergencystretch}{3em}  % prevent overfull lines
\providecommand{\tightlist}{%
  \setlength{\itemsep}{0pt}\setlength{\parskip}{0pt}}
\setcounter{secnumdepth}{0}
% Redefines (sub)paragraphs to behave more like sections
\ifx\paragraph\undefined\else
\let\oldparagraph\paragraph
\renewcommand{\paragraph}[1]{\oldparagraph{#1}\mbox{}}
\fi
\ifx\subparagraph\undefined\else
\let\oldsubparagraph\subparagraph
\renewcommand{\subparagraph}[1]{\oldsubparagraph{#1}\mbox{}}
\fi
\usepackage{caption}
\DeclareCaptionLabelFormat{nolabel}{}
\captionsetup{labelformat=nolabel}

\title{CSci 450: Organization of Programming Languages\\
Using Data Abstraction in Lua}
\author{H. Conrad Cunningham}
\date{13 September 2016}

\begin{document}
\maketitle

Copyright (C) 2016, H. Conrad Cunningham

\textbf{Acknowledgements:} Adapted from my notes \emph{Introduction to
Functional Programming Using Haskell} (under development, 2016) and
example Lua modules for Rational Arithmetic.

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

\setcounter{section}{1}

\section{Using Data Abstraction}\label{using-data-abstraction}

How can we make a program robust with respect to change in the form of
its data? A good technique is data abstraction. Let's begin with an
example.

\subsection{Rational number
arithmetic}\label{rational-number-arithmetic}

For this example, let's implement a group of Lua functions to perform
rational number (fraction) arithmetic.

In mathematics we usually write rational numbers in the form
\(\frac{\texttt{x}}{\texttt{y}}\) where \texttt{x} and \texttt{y} are
integers and \texttt{y} \(\neq\) \texttt{0}.

For now, let's assume we have a Lua constructor function

\begin{verbatim}
    makeRat(x,y) 
\end{verbatim}

to create a rational number instance from its numerator \texttt{x} and
denominator \texttt{y}. That is, \texttt{makeRat(x,\ y)} constructs
rational number \(\frac{\texttt{x}}{\texttt{y}}\).

Further, let us assume we have selector functions \texttt{numer(r)} and
\texttt{denom(r)} that each take a rational number argument and return
its numerator and denominator, respectively. That is, they satisfy the
equalities:

\begin{verbatim}
    numer(makeRat(x,y)) == x
    denom(makeRat(x,y)) == y
\end{verbatim}

We consider how to implement rational numbers in Lua later, but for now
let's look at rational arithmetic using the constructor and selector
functions above.

Given the knowledge of rational arithmetic from mathematics, we can
define the operations for unary negation, addition, subtraction,
multiplication, and division.

\begin{verbatim}
    local function negRat(r)
       return makeRat(- numer(r), denom(r))
    end

    local function addRat(r,s)
       return makeRat(numer(r) * denom(s) + numer(s) * denom(r),
                      denom(r) * denom(s)                       )
    end

    local function subRat(r,s)
       return makeRat(numer(r) * denom(s) - numer(s) * denom(r),
                      denom(r) * denom(s)                       )
    end

    local function mulRat(r,s)
       return makeRat(numer(r) * numer(s), denom(r) * denom(s))
    end

    local function divRat(r,s)
       return makeRat(numer(r) * denom(s), denom(r) * numer(s))
    end
\end{verbatim}

We can also define a function \texttt{showRat} to convert a rational
number to a convenient string representation.

\begin{verbatim}
    local function showRat(r) 
       return tostring(numer(r)) .. "/" .. tostring(denom(r)) 
    end
\end{verbatim}

Because the comparison operations are similar to each other, they are
good candidates for us to use a higher-order function. We can abstract
out the common pattern of comparisons into a function that takes the
corresponding integer comparison as an argument.

To compare two rational numbers, we can express their values in terms of
a common denominator (e.g., \texttt{denom(x)\ *\ denom(y)}) and then
compare the numerators using the integer comparisons. We can thus
abstract the comparison into a higher-order function \texttt{compare}
that takes an appropriate integer relational operator and returns a
function that compares the two numerators accordingly.

\begin{verbatim}
    local function compare(comp)
       return
          function(r,s)
             local x, y = numer(r) * denom(s), denom(r) * numer(s)
             return comp(x,y)
          end
    end
\end{verbatim}

Then we can define functions for the six relational operators as
follows:

\begin{verbatim}
    local eqRat  = compare(function(x,y) return x == y end)
    local neqRat = compare(function(x,y) return x ~= y end)
    local ltRat  = compare(function(x,y) return x < y  end)
    local leqRat = compare(function(x,y) return x <= y end)
    local gtRat  = compare(function(x,y) return x > y  end)
    local geqRat = compare(function(x,y) return x >= y end)
\end{verbatim}

All these rational arithmetic functions use the constructor function
\texttt{makeRat} and the selector functions \texttt{numer} and
\texttt{denom} assumed above. They do not depend upon any specific
representation for rational numbers.

The above functions work on rational numbers as a \emph{data
abstraction} defined by the constructor function \texttt{makeRat} and
selector functions \texttt{numer} and \texttt{denom}.

\subsection{Rational number data
representation}\label{rational-number-data-representation}

Now, how can we represent rational numbers?

We can represent a rational number as a two-element array (table) with
numerator at index 1 and denominator at index 2. For example,
\texttt{\{1,7\}}, \texttt{\{-1,-7\}}, \texttt{\{3,21\}}, and
\texttt{\{168,1176\}} all represent \(\frac{\texttt{1}}{\texttt{7}}\).

As with any value that can be expressed in many different ways, it is
useful to define a single \emph{canonical} (or \emph{normal}) form for
representing rational number values.

It is convenient for us to choose a rational number representation
\texttt{\{x,y\}} that satisfies the following \emph{implementation
(representation) invariant}:

\begin{quote}
\texttt{y\ \textgreater{}\ 0}, \texttt{x} and \texttt{y} are relatively
prime, and zero is denoted by \texttt{\{0,1\}}.
\end{quote}

By \emph{relatively prime}, we mean that the two integers have no common
divisors except 1.

By \emph{invariant}, we mean a property that always holds except
temporarily while being operated upon. The constructor must make it true
and it remains true before and after all mutator and accessor
operations. It is true before any explicit destructor operation.

An \emph{implementation invariant} is an invariant that is stated in
terms of the concrete data structures used.

This representation has the advantage that the magnitudes of the
numerator \texttt{x} and denominator \texttt{y} are kept small, thus
reducing problems with overflow arising during arithmetic operations.

We thus provide a function for constructing rational numbers in this
canonical form. We define constructor \texttt{makeRat} as follows. This
function checks whether arguments are integers for Lua before 5.3.

\begin{verbatim}
    local function makeRat(x,y)
       if type(x) == "number" and type(y) == "number" and 
             x == math.floor(x) and y == math.floor(y) and y ~= 0 then
          return newRat(x,y)
       else
          error("Cannot construct rational number " ..
                tostring(x) .. "/" .. tostring(y)     )
       end
    end
\end{verbatim}

The \texttt{makeRat} constructor delegates the actual construction of
the rational number to function \texttt{newRat}. Function
\texttt{newRat} assumes that it is called with two appropriate integers.

\begin{verbatim}
    local function newRat(x,y)
       if x == 0 then
          return {0,1}
       else
          local xx = signum(y) * x
          local yy = math.abs(y)
          local d  = gcd(xx,yy)
          return {xx/d, yy/d}
       end
    end
\end{verbatim}

The function \texttt{signum} takes a number and returns the integer
\texttt{-1}, \texttt{0}, or \texttt{1} when the number is negative,
zero, or positive, respectively.

\begin{verbatim}
    local function signum(n)
       if n == 0 then
          return 0 
       elseif n > 0 then
          return 1
       else
          return -1
       end
    end
\end{verbatim}

The function \texttt{gcd} takes two integers and returns their greatest
common divisor.

\begin{verbatim}
    local function gcd(x,y)
       local function gcdaux(x,y)
          if y == 0 then
             return x
          else
             return gcdaux(y, x % y) -- tail recursive
          end
       end

       return gcdaux(math.abs(x), math.abs(y))
    end
\end{verbatim}

Function \texttt{gcd} uses a tail recursive internal function
\texttt{gcdaux} to compute the gcd on the absolute values of its two
integer arguments. It uses the Euclidean Algorithm. (Operation
\texttt{\%} returns the remainder from dividing its first operand by its
second.)

Given \texttt{makeRat} defined as above, we can define \texttt{numer}
and \texttt{denom} as follows:

\begin{verbatim}
    local function numer(r)
       return r[1]
    end

    local function denom(r)
       return r[2]
    end
\end{verbatim}

These functions access the actual data structure used to represent the
rational numbers.

\subsection{Data abstraction and
modules}\label{data-abstraction-and-modules}

There are three groups of functions defined in this package:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  the twelve public rational arithmetic functions \texttt{negRat},
  \texttt{addRat}, \texttt{subRat}, \texttt{mulRat}, \texttt{divRat},
  \texttt{showRat}, \texttt{eqRat}, \texttt{neqRat}, \texttt{ltRat},
  \texttt{leqRat}, \texttt{gtRat}, and \texttt{geqRat}.
\item
  the public constructor function \texttt{makeRat} and public selector
  functions \texttt{numer} and \texttt{denom}.
\item
  the private utility functions called only by the second group
  \texttt{signum}, \texttt{gcd}, and \texttt{newRat}.
\end{enumerate}

As we have seen, \texttt{makeRat}, \texttt{numer}, and \texttt{denom} in
group 2 form the \emph{interface} to the \emph{data abstraction} that
hides the information about the representation of the data. We can
\emph{encapsulate} the group 2 and 3 functions in a Lua \emph{module}.

We put this source code in a script file named (say)
\texttt{rationalCore.lua}. We define the functions so that a function is
defined before it is used, e.g., in the order \texttt{signum},
\texttt{gcd}, \texttt{newRat}, \texttt{makeRat}, \texttt{numer}, and
\texttt{denom}.

As the last executable statement in the module's script, we return the
module table with the public functions defined with appropriate field
names.

\begin{verbatim}
    return { makeRat = makeRat, numer = numer, denom = denom }
\end{verbatim}

Questions:

\begin{itemize}
\item
  Should we also include the function \texttt{newRat} in the public
  interface? What are the advantages and disadvantages of doing so?
\item
  Should we also include the functions \texttt{signum} and \texttt{gcd}
  in the public interface? Or should we, instead, put them in a separate
  module?
\end{itemize}

The rational arithmetic functions in group 1 use the core data
abstraction and, in turn, extend the interface to include rational
number arithmetic operations.

We can encapsulate these in another module \texttt{rational}. This Lua
module loads the data representation module an defines local variables
for the module's operations.

\begin{verbatim}
    local ratco = require("rationalCore")
    local makeRat, numer, denom =
       ratco.makeRat, ratco.numer, ratco.denom 
\end{verbatim}

The module returns both the group 1 and group 2 functions.

\begin{verbatim}
    return { makeRat = makeRat, numer   = numer,  denom   = denom,
             negRat  = negRat,  addRat  = addRat, subRat  = subRat,
             mulRat  = mulRat,  divRat  = divRat, showRat = showRat,
             eqRat   = eqRat,   neqRat  = neqRat, ltRat   = ltRat,
             leqRat  = leqRat,  gtRat   = gtRat,  geqRat  = geqRat
           }
\end{verbatim}

Other modules that use the rational number package can load Lua module
\texttt{rational}. This module can be reused wherever needed.

This modular approach to program design and implementation offers the
potential of scalability and robustness with respect to change.

One key to this \emph{information hiding} approach to design is to
identify the aspects of a software system that are most likely to change
from one version to another and make each a design \emph{secret} of some
module.

The secret of the \texttt{rationalCore} module is the rational number
data representation used. The secret of the \texttt{rational} module
itself is the methods used for rational number arithmetic.

Another key is the use of an \emph{abstract interface}. The interface to
each module focuses on providing operations that are general, not
specific to a particular implementation.

Let's now consider changes to the data representation.

\subsection{Alternative rational number data
representation}\label{alternative-rational-number-data-representation}

In the rational number data representation above (i.e., module
\texttt{rationalCore}), constructor \texttt{makeRat} creates pairs in
which the two integers are relatively prime and the sign is on the
numerator. Selector functions \texttt{numer} and \texttt{denom} just
return these stored values.

An alternative representation is to reverse this approach in functions
\texttt{newRat}, \texttt{numer}, and \texttt{denom}, as shown in the
module \texttt{rationalDeferGCD}.

\begin{verbatim}
    local function newRat(x,y)
       if x == 0 then
          return {0,1}
       else
          return {x,y}
       end
    end

    local function numer(r)
       local x,y = r[1], r[2]
       local xx = signum(y) * x
       local yy = math.abs(y)
       local d  = gcd(xx,yy)
       return xx / d
    end

    local function denom(r)
       local x,y = r[1], r[2]
       local xx = signum(y) * x
       local yy = math.abs(y)
       local d  = gcd(xx,yy)
       return yy / d
    end
\end{verbatim}

This approach defers the calculation of the greatest common divisor
until a selector is called.

The implementation invariant for this rational number representation
requires that, for \texttt{\{x,y\}},

\begin{quote}
\texttt{y} \(\neq\) \texttt{0} and zero is represented by
\texttt{\{0,1\}}.
\end{quote}

Furthermore, function \texttt{numer} and \texttt{denom} satisfy the
equalities

\begin{verbatim}
    numer (makeRat(x,y)) == x'
    denom (makeRat(x,y)) == y'
\end{verbatim}

where \texttt{y\textquotesingle{}\ \textgreater{}\ 0},
\texttt{x\textquotesingle{}} and \texttt{y\textquotesingle{}} are
relatively prime, and
\(\frac{\texttt{x}}{\texttt{y}} = \frac{\texttt{x'}}{\texttt{y'}}\).

Question:

\begin{itemize}
\tightlist
\item
  What are the advantages and disadvantages of the two data
  representations?
\end{itemize}

Like module \texttt{rationalCore}, the design secret for module
\texttt{rationalDeferGCD} is the rational number data representation.

\subsection{Another rational number data
representation}\label{another-rational-number-data-representation}

Another alternative to \texttt{rationalCore} and
\texttt{rationalDeferGCD} is a module that uses a \emph{closure} instead
of an array to represent a rational number. (We use a parameterless
closure, which is also called a \emph{thunk}.)

We call build module \texttt{rationalClo} around the following altered
definitions.

\begin{verbatim}
    local function newRat(x,y)
       if x == 0 then
          return -- return thunk (closure)
             function() return 0, 1 end -- two returns
       else
          return -- return thunk (closure)
             function()
                local xx = signum(y) * x
                local yy = math.abs(y)
                local d  = gcd(xx,yy)
                return xx/d, yy/d -- two returns
             end
       end
    end

    local function numer(r)
       local x, _ = r() -- force thunk (closure)
       return x
    end

    local function denom(r)
       local _, y = r() -- force thunk (closure)
       return y
    end
\end{verbatim}

The implementation invariant for this rational number representation
requires that, for some \texttt{r},

\begin{quote}
For \texttt{x,\ y\ =\ r()}: \texttt{y} \(\neq\) \texttt{0}, \texttt{x}
and \texttt{y} are relatively prime, and if \texttt{x\ ==\ 0} then
\texttt{y\ ==\ 1}.
\end{quote}

Like modules \texttt{rationalCore} and \texttt{rationalDeferGCD}, the
design secret for module \texttt{rationalDeferGCD} is the rational
number data representation.

Regardless of which approach we use, the definitions of the arithmetic
and comparison functions do not change. Thus the \texttt{rational}
module can load data representation module \texttt{rationalCore},
\texttt{rationalDeferGCD}, or \texttt{rationalClo} and get the same
result.

\subsection{Files}\label{files}

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  \href{rational.lua}{Rational arithmetic module} -- outer layer
  implementation of Rational Arithmetic abstraction
\item
  \href{rationalCore.lua}{Rational number data representation using
  two-element arrays} -- module \texttt{rationalCore} implementing
  primitive layer

  \href{rationalCoreTest.lua}{partial test script}
\item
  \href{rationalDeferGCD.lua}{Rational number data representation using
  array but deferring GCD} -- module \texttt{rationalDeferGCD}
  implementing primitive layer

  \href{rationalDeferGCDTest.lua}{partial test script}
\item
  \href{rationalClo.lua}{Rational number data representation using
  closures} -- module \texttt{rationalClo} implementing primitive layer

  \href{rationalCloTest.lua}{partial test script}
\end{enumerate}

\end{document}