Encoding FIX in Object Calculi

Roy L. Crole

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 34, Issue: 1, page 15-38
  • ISSN: 0988-3754

Abstract

top
We show that the FIX type theory introduced by Crole and Pitts [3] can be encoded in variants of Abadi and Cardelli's object calculi. More precisely, we show that the FIX type theory presented with judgements of both equality and operational reduction can be translated into object calculi, and the translation proved sound. The translations we give can be seen as using object calculi as a metalanguge within which FIX can be represented; an analogy can be drawn with Martin Löf's Theory of Arities and Expressions. As well as providing a description of certain interesting recursive objects in terms of rather simpler expressions found in the FIX type theory, the translations will be of interest to those involved with the automation of operational semantics.

How to cite

top

Crole, Roy L.. "Encoding FIX in Object Calculi." RAIRO - Theoretical Informatics and Applications 34.1 (2010): 15-38. <http://eudml.org/doc/221978>.

@article{Crole2010,
abstract = { We show that the FIX type theory introduced by Crole and Pitts [3] can be encoded in variants of Abadi and Cardelli's object calculi. More precisely, we show that the FIX type theory presented with judgements of both equality and operational reduction can be translated into object calculi, and the translation proved sound. The translations we give can be seen as using object calculi as a metalanguge within which FIX can be represented; an analogy can be drawn with Martin Löf's Theory of Arities and Expressions. As well as providing a description of certain interesting recursive objects in terms of rather simpler expressions found in the FIX type theory, the translations will be of interest to those involved with the automation of operational semantics. },
author = {Crole, Roy L.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {FIX type theory},
language = {eng},
month = {3},
number = {1},
pages = {15-38},
publisher = {EDP Sciences},
title = {Encoding FIX in Object Calculi},
url = {http://eudml.org/doc/221978},
volume = {34},
year = {2010},
}

TY - JOUR
AU - Crole, Roy L.
TI - Encoding FIX in Object Calculi
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
PB - EDP Sciences
VL - 34
IS - 1
SP - 15
EP - 38
AB - We show that the FIX type theory introduced by Crole and Pitts [3] can be encoded in variants of Abadi and Cardelli's object calculi. More precisely, we show that the FIX type theory presented with judgements of both equality and operational reduction can be translated into object calculi, and the translation proved sound. The translations we give can be seen as using object calculi as a metalanguge within which FIX can be represented; an analogy can be drawn with Martin Löf's Theory of Arities and Expressions. As well as providing a description of certain interesting recursive objects in terms of rather simpler expressions found in the FIX type theory, the translations will be of interest to those involved with the automation of operational semantics.
LA - eng
KW - FIX type theory
UR - http://eudml.org/doc/221978
ER -

References

top
  1. M. Abadi and L. Cardelli, A Theory of Objects. Springer-Verlag, Monogr. Comput. Sci. (1996).  
  2. R.L. Crole, Functional Programming Theory (1995). Department of Mathematics and Computer Science Lecture Notes, LATEX format iv+68 pages with index.  
  3. R.L. Crole and A.M. Pitts, New Foundations for Fixpoint Computations: FIX Hyperdoctrines and the FIX Logic. Information and Computation98 (1992) 171-210. LICS '90 Special Edition of Information and Computation.  
  4. A.D. Gordon, Bisimilarity as a theory of functional programming. Electron. Notes Theor. Comput. Sci. 1 (1995).  
  5. A.D. Gordon, Everything is an object. Seminar Notes, Microsoft Research U.K. (1997).  
  6. C.A. Gunter, Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press (1992).  
  7. G. Kahn, Natural semantics, edited by K. Fuchi and M. Nivat, Programming of Future Generation Computers. Elsevier Science Publishers B.V. North Holland (1988) 237-258.  
  8. Z. Luo, Computation and Reasoning. Oxford University Press, Monogr. Comput. Sci. 11 (1994).  
  9. E. Moggi, Notions of computation and monads. Theoret. Comput. Sci.93 (1989) 55-92.  
  10. B. Nordström, K. Petersson and J.M. Smith, Programming in Martin-Löf's Type Theory. Oxford University Press, Monogr. Comput. Sci. (1990).  
  11. A.M. Pitts, Operationally Based Theories of Program Equivalence, edited by P. Dybjer and A.M. Pitts, Semantics and Logics of Computation (1997).  
  12. G.D. Plotkin, A structural approach to operational semantics. Technical Report DAIMI-FN 19. Department of Computer Science, University of Aarhus, Denmark (1981).  
  13. G. Winskel, The Formal Semantics of Programming Languages. Foundations of Computing. The MIT Press, Cambridge, Massachusetts (1993).  

NotesEmbed ?

top

You must be logged in to post comments.