Efficient type inference for record concatenation and subtyping
Proceedings - Symposium on Logic in Computer Science - Trang 125-136
Tóm tắt
Record concatenation, multiple inheritance, and multiple-object cloning are closely related and part of various language designs. For example, in Cardelli's untyped Obliq language, a new object can be constructed from several existing objects by cloning followed by concatenation; an error is given in case of field name conflicts. Type systems for record concatenation have been studied by M. Wand (1991), R. Harper and B. Pierce (1991), D. Remy (1992), and others; and type inference for the combination of record concatenation and subtyping has been studied by M. Sulzmann (1997) and by F. Pottier (2000). In this paper we present the first polynomial-time type inference algorithm for record concatenation, subtyping, and recursive types. Our example language is the Abadi-Cardelli object calculus extended with a concatenation operator The type inference algorithm runs in O(n/sup 5/) time where n is the size of the program. Our algorithm enables efficient type checking of Obliq programs without changing the programs at all.
Từ khóa
#Cloning #Concatenated codes #Computer science #Polynomials #Runtime #Calculus #Inference algorithms #LogicTài liệu tham khảo
10.1145/154766.155375
10.1145/143165.143202
10.1145/360204.360230
10.1109/LICS.1993.287570
10.1007/3-540-46425-5_21
10.1007/BF01212524
palsberg, 2002, Automatic discovery of co-variant read-only fields, Proceedings of FOOL'02 Ninth International Workshop on Foundations of Object-Oriented Languages
10.1145/210184.210187
10.1145/232706.232715
10.1007/3-540-58715-2_117
sulzmann, 1997, Designing record systems
10.1016/0890-5401(91)90050-C
10.1006/inco.1994.1093
zwanenburg, 1995, Record concatenation with intersection types
zwanenburg, 1996, A type system for record concatenation and subtyping, Informal proceedings of Third Workshop on Foundations of Object-Oriented Languages (FOOL 3)
10.1145/199448.199516
borning, 1982, Multiple inheritance in Smalltalk80, Proceedings of AAAI
10.1006/inco.1995.1168
abadi, 1996, A Theory of Objects, 10.1007/978-1-4419-8598-9
mcallester, 1999, On the complexity analysis of static analyses, SAS'99 Proceedings of the 6th International Symposium on Static Analysis, 312
10.1016/S0022-0000(05)80051-0
10.1145/99583.99603
10.1145/353171.353192
nielson, 1989, The typed lambda-calculus with first-class processes, Proc PARLE, 357
10.1016/B978-0-444-88074-1.50024-X