Types and Type Checking in Stack-Based Query Languages

• Autorzy: Hryniów R. , Lentner M. , Stencel K. , Subieta K.
• Języki publikacji: EN

Abstrakty

EN

In this report we propose a new approach to types and static type checking in object-oriented database query and programming languages. In contrast to typical approaches to types which involve very advanced mathematical concepts we present a type system from the practitioners' point of view. We argue that many features of current object-oriented query/programming languages, such as ellipses, automatic coercions and irregularities in data structures, cause that very formal type systems are irrelevant to practical situations. We treat types as some syntactic qualifiers (tokens or some structures of tokens) attached to objects, procedures, modules and other data/program entities. Such syntactic qualifiers we call signatures. We avoid the simpleminded notion that a type has some internal semantics e.g. as a set of values. In our assumptions a type inference system is based on predefined decision tables involving signatures and producing type checking decisions, which can be the following: (1) type error, (2) new signature, (3) dereference, coercion and/or delegation of a type check to run-time. A type inference decision table is to be developed for every query/programming operator. Type inferences are implied by the stack-based approach (SBA) to object-oriented query/programming languages. Static type checking is just a compile time simulation of the run-time computation. Thus the type checker is based on data structures that statically model run-time structures and processes, that is: (1) metabase (internal representation of a database schema, a counterpart of an object store), (2) static environment stack (a counterpart of run-time environment stack), (3) static result stack (a counterpart of run-time result stack) and (4) type inference decision tables (a counterpart of run-time computations). Then, we present the static type check procedure which is driven by the metabase, the static stacks and the type inference decision tables. To discover several type errors in one run we show how to correct some type errors during the type check. Finally we present our prototype implementation showing that our approach is feasible and efficient with moderate implementation effort.

PL

W raporcie proponujemy nowe podejście do typów i statycznej kontroli typologicznej w obiektowych językach zapytań/programowania. W przeciwieństwie do podejść wykorzystujących zaawansowane koncepcje matematyczne prezentujemy tu pozycję praktyków. Wiele cech obecnych języków zapytań/programowania, takich jak elipsy, automatyczne koercje oraz nieregularności struktur danych, powodują, że bardzo formalne systemy typologiczne nie odpowiadają praktyce. Proponujemy typy jako syntaktyczne kwalifikatory (znaki lub struktury znaków) przypisane do obiektów, procedur oraz innych bytów programistycznych. Takie kwalifikatory nazwaliśmy sygnaturami. Unikamy popularnego punktu widzenia, w którym typ posiada wewnętrzną semantykę, np. w postaci zbioru wartości. System wnioskowania o typie jest oparty na tabelach decyzyjnych działających na sygnaturach i generujących decyzje w zakresie kontroli typologicznej, które mogą być następujące: (1) błąd typologiczny, (2) nowa sygnatura, (3) dereferencja, koercja i/lub oddelegowanie kontroli typu do czasu wykonania. Tablice decyzyjne powinny być sporządzone dla każdego operatora występującego w zapytaniach/programach. Wnioskowanie o typie jest implikowane przez podejście stosowe (SBA) do obiektowych języków zapytań/programowania. Statyczna kontrola typologiczna symuluje podczas kompilacji tę sytuację, która zajdzie podczas czasu wykonania. Stąd kontroler typów jest oparty na strukturach danych, które statycznie modelują struktury i procesy czasu wykonania, tj.: (1) metabaza (wewnętrzna reprezentacja schematu, odpowiednik składu obiektów), (2) statyczny stos środowiskowy (odpowiednik stosu środowiskowego), (3) statyczny stos rezultatów (odpowiednik stosu rezultatów), (4) tablice decyzyjne wnioskowania o typie (odpowiednik operatorów). Następnie prezentujemy procedurę statycznej kontroli typów, której działanie jest oparte na metabazie, statycznych stosach i tabelach decyzyjnych. Aby wykryć wiele błędów typologicznych w jednym przebiegu pokazujemy, jak należy skorygować pewne błędy typologiczne podczas kontroli typologicznej. Na końcu prezentujemy prototypową implementację pokazującą, że nasze podejście jest osiągalne i efektywne przy umiarkowanym wysiłku implementacyjnym.

Słowa kluczowe

EN

type; static type checking; query language; database; object-oriented; data schema; Stack-Based Approach (SBA)

PL

typ; statyczna kontrola typologiczna; język zapytań; baza danych; obiektowo-zorientowany; schemat danych; podejście stosowe

• Wydawca: Instytut Podstaw Informatyki PAN
• Czasopismo: Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
• Rocznik: 2005
• Tom: Nr 984
• Strony: 1--60
• Opis fizyczny: Bibliogr. 28 poz.

Twórcy

autor

Hryniów R.

• Polish-Japanese Institute of Information Technology ul. Koszykowa 86, 02-008 Warsaw, Poland

autor

Lentner M.

• Polish-Japanese Institute of Information Technology ul. Koszykowa 86, 02-008 Warsaw, Poland

autor

Stencel K.

• Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097 Warsaw Poland

