%O BookSection 
%F cfhps91b
%A Cai, Jiazhen
%A Facon, Philippe
%A Henglein, Fritz
%A Paige, Robert
%A Schonberg, Edmond
%T Type Analysis and Data Structure Selection
%B Constructing Programs from Specifications
%E M{ö}ller, 
%P 125-164
%I North-Holland
%X Schwartz et al. described an optimization to implement built-in ab- stract types such as sets and maps with efficient data structures. Their transformation rests on the discovery of finite universal sets, called bases, to be used for avoiding data replication and for creating aggregate data structures that implement associative access by simpler cursor or pointer access. The SETL implementation used global analysis similar to classical dataflow for typings and for set inclusion and membership relationships to determine bases. However, the optimized data structures selected by this optmization did not include a primitive linked list or array, and all optimized data structures retained some degree of hashing. Hence, this heuristic approach only resulted in an expected improvement in performance over default implementations. The analysis was complicated by SETL's imperative style, weak typing, and low level control structures. The implemented optimizer was large (about 20,000 lines of SETL source code) and only partially operational
%U http://www.diku.dk/hjemmesider/ansatte/henglein/papers/cai1991.pdf
%8 May
%D 1991
%K dbprog