Copyright (C) 2017, 2018, H. Conrad Cunningham

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 7, Data Abstraction, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.

Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of September 2018 is a recent version of Firefox from Mozilla.

Code: The Haskell modules for the Rational Arithmetic case study are in files RationalCore.hs, RationalDeferGCD.hs, Rational1.hs, and Rational2.hs.

Lecture Goals

• Illustrate use of data abstraction

• Reinforce and extend the concepts of modular design and programming using Haskell modules

  E.g. invariants

Kinds of Abstraction

1. Procedural abstraction: separate properties of action from implementation details

   Break complex actions into subprograms; develop program as sequence of calls

2. Data abstraction: separate properties of data from representation details

   Identify key data representations; develop program around these and associated operations

Rational Numbers

Mathematical rational numbers $\frac{\texttt{x}}{\texttt{y}}$ where

• x and y integers

• y $\neq$ 0

Rational Number Abstraction

• Data type Rat

• Constructor makeRat :: Int -> Int -> Rat
  where makeRat x y creates math value $\frac{\texttt{x}}{\texttt{y}}$ with $\texttt{y} \neq 0$

• Selector functions numer, denom :: Rat -> Int where:

  if makeRat x y == r in Haskell, then $\frac{\texttt{numer r}}{\texttt{denom r}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$ in math

• Constant zeroRat represents rational number 0

Rational Arithmetic Operations

Assuming data abstraction (Rat, makeRat, zeroRat, numer, denom)

    negRat :: Rat -> Rat 
    negRat x = makeRat (- numer x) (denom x)

    addRat, subRat, mulRat, divRat :: Rat -> Rat -> Rat
    addRat x y = makeRat (numer x * denom y + numer y * denom x)
                         (denom x * denom y) 
    subRat x y = makeRat (numer x * denom y - numer y * denom x)
                         (denom x * denom y) 
    mulRat x y = makeRat (numer x * numer y) (denom x * denom y) 
    divRat x y  -- (2) (3)
        | eqRat y zeroRat = error "Attempt to divide by 0"
        | otherwise       = makeRat (numer x * denom y)
                                    (denom x * numer y)

    eqRat :: Rat -> Rat -> Bool 
    eqRat x y = (numer x) * (denom y) == (numer y) * (denom x)

Representing Rationals

• Choose type synonym Rat

      type Rat = (Int, Int) 

  (1,7), (-1,-7), (3,21), (168,1176) all represent $\frac{\texttt{1}}{\texttt{7}}$

• Choose canonical (normal) form (x,y) that satisfies Rational Representation Property (next slide)

Rational Representation Prop.

• (x,y) $\in$ (Int,Int)

• y > 0

• if x == 0, then y == 1

• x and y are relatively prime

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Advantages of Representation

• Keeps integer magnitudes small – reduces Int overflow issues

• Gives unique representation for zero

      zeroRat :: (Int,Int)
      zeroRat = (0,1)

Implementing Rationals (1)

First implement constructor

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" ) 
    makeRat 0 _ = zeroRat
    makeRat x y = (x' `div` d, y' `div` d) 
        where x' = (signum' y) * x  -- (1,2)
              y' = abs' y 
              d  = gcd' x' y'

1. where clause introduces local definitions x', y', d within makeRat body

2. type inference for x', y', d — all Int because of makeRat signature

Implementing Rationals (2)

Precondition of makeRat x y

y /= 0

Postcondition of makeRat x y = (x',y')

(x',y') satisfies the Rational Representation Property

Rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Together postconditions imply $\frac{\texttt{x'}}{\texttt{y'}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$

Implementing Rationals (3)

    signum' :: Int -> Int      -- similar Prelude signum
    signum' n | n == 0     =  0 
              | n > 0      =  1 
              | otherwise  = -1 

    abs' :: Int -> Int         -- similar Prelude abs
    abs' n | n >= 0    =  n
           | otherwise = -n

    gcd' :: Int -> Int -> Int  -- similar Prelude gcd
    gcd' x y = gcd'' (abs' x) (abs' y) 
        where gcd'' x 0 = x 
              gcd'' x y = gcd'' y (x `rem` y) 

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)

Implementing Rationals (4)

    numer, denom :: Rat -> Int
    numer (x,_) = x
    denom (_,y) = y

Preconditions for numer (x,y) and denom (x,y)

