Advanced Programming I Lecture Notes

3 May 2007 • Objects in C

Outline

Objectives

• Improve on the text's ADTs.

  • ADT design choices.

  • ADT implementation techniques.

  • Example C implementation techniques.

• Implementing something approaching objects in C.

  • Sketch out object implementation tecniques.

  • Understand objects better.

A Stack Interface

#ifndef STACK_H
#define STACK_H

# include <stdlib.h>  /* for NULL */
# include "list.h"

  typedef List Stack;

# define stack_init list_init
# define stack_destroy list_destroy

  int stack_push(Stack *, const void * data);
  int stack_pop(Stack *, void ** data);

# define stack_peek(_s) \
    ((_s)→head == NULL ? NULL : (_s)→head->data)
# define stack_size list_size

#endif

typedefs

• A typedef declares a synonym for a type.

  • typedefs do not declare a new type.

    Stack s;
    List * lp = &s;  /* o.k. */
    

• Read a typedef like a variable declaration, except for type synonyms.

  int * ip;         /* variable ip */
  typedef int * ip; /* type synonym ip */
  

#define Macros

• A #define macro defines a textual replacement.

  • #define source_text result_text

• Every following occurrence of source_text is replaced by result_text.

  #define stack_size list_size
  
  if (stack_size(stk)) ...
  
  if (list_size(stk)) ...
  

#define Macro Parameters

• Macro parameters are substituted in during the replacement.

  • Parameter replacement is also textual.

  
  # define stack_peek(_s) \
      ((_s)→head == NULL ? NULL : (_s)→head->data);
  
  int top = 
    stack_peek(intstk);
  
  int top = 
    ((intstk)→head == NULL ? NULL : (intstk)→head→data);
  

Void Pointers

• The type void * is a void pointer.

• Any pointer type can be converted to a void pointer and vice versa.

  int i = 3;
  int * ip = &i;
  void * vp = &i;        /* o.k. */
  int * jp = (int *) vp; /* o.k. */
  

• Void pointers can't be dereferenced.

  • The are opaque pointers.

What's Wrong?

# include "list.h"

  typedef List Stack;

# define stack_init list_init
# define stack_destroy list_destroy

  int stack_push(Stack *, const void * data);
  int stack_pop(Stack *, void ** data);

# define stack_peek(_s) \
    ((_s)→head == NULL ? NULL : (_s)→head→data)
# define stack_size list_size

• Client-visible implementation details.

  • There shouldn't be any.

Implementation Details

• Implementation details should be hidden from the client.

  • Simpler client interfaces.

  • Preserve implementation flexibility.

  • Decouple clients and provider ADTs.

  • Maintain ADT integrity.

• Minimal interfaces aren't always correct.

  • Non-minimal interfaces rarely stay correct.

A New Stack Interface

#ifndef STACK_H
#define STACK_H

  typedef void * Stack;

  Stack stack_make();
  void stack_unmake(Stack);

  int stack_push(Stack, const void * data);
  int stack_pop(Stack, void ** data);

  int stack_peek(Stack, void ** data);
  unsigned stack_size(Stack);

#endif

Opaque ADT Types

• Multi-instance ADTs require instance naming.

• The ADT type can be the instance names.

  typedef void * Stack;
  

• A type in this sense is an instance tag.

  • The declaration

    typedef int Stack;
    

    would work as well, but may require extra mapping.

Singleton ADTs

• Single-instance ADTs (singleton ADTs) don't need a type.

  • The ADT itself is the instance.

• Singleton ADTs are usually of limited use, but do have advantages over multi-instance ADTs:

  • Singleton ADTs are simpler to design and implement.

  • Singleton ADTs are simpler to use.

Singleton ADT Interface

#ifndef STACK_H
#define STACK_H

  void stack_init();
  void stack_term();

  int stack_push(const void * data);
  int stack_pop(void ** data);

  int stack_peek(void ** data);
  unsigned stack_size();

#endif

Client-Side Details

• The client-side (let us assume) is done.

  • The client can go off and write code.

  • The ADT implementor can go off and write code too.

• If not, the client and ADT implementor can negotiate over the interface.

  • A small, well-defined, circumscribed subject.

  • Can be difficult and partially non-technical.

ADT Implementation

• The ADT provider is free to choose any implementation.

  • As long as it satisfies the interface.

