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

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Section 6.2, Using Top-Down Stepwise Refinement, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming. This is part of Chapter 6, Procedural Abstraction.

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 module for the Square root case study is in source file Sqrt.hs. Source file TestSqrt.hs includes some smoke testing code.

Lecture Goals

• Illustrate use of procedural abstraction

• Introduce a development method for programs with several functions

• Introduce modular programming using Haskell modules

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

Square Root Problem

• Problem: find the number $y$ such that

  $y \geq 0$ and $y^{2} = x$.

• Newton’s method of successive approximations

  1. Guess value of $y$
  2. If guess is “good enough”, return it as $y$
  3. Compute “improved” guess
     • “average” guess $y$ and $x/y$
     • go back to step 2

Solution Strategy (1 of 2)

Top-down stepwise refinement – adapt general method to Haskell

• Start with high-level solution

  • define one or more functions

  • include both concrete code (Haskell) and abstract code (pseudocode)

  • give type signatures of functions

  • specify inputs, outputs, and termination conditions

Solution Strategy (2 of 2)

• Choose an abstract (incomplete) part

  • refine it into subparts: concrete Haskell and abstract pseudocode

  • refine data structures if needed

  • consider relevant criteria (termination, time, space, generality, etc.)

  • stay with problem terminology and notation

  • if not a good choice, back up and try other choices

• Continue previous step until all parts executable and meet criteria

High-level Solution (1 of 2)

Postulate function with signature

    sqrtIter :: Double -> Double -> Double 

Encode Newton method step 2

    sqrtIter guess x 
        | goodEnough guess x = guess 
        | otherwise          = sqrtIter (improve guess x) x 

• goodEnough determines when sufficiently close to solution

      goodEnough :: Double -> Double -> Bool 

High-level Solution (2 of 2)

    sqrtIter guess x 
        | goodEnough guess x = guess 
        | otherwise          = sqrtIter (improve guess x) x 

• improve generates better guess

      improve :: Double -> Double -> Double

• improve guess x must always yield better guess (approach base case)

Refinement: improve

Refine improve in Newton step 3 – assuming precondition x >= 0 && guess > 0

    improve :: Double -> Double -> Double
    improve guess x = average guess (x/guess)

• average computes mean of two values

      average :: Double -> Double -> Double
      average x y = (x + y) / 2

• new guess average guess (x/guess) closer to exact solution (assuming guess > 0)

Refinement: goodEnough

Refine goodEnough

• be wary of inexact floating point arithmetic!

• choose tolerance of 0.001 (might not work in all cases)

      goodEnough :: Double -> Double -> Bool 
      goodEnough guess x = abs (square guess - x) < 0.001 

• abs absolute value function from standard library (Prelude)

• square easy (could just be guess * guess)

      square :: Double -> Double 
      square x = x * x 

Initial Guess

Sufficient just to use 1

    sqrt' :: Double -> Double
    sqrt' x | x >= 0 = sqrtIter 1 x

• hide guess argument to sqrtIter

• avoid name clash with sqrt function in standard Prelude

Making Haskell Module Sqrt.hs

    module Sqrt -- put in file "Sqrt.hs"
        (sqrt') -- only export sqrt', others hidden
    where

    sqrt' :: Double -> Double
    sqrt' x | x >= 0 = sqrt_iter 1 x

    sqrt_iter :: Double -> Double -> Double
    sqrt_iter guess x
        | good_enough guess x = guess
        | otherwise           = sqrt_iter (improve guess x) x

    good_enough :: Double -> Double -> Bool
    good_enough guess x = abs (square guess - x) < 0.001

    square :: Double -> Double
    square x = x * x

    average :: Double -> Double -> Double
    average x y = (x + y) / 2

    improve :: Double -> Double -> Double
    improve guess x = average guess (x/guess)

Using Haskell Module

Example use of Sqrt module (from TestSqrt.hs)

    module TestSqrt
    where

    import Sqrt -- file Sqrt.hs, import all public features 

    main = do
        putStrLn (show (sqrt' 16))
        putStrLn (show (sqrt' 2))

Key Ideas

• Top-down stepwise refinement method

  • develop incrementally
  • define type signatures
  • specify inputs and outputs
  • specify and enforce termination conditions

• Haskell modules

• Newton’s method applied to square root

Source Code

• Square Root module Sqrt.hs

• Smoke testing module TestSqrt.hs