Logical Methods in Computer Science · 2017 · 21 citations · 8 references
ComputingComputer ScienceLogicProgramming LanguagesTheory Of ComputationFormal SemanticsModal LogicRecursion TheoryType CheckingType SystemsContextual EquivalenceGuarded RecursionLambda CalculusOperational SemanticsRecursionRecursive TypesType TheoryTyped Lambda Calculus
We present the guarded lambda-calculus, an extension of the simply typed lambda-calculus with guarded recursive and coinductive types. The use of guarded recursive types ensures the productivity of well-typed programs. Guarded recursive types may be transformed into coinductive types by a type-former inspired by modal logic and Atkey-McBride clock quantification, allowing the typing of acausal functions. We give a call-by-name operational semantics for the calculus, and define adequate denotational semantics in the topos of trees. The adequacy proof entails that the evaluation of a program always terminates. We introduce a program logic with L\"ob induction for reasoning about the contextual equivalence of programs. We demonstrate the expressiveness of the calculus by showing the definability of solutions to Rutten's behavioural differential equations.
8
A modal analysis of staged computation
Rowan Davies, Frank Pfenning · Journal of the ACM · 2001 · 300 citations
On an Intuitionistic Modal Logic
Gavin Bierman, Valeria de Paiva · Studia Logica · 2000 · 148 citations
Humanities, Philosophy, Logic +5
Ralf Jung, Robbert Krebbers, Lars Birkedal et al. · 2016 · 113 citations · Full text