Jiazhen Cai, Philippe Facon, Fritz Henglein, Robert Paige, Edmond Schonberg. Type Analysis and Data Structure Selection. In Constructing Programs from Specifications, Published in the US by Elsevier Science Publishing Company Inc, 655 Ave. of the Americas, New York, NY 10010; ISBN: 0 444 89184 6, Möller (ed.), Published in the US by Elsevier Science Publishing Company Inc, 655 Ave. of the Americas, New York, NY 10010; ISBN: 0 444 89184 6, pp. 125-164, North-Holland, May 1991.
Download paper:
Adobe portable document (pdf)
Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
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
[ Dbprog ]
J. Cai
Ph. Facon
Fritz Henglein
Robert Paige
E. Schonberg
@InCollection{cfhps91b,
Author = {Cai, Jiazhen and Facon, Philippe and Henglein, Fritz and Paige, Robert and Schonberg, Edmond},
Title = {Type Analysis and Data Structure Selection},
BookTitle = {Constructing Programs from Specifications},
editor = {M{ö}ller, },
Pages = {125--164},
Publisher = {North-Holland},
Month = {May},
Year = {1991}
}
Get EndNote Reference (.ref)