\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 Stepwise Refinement 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 Stepwise Refinement 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 function for Square Root.

\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 Top-Down Stepwise
Refinement}\label{using-top-down-stepwise-refinement}

A useful and intuitive design process for a small program is to begin
with a high-level solution and gradually fill in the details. We call
this process top-down stepwise refinement.

Let's consider an example.

\subsection{Developing a square root
package}\label{developing-a-square-root-package}

Consider the problem of computing the nonnegative square root of a
nonnegative number \(x\). Mathematically, we want to find the number
\(y\) such that

\begin{quote}
\(y \geq 0\) and \(y^{2} = x\).
\end{quote}

A common algorithm in mathematics for computing the above \(y\) is to
use Newton's method of successive approximations, which has the
following steps for square root:

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\tightlist
\item
  Guess at the value of \(y\).
\item
  If the current approximation (guess) is sufficiently close (i.e.~good
  enough), return it and stop; otherwise, continue.
\item
  Compute an improved guess by averaging the value of \(y\) and \(x/y\),
  then go back to step 2.
\end{enumerate}

To encode this algorithm in Lua, we work top down to decompose the
problem into smaller parts until each part can be solved easily. We
begin this \emph{top-down stepwise refinement} by defining a function

\begin{verbatim}
    sqrt_iter(guess,x)
    
\end{verbatim}

to compute the square root of \texttt{x} iteratively, where
\texttt{guess} is the current approximation.

We can encode step 2 of the above algorithm in Lua as follows:

\begin{verbatim}
    local function sqrt_iter(guess,x)
       if good_enough(guess,x) then
          return guess
       else
          return sqrt_iter(improve(guess,x),x)
       end
    end
\end{verbatim}

We have two cases:

\begin{itemize}
\item
  When the current approximation \texttt{guess} is sufficiently close to
  \texttt{x}, we return \texttt{guess}.

  We abstract this decision into a separate function:

\begin{verbatim}
good_enough(guess,x)
\end{verbatim}
\item
  When the approximation is not yet close enough, we reduce the problem
  to another application of \texttt{sqrt\_iter} itself to an improved
  approximation.

  We abstract the improvement process into a separate function:

\begin{verbatim}
improve(guess,x)
\end{verbatim}

  To ensure termination of \texttt{sqrt\_iter}, the argument
  \texttt{improve(guess,x)} on the recursive call must get closer to a
  value that satisfies its base case.
\end{itemize}

The function \texttt{improve} takes the current \texttt{guess} and
\texttt{x} and carries out step 3 of the algorithm, thus averaging
\texttt{guess} and \texttt{x/guess}, as follows:

\begin{verbatim}
    local function improve(guess,x)
       return average(guess,x/guess)
    end
\end{verbatim}

Here we abstract \texttt{average} into a separate function as follows:

\begin{verbatim}
    local function average(x,y)
       return (x + y) / 2
    end
\end{verbatim}

The new guess is closer to the square root than the previous guess. Thus
the algorithm will terminate assuming a good choice for function
\texttt{good\_enough}, which guards the base case of the
\texttt{sqrt\_iter} recursion.

How should we define \texttt{good\_enough}? Given that we are working
with the limited precision of computer floating point arithmetic, it is
not easy to choose an appropriate test for all situations. Here we
simplify this and use a tolerance of 0.001.

We thus postulate the following definition for \texttt{good\_enough}:

\begin{verbatim}
   local function good_enough(guess,x)
       return math.abs(square(guess)- x) < 0.001
    end
\end{verbatim}

In the above, \texttt{math.abs} is the built-in absolute value function
defined in the Lua \texttt{math} library. We define \texttt{square} as
the following simple function (but could replace it by just
\texttt{guess\ *\ guess}).

\begin{verbatim}
    local function square(x)
       return x * x
    end
\end{verbatim}

What is a good initial guess? It is sufficient to just use 1. So we can
define an overall square root function \texttt{sqrt} as follows:

\begin{verbatim}
    local function sqrt(x)
       if type(x) == "number" and x >= 0 then
          return sqrt_iter(1,x)
       else
          error("Square root cannot be computed for "
                .. tostring(x), 2)
       end
    end
\end{verbatim}

\subsection{Packaging the functions}\label{packaging-the-functions}

Because the only public function needed is \texttt{sqrt}, we can make
all the other functions local to \texttt{sqrt}. That is, we put their
definitions inside the body of \texttt{sqrt}. We must define each of the
functions before it is called by another function.

\begin{verbatim}
    local function sqrt(x)

       local function square(x)
          return x * x
       end

       local function good_enough(guess,x)
          return math.abs(square(guess)- x) < 0.001
       end

       local function average(x,y)
          return (x + y) / 2
       end

       local function improve(guess,x)
          return average(guess,x/guess)
       end

       local function sqrt_iter(guess,x)
          if good_enough(guess,x) then
             return guess
          else
             return sqrt_iter(improve(guess,x),x)
          end
       end

       if type(x) == "number" and x >= 0 then
          return sqrt_iter(1,x)
       else
          error("Square root cannot be computed for " 
                .. tostring(x), 2)
       end
    end
\end{verbatim}

An alternative would be to put these functions in a Lua module and just
export function \texttt{sqrt}.

\subsection{Top-down stepwise
refinement}\label{top-down-stepwise-refinement}

The program design strategy known as \emph{top-down stepwise refinement}
is a relatively intuitive design process that has long been applied in
the design of structured programs in imperative procedural languages. It
is also useful in the functional programming setting, as is shown by the
square root example above.

In Lua, we can apply top-down stepwise refinement as follows.

\begin{enumerate}
\def\labelenumi{\arabic{enumi}.}
\item
  Start with a high-level solution to the problem consisting of one or
  more functions. For each function, identify its signature and
  functional requirements (i.e., its inputs, outputs, and termination
  condition).

  Some parts of each function are abstracted as ``pseudocode''
  expressions or as-yet-undefined function calls.
\item
  Choose one of the incomplete parts. Consider its signature and
  functional requirements. Refine the incomplete part by breaking it
  into subparts or, if simple, defining it directly in terms of Lua
  expressions (including calls to library functions).

  When refining an incomplete part, consider the various options
  according to the relevant design criteria (e.g., time, space,
  generality, understandability, elegance, etc.)

  The refinement of the function may require a refinement of the data
  being passed. If so, back up in the refinement process and readdress
  previous design decisions as needed.

  If it not possible to design an appropriate refinement, back up in the
  refinement process and readdress previous design decisions.
\item
  Continue step 2 until all parts are fully defined in terms of Lua code
  and data and the resulting set of functions meets all required
  criteria.
\end{enumerate}

For as long as possible, we should stay with terminology and notation
that is close to the problem being solved. We can do this by choosing
appropriate function names and signatures and data types.

For stepwise refinement to work well, we must be willing to back up to
earlier design decisions when appropriate. We should keep good
documentation of the intermediate design steps.

The stepwise refinement method can work well for small programs, but it
may not scale well to large, long-lived, general purpose programs. In
particular, stepwise refinement may lead to a module structure in which
modules are tightly coupled and not robust with respect to changes in
requirements. A combination of techniques may be needed to develop
larger software systems.

\subsection{Files}\label{files}

\begin{itemize}
\tightlist
\item
  \href{sqrt.lua}{Square root code adapted from SICP}
\end{itemize}

\end{document}