Relating function spaces to resourced function spaces
Author(s) -
Lidia Sánchez-Gil,
Mercedes Hidalgo-Herrero,
Yolanda Ortega-Mallén
Publication year - 2011
Publication title -
eprints complutense repositorio institucional de la ucm (universidad complutense de madrid)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1145/1982185.1982469
Subject(s) - denotational semantics , domain theory , semantics (computer science) , domain (mathematical analysis) , function (biology) , countable set , denotational semantics of the actor model , operational semantics , computer science , power domains , discrete mathematics , mathematics , space (punctuation) , algebra over a field , theoretical computer science , pure mathematics , programming language , mathematical analysis , physics , evolutionary biology , biology , voltage , quantum mechanics , operating system
In order to prove the computational adequacy of the (operational) natural semantics for lazy evaluation with respect to a standard denotational semantics, Launchbury defines a resourced denotational semantics. This should be equivalent to the standard one when given infinite resources, but this fact cannot be so directly established, because each semantics produces values in a different domain. The values obtained by the standard semantics belong to the usual lifted function space D = [D → D]⊥, while those produced by the resourced semantics belong to [C → E] where E satisfies the equation E = [[C → E] → [C → E]]⊥ and C (the domain of resources) is a countable chain domain defined as the least solution of the domain equation C = C⊥. We propose a way to relate functional values in the standard lifted function space to functional values in the corresponding resourced function space. We first construct the initial solution for the domain equation E = [[C → E]] → [C → E]]⊥ following Abramsky's construction of the initial solution of D = [D → D]⊥. Then we define a "similarity" relation between values in the constructed domain and values in the standard lifted function space. This relation is inspired by Abramsky's applicative bisimulation. Finally we prove the desired equivalence between the standard denotational semantics and the resourced semantics for the lazy λ-calculus.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom