1976/01/01 by Peter Henderson, James H. Morris · 327 citations
Computer Science · #Algorithms and Data Compression #Computer science #Correctness #Critical section #Functional programming #Lazy evaluation #Lisp #Logic, programming, and type systems #Natural Language Processing Techniques #Partial evaluation #Programming language #Semantics (computer science) #Substitution (logic) #Theoretical computer science
paper · pdf · doi:10.1145/800168.811543
openalex publication_date 1976/01/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/29
A different way to execute pure LISP programs is presented. It delays the evaluation of parameters and list structures without ever having to perform more evaluation steps than the usual method. Although the central idea can be found in earlier work this paper is of interest since it treats a rather well-known language and works out an algorithm which avoids full substitution. A partial correctness proof using Scott-Strachey semantics is sketched in a later section.