8: Modules

8.1: Modules in C: files and the C preprocessor

8.1.1: Simple modules, #include

SML complex module
structure Complex = struct
  type complex = real * real ;

  (* complex_sub : complex -> complex -> complex *)
  fun complex_sub (r,s) (t,u)
      = (r-t,s-u) : complex ;

  (* complex_multiply : complex -> complex -> complex *)
  fun complex_multiply (r,s) (t,u)
      = (r*u+s*t,s*u-r*t) : complex ;

  (* complex_distance : complex -> real *)
  fun complex_distance (r,s)
      = sqrt (r*r+s*s) ;
end ;
C complex module
#include <math.h>

typedef struct {
  double im , re ;
} complex ;

complex complex_sub( complex c, complex d ) {
  complex r ;
  r.im = c.im - d.im ;
  r.re = c.re - d.re ;
  return r ;
}

complex complex_multiply( complex c, complex d ) {
  complex r ;
  r.im = c.im * d.re + d.im * c.re ;
  r.re = c.re * d.re - d.im * c.im ;
  return r ;
}

double complex_distance( complex c ) {
  return sqrt( c.im * c.im + c.re * c.re ) ;
}
SML complex module interface
signature COMPLEX = sig
  type complex ;
  val complex_sub      : complex -> complex -> complex ;
  val complex_multiply : complex -> complex -> complex ;
  val complex_distance : complex -> real ;
end ;
SML complex module implementation
structure Complex : COMPLEX = struct
  type complex = real * real ;

  fun complex_sub (r,s) (t,u)
      = (r-t,s-u) : complex ;

  fun complex_multiply (r,s) (t,u)
      = (r*u+s*t,s*u-r*t) : complex ;

  fun complex_distance (r,s)
      = sqrt (r*r+s*s) ;
end ;
C complex module interface
typedef struct {
  double im , re ;
} complex ;

extern complex complex_sub( complex c, complex d ) ;
extern complex complex_multiply( complex c, complex d ) ;
extern double  complex_distance( complex c ) ;
C complex module implementation
#include <math.h>
#include "complex.h"

complex complex_sub( complex c, complex d ) {
  complex r ;
  r.im = c.im - d.im ;
  r.re = c.re - d.re ;
  return r ;
}

complex complex_multiply( complex c, complex d ) {
  complex r ;
  r.im = c.im * d.re + d.im * c.re ;
  r.re = c.re * d.re - d.im * c.im ;
  return r ;
}

double complex_distance( complex c ) {
  return sqrt( c.im * c.im + c.re * c.re ) ;
}
C include complex
#include "complex.h"
C import IO interface
#include <stdio.h>
C complex main program
#include <stdio.h>
#include "complex.h"

complex complex_square( complex x ) {
  return complex_multiply( x, x ) ;
}

void complex_print( complex x ) {
  printf( "(%f+%fi)", x.re, x.im ) ;
}

int main( void ) {
  complex x = { 2.0, 1.0 } ;
  complex y = complex_square( x ) ;
  complex z = complex_sub( x, y ) ;
  complex_print( y ) ; printf( "\n" ) ;
  complex_print( z ) ; printf( "\n" ) ;
  return 0 ;
}

8.1.2: Type checking across modules

8.1.3: Double imports

C graphics module interface
#include "vector.h"
#include "matrix.h"
/*  graphics function prototypes */
C matrix module interface
#include "vector.h"

typedef struct {
  vector *columns ;
  int coordinates ;
} matrix ;
extern matrix matrix_multiply( matrix x, matrix y ) ;
extern vector matrix_vector( matrix x, vector y ) ;
C vector module interface
typedef struct {
  double *elements ;
  int coordinates ;
} vector ;
extern double vector_multiply( vector x, vector y ) ;
extern vector vector_add( vector x, vector y ) ;
C graphics module preprocessed file
typedef struct {           /* Lines imported by graphics.h */
  double *elements ;
  int coordinates ;
} vector ;
extern double vector_multiply( vector x, vector y ) ;
extern vector vector_add( vector x, vector y ) ;

