Efficient execution of programs with static semantics
George Becker, Neil V. Murray · ACM SIGPLAN Notices · 1995
An extension to single-threading (using each value exactly once) is presented that allows efficient execution of functional programs while maintaining their static semantics. This extension preserves the idea of only one, possibly modifying, use of a data item, and also allows any number of read-only uses. The inefficiency problem is overcome by imposing a restriction on function composition. The proposed method is based upon a static analysis of function definitions and calls. This analysis is linear in the size of function definitions, and additive between functions. Unlike approaches utilized in optimizing compilers, the proposed method can be applied even to large programs, and it guarantees the asymptotic complexity of corresponding imperative programs while obviating the need for garbage collection. An experimental functional programming language based on these ideas has been designed and implemented.