ACM Transactions on Programming Languages and Systems · 1992 · 26 citations · 24 references
Language StudiesComputer ScienceLinguisticsProgramming LanguagesSemanticsSyntaxFormal SemanticsSyntax-semantics InterfaceAbstract Syntax ModelingEquational LogicEquational ReasoningOperational SemanticsOperatorsStructural Operational Semantics
In this paper we introduce M-LISP, a dialect of LISP designed with an eye toward reconciling LISP's metalinguistic power with the structural style of operational semantics advocated by Plotkin [28]. We begin by reviewing the original definition of LISP [20] in an attempt to clarify the source of its metalinguistic power. We find that it arises from a problematic clause in this definition. We then define the abstract syntax and operational semantics of M-LISP, essentially a hybrid of M-expression LISP and Scheme. Next, we tie the operational semantics to the corresponding equational logic. As usual, provable equality in the logic implies operational equality. Having established this framework we then extend M-LISP with the metalinguistic eval and reify operators (the latter is a nonstrict operator that converts its argument to its metalanguage representation). These operators encapsulate the matalinguistic representation conversions that occur globally in S-expression LISP. We show that the naive versions of these operators render LISP's equational logic inconsistent. On the positive side, we show that a naturally restricted form of the eval operator is confluent and therefore a conservative extension of M-LISP. Unfortunately, we must weaken the logic considerably to obtain a consistent theory of reification.
24
Can programming be liberated from the von Neumann style?
John Backus · Communications of the ACM · 1978 · 2.6K citations · Full text
Call-by-name, call-by-value and the λ-calculus
Gordon Plotkin · Theoretical Computer Science · 1975 · 1.2K citations
Definitional interpreters for higher-order programming languages
John Reynolds · 1972 · 668 citations
Gilles Kahn · Symposium on Theoretical Aspects of Computer Science · 1987 · 523 citations