typedef struct {           /* Lines imported via matrix.h */
  double *elements ;
  int coordinates ;
} vector ;
extern double vector_multiply( vector x, vector y ) ;
extern vector vector_add( vector x, vector y ) ;

typedef struct {           /* Lines imported by graphics.h */
  vector *columns ;
  int coordinates ;
} matrix ;
extern matrix matrix_multiply( matrix x, matrix y ) ;
extern vector matrix_vector( matrix x, vector y ) ;

/*  graphics function prototypes */
C vector module interface with ifndef
#ifndef VECTOR_H
#define VECTOR_H

typedef struct {
  double *elements ;
  int coordinates ;
} vector ;

extern double vector_multiply( vector x, vector y ) ;
extern vector vector_add( vector x, vector y ) ;

#endif /* VECTOR_H */

8.1.4: Modules without an implementation

C boolean interface
#ifndef BOOL_H
#define BOOL_H

typedef enum { false = 0 , true = 1 } bool ;

#endif /* BOOL_H */

8.1.5: The macro semantics of #define directives

C define a constant
#define monkeys    42 gorillas and 12 gibbons
C abuse of #define
#define BECOMES   =
#define INCREMENT ++
C defining x, y, z
#define x    4
#define y    x+x
#define z    y*y
int q = z ;
C defining x, y, z properly
#define x    (4)
#define y    (x+x)
#define z    (y*y)
int q = z ;
C define a macro that computes the minimum
#define min(x,y)   ( (x)<(y) ? (x) : (y) )
C min replacement text
( (x)<(y) ? (x) : (y) )
C minimum of 'p' and 'q'
(('p')<('q')?('p'):('q'))
C minimum of 'a' and getchar()
min( 'p', getchar() )
C semantics of textual substitution
( ('p')<( getchar() ) ? ('p') : ( getchar() ) )
C minimum function
int minf( int x, int y ) {
  return x < y ? x : y ;
}

8.2: Compiling modules

8.2.1: Separate compilation under UNIX

SH compile vector.c
cc -c vector.c
SH link modules
cc vector.o matrix.o graphics.o -o graphics
SH compile and link modules
cc -c vector.c
cc -c matrix.c
cc -c graphics.c
cc vector.o matrix.o graphics.o -o graphics
MAKE vector rule only
vector.o:
        cc -c vector.c
MAKE vector, including dependencies
vector.o:
        cc -c vector.c
vector.o: vector.c
vector.o: vector.h
MAKE vector dependencies
vector.o: vector.c vector.h
MAKE vector short rule
vector.o: vector.c vector.h
        cc -c vector.c
MAKE matrix rules
matrix.o: matrix.c matrix.h vector.h
        cc -c matrix.c
MAKE vector and matrix
vector.o: vector.c vector.h
        cc -c vector.c

matrix.o: matrix.c matrix.h vector.h
        cc -c matrix.c

Answer to exercise 8.1

MAKE graphics rules
graphics.o: graphics.c graphics.h matrix.h vector.h
        cc -c graphics.c

Answer to exercise 8.2

MAKE graphics, vector and matrix rules
vector.o: vector.c vector.h
        cc -c vector.c
matrix.o: matrix.c matrix.h vector.h
        cc -c matrix.c
graphics.o: graphics.c graphics.h matrix.h vector.h
        cc -c graphics.c
MAKE linking graphics
graphics:
        cc -o graphics vector.o matrix.o graphics.o
MAKE graphics dependencies
graphics: vector.o matrix.o graphics.o
MAKE complete make file for graphics
graphics: vector.o matrix.o graphics.o
        cc -o graphics vector.o matrix.o graphics.o
vector.o: vector.c vector.h
        cc -c vector.c
matrix.o: matrix.c matrix.h vector.h
        cc -c matrix.c
