Logic in Computer Science (LICS 1992)

Paper: Observable algorithms on concrete data structures (at LICS 1992)

Authors: Curien, P.-L.

Abstract

A contribution to the investigation of sequentiality and full abstraction for sequential programming languages, focusing on the language PCF, is presented. Ideas of R. Cartwright and M. Felleisen (1992) on observable sequentiality are fit into the framework of concrete data structures and sequential algorithms. An extension of the category of sequential algorithms is shown to provide an order-extensional model of PCF. The key to this is the presence of errors in the semantic domains. The model of observable algorithms is fully abstract for an extension of PCF. This extension has errors too, as well as a control operation catch as found in languages such as Scheme or CommonLisp

BibTeX

  @InProceedings{Curien-Observablealgorithm,
    author = 	 {Curien, P.-L.},
    title = 	 {Observable algorithms on concrete data structures},
    booktitle =  {Proceedings of the Seventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1992},
    year =	 1992,
    editor =	 {Andre Scedrov},
    month =	 {June}, 
    pages =      {432--443},
    location =   {Santa Cruz, CA, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }