with Interpreters

and Functional Programming

— Section 6.2 —

Using Top-Down Stepwise Refinement

(Procedural Abstraction)

**H. Conrad Cunningham**

**12 September 2018**

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.

Illustrate use of procedural abstraction

Introduce a development method for programs with several functions

Introduce modular programming using Haskell modules

**Procedural abstraction:**separate properties of*action*from implementation detailsBreak complex actions into subprograms; develop program as sequence of calls

**Data abstraction:**separate properties of*data*from representation detailsIdentify key data representations; develop program around these and associated operations

Problem: find the number $y$ such that

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

Newton’s method of successive approximations

- Guess value of $y$
- If guess is “good enough”, return it as $y$
- Compute “improved” guess
- “average” guess $y$ and $x/y$
- go back to step 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

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

Postulate function with signature

Encode Newton method step 2

`goodEnough`

determines when sufficiently close to solution

`improve`

generates better guess`improve guess x`

must**always**yield better guess (approach base case)

`improve`

Refine `improve`

in Newton step 3 – assuming *precondition* `x >= 0 && guess > 0`

`average`

computes mean of two valuesnew guess

`average guess (x/guess)`

closer to exact solution (assuming`guess > 0`

)

`goodEnough`

Refine `goodEnough`

be wary of inexact floating point arithmetic!

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

`abs`

absolute value function from standard library (Prelude)`square`

easy (could just be`guess * guess`

)

Sufficient just to use 1

hide

`guess`

argument to`sqrtIter`

avoid name clash with

`sqrt`

function in standard Prelude

`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)
```

Example use of `Sqrt`

module (from `TestSqrt.hs`

)

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

Square Root module

`Sqrt.hs`

Smoke testing module

`TestSqrt.hs`