graphics.o: graphics.c graphics.h matrix.h vector.h
        cc -c graphics.c
MAKE complete make file for graphics using defaults
graphics: vector.o matrix.o graphics.o
        cc -o graphics vector.o matrix.o graphics.o

vector.o: vector.c vector.h
matrix.o: matrix.c matrix.h vector.h
graphics.o: graphics.c graphics.h matrix.h vector.h
MAKE duplicated list
graphics: vector.o matrix.o graphics.o
        cc -o graphics vector.o matrix.o graphics.o
MAKE make abbreviation facility
N=T
MAKE using the make abbreviation facility
OBJECTS=vector.o matrix.o graphics.o
graphics: $(OBJECTS)
        cc -o graphics $(OBJECTS)
MAKE objects
vector.o matrix.o graphics.o
MAKE define CFLAGS
CFLAGS=-O
MAKE define CC
CC=gcc
MAKE dependency accidentally omitted
matrix.o: vector.h
MAKE before calling makedepend
OBJECTS=vector.o matrix.o graphics.o
graphics: $(OBJECTS)
        cc -o graphics $(OBJECTS)
SH make depend
makedepend graphics.c vector.c matrix.c
MAKE after calling makedepend
OBJECTS=vector.o matrix.o graphics.o
graphics: $(OBJECTS)
        cc -o graphics $(OBJECTS)

# DO NOT DELETE THIS LINE -- make depend depends on it.

graphics.o: graphics.c graphics.h vector.h matrix.h
vector.o: vector.c vector.h
matrix.o: matrix.c matrix.h vector.h
MAKE adding a depend target
depend:
        makedepend graphics.c vector.c matrix.c
MAKE graphics complete
CFLAGS=-O
OBJECTS=vector.o matrix.o graphics.o

graphics: $(OBJECTS)
        cc -o graphics $(OBJECTS)

depend:
        makedepend graphics.c vector.c matrix.c

# DO NOT DELETE THIS LINE -- make depend depends on it.

graphics.o: graphics.c graphics.h vector.h matrix.h
vector.o: vector.c vector.h
matrix.o: matrix.c matrix.h vector.h

8.2.2: Separate compilation on other systems

8.3: Global variables

8.3.1: Random number generation, how to use a global variable

SML random module interface
signature RANDOM = sig
  type random ;
  val random_init : random ;
  val random_number : random -> int -> random ;
end ;
SML random module implementation
structure Random : RANDOM = struct
  type random = (int * int) ;

  val period = 31 ;
  val root = 11 ;

  val random_init
      = (1,1) ;

  fun random_number (num,seed) range
      = (seed mod range, root * seed mod period) ;
end ;
C functional random module interface
typedef struct {
  int number ;
  int seed ;
} random ;

extern random random_init( void ) ;
extern random random_number( random state, int range ) ;
C functional random module implementation
#include "random.h"

#define period 31
#define root 11

random random_init( void ) {
  random x = {1,1} ;
  return x ;
}

random random_number( random state, int range ) {
  random result ;
  result.number = state.seed % range ;
  result.seed = root * state.seed % period ;
  return result ;
}
C imperative random module interface
extern void random_init( void ) ;
extern int random_number( int range ) ;
C imperative random module implementation
#include "random.h"

static int state ;

#define period 31
#define root 11

void random_init( void ) {
  state = 1 ;
}

int random_number( int range ) {
  int result = state % range ;
  state = root * state % period ;
  return result ;
}
C declaration of global variable
static int state ;

8.3.2: Moving state out of modules

C explicit state random module interface
typedef struct {
  int seed ;
} random ;

extern random *random_init( void ) ;
extern int     random_number( random *state, int range ) ;
C explicit state random module implementation
#include "random.h"

#define period 31
#define root 11

random *random_init( void ) {
  random *state = malloc( sizeof( random ) ) ;
  if( state == NULL ) {
    printf( "random_init: no space\n" ) ;
    abort( ) ;
  }
  state->seed = 1 ;
  return state ;
}

