4: Structs and Unions

4.1: Structs

SML point
type point = real * real ;
SML rotate
(* rotate : point -> point *)
fun rotate (p_x,p_y) = (p_y,0.0-p_x) ;
SML rotate examples
rotate ( 1.0, 0.0) = ( 0.0,~1.0) ;
rotate (~0.1,~0.3) = (~0.3, 0.1) ;
rotate ( 0.7,~0.7) = (~0.7,~0.7) ;
C general form of a struct declaration
struct {
  t_0 m_0 ;
  t_1 m_1 ;
  ...
}
C point
typedef struct {
  double x ;
  double y ;
} point ;
C rotate
point rotate( point p ) {
  point r ;
  r.x = p.y ;
  r.y = -p.x ;
  return r ;
}
C print point
void print_point( point p ) {
  printf( "(%f,%f)\n", p.x, p.y ) ;
}
C three points
int main( void ) {
  point r ;
  r.x = 1 ; r.y = 0 ;
  print_point( rotate( r ) ) ;
  r.x = -0.1 ; r.y = -0.3 ;
  print_point( rotate( r ) ) ;
  r.x = 0.7 ; r.y = -0.7 ;
  print_point( rotate( r ) ) ;
  return 0 ;
}
C Alternative main for rotate
int main( void ) {
  const point r0 = {   1, 0 } ;
  const point r1 = {-0.1, -0.3 } ;
  const point r2 = { 0.7, -0.7 } ;
  print_point( rotate( r0 ) ) ;
  print_point( rotate( r1 ) ) ;
  print_point( rotate( r2 ) ) ;
  return 0 ;
}

4.2: Structs in structs

SML rectangle
type rectangle = point * point ;
SML area
(* area : rectangle -> real *)
fun area ((llx,lly),(urx,ury))
    = absolute ((urx-llx) * (ury-lly)) ;
C rectangle
typedef struct {
  double x ;        /* X-coordinate of point */
  double y ;        /* Y-coordinate of point */
} point ;

typedef struct {
  point ll ;        /* Lower Left hand corner */
  point ur ;        /* Upper Right hand corner */
} rectangle ;
C area
double area( rectangle r ) {
  return absolute( ( r.ur.x - r.ll.x ) *
                   ( r.ur.y - r.ll.y ) ) ;
}
C alternative rectangle
typedef struct {
  struct {
    double x ;        /* X-coordinate of point */
    double y ;        /* Y-coordinate of point */
  } ll, ur ;	      /* Lower left & Upper right */
} rectangle ;

4.3: Unions in structs: algebraic data types

SML distance
datatype distance = Angstrom  of real |
                    Mile      of real |
                    Kilometre of real |
                    Lightyear of real ;
SML convert distance into millimetres
(* mm : distance -> real *)
fun mm (Angstrom x)    = x * 1E~7
  | mm (Kilometre x)   = x * 1E6
  | mm (Mile x)        = x * 1.609344E6
  | mm (Lightyear x)   = x * 9.4607E21 ;
SML mm
mm (Mile 1.0) + mm (Kilometre 4.0) = 5609344.0 ;

4.3.1: Union types

C general form of a union declaration
union {
  t_0 m_0 ;
  t_1 m_1 ;
  ...
}
C pair
typedef struct {
  int x ;
  int y ;
} pair ;
C struct
typedef struct {
  int i ;
  double d ;
  pair p ;
} structtype ;

structtype structx ;
C union
typedef union {
  int i ;
  double d ;
  pair p ;
} uniontype ;

uniontype unionx ;
C how to abuse a union
int abuse_union( double x ) {
  uniontype y ;
  y.d = x ;
  return y.i ;
}
C datatype for distance
typedef enum { Angstrom,  Mile,
               Kilometre, Lightyear } distancetype ;

typedef struct {
  distancetype tag ;
  union {
    double angstroms ;
    double miles ;
    double kilometres ;
    double lightyears ;
  } contents ;
} distance ;

Answer to exercise 4.2

SML coordinate
datatype coordinate = Polar     of  real * real |
                      Cartesian of  real * real ;
C coordinate
typedef enum { Polar, Cartesian } coordinatetype ;

typedef struct {
  coordinatetype tag ;
  union {
    struct {
      double x ;
      double y ;
    } cartesian ;
    struct {
      double r ;
      double theta ;
    } polar ;
  } contents ;
} coordinate ;

4.3.2: Pattern matching: the switch statement

