Programming languages with countable nondeterministic choice are computationally interesting since countable nondeterminism arises when modeling fairness for concurrent systems. Because countable choice introduces non-continuous behaviour, it is well-known that developing semantic models for programming languages with countable nondeterminism is challenging. We present a step-indexed logical relations model of a higher-order functional programming language with countable nondeterminism and demonstrate how it can be used to reason about contextually defined may- and must-equivalence. In earlier step-indexed models, the indices have been drawn from omega. Here the step-indexed relations for must-equivalence are indexed over an ordinal greater than omega. Finally, we define step-indexed logical relations for showing the adequacy of a continuation-passing-style transformation of the language.
A preliminary version of this work has been presented at CSL'11. The present version includes more proofs, and a section with a new application of step-indexed relational reasoning for showing the adequacy of a cps-transformation of our language.