• The ADT can have several implementations.

  stack-array.c
stack-vector.c
stack-linkedlist.c

  • The client links with the appropriate implementation.

Implementation Details

• The ADT implementation should provide three things:

  1. The instance data structures.

  2. The operation implementations.

  3. A mapping between client and private instance representations.

• Other things may be required.

  • Correctness demonstrations, for example.

Instance Data Structures

• The implementor's choice.

• The data for an instance is usually stored in a structure.

  struct stack_data
    const unsigned max = 10
    unsigned top
    void * data[max]
  
  struct stack_data
    unsigned max, top
    void ** data
  
  struct stack_data
    linked_list data

Static vs Dynamic Instances

• ADT instances can be off the heap, in an array, or in a vector.

  • With all the usual trade-offs.

• Don't underestimate a static implementation.

  const unsigned max = 10
  stack_data instances[max]
  bool in_use[max]

  • Obvious disadvantages but subtle advantages.

    • Particularly when things go wrong.

ADT Operations

• Nothing unusual here.

• Defensive programming is important.

  • “Defensive programming” — where the finger points once something has crashed and burned.

  • Design by contract, or similar.

  • A simple, well-defined interface is crucial.

Implementation Details

• The ADT implementation should provide three things:

  1. The instance data structures.

  2. The operation implementations.

  3. A mapping between client and private instance representations.

Client-Instance Mapping

• The client has a tag for the instance;
  The implementation needs the instance data.

  Stack s = stack_new();
  stack_push(s, data);
  

• Let the tag be a pointer to the instance data.

  • A cast does the mapping.

    int stack_push(Stack s, void * data) 
      stack_data * sd = (stack_data *) s
      if (sd→top ≥ sd→max)
        return stack_overflow
    

Mapping Validation

• If possible, validate the tag before mapping.

  stack_data * map_tag(Stack tag)
  
    unsigned i = (unsigned) sd
  
    if (i ≥ max) or not in_use[i]
      error(bad tag)
  
    return instances + i
  
  int stack_push(Stack s, void * data)
    stack_data * sd = map_tag(s)
  

Objectives

• Improve on the text's ADTs.

  • Cleaner interfaces.

  • More flexible and robust implementations, and more of them.

• Implementing something approaching objects in C.

Why Objects?

• There are many reasons to persue object-oriented design and implementation.

• Subtype polymorphism is the one that's important.

  • Clarifies and organizes reuse.

  • Leads to component-based design and implementation.

  • And then to frameworks.

Why Objects in C?

• Not subtype polymorphism.

  • The C type system can't handle it.

• However, pseudo-subtype polymorphism is still useful.

  • “Pseudo” meaning no “help from the compiler”.

• Impose structure on system design and implementation.

Objects in C?

• C is too low-level to directly support object orientation.

  • But it can implement it: C++ was originally translated to C.

• Object-oriented wrappers around C code is a common technique.

  • For varying levels of “object-oriened”.

• The questions are “How close can we get?” and “How ugly will it be?”

Shared Interfaces

• Parent-child objects share a common interface.

  • In particular, the child contains the parent's interface.

  class shape { void draw(); }
  class triangle : shape { }
  class circle : shape { }
  
  shapes display_list[]
  display_list[0] = triangle_new()
  display_list[1] = circle_new()
  
  for i = 0 to n
    display_list[i].draw()

Shared ADT Interfaces

• Can ADTs share interfaces?

  • Not really because operation names must differ.

    void shape_draw(Shape)
    void triangle_draw(Triangle)
    void square_draw(Square)
    

  • C does not overload function names.

    void draw(Shape)
    void draw(Triangle)
    void draw(Square)
    

Shared struct Fields

• C structs may share field names.

  struct Square
    real area
    real center_x, center_y
  
  struct Circle
    real area
    real center_x, center_y
  

• Unfortunately, structs may not contain function definitions.

Function Pointers

• Fortunately, structs may contain function pointers.

• A function pointer is a pointer to the code executed by a function.

  

• Function pointers are similar to the other pointer types in C.

Function Pointers in structs

• Adding function pointers to structs produces object-like data instances.

  struct Triangle
    real (* area)(Triangle)
    void (* draw)(Triangle)
    void (* move)(Triangle, real, real)
  
  struct Square
    real (* area)(Square)
    void (* draw)(Square)
    void (* move)(Square, real, real)
  

