Implementing primitive datatypes for higher level languages

Implementation of modern programming languages is a complex task. Bridging the semantic gap between abstract linguistic constructs and concrete hardware components requires much software, including compilers, interpreters, runtime libraries, and programming environments. Compiler construction has long been aided by parser generators and attribute grammar evaluators, but the other components have been neglected, even though they constitute the largest parts of implementations of Lisp, Prolog, Smalltalk, and similar languages. Within an implementation, the representation of primitive datatypes such as numbers, lists, strings, and symbols require some of the most difficult decisions by the implementor. The effectiveness of type discrimination schemes, interactions between storage allocation and virtual memory, and general time/space tradeoffs are issues that have no simple resolution; they must be evaluated for each implementation. The problems are approached from three directions: a survey of representation ideas used in existing systems, a set of design rules that mimic the behavior of expert implementors, and an automatic designer that generates the primitive datatypes of