# Encoding FIX in Object Calculi

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topCrole, 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- M. Abadi and L. Cardelli, A Theory of Objects. Springer-Verlag, Monogr. Comput. Sci. (1996). Zbl0876.68014
- R.L. Crole, Functional Programming Theory (1995). Department of Mathematics and Computer Science Lecture Notes, LATEX format iv+68 pages with index.
- 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. Zbl0763.03031
- A.D. Gordon, Bisimilarity as a theory of functional programming. Electron. Notes Theor. Comput. Sci. 1 (1995). Zbl0910.68118
- A.D. Gordon, Everything is an object. Seminar Notes, Microsoft Research U.K. (1997).
- C.A. Gunter, Semantics of Programming Languages: Structures and Techniques. Foundations of Computing. MIT Press (1992). Zbl0823.68059
- 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.
- Z. Luo, Computation and Reasoning. Oxford University Press, Monogr. Comput. Sci. 11 (1994). Zbl0823.68101
- E. Moggi, Notions of computation and monads. Theoret. Comput. Sci.93 (1989) 55-92. Zbl0723.68073
- B. Nordström, K. Petersson and J.M. Smith, Programming in Martin-Löf's Type Theory. Oxford University Press, Monogr. Comput. Sci. (1990). Zbl0744.03029
- A.M. Pitts, Operationally Based Theories of Program Equivalence, edited by P. Dybjer and A.M. Pitts, Semantics and Logics of Computation (1997). Zbl0919.68086
- G.D. Plotkin, A structural approach to operational semantics. Technical Report DAIMI-FN 19. Department of Computer Science, University of Aarhus, Denmark (1981).
- G. Winskel, The Formal Semantics of Programming Languages. Foundations of Computing. The MIT Press, Cambridge, Massachusetts (1993).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.