OPUS 4 Latest Documents RSS FeedLatest documents
http://publikationen.ub.uni-frankfurt.de/index/index/
Tue, 22 Jun 2010 17:45:50 +0200Tue, 22 Jun 2010 17:45:50 +0200Counterexamples to simulation in non-deterministic call-by-need lambda-calculi with letrec
http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7827
This note shows that in non-deterministic extended lambda calculi with letrec, the tool of applicative (bi)simulation is in general not usable for contextual equivalence, by giving a counterexample adapted from data flow analysis. It also shown that there is a flaw in a lemma and a theorem concerning finite simulation in a conference paper by the first two authors.Manfred Schmidt-Schauß; Elena Machkasova; David Sabelworkingpaperhttp://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7827Tue, 22 Jun 2010 17:45:50 +0200Contextual equivalence in lambda-calculi extended with letrec and with a parametric polymorphic type system
http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/6667
This paper describes a method to treat contextual equivalence in polymorphically typed lambda-calculi, and also how to transfer equivalences from the untyped versions of lambda-calculi to their typed variant, where our specific calculus has letrec, recursive types and is nondeterministic. An addition of a type label to every subexpression is all that is needed, together with some natural constraints for the consistency of the type labels and well-scopedness of expressions. One result is that an elementary but typed notion of program transformation is obtained and that untyped contextual equivalences also hold in the typed calculus as long as the expressions are well-typed. In order to have a nice interaction between reduction and typing, some reduction rules have to be accompanied with a type modification by generalizing or instantiating types.Manfred Schmidt-Schauß; David Sabel; Frederik Harwathworkingpaperhttp://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/6667Tue, 07 Jul 2009 13:30:55 +0200On correctness of buffer implementations in a concurrent lambda calculus with futures
http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/6666
Motivated by the question of correctness of a specific implementation of concurrent buffers in the lambda calculus with futures underlying Alice ML, we prove that concurrent buffers and handled futures can correctly encode each other. Correctness means that our encodings preserve and reflect the observations of may- and must-convergence. This also shows correctness wrt. program semantics, since the encodings are adequate translations wrt. contextual semantics. While these translations encode blocking into queuing and waiting, we also provide an adequate encoding of buffers in a calculus without handles, which is more low-level and uses busy-waiting instead of blocking. Furthermore we demonstrate that our correctness concept applies to the whole compilation process from high-level to low-level concurrent languages, by translating the calculus with buffers, handled futures and data constructors into a small core language without those constructs.Jan Schwinghammer; David Sabel; Joachim Niehren; Manfred Schmidt-Schaußworkingpaperhttp://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/6666Tue, 07 Jul 2009 13:22:26 +0200