Common interface to some containers ¶

After having started Vicare’s container libraries (stack, queue, deque, …), the problem of “generic programming” obviously arose; a very simple and partial solution is implemented by some new libraries. All the changes discussed here are in the master branch.

There are at least two instances of the problem:

1. Defining data structures collecting a specific type of objects, so that the insertion and retrieval operations on the container know what type to expect and what type to return. This is for the future.
2. Defining a common interface to containers providing similar operations. This is what is discussed here.

The solution adopted by many languages is: support for interfaces with early and late binding; if we can specify that a function accepts as argument an object implementing the “stack interface”, that function can call the usual methods ‘top’, ‘push’, ‘pop’ on the stack–like object. One of the following techniques is used:

Early binding, static dispatch

If the true operand type can be determined at compile–time: the call to an actual method function can be inserted at compile–time.

Late binding, dynamic dispatch

If the true operand type cannot be determined at compile–time: at run–time, the type descriptor of the operand must be inspected and a table of methods queried for the implemented interfaces.

Support for interfaces, early and late bindings is for the future. What is implemented by the new libraries is a set of record types that unify the basic operations on common containers. So the library (vicare containers istacks) defines the “abstract” record type <istack> and the library (vicare containers istacks lists) provides a “concrete” implementation of the <istack> type using built–in lists as storage; usage example:

(import (vicare)
  (vicare containers istacks)
  (vicare containers istacks lists))

(define S
  (make-istack-list))

(istack-push! S 0)
(istack-push! S 1)
(istack-push! S 2)

(istack-top  S)         ⇒ 2
(istack-pop! S)         ⇒ 2
(istack-pop! S)         ⇒ 1

The library (vicare containers istacks chains) provides a “concrete” implementation of the <istack> type using a chain as storage; chains are doubly–linked lists defined by the library (vicare containers chains). Usage example:

(import (vicare)
  (vicare containers chains)
  (vicare containers istacks)
  (vicare containers istacks chains))

(define S
  (make-istack-chain (chain)))

(istack-push! S 0)
(istack-push! S 1)
(istack-push! S 2)

(istack-top  S)         ⇒ 2
(istack-pop! S)         ⇒ 2
(istack-pop! S)         ⇒ 1

Every container that can implement last–in/first–out insertion and extraction operations can become a concrete implementation of <istack>; at present the following libraries deal with the common stack api:

(vicare containers istacks)
(vicare containers istacks lists)
(vicare containers istacks ilists)
(vicare containers istacks ralists)
(vicare containers istacks chains)
(vicare containers istacks dynamic-arrays)
(vicare containers istacks stacks)
(vicare containers istacks deques)

Similarly, a common api is defined for queues through the record type <iqueue>; every container that can implement first–in/first–out insertion and extraction operations can become a concrete implementation of <iqueue>; at present the following libraries deal with the common queue api:

(vicare containers iqueues)
(vicare containers iqueues dynamic-arrays)
(vicare containers iqueues queues)
(vicare containers iqueues deques)
(vicare containers iqueues chains)

Similarly, a common api is defined for deques through the record type <ideque>; every container that can implement a sequence of object with front and rear insertion and extraction operations can become a concrete implementation of <ideque>; at present the following libraries deal with the common deque api:

(vicare containers ideques)
(vicare containers ideques dynamic-arrays)
(vicare containers ideques deques)
(vicare containers ideques chains)

Proper interface support with early and late binding is better, but these common apis are ready today.