Arguments (x,y) satisfy Rational Representation Property

Postconditions for numer (x,y) = x and denom (x,y) = y

$\frac{\texttt{numer (x,y)}}{y}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$ — no change to input

$\frac{\texttt{x}}{\texttt{denom (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$ — no change to input

Modularization

Package has groups of features:

1. public rational arithmetic functions: negRat, addRat, subRat, mulRat, divRat, eqRat

2. public type Rat, constant zeroRat, constructor makeRat, selectors numer and denom, string converter showRat

3. private utility functions used by second group, but just reimplementations of Prelude functions

Module RationalCore

• Hide secret of rational number data representation

• Reveal public interface: Rat, zeroRat, makeRat, numer, denom, showRat — plus pre/postconditions

• Encapsulate implementations as Haskell module RationalCore.

      module RationalCore
          (Rat, makeRat, zeroRat, numer, denom, showRat)
      where
          -- Rat, makeRat, numer, denom, showRat definitions

• Include utility functions or use Prelude versions directly

Module Rational (1)

• Hide secret of Rational Arithmetic operation implementation (and data representation)

• Use RationalCore data abstraction through its public interface

• Reveal public interface to Rational Arithmetic operations: negRat, addRat, subRat, mulRat, divRat, eqRat – plus pre/postconditions

• Also reveal public interface of core data abstraction: makeRat, numer, denom, showRat – plus pre/postconditions

Module Rational (2)

• Encapsulate implementation as Haskell Rational1

      module Rational1    -- note suffix 1
        ( Rat, makeRat, numer, denom, showRat, -- from RationalCore
          negRat, addRat, subRat, mulRat, divRat, eqRat )
      where
        import RationalCore
        -- negRat, addRat, subRat, mulRat, divRat, eqRat definitions 

Modularization Critique

• Enables modules to be reused

• Offers robustness with respect to change — data representation and arithmetic algorithms change independently

• Allows multiple implementations of each module by keeping public interface stable

• Enables understanding of one module without understanding of internal details of modules it uses

• Costs some in extra code and execution efficiency — likely does not matter given benefits and compiler optimizations

Alternative Data Representation

• Previous module RationalCore:

  • constructor makeRat creates pairs of relatively prime integers

  • selectors numer and denom just return stored integer

• Alternative module RationalDeferGCD:

  • constructor makeRat just stores integers

  • selectors numer and denom returns relatively prime

• Question: What are the advantages and disadvantages of the two data representations?

Implementing RationalDeferGCD (1)

    module RationalDeferGCD
        (Rat, zeroRat, makeRat, numer, denom, showRat)
    where

    type Rat = (Int,Int)

    zeroRat :: (Int,Int)
    zeroRat = (0,1)

    makeRat :: Int -> Int -> Rat
    makeRat x 0 = error ( "Cannot construct a rational number "
                          ++ show x ++ "/0" )
    makeRat 0 y = zeroRat 
    makeRat x y = (x,y)

Implementing RationalDeferGCD (2)

    numer :: Rat -> Int
    numer (x,y) = x' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    denom :: Rat -> Int
    denom (x,y) = y' `div` d
        where x' = (signum' y) * x 
              y' = abs' y 
              d  = gcd' x' y'

    showRat :: Rat -> String
    showRat x = show (numer x) ++ "/" ++ show (denom x)
    
    -- signum', abs', gcd' as before

Deferred Representation Prop.

• (x,y) $\in$ (Int,Int)

• y /= 0

• if x == 0, then y == 1

• rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Compare: Allows y < 0, not relatively prime

RationalDeferGCD Contracts (1)

Precondition makeRat x y

y /= 0

Postcondition makeRat x y = (x',y')

(x',y') satisfies the Deferred Representation Property

Rational number value is $\frac{\texttt{x}}{\texttt{y}}$

RationalDeferGCD Contracts (2)

Precondition numer (x,y) and denom(x,y)

(x,y) satisfies Deferred Representation Property

Postconditions numer (x,y) = x' and denom (x,y) = y

$\frac{\texttt{numer (x,y)}}{y'}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$ — no change to input

$\frac{\texttt{x'}}{\texttt{denom (x,y)}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$ — no change to input

If makeRat x y == r, numer r = x', and denom r = y', then postconditions imply that $\frac{\texttt{x'}}{\texttt{y'}}$ $=$ $\frac{\texttt{x}}{\texttt{y}}$

Module RationalDeferGCD

• Hide “secret” of rational number data representation

• Reveal public interface: Rat, zeroRat, makeRat, numer, denom, showRat — plus preconditions, postconditions

• Encapsulate implementations as Haskell module RationalDeferGCD.

• Include utility functions or use Prelude versions directly

Using RationalDeferGCD

    module Rational2    -- note suffix 2
      ( Rat, zeroRat, makeRat, numer, denom, showRat,
        negRat, addRat, subRat, mulRat, divRat, eqRat )
    where

    import RationalDeferGCD
    -- negRat, addRat, subRat, mulRat, divRat, eqRat definitions
    -- code same as in Rational1

“Abstract” Modules

RationalCore and RationalDeferGCD

• have same interface and functionality

• are interchangeable

• represent by “abstract module” RationalRep (not Haskell 2010 concept)

Rational1 and Rational2

• are same except module name and RationalRep import

Rational Number Package

Figure 7-1. Module Dependencies

Invariants (1)

Invariants assert what must hold for an “object” to be valid

Invariant:

Logical assertion that always holds for every “object” created by public constructors and manipulated only by public operations

Interface invariant:

Invariant stated in terms of public features and abstract properties of “object”

Implementation (representation) invariant:

Detailed invariant giving required relationships among internal features of implementation of “object”

Invariants (2)

• Preconditions of all public operations except constructors

• Postconditions of all public operations except destructors

RationalRep Interface Invariant

For any valid Haskell rational number r:

r $\in$ Rat

denom r > 0

If numer r == 0, then denom r == 1

numer r and denom r are relatively

Rational number value is $\frac{\texttt{numer r}}{\texttt{denom r}}$

RationalRep Pre/Postconditions (1)

Abstract interface precondition makeRat x y

y /= 0

Abstract interface postcondition makeRat x y = r

r satisfies the RationalRep Interface Invariant

Rational number r’s value is $\frac{\texttt{x}}{\texttt{y}}$

RationalRep Pre/Postconditions (2)

Abstract interface precondition numer r and denom r

r satisfies the RationalRep Interface Invariant

Abstract interface postcondition numer r = x' and denom r = y'

Rational number value $\frac{\texttt{x'}}{\texttt{denom r}}$ equals rational number value of r

Rational number value $\frac{\texttt{numer r}}{y'}$ equals rational number value of r

RationalCore Implementation Inv.

For any valid Haskell rational number r:

r == (x,y) for some (x,y) $\in$ Rat

y > 0

if x == 0, then y == 1

x and y are relatively prime

Rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Implies interface invariant given RationalCore implementation

RationalDeferGCD Implementation Inv.

For any valid Haskell rational number r:

r == (x,y) for some (x,y) $\in$ Rat

y /= 0

if x == 0, then y == 1

Rational number value is $\frac{\texttt{x}}{\texttt{y}}$

Implies interface invariant given RationalCore implementation

Other Alternative Representations

• Change alias Rat to use Integer

• Replace alias Rat by a user-defined type Rat

• Divide work differently between makeRat, numer, denom

Haskell Module System

• Haskell 2010’s weak module system does not support multiple implementations well

• GHC’s new mixin package system Backpack offers new possibilities

  Backpack adds a way to define interfaces to “abstract” modules

Testing

Chapter 12 discusses testing of package — test against abstract interface and contracts

• Module RationalRep

  • TestRatRepCore.hs for RationalCore

  • TestRatRepDefer.hs for RationalDeferGCD

• Module Rational

  • TestRational1.hs for Rational using RationalCore.

  • TestRational2.hs for Rational using RationalDeferGCD.

Defining Haskell Modules

• Define in a separate file — enables separate compilation, reuse

• Export public features (functions and data types)

• Do not export private features (functions and data types)

• Use good software engineering design

  • export abstract interface, use criteria for good interfaces
  • hide secret
  • document constraints and assumptions (preconditions, postconditions, invariants)

Key Ideas

• Data abstraction as design, implementation, and testing technique

  • information hiding
  • interface – concrete and abstract
  • preconditions and postconditions
  • invariants – interface and implementation

• Haskell modules

• Rational numbers

Source Code

• RationalCore.hs module

• Rational1.hs module

• RationalDeferGCD.hs module

• Rational2.hs module

• Testing listed on earlier slide