Let's say we want to implement a stack with the following interface: struct stack; typedef struct stack *stack; extern stack stack_create(void); extern void stack_push(stack s, void *element); extern void stack_pop(stack s); extern void *stack_top(stack s); extern int stack_empty(stack s); We want to implement the stack as a linked list of elements. Notice first that we have a problem. How do we represent the empty stack? We could use NULL. But now how do we implement stack_push? Let's try: struct stack { void *element; stack next; }; stack stack_create(void) { return NULL; } void stack_push(stack s, void *element) { stack temp = malloc(sizeof(struct stack)); temp -> element = element; temp -> next = s; s = temp; } this does not work, since s is passed by value. The statement s = temp; will have no effect in the caller. So what do we do? Perhaps try passing by reference: extern void stack_push(stack *s, void *element); void stack_push(stack *s, void *element) { stack temp = malloc(sizeof(struct stack)); temp -> element = element; temp -> next = *s; *s = temp; } This is clearly unacceptable, since now we have changed the interface. Furthermore, the interface now reveals the implementation. OK, but if we had C++ we could hide it this way: extern void stack_push(statck& s, void *element); void stack_push(stack& s, void *element) { stack temp = malloc(sizeof(struct stack)); temp -> element = element; temp -> next = s; s = temp; } But now we can only call stack_push if the second value is a variable, and not if it is (say) the value of a function call: // incorrect now stack_push(find_first_stack(), element); Clearly, we don't respect the interface in this case. Similar solutions in C have the same problem, for instance those based on macros. The only reasonable solution to this problem is to use a header object. typedef struct list *list; struct list { void *element; list next; }; list cons(void *element, list l) { list temp = malloc(sizeof(struct list)); temp -> element = element; temp -> next = l; return temp; } struct stack { list elements; }; stack stack_create(void) { stack temp = malloc(sizeof(struct stack)); temp -> elements = NULL; return temp; } void stack_push(stack s, void *element) { s -> elements = cons(element, s -> elements); } int stack_empty(stack s) { return s -> elements == NULL; } void stack_pop(stack s) { list temp = s -> elements; assert(!stack_empty(s)); s -> elements = temp -> next; free(temp); } void stack_top(stack s) { assert(!stack_empty(s)); return s -> elements -> element; } Now suppose we want to implement another function: extern stack stack_copy(stack s); Here is how to do it: list list_copy(list l) { return l == NULL ? NULL : cons(l -> element, list_copy(l -> next)); } stack stack_copy(stack s) { stack temp = malloc(sizeof(struct stack)); temp -> elements = list_copy(s -> elements); return temp; } However, if we had the GC of Boehm, we could do better: void stack_pop(stack s) { assert(!stack_empty(s)); s -> elements = s -> elements -> next; } stack stack_copy(stack s) { stack temp = malloc(sizeof(struct stack)); temp -> elements = s -> elements; return temp; } and we no longer need list_copy. Notice that we don't really copy the stack contents. But we preserver an illusion that we do. The user can't tell the difference, and we can do something more efficient. Let's fill in the comments in the .h file /* This module uses the GC of Boehm. Thus, there is no need to specify memory allocation and deallocation. Memory is freed when it is no longer referenced. The push and pop operations are strictly imperative in that the alter the stack. We use uniform reference semantics, so all references to the same stack are affected by imperative operations. */ struct stack; typedef struct stack *stack; extern stack stack_create(void); extern void stack_push(stack s, void *element); extern int stack_empty(stack s); /* Precondition: the stack must not be emtpy, as reported by stack_empty() */ extern void stack_pop(stack s); /* Precondition: the stack must not be emtpy, as reported by stack_empty() */ extern void *stack_top(stack s); /* Return a new, independent stack with the same elements as s */ extern stack stack_copy(stack s); Now, if we make the stack functional instead of imperative, we don't need (and should not use) the header object (assuming GC): /* This module uses the GC of Boehm. Thus, there is no need to specify memory allocation and deallocation. Memory is freed when it is no longer referenced. The push and pop operations are strictly functional in that the do not alter the stack passed as argument. */ /* since stacks are immutable, no copy operation is necessary */ struct stack; typedef struct stack *stack; extern stack stack_create(void); extern stack stack_push(stack s, void *element); extern int stack_empty(stack s); /* Precondition: the stack must not be emtpy, as reported by stack_empty() */ extern stack stack_pop(stack s); /* Precondition: the stack must not be emtpy, as reported by stack_empty() */ extern void *stack_top(stack s); struct stack { void *element; stack next; }; stack stack_create(void) { return NULL; } stack stack_push(stack s, void *element) { stack temp = malloc(sizeof(struct stack)); temp -> element = element; temp -> next = s; return temp; } stack stack_pop(stack s) { return s -> next; } int stack_empty(stack s) { return s == NULL; } void * stack_top(stack s) { assert(!stack_empty(s)) return s -> element; } Now, let's see what happens if we do a queue instead of a stack. First let's do the imperative case: struct queue; typedef struct queue *queue; extern queue queue_create(void); extern void queue_enq(queue q, void *element); extern int queue_empty(queue q); /* Precondition: the queue must not be empty as reported by queue_empty() The front element of the queue is returned and deleted from the queue */ extern void *queue_deq(queue q); /* return a new independent queue with the same elements as q */ extern queue queue_copy(queue q); The list must be copied in queue_copy to preserve independence. Now, lets do the functional case