Lösch, Steffen ;
Pitts, Andrew M.
Relating Two Semantics of Locally Scoped Names
Abstract
The operational semantics of programming constructs involving locally
scoped names typically makes use of stateful "dynamic allocation": a
set of currentlyused names forms part of the state and upon entering
a scope the set is augmented by a new name bound to the scoped
identifier. More abstractly, one can see this as a transformation of
local scopes by expanding them outward to an implicit toplevel. By
contrast, in a neglected paper from 1994, Odersky gave a stateless
lambda calculus with locally scoped names whose dynamics contracts
scopes inward. The properties of "Oderskystyle" local names are quite
different from dynamically allocated ones and it has not been clear,
until now, what is the expressive power of Odersky's notion. We show
that in fact it provides a direct semantics of locally scoped names
from which the more familiar dynamic allocation semantics can be
obtained by continuationpassing style (CPS) translation. More
precisely, we show that there is a CPS translation of typed lambda
calculus with dynamically allocated names (the PittsStark
nucalculus) into Odersky's lambdanucalculus which is
computationally adequate with respect to observational equivalence in
the two calculi.
BibTeX  Entry
@InProceedings{lsch_et_al:LIPIcs:2011:3245,
author = {Steffen L{\"o}sch and Andrew M. Pitts},
title = {{Relating Two Semantics of Locally Scoped Names}},
booktitle = {Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL},
pages = {396411},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897323},
ISSN = {18688969},
year = {2011},
volume = {12},
editor = {Marc Bezem},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3245},
URN = {urn:nbn:de:0030drops32454},
doi = {10.4230/LIPIcs.CSL.2011.396},
annote = {Keywords: local names, continuations, typed lambdacalculus, observational equivalence}
}
2011
Keywords: 

local names, continuations, typed lambdacalculus, observational equivalence 
Seminar: 

Computer Science Logic (CSL'11)  25th International Workshop/20th Annual Conference of the EACSL

Issue date: 

2011 
Date of publication: 

2011 