EFFICIENT EXECUTION OF PROGRAMS WITH STATIC SEMANTICS

An extension to single-threading (using each value exactly once) is pr esented that allows efficient execution of functional programs while m aintaining their static semantics. This extension preserves the idea o f only one, possibly modifying, use of a data item, and also allows an y number of read-only uses. The inefficiency problem is overcome by im posing a restriction on function composition. The proposed method is b ased upon a static analysis of function definitions and calls. This an alysis is linear in the size of function definitions, and additive bet ween functions. Unlike approaches utilized in optimizing compilers, th e proposed method can be applied even to large programs, and it guaran tees the asymptotic complexity of corresponding imperative programs wh ile obviating the need for garbage collection. An experimental functio nal programming language based on these ideas have been designed and i mplemented.