Example

• How's it look?

  Triangle t = triangle_new()
  Square s = square_new()
  
  s→draw(s)
  t→draw(t)

• Does it do what we want?

  display_list[0] = triangle_new()
  display_list[1] = square_new()
  
  for i = 0 to n
    display_list[i]→draw(display_list[i])

Implentation

• The implementation is fairly straightforward once you get function pointers.

static void triangle_draw(Triangle) {...}

Triangle triangle_new()

  Triangle t = malloc(struct Triangle)

  t→draw = triangle_draw
  t→area = triangle_area
  // and so on.

  return t

Parent Implentation

• What does a parent implementation look like?

  • Mostly they look like child implementations.

• Abstract parents should not create instances.

  • Abstract parents specify the shared interface.

  • Abstract parents have no significant implementation.

  Shape shape_new()
    error("calling shape_new()")
    return NULL
  

Interface

• The interface is also fairly straightforward.

  #ifndef _triangle_h_
  #define _triangle_h_
  
  typedef struct Triangle {
    void (* move)(Triangle *, real, real);
    real (* area)(Triangle *);
    void (* draw)(Triangle *);
    } * Triangle;
  
  Triangle triangle_new();
  void triangle_delete(Triangle);
  
  #endif

Some Problems

• There are a few (!) problems:

  1. Where's the interface sharing?

  2. What are the types? Do they compile without errors?

• Both of these problems can be resolved using the same techniques.

  • But here's where it starts to get ugly.

Shared Interfaces?

• The interfaces given so far have been shared rather than common.

  struct Shape
    real (* area)(Shape)
    void (* draw)(Shape)
    void (* move)(Shape, real, real)
  
  struct Triangle
    real (* area)(Triangle)
    void (* draw)(Triangle)
    void (* move)(Triangle, real, real)
  
  struct Square
    real (* area)(Square)
    void (* draw)(Square)
    void (* move)(Square, real, real)

Shared vs Common

• Common interfaces result in fragile code.

  • Changes in the parent interface need to be copied to all the children.

  • A change in the child interface may unintentionally conflict with the parent's interface.

• #define macros can help establish shared interfaces.

  • This is a step towards inheritance.

#define Sharing

• Using textual substitution gives straightforward, if ugly, interface sharing.

#define Shape_Pubic_Interface \
  real (* area)(Shape); \
  void (* draw)(Shape); \
  void (* move)(Shape, real, real)

#define Circle_Circle_Interface \
  Shape_Public_Interface; \
  real (* get_radius)(Circle)

Shape Interface Example

• Assume Shape is abstract.

#ifndef _shape_h_
#define _shape_h_

#define Shape_Pubic_Interface \
  real (* area)(Shape); \
  void (* draw)(Shape); \
  void (* move)(Shape, real, real)

typedef struct Shape {
  Shape_Public_Interface;
  } * Shape;

#endif

Circle Interface Example

#ifndef _circle_h_
#define _circle_h_

#include "shape.h"

#define Circle_Pubic_Interface \
  Shape_Public_Interface; \
  real (* get_radius)(struct Circle *)

typedef struct Circle {
  Circle_Public_Interface;
  } * Circle;

Circle circle_new();
void circle_delete(Circle);

#endif

Some Problems

• There are a few (!) problems:

  1. Where's the interface sharing?

     • It's done by #define macros.

  2. What are the types? Do they compile without errors?

     • The problem here is type subversion (or punning).

Differing Parameter Types

• The Circle struct expands to

  typedef struct Circle {
    real (* area)(Shape);
    void (* draw)(Shape);
    void (* move)(Shape, real, real);
    real (* get_radius)(struct Circle *);
    } * Circle;
  

• Does mixing parameter types cause problems?

  • If so, what kind of problems and how can they be fixed?

Subverted Parameter Types

• Does using one struct type as if it is another type cause problems?

  shapes display_list[]
  display_list[0] = triangle_new()
  display_list[1] = circle_new()
  
  for i = 0 to n
    display_list[i].draw()

  • If not, why not?

Type Problems

• There are two type problems to worry about:

  1. Those that cause compilation errors.

  2. Those that cause run-time errors.

• Compilation errors have to be fixed in the code.

• Run-time errors cant' be fixed and have to be avoided.