% CSci 450: Organization of Programming Languages \ Using Data Abstraction in Lua % H. Conrad Cunningham % 13 September 2016 Copyright (C) 2016, H. Conrad Cunningham **Acknowledgements:** Adapted from my notes *Introduction to Functional Programming Using Haskell* (under development, 2016) and example Lua modules for Rational Arithmetic. **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} # 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. ## 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 `x` and `y` are integers and `y` $\neq$ `0`. For now, let's assume we have a Lua constructor function makeRat(x,y) to create a rational number instance from its numerator `x` and denominator `y`. That is, `makeRat(x, y)` constructs rational number $\frac{\texttt{x}}{\texttt{y}}$. Further, let us assume we have selector functions `numer(r)` and `denom(r)` that each take a rational number argument and return its numerator and denominator, respectively. That is, they satisfy the equalities: numer(makeRat(x,y)) == x denom(makeRat(x,y)) == y 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. 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 We can also define a function `showRat` to convert a rational number to a convenient string representation. local function showRat(r) return tostring(numer(r)) .. "/" .. tostring(denom(r)) end 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., `denom(x) * denom(y)`) and then compare the numerators using the integer comparisons. We can thus abstract the comparison into a higher-order function `compare` that takes an appropriate integer relational operator and returns a function that compares the two numerators accordingly. 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 Then we can define functions for the six relational operators as follows: 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) All these rational arithmetic functions use the constructor function `makeRat` and the selector functions `numer` and `denom` assumed above. They do not depend upon any specific representation for rational numbers. The above functions work on rational numbers as a *data abstraction* defined by the constructor function `makeRat` and selector functions `numer` and `denom`. ## 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, `{1,7}`, `{-1,-7}`, `{3,21}`, and `{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 *canonical* (or *normal*) form for representing rational number values. It is convenient for us to choose a rational number representation `{x,y}` that satisfies the following *implementation (representation) invariant*: > `y > 0`, `x` and `y` are relatively prime, and zero is denoted by `{0,1}`. By *relatively prime*, we mean that the two integers have no common divisors except 1. By *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 *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 `x` and denominator `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 `makeRat` as follows. This function checks whether arguments are integers for Lua before 5.3. 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 The `makeRat` constructor delegates the actual construction of the rational number to function `newRat`. Function `newRat` assumes that it is called with two appropriate integers. 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 The function `signum` takes a number and returns the integer `-1`, `0`, or `1` when the number is negative, zero, or positive, respectively. local function signum(n) if n == 0 then return 0 elseif n > 0 then return 1 else return -1 end end The function `gcd` takes two integers and returns their greatest common divisor. 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 Function `gcd` uses a tail recursive internal function `gcdaux` to compute the gcd on the absolute values of its two integer arguments. It uses the Euclidean Algorithm. (Operation `%` returns the remainder from dividing its first operand by its second.) Given `makeRat` defined as above, we can define `numer` and `denom` as follows: local function numer(r) return r[1] end local function denom(r) return r[2] end These functions access the actual data structure used to represent the rational numbers. ## Data abstraction and modules There are three groups of functions defined in this package: 1. the twelve public rational arithmetic functions `negRat`, `addRat`, `subRat`, `mulRat`, `divRat`, `showRat`, `eqRat`, `neqRat`, `ltRat`, `leqRat`, `gtRat`, and `geqRat`. 2. the public constructor function `makeRat` and public selector functions `numer` and `denom`. 3. the private utility functions called only by the second group `signum`, `gcd`, and `newRat`. As we have seen, `makeRat`, `numer`, and `denom` in group 2 form the *interface* to the *data abstraction* that hides the information about the representation of the data. We can *encapsulate* the group 2 and 3 functions in a Lua *module*. We put this source code in a script file named (say) `rationalCore.lua`. We define the functions so that a function is defined before it is used, e.g., in the order `signum`, `gcd`, `newRat`, `makeRat`, `numer`, and `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. return { makeRat = makeRat, numer = numer, denom = denom } Questions: - Should we also include the function `newRat` in the public interface? What are the advantages and disadvantages of doing so? - Should we also include the functions `signum` and `gcd` in the public interface? Or should we, instead, put them in a separate module? 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 `rational`. This Lua module loads the data representation module an defines local variables for the module's operations. local ratco = require("rationalCore") local makeRat, numer, denom = ratco.makeRat, ratco.numer, ratco.denom The module returns both the group 1 and group 2 functions. 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 } Other modules that use the rational number package can load Lua module `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 *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 *secret* of some module. The secret of the `rationalCore` module is the rational number data representation used. The secret of the `rational` module itself is the methods used for rational number arithmetic. Another key is the use of an *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. ## Alternative rational number data representation In the rational number data representation above (i.e., module `rationalCore`), constructor `makeRat` creates pairs in which the two integers are relatively prime and the sign is on the numerator. Selector functions `numer` and `denom` just return these stored values. An alternative representation is to reverse this approach in functions `newRat`, `numer`, and `denom`, as shown in the module `rationalDeferGCD`. 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 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 `{x,y}`, > `y` $\neq$ `0` and zero is represented by `{0,1}`. Furthermore, function `numer` and `denom` satisfy the equalities numer (makeRat(x,y)) == x' denom (makeRat(x,y)) == y' where `y' > 0`, `x'` and `y'` are relatively prime, and $\frac{\texttt{x}}{\texttt{y}} = \frac{\texttt{x'}}{\texttt{y'}}$. Question: - What are the advantages and disadvantages of the two data representations? Like module `rationalCore`, the design secret for module `rationalDeferGCD` is the rational number data representation. ## Another rational number data representation Another alternative to `rationalCore` and `rationalDeferGCD` is a module that uses a *closure* instead of an array to represent a rational number. (We use a parameterless closure, which is also called a *thunk*.) We call build module `rationalClo` around the following altered definitions. 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 The implementation invariant for this rational number representation requires that, for some `r`, > For `x, y = r()`: `y` $\neq$ `0`, `x` and `y` are relatively prime, and if `x == 0` then `y == 1`. Like modules `rationalCore` and `rationalDeferGCD`, the design secret for module `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 `rational` module can load data representation module `rationalCore`, `rationalDeferGCD`, or `rationalClo` and get the same result. ## Files 1. [Rational arithmetic module]() -- outer layer implementation of Rational Arithmetic abstraction 2. [Rational number data representation using two-element arrays ]() -- module `rationalCore` implementing primitive layer [partial test script]() 3. [Rational number data representation using array but deferring GCD ]() -- module `rationalDeferGCD` implementing primitive layer [partial test script]() 3. [Rational number data representation using closures ]() -- module `rationalClo` implementing primitive layer [partial test script]()