int random_number( random *state, int range ) {
  int result = state->seed % range ;
  state->seed = root * state->seed % period ;
  return result ;
}

8.3.3: Scoping and life time of global and local variables

C counter
int counter( void ) {
  static int count = 10 ;
  return count++ ;
}
C declaration of an external variable
int very_global_count = 10 ;
C declaration of an external variable in the interface
extern int very_global_count ;
C module 1 with counter
int counter ;
C module 2 with counter
int counter ;

8.4: Abstract Data Types

C random complete type definition
typedef struct {
  int seed ;
} random ;
C random incomplete type definition
typedef struct random_struct random ;
C hidden state random module interface
typedef struct random_struct random ;

extern random *random_init( void ) ;
extern int     random_number( random *state, int range ) ;
C hidden state random module implementation
#include "random.h"

#define period 31
#define root 11

struct random_struct {
  int seed ;
} ;

random *random_init( void ) {
  random *state = malloc( sizeof( random ) ) ;
  if( state == NULL ) {
    printf( "random_init: no space\n" ) ;
    abort( ) ;
  }
  state->seed = 1 ;
  return state ;
}

int random_number( random *state, int range ) {
  int result = state->seed % range ;
  state->seed = root * state->seed % period ;
  return result ;
}
C changed structure definition
struct random_struct {
  int state1 ;
  int state2 ;
} ;

Exercise 8.5

C buffered stream interface
typedef struct buffer Buffer ;

extern Buffer* b_create( FILE *input, int size );
extern bool b_advance( Buffer *b, int n ) ;
extern void b_read(    Buffer *b, char *s, int n ) ;
extern int  b_compare( Buffer *b, char *s, int n ) ;
extern void b_close(   Buffer *b ) ;
C alternative buffered stream interface
typedef struct buffer *AltBuffer ;

AltBuffer b_create( FILE *input, int size );
bool      b_advance( AltBuffer b, int n ) ;
...

Exercise 8.6

C String List functions
typedef struct string_list *Slist ;

extern Slist slist_cons( char *s, Slist tail ) ;
extern char* slist_head( Slist x ) ;
extern Slist slist_tail( Slist x ) ;
extern Slist slist_append( Slist x, Slist y ) ;
extern void  slist_destroy( Slist x ) ;

8.5: Polymorphic typing

SML monomorphic list
datatype char_list
  = Nil
  | Cons of (char*char_list);
SML polymorphic list
datatype 'a list
  = Nil
  | Cons of ('a*'a list);
C polymorphic list
typedef struct list_struct {
  void                 *list_head ;
  struct list_struct   *list_tail ;
} *list ;
C polymorphic cons, first attempt
list cons( void *head, list tail ) {
  list l = malloc( sizeof( struct list_struct ) ) ;
  l->list_head = head ;
  l->list_tail = tail ;
  return l ;
}
C illegal polymorphic list 1
  cons( &'H', cons( &'i', NULL ) ) /* ILLEGAL C */
C incorrect polymorphic list hi
list list_hi( void ) {
  char H = 'H' ;
  char i = 'i' ;
  list hi = cons( &H, cons( &i, NULL ) ) ; /* INCORRECT */
  return hi ;
}
C polymorphic cons, incomplete
list cons( void *head, list tail ) {
  list l  = malloc( sizeof( struct list_struct ) ) ;
  void *copy_of_head = malloc( /*  size of the data */ ) ;
  /*  copy the data from *head to *copy_of_head */
  l->list_head = copy_of_head ;
  l->list_tail = tail ;
  return l ;
}
C copy the data from *head to *copy_of_head
memcpy( copy_of_head, head, /*  size of the data */ ) ;
C polymorphic cons, complete
list cons( void *head, list tail, int size ) {
  list l  = malloc( sizeof( struct list_struct ) ) ;
  void *copy_of_head = malloc( size ) ;
  memcpy( copy_of_head, head, size ) ;
  l->list_head = copy_of_head ;
  l->list_tail = tail ;
  return l ;
}
C polymorphic list of list
#define char_cons(c,cs) cons( c, cs, sizeof( char ) )
#define list_cons(c,cs) cons( c, cs, sizeof( list ) )