C general form of the switch statement
switch( e ) {
  case c_1 : S_1 ;
  case c_2 : S_2 ;
  ...
  default : S_d ;
}
C distance conversion program
double mm( distance x ) {
  switch( x.tag ) {
    case Angstrom:  return x.contents.angstroms * 1e-7 ;
    case Kilometre: return x.contents.kilometres * 1e6 ;
    case Mile:      return x.contents.miles * 1.609344e6 ;
    case Lightyear: return x.contents.lightyears*9.4607e21;
    default:        abort() ;
  }
}

int main( void ) {
  distance x, y ;
  x.tag = Mile ;      x.contents.miles      = 1.0 ;
  y.tag = Kilometre ; y.contents.kilometres = 4.0 ;
  printf( "%f\n", mm( x ) + mm( y ) ) ;
  return 0 ;
}
C double power function
double double_power( double r, int p ) {
  switch( p ) {
    case 4 : r = r * r ;
    case 3 : r = r * r ;
    case 2 : r = r * r ;
    case 1 : r = r * r ;
  }
  return r ;
}
C legs
typedef enum { Ant, Ecoli, Lizard,
               Cat, Stork, Fuchsia } species ;

int legs( species s ) {
  switch( s ) {
    case Ant:    return 6;
    case Cat:
    case Lizard: return 4;
    case Stork:  return 2;
    default:     return 0;
  }
}

4.3.3: Algebraic types in other imperative languages

C point structure
typedef struct {
  double x ;
  double y ;
} point ;
Pascal point structure
type point = record
  x: real;
  y: real;
end;
C coordinatetype
typedef enum
 { Polar, Cartesian }
   coordinatetype;
Pascal coordinatetype
type coordinatetype =
  ( Polar, Cartesian ) ;

C coordinate definition
typedef struct {
  coordinatetype tag ;
  union {
    struct {
      double x ;
      double y ;
    } cartesian ;
    struct {
      double r ;
      double theta ;
    } polar ;
  } contents ;
} coordinate ;
Pascal coordinate definition
type coordinate = record
  case tag : coordinatetype
  of
    Cartesian:
    (   x : real;
        y : real;
    );
    Polar:
    (   r : real;
        theta : real;
    );

end ;
C ++ coordinate definition
typedef struct {
  coordinatetype tag ;
  union {
    struct {
      double x ;
      double y ;
    } cartesian ;
    struct {
      double r ;
      double theta ;
    } polar ;
  } ;
} coordinate ;

4.4: Pointers: references to values

4.4.1: Defining pointers

C declaration of the example above
void pointer_example( void ) {
  int i = 123 ;
  int *p = &i ;
  printf("i: %d, *p: %d\n", i, *p ) ;
}
C output example
i: 123, *p: 123
C pointer to integer
typedef int * pointer_to_integer ;
C the example with two more pointers
void extended_pointer_example( void ) {
  int   i = 123 ;
  int  *p = &i ;
  int  *q = &i ;
  int **r = &p ;
  printf("i: %d, *p: %d, *q: %d, **r: %d\n", i, *p, *q, **r ) ;
}
C output example 2
i: 123, *p: 123, *q: 123, **r: 123

Answer to exercise 4.4

C a pointer to a pointer to an integer
typedef double ** pointer_to_pointer_to_double ;

Exercise 4.5

C what are the differences and similarities of these types
typedef struct {
  double *x ; int y ;
} type0 ;
typedef type0 *type1 ;

4.4.2: Assignments through pointers

C assigning through pointers
void pointer_assignment( void ) {
  int   i = 123 ;
  int   j = 1972 ;
  int  *p = &i ;
  int **r = &p ;
  *p = 42 ;		/* First assignment */
  *r = &j ;		/* Second assignment */
  *p = i + 1 ;		/* Third assignment */
  printf("i: %d, j: %d, *p: %d, **r: %d\n", i, j, *p, **r );
}
C assigning through pointers output
i: 42, j: 43, *p: 43, **r: 43

4.4.3: Passing arguments by reference

SML employee
type employee = int * real * int * int ;
SML payrise
(* payrise : employee -> real -> employee *)
fun payrise (nr, salary, birth, employed) inc
    = (nr, salary * (1.0+inc/100.0), birth, employed) ;
