Paper: Non-determinism in a functional setting (at LICS 1993)

Authors: C.-H. Luke Ong

Abstract

The pure untyped lambda calculus augmented with an (erratic) choice operator is considered as an idealised nondeterministic functional language. Both the `may' and the `must' modalities of convergence are of interest. Following Abramsky's (1991) work on domain theory in logical form, we identify the denotational type that captures the computational situation δ=P[[δ→δ]⊥], where P[-] is the Plotkin power-domain functor. We then carry out a systematic programme that hinges on three distinct interpretations of δ, namely process-theoretic, denotational, and logical. The main theme of the programme is the complementarity of the various interpretations of δ. This work may be seen as a step towards a rapprochement between the algebraic theory of processes in concurrency on the one hand, and the lazy lambda calculus as a foundation for functional programming on the other

BibTeX

  @InProceedings{Ong-Nondeterminisminafu,
    author = 	 {C.-H. Luke Ong},
    title = 	 {Non-determinism in a functional setting},
    booktitle =  {Proceedings of the Eighth Annual IEEE Symposium on Logic in Computer Science (LICS 1993)},
    year =	 {1993},
    month =	 {June}, 
    pages =      {275--286},
    location =   {Montreal, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }