Journal of Functional Programming · 1992 · 96 citations · 7 references
ComputingComputer ScienceProgramming LanguagesRepresentation TheoryTheory Of ComputationAbstract InterpretationDeductive VerificationIntermediate RepresentationRecursion TheoryType SystemsConstructive Proof TheoryConstructive ProofsFixed-point SemanticsFixpoint ComputationLambda CalculusLambda Calculus SemanticsReductionsTyped Lambda Calculus
Abstract We start by giving a compact representation schema for λ-terms, and show how this leads to an exceedingly small and elegant self-interpreter. We then define the notion of a self-reducer , and show how this too can be written as a small λ-term. Both the self-interpreter and the self-reducer are proved correct. We finally give a constructive proof for the second fixed point theorem for the representation schema. All the constructions have been implemented on a computer, and experiments verify their correctness. Timings show that the self-interpreter and self-reducer are quite efficient, being about 35 and 50 times slower than direct execution using a call-by-need reductions strategy
7
An inverse of the evaluation functional for typed lambda -calculus
Ulrich Berger, H. Schwichtenberg · 2002 · 200 citations · Full text
Metacircularity in the polymorphic λ-calculus
Frank Pfenning, Peter Lee · Theoretical Computer Science · 1991 · 36 citations