1985 · 14 citations · 13 references
ComputingComputer ScienceFormal MethodsProgramming LanguagesSemanticsFormal SemanticsFunctional ProgrammingRegular LanguagesCompletenessDenotational ModelsOperational SemanticsRewrite SystemsRewriting SystemsStructural Operational SemanticsTerm Rewriting
We consider languages whose operational semantics is given by a set of rewrite rules. For such languages, it is important to be able to determine that there are enough rules to completely reduce all meaningful expressions, but not so many that the system of rules is inconsistent. We develop a formal framework in which to give a precise treatment of these soundness and completeness issues. We believe our approach to be novel in that we make heavy use of denotational semantics in our proof of completeness. The particular language for which we answer these questions is an extended version of the functional programming language FP; however the applicability of these techniques extends beyond the realm of FP rewriting systems.
13
Can programming be liberated from the von Neumann style?
John Backus · Communications of the ACM · 1978 · 2.6K citations · Full text
R. M. Burstall, David MacQueen, Donald Sannella · 1980 · 351 citations
Peter Henderson, James H. Morris · 1976 · 327 citations · Full text