Search

We have implemented a data structure selection system to demonstrate the feasibility of our ideas. The system consists of several computer programs written in SAIL and PDP-10 assembly language. The assembly language parts of the system have been abstracted from the standard SAIL compiler, and are used to parse user programs and do the machine code emission in the final compiler. All the rest is written in SAIL. We make extensive use of the LEAP information structures in the SAIL coded portions. Communication between programs is accomplished by having each program write the contents of the LEAP information structures to a disk file which is later read by the next program in the series. The system we have designed to perform selection of low-level data structures logically consists of three major components: information gathering, structure selection, and final compilation and execution (See Figure 1). We will note other techniques which we feel are applicable to a selection system which are not part of our system.

In Section I, we mentioned many abstract data structures which we feel should be available in high level programming languages, including various kinds of queues, stacks, and mapping functions. This list is far from complete. We would imagine other programmers to have their own lists. The ones we chose hopefully form a basis for others. We hope that future systems will not only include the information structures mentioned, but will provide extension mechanisms to allow the user to define new information structures. These extension mechanisms should allow representations for user defined structures to be chosen much the same way as for built-in information structures. In our demonstration system, we have limited ourselves to those abstract data types already available in LEAP: sets, sequences and a single ternary relation. Let us now consider these information structures.

We feel that the system has performed quite well. In general it has chosen appropriate data structures for the programs considered. Where it has failed to choose optimum structures, it has led us to specific defects in our models of storage and execution time. Some of these, like the use of constant list indices can be easily handled by simple modifications. Others such as storage fragmentation and using internal properties of other structures (such as the fact that the NEW allocator usually returns items in increasing order) are not so easily handled.