C Person data structure
typedef struct {
  int employee_number ;
  double salary ;
  int year_of_birth ;
  int year_of_employment ;
} employee ;
C applicative implementation of payrise
employee payrise_ap( employee e, double inc ) {
  e.salary = e.salary * (1 + inc/100) ;
  return e ;
}
C applicative give people a 3.5% payrise
int main( void ) {
  employee e0 = { 13, 20000.0, 1972, 1993 } ;
  employee e1 ;
  e1 = payrise_ap( e0, 3.5 ) ;
  return 0 ;
}
C applicative payrise
employee payrise_ap( employee e, double inc ) {
  e.salary = e.salary*(1+inc/100);
  return e ;
}
C alternative give people a 3.5% payrise
int main( void ) {
  employee e0 = { 13, 20000.0, 1972, 1993 } ;
  employee e1 ;
  e1 = payrise_ap( e0, 3.5 ) ;
  return 0 ;
}
C Imperative implementation of payrise
void payrise_im( employee *e, double inc ) {
  (*e).salary= (*e).salary * (1+inc/100) ;
}
C Idiomatic imperative implementation of payrise
void payrise_im( employee *e, double inc ) {
  e->salary *= 1 + inc/100 ;
}
C give people a 3.5% payrise
int main( void ) {
  employee e0 = { 13, 20000.0, 1972, 1993 } ;
  payrise_im( &e0, 3.5 ) ;
  return 0 ;
}
C imperative payrise
void payrise_im( employee *e, double inc ) {
  e->salary *= 1 + inc/100 ;
}
C give people a 3.5% payrise-2
int main( void ) {
  employee e0 = { 13, 20000.0, 1972, 1993 } ;
  payrise_im( &e0, 3.5 ) ;
  return 0 ;
}

Answer to exercise 4.7

C imperative rotate program
#include <stdio.h>

typedef struct {
  double x ;
  double y ;
} point ;

void print_point( point *p ) {
  printf( "(%f,%f)\n", p->x, p->y ) ;
}

void rotate( point *p ) {
  double ty = p->y ;
  p->y = -p->x ;
  p->x = ty ;
}

int main( void ) {
  point r0 = {   1, 0 } ;
  point r1 = {  -0.1, -0.3 } ;
  point r2 = { 0.7, -0.7 } ;
  rotate( &r0 ) ;
  print_point( &r0 ) ;
  rotate( &r1 ) ;
  print_point( &r1 ) ;
  rotate( &r2 ) ;
  print_point( &r2 ) ;
  return 0 ;
}
C multiple assignment
(p->y,p->x) = (-p->x,p->y) ;

4.4.4: Lifetime of pointers and storage

C Incorrect use of a pointer
int *wrong( void ) {
  int x = 2 ;
  return &x ;
}

int main( void ) {
  int *y = wrong() ;
  printf("%d\n", *y ) ;
  return 0 ;
}

4.5: Void pointers: partial application