list list_of_list( void ) {
  char H     = 'H' ;
  char i     = 'i' ;
  char o     = 'o' ;
  list hi    = char_cons( &H, char_cons( &i, NULL ) ) ;
  list ho    = char_cons( &H, char_cons( &o, NULL ) ) ;
  list hi_ho = list_cons( &hi,list_cons( &ho,NULL ) ) ;
  return hi_ho ;
}
C polymorphic head
void * head( list l ) {
  if( l == NULL ) {
    abort() ;
  }
  return l->list_head ;
}
C polymorphic tail
list tail( list l ) {
  if( l == NULL ) {
    abort() ;
  }
  return l->list_tail ;
}

Answer to exercise 8.8

C polymorphic length with while statement
int length( list x_xs ) {
  int accu = 0 ;
  while( x_xs != NULL ) {
    accu++ ;
    x_xs = tail( x_xs ) ;
  }
  return accu ;
}
C polymorphic nth
void * nth( list x_xs, int n ) {
  while( n != 0 ) {
    x_xs = tail( x_xs ) ;
    n-- ;
  }
  return head( x_xs ) ;
}
C extra filter
list extra_filter( bool (*pred)( void *, void * ),
		   void * arg, list x_xs, int size ) {
  if ( x_xs == NULL ) {
    return NULL ;
  } else {
    void * x = head( x_xs ) ;
    list xs = tail( x_xs ) ;
    if( pred( arg, x ) ) {
      return cons(x, extra_filter(pred,arg,xs,size), size);
    } else {
      return extra_filter( pred, arg, xs, size ) ;
    }
  }
}

Answer to exercise 8.9

C polymorphic append with open list and advanced pointer
list append( list xs, list ys, int size ) {
  list accu = ys ;
  list *lastptr = &accu ;
  while( xs != NULL ) {
    list new = cons( head( xs ), ys, size ) ;
    *lastptr = new ;
    lastptr = & new->list_tail ;
    xs = tail( xs ) ;
  }
  return accu ;
}
C polymorphic list interface
#ifndef LIST_H
#define LIST_H

typedef struct list_struct *list ;

extern list  cons( void *head, list tail, int size ) ;

extern int   length( list x_xs ) ;

extern void *head( list l ) ;
extern void *nth( list x_xs, int n ) ;
extern list  tail( list l ) ;
extern list  append( list xs, list ys, int size ) ;
extern list  extra_filter( bool (*pred)( void *, void * ),
		           void * arg, list x_xs,
                           int size ) ;
#endif /* LIST_H */

Summary

C Header type
typedef struct s t ;
C Implementation type
struct s {
  ...
} ;

Further exercises

Answer to exercise 8.10

C memo factorial
#define MAX 12

int fac( int n ) {
  static int memo[MAX] = {1,0} ;
  if( n < 1 || n > MAX ) {
    abort( ) ;
  } else {
    int r = memo[n-1] ;
    if( r == 0 ) {
      r = n * fac( n-1 ) ;
      memo[n-1] = r ;
    }
    return r ;
  }
}

Answer to exercise 8.11

C polymorphic array ADT
typedef struct Array *Array ;

extern Array arraynew( int l, int u, int size ) ;
extern void  arrayextend( Array a, int l, int u ) ;
extern void  arraystore( Array a, int index, void *value ) ;
extern void* arrayload( Array a, int index ) ;
C polymorphic array ADT implementation fragment
struct Array {
  int l, u ;	/* Store current bounds of array */
  int size ;	/* Store size of elements in array */
  void **data ;	/* Store pointers to elements */
} ;