autor

Subieta K.

• Polish-Japanese Institute of Information Technology ul. Koszykowa 86, 02-008 Warsaw, Poland
• Institute of Computer Science PAS, ul. Ordona 21, 01-237 Warszawa, Polska

Bibliografia

• M.Abadi, L.Cardelli. A Theory of Objects. Springer Verlag 1996, ISBN:03 87947752.
• S.AIagic: F-Boundcd Polymorphism for Database Programming Languages. East/West Database Workshop, Springer 1994, 125-137
• S.Alagie. The ODMG Object Model: Docs it Make Sense? Proc. OOPSLA Conf., 253-270, 1997
• S.Alagie, Type Checking OQL Queries in the ODMG Type Systems, ACM Transactions on Database Systems, 24 (3), pp. 319- 360, 1999.
• S. Alagic, A Family of the ODMG Object Models. Proceedings of ADBIS '99, Springer LNCS 1691, 1999, pp.14-30
• M.Atkinson, P.Buncman. Types and Persistence in Database Programming Languages. ACM Computing Surveys 19(2), 105- 190, 1987
• M.Atkinson, R.Morrison. Orthogonally Persistent Object Systems. The VLDB Journal 4(3), 319-401, 1995
• P.S.Canning, W.R.Cook, W.L.Hill, W.G.Olthoff, J.C.Mitchell: F-Bounded Polymorphism for Object-Oriented Programming. FPCA '89 Conference on Functional Programming Languages and Computer Architecture. ACM Press, 1989, pp.273-280
• L.Cardelli: A Semantics of Multiple Inheritance. Information and Computation, Volume 76, Number 1, January 1988, pp. 138-164 L.Cardelli, P.Wegncr. On Understanding Types, Data Abstraction and Polymorphism. ACM Computing Surveys 17(4), 471-522, 1985
• L.Cardelli. Typeful Programming. Technical Report, Digital Systems Research Center Report 45, Palo Alto, USA, 1989
• R.Goldman, J.Widom, DataGuides: Enabling Query Formulation and Optimization Semistructured Databases, Twenty-Third International Conference on Very Large Data Bases,, pp. 436-445, ftp://db.stanford.edu/pub/papers/dataguide.ps, 1997.
• P.Habela, M.Roantree, K.Subieta. Flattening the Metamodel for Object Databases. Proc. of ADBIS'2002 Conf. Bratislava, Slovakia, Springer LNCS 2435, pp. 263-275, 2002
• P.Habela, K.Subieta: Overcoming the Complexity of Object- Oriented DBMS Metadata Management. Proc. 001S’2003, Springer LNCS 2817, pp.214-225, 2003
• J.C.Mitchell, G.D.Plotkin: Abstract Types Have Existential Type. ACM Trans. Program. Lang. Syst. 10(3), pp. 470-502 1988
• OMG Model Driven Architecture. Defined by the MDA Guide Version 1.0.1, http://www.omg.org/mda/
• R.G.G.Cattell, D. K. Barry, M. Berler, J. Eastman, D. Jordan,
• C. Russell, O. Schadow, T. Stanienda, F. Velez, The object data standard: ODMG 3.0, Morgan Kaufman, 2000.
• Object Management Group: OMG C0RBA/I10P1M Specifications.http://www.omg.org/tcchnology/documents/corba_spec_eataIog.htm 2002
• J.W.Schmidt, F.Matthcs. The DBPL Project: Advances in Modular Database Programming. Information Systems 19(2): 121-140(1994)
• SML.NET: Functional programming on the .NET CLR, http://www.cl.cam.ac.uk/Research/TSG/SMLNET/
• K.Subieta. Theory and Construction of Object Query Languages, Publishers of the Polish-Japanese Institute of Information Technology, 2004 (in Polish)
• K.Subieta. Semantics of Query Languages for Network Databases, ACM Transactions on Database Systems, Vol. 10, No. 3, pp. 347- 394, 1985
• K.Subieta “Denotational Semantics of Query Languages”, Information Systems, Vol. 12, No. 1, 1987
• K.Subieta, M.Missala, K.Anacki “The LOQ1S System. Description and Programmer Manual”, Institute of Computer Science, Polish Academy of Sciences, Report 695, Warsaw, November 1990
• K.Subieta “LOQIS: The Programming System Having Database Capabilities”, Institute of Computer Science, Polish Academy of Sciences, Report 694, Warsaw, October 1990 (in Polish)
• K.Subieta “LOQIS: The Object-Oriented Database Programming System”, Proceedings of the 1st Intl. East/West Database Workshop on Next Generation Information System Technology, Springer LNCS 504, pp. 403-421, 1991
• K.Subieta, C.Bceri, F.Matthcs, J.W.Schmidt. A Stack-Based Approach to Query Languages. Proc. 2nd East-West Database Workshop, 1994, Springer Workshops in Computing, 1995
• K.Subieta, Y.Kambayashi, J.Leszczylowski “Procedures in Object- Oriented Query Languages”, Proc. ofVLDB,pp. 182-193, 1995