Novel array representation methods in support of a microcomputer-based APL interpreter

Objective: To study novel ways of representing data arrays for potential application in a microcomputer-based APL interpreter. The goal is to find, for arrays containing mixed integers and real numbers, a way to improve both storage efficiency and thruput, over that obtainable using conventional APL interpreter array representations. Investigation: For the purposes of this study, three representative APL operators were chosen for implementation - dyadic addition, multiplication and selection. To establish a set of base cases from which to work, these three operators were implemented for two distinctly different data structures: Case-0: arrays containing only fixed length floating point data elements Case-1: arrays containing only fixed length integer data elements These two cases are termed homogeneous because all data elements within each array share a common data structure - the conventional approach for APL interpreters. Three additional heterogeneous cases were then built upon the homogeneous base cases: Case-2: arrays containing mixed floating point and integer fixed length data elements Case-3: arrays containing mixed floating point and integer data elements, with the integer elements having variable length Case-4: arrays containing fixed length pointers to variable length Case-3 data elements For all of these cases, space and time tradeoffs were studied and charted. Exerciser programs were written in BASIC to drive the 5 Case-n implementations to enable direct comparison of the 5 storage allocation approaches; these driver routines prepared test data, ran the addition/multiplication/selection exercises, retrieved time and space measurements, and performed data reduction for presentation in this report. The 5 Case-n implementors were written in 6502 CPU assembly language, and provided the functions of addition, multiplication, selection, timing, and data format conversion between BASIC and Case-n data structures. Fixed length floating point arithmetic was supported on the target microcomputer for which all code was written -an Atari 800. In support of multi-byte integer arithmetic, however, original addition and multiplication atomic functions required development. Conclusions: Of the 5 cases implemented, Case-3 (heterogeneous variable length data elements) showed the greatest promise for saving space without adversely affecting addition and multiplication thruput. However, the selection algorithm had to be modified from an address calculation scheme based upon the indices of the desired elements to a search algorithm more suited to the variable length data elements. This produced astonishingly fast selection thruput for some applications, and dismally poor selection performance for others. At the end of the report are suggestions for future development of the variable length data element selection algorithm. Case-4 (pointers to heterogeneous variable length data elements) was introduced to enable the conventional address calculation selection scheme for variable length elements. The addition of the pointers did not have much impact upon thruput, but the additional space required for the pointers erased the space savings achieved with variable length elements