Efficient Inference of Object Types
DOI:
https://doi.org/10.7146/brics.v2i32.19935Resumé
Abadi and Cardelli have recently investigated a calculus of objects[2]. The calculus supports a key feature of object-oriented languages:
an object can be emulated by another object that has more refined
methods. Abadi and Cardelli presented four first-order type systems
for the calculus. The simplest one is based on finite types and no
subtyping, and the most powerful one has both recursive types and
subtyping. Open until now is the question of type inference, and
in the presence of subtyping the absence of minimum typings poses
practical problems for type inference [2].
In this paper we give an O(n^3) algorithm for each of the four type
inference problems and we prove that all the problems are P-complete.
We also indicate how to modify the algorithms to handle functions and
records.
Downloads
Publiceret
1995-06-02
Citation/Eksport
Palsberg, J. (1995). Efficient Inference of Object Types. BRICS Report Series, 2(32). https://doi.org/10.7146/brics.v2i32.19935
Nummer
Sektion
Artikler
Licens
Authors who publish with this journal agree to the following terms:- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
