Latest documents http://publikationen.stub.uni-frankfurt.de/index/index/ Thu, 29 Jan 2009 09:16:03 +0100 Thu, 29 Jan 2009 09:16:03 +0100 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/6176 We show on an abstract level that contextual equivalence in non-deterministic program calculi defined by may- and must-convergence is maximal in the following sense. Using also all the test predicates generated by the Boolean, forall- and existential closure of may- and must-convergence does not change the contextual equivalence. The situation is different if may- and total must-convergence is used, where an expression totally must-converges if all reductions are finite and terminate with a value: There is an infinite sequence of test-predicates generated by the Boolean, forall- and existential closure of may- and total must-convergence, which also leads to an infinite sequence of different contextual equalities. Manfred Schmidt-Schauß; David Sabel workingpaper http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/6176 Thu, 29 Jan 2009 09:16:03 +0100 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/6036 Various concurrency primitives have been added to sequential programming languages, in order to turn them concurrent. Prominent examples are concurrent buffers for Haskell, channels in Concurrent ML, joins in JoCaml, and handled futures in Alice ML. Even though one might conjecture that all these primitives provide the same expressiveness, proving this equivalence is an open challenge in the area of program semantics. In this paper, we establish a first instance of this conjecture. We show that concurrent buffers can be encoded in the lambda calculus with futures underlying Alice ML. Our correctness proof results from a systematic method, based on observational semantics with respect to may and must convergence. Jan Schwinghammer; David Sabel; Joachim Niehren; Manfred Schmidt-Schauß workingpaper http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/6036 Thu, 20 Nov 2008 16:20:55 +0100 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/192 We investigate methods and tools for analysing translations between programming languages with respect to observational semantics. The behaviour of programs is observed in terms of may- and must-convergence in arbitrary contexts, and adequacy of translations, i.e., the reflection of program equivalence, is taken to be the fundamental correctness condition. For compositional translations we propose a notion of convergence equivalence as a means for proving adequacy. This technique avoids explicit reasoning about contexts, and is able to deal with the subtle role of typing in implementations of language extension. Manfred Schmidt-Schauß; Joachim Niehren; Jan Schwinghammer; David Sabel workingpaper http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/192 Fri, 07 Mar 2008 16:07:51 +0100 http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/191 The paper proposes a variation of simulation for checking and proving contextual equivalence in a non-deterministic call-by-need lambda-calculus with constructors, case, seq, and a letrec with cyclic dependencies. It also proposes a novel method to prove its correctness. The calculus' semantics is based on a small-step rewrite semantics and on may-convergence. The cyclic nature of letrec bindings, as well as non-determinism, makes known approaches to prove that simulation implies contextual equivalence, such as Howe's proof technique, inapplicable in this setting. The basic technique for the simulation as well as the correctness proof is called pre-evaluation, which computes a set of answers for every closed expression. If simulation succeeds in finite computation depth, then it is guaranteed to show contextual preorder of expressions. Manfred Schmidt-Schauß; Elena Machkasova workingpaper http://publikationen.stub.uni-frankfurt.de/frontdoor/index/index/docId/191 Fri, 07 Mar 2008 16:05:42 +0100