1974 shaares
6 private links
6 private links
The objective of this proposal is to standardize the usage of common data structures within the context of the C language. The existence of a common standard interface for lists, hash tables, flexible arrays, and other containers has several advantages:
User code remains portable across different projects. In C, we all use the FILE abstraction, for instance. This abstraction allows software to be compatible across a large spectrum of machines and operating systems. Imagine what would happen if each project had to develop a file stream abstraction again and again. This is the case when using lists, for instance. Today, we have in all significant projects written in C a list module, and probably other ones like hash tables, etc.
Avoid duplication of effort. Most of the list or hash tables modules can't be debugged completely and are the source of never ending problems.
Lack of standards makes the merging of two projects very difficult since in most cases the interfaces and data structures are slightly different. This leads to a complete rewrite of one of the modules, or to ädapter" software that will translate from one list implementation to the other, adding yet another layer of complexity to the merged project.
The language becomes more expressive since it becomes possible to reason within a high level environment. The lack of operations for handling advanced data structures conditions programmers to use low level solutions like making an array with a fixed maximum size instead of a list even if the programmer would agree that a list would be a more adequate solution to the problem. Confronted to the alternative of developing yet another list module or opting for a low level solution many time constrained programmers will opt for the second solution.
The portable specifications provide a common framework for library writers and compiler/system designers to build compatible yet strongly specialized implementations.
The language becomes easier to analyze mathematically. In their very interesting paper "Precise reasoning for programs using containers", Dillig, Dillig and Aiken 1 enumerate three main points that make program analysis easier using containers:
Understanding the contents of a container doesn't require understanding the container's implementation
Verifying container implementations requires different techniques and degrees of automation than verifying their clients. Hence, separating these two tasks allows us to choose the verification techniques best suited for each purpose.
There are orders of magnitude more clients of a container than there are container implementations. This fact makes it possible to annotate a handful of library interfaces in order to analyze many programs using these containers.
It is possible to abstract from the nature of any container (using the iterator construct) what allows a series of algorithms to be written without having to bind them to a precise data structure. Containers present a uniform interface to the rest of the program.