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

Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Section 6.3, Modular Design and Programming, 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.

Lecture Goals

• Introduce modular development methods for

  • larger programs than so far
  • programs with more complex data
  • programs whose requirements may change
  • programs with multiple versions over time

• Describe how to use Haskell modules effectively with these methods

Module

• “a work assignment given to a programmer or group of programmers” [Parnas 1978] — software engineering concept

• Also program unit defined by convention or construct — programming language concept

• Ideally language feature supports software engineering method

Goals of Modular Design

1. Enable programmers to understand system by focusing on one module at time (comprehensibility)

2. Shorten development time by minimizing required communication among groups (independent development)

3. Make system flexible by limiting number of modules affected by significant changes (changeability)

Information-Hiding Module

• Forms cohesive unit of functionality separate from other modules

• Hides a design decision (its secret) from other modules

• Encapsulates aspect of system likely to change (its secret)

• Aspects likely to change independently become secrets of separate modules

• Aspects unlikely to change become interactions (connections) among modules

Secret of Square Root Module

• Algorithm for computing square root

Contracts

Contract specifies how function (e.g. within module) behaves

• Precondition

• Postcondition

• Invariant (in next chapter)

Precondition

Precondition:

Logical assertion that caller (client) must ensure holds before function call

• Implicitly requires type signature satisfied

• Specifies valid combinations of values of arguments and global structures accessed or modified

• Means called function expected to terminate with correct result

Postcondition

Postcondition:

If precondition holds, then function must terminate with this logical assertion satisfied

• Implicitly requires type signature satisfied

• Specifies return values (and new state) in terms of arguments and state before call

Factorial Contracts (1)

    fact3 :: Int -> Int
    fact3 0 = 1 
    fact3 n = n * fact3 (n-1) 

Precondition: n >= 0 (to avoid infinite recursion)

Postcondition: fact n $=$ $fact'(n)$ (math definition)

Same for fact1 and fact2

Factorial Contracts (2)

    fact4 :: Int -> Int 
    fact4 n 
      | n == 0 =  1 
      | n >= 1 =  n * fact4 (n-1)

Precondition: n >= 0 (to avoid failing pattern match)

Postcondition: fact4 n $=$ $fact'(n)$

Same for fact4'

Factorial Contracts (3)

    fact5 :: Int -> Int 
    fact5 n = product [1..n]

Precondition: True — “weaker” than others

Postcondition: fact5 n == if n >= 0 then fact’(n) else 1 — “stronger” than others

Square Root Contract

Precondition sqrt' x: x >= 0 — undefined for negatives

Postcondition: sqrt' x:

    (sqrt x - 0.001)^2 < (sqrt x)^2 < (sqrt x + 0.001)^2

Module Interface

Interface:

• “set of assumptions … each programmer needs to make about the other program … to demonstrate the correctness of his own program” [Britton 1981/] (Britton, Parker, and Parnas)

• includes public function signatures (name, arguments, return)

• includes constraints on environment and argument values (preconditions, postconditions, invariants)

Interface for Sqrt Module

• sqrt :: Double -> Double

• Precondition and postcondition defined above

Abstract Interface for Module

Abstract interface:

• does not change when one module implementation substituted for another

• concentrates on module’s essential aspects and obscures incidental aspects that vary among implementations

Information hiding with abstract interfaces supports software reuse

Abstract Interface for Sqrt Module

• Same as concrete interface in this case, not in general (see example in chapter 7)

• sqrt :: Double -> Double

• Precondition and postcondition defined above

Client-Supplier Relationship (1)

Design from two points of view simultaneously:

supplier

developers of the module—providers of the services

client

users of the module—users of the services (e.g. designers of other modules)

   ________________             ________________ 
  |                |           |                |
  |     Client     |===USES===>|    Supplier    |
  |________________|           |________________|

    (module user)                   (module)

Client-Supplier Relationship (2)

Supplier’s concerns:

• efficient and reliable algorithms and data structures

• convenient implementation

• easy maintenance

Client-Supplier Relationship (3)

Clients’ concerns:

• accomplishing their own tasks

• using supplier module without effort to understand internals

• having sufficient, but not overwhelming, set of operations.

Client-Supplier Contract (1)

1. Gives responsibilities of client

   Conditions under which supplier must deliver results

   When preconditions of operations satisfied

2. Gives the responsibilities of the supplier

   Benefits supplier must deliver

   make the postconditions hold

Client-Supplier Contract (2)

• Protects client by specifying how much must be done by supplier

• Protects supplier by specifying how little acceptable to client

Criteria for Good Interfaces (1)

Cohesion:

Fit all operations together to support single, coherent purpose

Consistency:

Provide internally consistent set of operations (naming, arguments, return, behavior) — avoid surprises!

Simplicity:

Avoid needless features

No redundancy:

Avoid offering same service in multiple ways

Criteria for Good Interfaces (2)

Atomicity:

Do not combine several operations if needed individually — each primitive, not decomposable into others

Completeness:

Include all primitive operations that make sense for abstraction

Reusability:

Make general for use beyond initial context

Robustness:

Keep interface stable even if implementation changes

Criteria for Good Interfaces (3)

Convenience:

Provide additional operations for user convenience — after careful study

• Tradeoff conflicts among criteria: completeness vs. simplicity, reusability vs. simplicity, convenience vs. { consistency, simplicity, no redundancy, atomicity}

• Tradeoff criteria against efficiency and functionality

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

• Module as unit of work in software engineering

  • information hiding

  • secret

  • abstract interface

  • contract

• Client-supplier relationship and contract

• Criteria for good interfaces

• Haskell module features