Similarity implies equivalence in a class of non-deterministic call-by-need lambda calculi
It has become a standard approach to reason about contextual equivalence using some notion of (bi)simulation. The main technical task of this approach is to show that (bi)simulation is a (pre)congruence, and hence is sound for reasoning about contextual equivalence Howe devised a method to prove this, and his method has been widely adapted and applied. This paper deals with this challenge for call-by-need computation including non-determinism. In this setting, sharing of sub-computations must be taken into account due to its observable effects on the outcome of computations. The technical results of this paper are the definition of a class of non-deterministic reduction-based functional languages (SHOCS) The definition of this class is in terms of a schematic characterization of the reduction rules of the language. The main result is that for SHOCS languages mutual Similarity is sound for reasoning about contextual equivalence based oil may-convergence The paper also contains a presentation of a particular non-deterministic call-by-need calculus with let, case, constructors, and seq (C) 2009 Elsevier Inc All rights reserved.
call-by-need contextual equivalence lambda calculus bisimulation non-deterministic lambda calculus higher-order programming languages