SML parabola
(* parabola : real -> real -> real *)
fun parabola c x = x * x - c : real ;
SML bisection of parabola
bisection (parabola 2.0) 1.0 2.0 = 1.4140625 ;
bisection (parabola 4.0) 1.0 4.0 = 1.999755859375 ;
SML quadratic
(* quadratic : real -> real -> real -> real *)
fun quadratic b c x = x * x - b * x - c : real ;
SML bisection of quadratic
bisection (quadratic  2.0 3.0) 1.0   4.0 = 3.000244140625 ;
bisection (quadratic ~2.5 8.1) 0.0 100.0 = 1.8585205078125;
SML bisection with extra argument
(* extra_bisection : ('a->real->real) ->
                     'a -> real -> real -> real *)
fun extra_bisection f x l h
    = let
         val m = (l + h) / 2.0
         val f_m = f x m          (* arg. x added *)
      in
         if absolute f_m < eps
            then m
            else if absolute(h-l) < delta
                    then m
                    else if f_m < 0.0
(* arg. x added *)       then extra_bisection f x m h
(* arg. x added *)       else extra_bisection f x l m
        end ;
SML extra bisection call
extra_bisection parabola 2.0 1.0 2.0
SML quadratic with tuple
(* quadratic : real*real -> real -> real *)
fun quadratic (b,c) x = x * x - b * x - c : real ;
C bisection with extra argument
double extra_bisection( double (*f)( void *, double ),
                        void * x, double l, double h  ) {
  double m ;
  double f_m ;
  while( true ) {
    m = (l + h) / 2.0 ;
    f_m = f( x, m ) ;  /* argument x added */
    if( absolute( f_m ) < eps ) {
      return m ;
    } else if( absolute( h-l ) < delta ) {
      return m ;
    } else if( f_m < 0 ) {
      l = m ;
    } else {
      h = m;
    }
  }
}
C just parabola
double parabola( double *c, double x ) {
  return x * x - (*c) ;
}
C just quadratic
typedef struct {
  double b ;
  double c ;
} double_double ;

double quadratic( double_double *bc, double x ) {
  return x * x - bc->b * x - bc->c ;
}
C Calling bisection with extra argument
int main( void ) {
  double        c ;
  double_double dd ;
  c = 2.0 ;
  printf("%f\n", extra_bisection( parabola, /* Type error */
                                  &c, 1.0, 2.0 ) ) ;
  c = 4.0 ;
  printf("%f\n", extra_bisection( parabola, /* Type error */
                                  &c, 1.0, 4.0 ) ) ;
  dd.b = 2.0 ;
  dd.c = 3.0 ;
  printf("%f\n", extra_bisection( quadratic,/* Type error */
                                  &dd, 1.0, 4.0 ) ) ;
  dd.b = -2.5 ;
  dd.c = 8.1 ;
  printf("%f\n", extra_bisection( quadratic,/* Type error */
                                  &dd, 0.0, 100.0 ) ) ;
  return 0 ;
}
C required type
double (*)( void *, double )
C parabola type
double (*)( double *, double )
C quadratic type
double (*)( double_double *, double )
C type correct parabola and quadratic
double parabola( void *p, double x ) {
  double *c = p ;
  return x * x - (*c) ;
}

typedef struct {
  double b ;
  double c ;
} double_double ;

double quadratic( void *p, double x ) {
  double_double *bc = p ;
  return x * x - bc->b * x - bc->c ;
}

4.5.1: The danger of explicit type casts

C explicit type cast
(t) x
C type-cast
double *c = (double *) p ;
C Alternative calls to bisection with extra argument
extra_bisection( (double (*)(void *,double)) parabola,
                 &c, 4.0, 7.0) ;
/* initialise dd */
extra_bisection( (double (*)(void *,double)) quadratic,
                 &dd, 4.0, 7.0 ) ;
C Another alternative call to bisection with extra argument
extra_bisection( (double (*)(void *,double)) 42,
                 &dd, 1.0, 3.0 ) ;

4.5.2: Void pointers and parametric polymorphism

C header of bisection with extra argument
double extra_bisection( double (*f)( double, void *),
                        void * x, double l, double h  )
SML type of bisection with extra argument
(* extra_bisection : ('a->real->real) ->
                     'a -> real -> real -> real *)
C incorrect call to bisection with extra argument
char t ;
extra_bisection( quadratic, &t, 0, 1 ) ;

Summary

C general form of a C struct definition
typedef struct
  /* optional name */ {
  t_1 m_1 ; ... t_n m_n ;
} t ;
C general form of a C union definition
typedef union
  /* optional name */ {
  t_1 m_1 ; ... t_n m_n ;
} t ;
C general form of a C switch statement
switch( e ) {
  case c_1 : S_1
  case c_2 : S_2
  ...
  default : T
}
C general form of a C case label with statements
case c_i: S_i ; break ;

Further exercises

Exercise 4.10

C pointer main
int main( void ) {
  int i = 3 ;
  int * p = & i ;
  int * * q = & p ;
  printf( "%d %d %d %d %d %d %d\n",
          3, i, p==*q, *p, q==& p, *q==&i, **q ) ;
  return 0 ;
}
C twice 1
int twice( int (*f) (int), int a ) {
  return f( f( a ) ) ;
}

int add( int a ) {
  return a + 1 ;
}

int main( void ) {
  printf("%d\n", twice( add, 2 ) ) ;
  return 0 ;
}
C twice 2
int twice( int (*f) (int, int, int),
           int x, int y, int a ) {
  return f( x, y, f( x, y, a ) ) ;
}

int add( int a, int b, int c ) {
  return a + b + c ;
}

int main( void ) {
  printf("%d\n", twice( add, 2, 3, 4 ) ) ;
  return 0 ;
}
C twice 3
typedef struct {
  int l, r ;
} pair ;

int twice( int (*f) ( void *, int ),
           void * x, int a ) {
 return f( x, f( x, a ) ) ;
}

int add( void * p, int c ) {
  pair * q = p ;
  return q->l + q->r + c ;
}

int main( void ) {
  pair p = {2, 3} ;
  printf("%d\n", twice( add, &p, 4 ) ) ;
  return 0 ;
}