Modularization & ADTs
Optional Textbook Readings: CP:AMA 19.1, 10.2 – 10.5
The primary goal of this section is to be able to write a module.
CS 136 Winter 2022 06: Modularization & ADTs 1
Copyright By PowCoder代写 加微信 powcoder
Modularization
So far we have been designing programs with all of our definitions in a single source (.c) file.
For larger programs, keeping all of the code in one file is unwieldy.
Teamwork on a single file is awkward, and it is difficult to share or re-use code between programs.
A better strategy is to use modularization to divide programs into well defined modules.
CS 136 Winter 2022 06: Modularization & ADTs 2
The concept of modularization extends far beyond computer science. There are examples of modularization in construction, automobiles, furniture, nature, etc.
A practical example of a good modular design is an “AA battery”.
We have already seen an elementary type of modularization in the form of helper functions that can “help” many other functions.
We will extend and formalize this notion of modularization.
When designing larger programs, we move from writing “helper functions” to writing “helper modules”.
CS 136 Winter 2022 06: Modularization & ADTs 3
A module provides a collection of functions† that share a common aspect or purpose.
† Modules can provide elements that are not functions (e.g., data structures and variables) but their primary purpose is to provide functions.
For convenience in these notes, we describe modules as providing only functions.
CS 136 Winter 2022 06: Modularization & ADTs 4
Many modern languages have strong support for modules.
For example, recently (2020) modules were added to C++, with the new import and export keywords;
export module linear_algebra;
import matrix;
export void row_reduce(…) {…}
The C language does not fully support modules as they are understood in modern programming.
However, we can still achieve module-like behaviour and learn the core concepts of modularization.
C “modules” are also commonly known as libraries.
CS 136 Winter 2022 06: Modularization & ADTs 5
Modules vs. files
In this course, and in much of the “real world”, it is considered good
style to store modules in separate files.
While the terms file and module are often used interchangeably, a
file is only a module if it provides functions for use outside of the file.
Some computer languages enforce this relationship (one file per module), while in others it is only a popular convention.
There are advanced situations (beyond the scope of this course) where it may be more appropriate to store multiple modules in one file, or to split a module across multiple files.
CS 136 Winter 2022 06: Modularization & ADTs 6
Terminology
It is helpful to think of a “client” that requires the functions that a
module provides.
In practice, the client is a file that may be written by yourself, a co-worker or even a stranger.
Conceptually, it is helpful to imagine the client as a stranger.
CS 136 Winter 2022 06: Modularization & ADTs 7
Large programs can be built from many modules.
A module can be a client itself and require functions from other modules.
The module dependency graph cannot have any cycles. There must be a “root” (or main file) that acts only as a client.
This is the program file that defines main and is “run”.
CS 136 Winter 2022 06: Modularization & ADTs 8
Building a program
In Section 04 we briefly discussed how we convert (“compile”) a source file (.c) into machine code (.o or .ll) before it can be “run”.
When building a program, we can combine (“link” ) multiple machine code files together to form a single program.
In practice, that means we can “build” a program from multiple source code files and/or machine code files.
main.c module1.c module2.c module3.ll
Modules do not contain a main function.
Only one main function can be defined in a program.
CS 136 Winter 2022 06: Modularization & ADTs 9
Motivation
There are three key advantages to modularization: re-usability, maintainability and abstraction.
Re-usability: A good module can be re-used by many clients. Once we have a “repository” of re-usable modules, we can construct large programs more easily.
Maintainability: It is much easier to test and debug a single module instead of a large program. If a bug is found, only the module that contains the bug needs to be fixed. We can even replace an entire module with a more efficient or more robust implementation.
CS 136 Winter 2022 06: Modularization & ADTs 10
Abstraction: To use a module, the client needs to understand what functionality it provides, but it does not need to understand how it is implemented. In other words, the client only needs an “abstraction” of how it works. This allows us to write large programs without having to understand how every piece works.
Modularization is also known in computer science as the Separation of Concerns (SoC).
CS 136 Winter 2022 06: Modularization & ADTs 11
example: fun number module
Imagine that some integers are more “fun” than others, and we want to create a fun module that provides an is_fun function.
// fun.c [MODULE]
// is_fun(n) determines if n is fun or not
bool is_fun(int n) {
return (n == -3 || n == 42 || n == 136 ||
n==225 ||n==1337||n==4010|| n == 8675309);
We have to learn a few more concepts before we can complete our module.
CS 136 Winter 2022 06: Modularization & ADTs 12
Our (yet to be completed) fun module illustrates the three key advantages of modularization.
re-usability: multiple programs can use the fun module. maintainability: When new integers become fun (or become less
fun), only the fun module needs to be changed.
abstraction: The client does not need to understand what makes an integer fun.
CS 136 Winter 2022 06: Modularization & ADTs 13
Calling module functions
is_fun is defined in the module (fun.c) file.
How can we call is_fun from our client (e.g., main.c)?
// main.c [CLIENT]
int main(void) {
// fun.c [MODULE]
bool is_fun(int n) {
b = is_fun(k); // ERROR
The is_fun function is not in scope.
Also, because C is statically typed, it needs to know the return and
parameter types of is_fun…
CS 136 Winter 2022 06: Modularization & ADTs 14
Declarations
In C, a function or variable must be declared before (“above”) it can be “accessed” (or referenced).
A declaration introduces an identifier (“name”) into a program and specifies its type.
In C, there is a subtle difference between a definition and a declaration.
Here, when we use “identifiers” it does not include structures (structs) – they are declared differently (more on them later).
CS 136 Winter 2022 06: Modularization & ADTs 15
Declaration vs. definition
• A declaration only specifies the type of an identifier. • A definition instructs C to “create” the identifier.
However, a definition also specifies the type of the identifier, so a definition also includes a declaration.
An identifier can be declared multiple times, but only defined once.
Unfortunately, not all computer languages and reference manuals use these terms consistently.
CS 136 Winter 2022 06: Modularization & ADTs 16
A function declaration is simply the function header followed by a semicolon (;) instead of a code block.
It specifies the function type (the return and parameter types).
example: function declaration
int my_add(int a, int b);
int main(void) {
trace_int(my_add(1, 2));
// function DECLARATION
// this is now ok
// function DEFINITION
int my_add(int a, int b) {
return a + b;
By declaring my_add above main, it is now available in main.
CS 136 Winter 2022 06: Modularization & ADTs 17
C ignores the parameter names in a function declaration (it is only interested in the parameter types).
The parameter names can be different from the definition or not present at all.
// These are all equivalent:
int my_add(int a, int b);
int my_add(int, int);
int my_add(int these_are, int ignored);
It is good style to include the correct (and meaningful) parameter names in the declaration to aid communication.
CS 136 Winter 2022 06: Modularization & ADTs 18
A variable declaration starts with the extern keyword, followed by the type and then the variable name. There is no initialization.
example: variable declaration
extern int g;
int main(void) {
printf(“%d\n”, g);
int g = 7;
// variable DECLARATION
// this is now ok
// variable DEFINITION
Variable declarations are uncommon.
CS 136 Winter 2022 06: Modularization & ADTs 19
Revisiting Scope
One way to think about declarations is that they extend the scope of
an identifier.
extern int g;
int main(void) {
printf(“%d\n”, g);
int g = 7;
// g OUT of scope
// declaration:
// g is now IN scope
// definition
CS 136 Winter 2022 06: Modularization & ADTs 20
Scope vs. memory
Remember, don’t confuse the concepts of scope with memory (or storage).
int main(void) {
printf(“%d\n”, z); // INVALID: z not in scope
int z = 2;
Remember, all global variables (from all files) are in memory before the program is “run”.
In the above example, z is in memory (and initialized) before main is called but z is not in scope within the main function because it has not yet been declared.
CS 136 Winter 2022 06: Modularization & ADTs 21
Program scope
A declaration can bring an identifier from another file into scope:
// main.c [CLIENT]
extern int g;
// g IN scope
int main(void) {
printf(“%d\n”, g); // ok
// module.c [MODULE]
int g = 7;
By default, C global identifiers are “accessible” to every file in the program if they are declared.
We will refer to this as program scope.
CS 136 Winter 2022 06: Modularization & ADTs 22
Revisiting module functions
We have solved our previous problem. We can now call our module function is_fun from our client (main.c) by declaring it:
// main.c [CLIENT]
// *** NEW declaration ***
bool is_fun(int n);
// fun.c [MODULE]
bool is_fun(int n) {
int main(void) {
b = is_fun(k);
CS 136 Winter 2022
06: Modularization & ADTs 23
Module scope
To “hide” a global identifier from other files, prefix the definition with
the static keyword. // main.c [CLIENT]
// this will not work
extern int g;
int main(void) {
printf(“%d\n”, g); // ERR
// module.c [MODULE]
static int g = 7;
In other words, the static keyword restricts the scope of a global identifier to the file (module) it is defined in.
We will refer to this as module scope.
CS 136 Winter 2022 06: Modularization & ADTs 24
Types of scope (revisited)
• local (block) identifiers
only available inside of the function (or block)
• global identifiers:
– program scope identifiers (default)
available to any file in the program (if declared)
– module scope identifiers (defined as static) only available in the file they are defined in
We continue to use global scope to refer to identifiers that have either program or module scope.
CS 136 Winter 2022 06: Modularization & ADTs 25
Use static to give module functions and variables module scope if they are not meant to be provided.
// fun.c [MODULE]
static const int module_scope_variable = 42;
static int is_fun_helper(int n) {
bool is_fun(int n) {
The static keyword is not related to static typing. private would have been a better choice than static.
CS 136 Winter 2022 06: Modularization & ADTs 26
Module interface
The module interface is the list of the functions that the module provides (including the documentation).
The interface is separate from the module implementation, which is the code of the module (i.e., function definitions).
The interface is everything that a client would need to use the module.
The client does not need to see the implementation.
CS 136 Winter 2022 06: Modularization & ADTs 27
Terminology (revisited)
The interface is what is provided to the client. The implementation is hidden from the client.
CS 136 Winter 2022 06: Modularization & ADTs 28
Interface contents
The contents of the interface include:
• an overall description of the module
• a function declaration for each provided function
• documentation (e.g., a purpose) for each provided function
Ideally, the interface would also provide examples to illustrate how the module is used and how the interface functions interact.
Examples are not required in this course.
CS 136 Winter 2022 06: Modularization & ADTs 29
Interface (.h) files
For C modules, the interface is placed in a separate file with a .h
file extension.
// fun.h [INTERFACE]
// This module is all about having fun
// is_fun(n) determines if n is a fun number
bool is_fun(int n);
The interface (.h) file has everything the client needs.
Interface files are also known as header files.
CS 136 Winter 2022 06: Modularization & ADTs 30
Clients can read the documentation in the interface (.h) file to understand how to use the provided functions.
The client can also “copy & paste” the function declarations from the interface file to make the module functions available.
// main.c [CLIENT]
// *** copied from .h ***
bool is_fun(int n);
int main(void) {
b = is_fun(k); // ok
But there is a much more elegant solution.
CS 136 Winter 2022 06: Modularization & ADTs 31
A preprocessor directive temporarily “modifies” a source file just before it is run (but it does not save the modifications).
The directive #include “cut & pastes” or “inserts” the contents of another file directly into the current file.
#include “fun.h” // insert the contents of fun.h
For clients, this is perfect: it inserts the interface of the module containing all of the function declarations, making all of the provided functions available to the client.
Always put any #include directives at the top of the file.
CS 136 Winter 2022 06: Modularization & ADTs 32
example: fun module
// fun.h [INTERFACE]
// This module is all
// about having fun
// is_fun(n) determines if
// n is a fun number
bool is_fun(int n);
// fun.c [IMPLEMENTATION]
#include “fun.h”
// see fun.h for details
bool is_fun(int n) {
////////////////////////////////////////////////////////////// // main.c [CLIENT]
#include “fun.h”
int main(void) {
b = is_fun(k);
CS 136 Winter 2022
06: Modularization & ADTs 33
Implementation notes
In the previous example, the fun implementation file (fun.c) included its own interface (fun.h).
This is good style as it ensures there are no discrepancies between the interface (declarations) and the implementation (definitions).
The function is_fun is fully documented in the interface file for the
client, so in the implementation a simple comment referring the
reader to the interface file is sufficient.
// see fun.h for details
bool is_fun(int n) {
CS 136 Winter 2022 06: Modularization & ADTs 34
For simple (non-pointer) parameters, const is meaningless in a function declaration.
The caller (client) does not need to know if the function mutates the copy of the argument value.
int my_function(int x);
int my_function(const int x) {
// mutation of x here is invalid
// DECLARATION
// (no const)
// DEFINITION
// (with const)
It is good style to use constant parameters in definitions to improve communication.
CS 136 Winter 2022 06: Modularization & ADTs 35
In addition to #include, The CP:AMA textbook frequently uses the #define directive. In its simplest form it performs a search & replace.
// replace every occurrence of MY_NUMBER with 42
#define MY_NUMBER 42
int my_add(int n) {
return n + MY_NUMBER;
In C99, it is usually better style to define a variable (constant), but you will still see #define in the “real world”.
In this course, we will not use #define.
CS 136 Winter 2022 06: Modularization & ADTs 36
Since the beginning of this course, we have seen
#include “cs136.h”
in our programs. We now understand that we have been using support tools and functions (e.g., trace_int and read_int) provided by a cs136 module.
The cs136.h interface file contains:
#include
#include
#include
#include
So our cs136 module was requiring additional modules.
CS 136 Winter 2022 06: Modularization & ADTs 37
C standard modules
Unlike Racket, there are no “built-in” functions in C.
Fortunately, C provides several standard modules (also known as
libraries) with many useful functions.
For example, the stdio module provides printf and scanf.
When using #include we use angle brackets (<>) to specify that the module is one of the standard modules and quotes (“”) for “regular” modules (i.e., ones we have written).
#include
#include “mymodule.h”
CS 136 Winter 2022 06: Modularization & ADTs 38
Here are some of the other modules that we have been using:
•
•
•
•
CS 136 Winter 2022 06: Modularization & ADTs 39
example: test client
For each module you design, it is good practice to create a test client that ensures the provided functions are correct.
// test-fun.c: testing client for the fun module
#include
#include “fun.h”
int main(void) {
assert(is_fun(42));
assert(!is_fun(13));
Do NOT add a main function to your implementation (e.g.,fun.c). Create a new test client with a main function.
CS 136 Winter 2022 06: Modularization & ADTs 40
There may be “white box” tests that cannot be tested by a client. These may include implementation-specific tests and tests for module-scope functions.
In these circumstances, you can provide a test_module_name function that asserts your tests are successful.
CS 136 Winter 2022 06: Modularization & ADTs 41
Designing modules
The ability to break a big programming project into smaller modules, and to define the interfaces between modules, is an important skill that will be explored in later courses.
Unfortunately, due to the nature of the assignments in this course, there are very few opportunities for you to design any module interfaces.
For now, we will have a brief discussion on what constitutes a good interface design.
CS 136 Winter 2022 06: Modularization & ADTs 42
Cohesion and coupling
When designing module interfaces, we want to achieve
high cohesion and low coupling.
High cohesion means that all of the interface functions are related and working toward a “common goal”. A module with many unrelated interface functions is poorly designed.
Low coupling means that there is little interaction between modules. It is impossible to completely eliminate module interaction, but it should be minimized.
CS 136 Winter 2022 06: Modularization & ADTs 43
CS 136 Winter 2022 06: Modularization & ADTs 44
Interface vs. implementation
We emphasized the distinction between the module interface and
the module implementation.
Another important aspect of interface design is information hiding, where the interface is designed to hide any implementation details from the client.
CS 136 Winter 2022 06: Modularization & ADTs 45
Information hiding
The two key advantages of information hiding are security and flexibility.
Security is important because we may want to prevent the client from tampering with data used by the module. Even if the tampering is not malicious, we may want to ensure that the only way the client can interact with the module is through the interface. We may need to protect the client from themselves.
By hiding the implementation details from the client, we gain the flexibility to change the implementation in the future.
CS 136 Winter 2022 06: Modularization & ADTs 46
Information hiding in C
With C modules, it is easy to hide the implementation details from the client.
Instead of providing the client with the implementation source code (.c file) you can provide a machine code (e.g., a .ll file). This is what we did wit
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com