结构数据处理语言的参数多态化研究

信息共享对各行各业越来越重要，其基础是信息标准化和规范化。可扩展标记语言（XML）能简单、灵活地描述各种带结构的数据，成为数据交换的事实标准。为了更好的处理，近年来出现了不少静态类型化XML处理语言，但大多数语言都缺少参数多态化或者仅提供有限的支持，限制了它们的实用性。XML处理也需要多态化。申请人及其合作者在近期的工作中首次提出了正则树类型的多态语义子类型关系的定义，并设计了多态语言的基本框架。本项目拟在已有的工作基础上继续研究结构数据处理语言的参数多态化。从理论上本项目将研究多态类型系统的凸模型，探讨参数化新的语义解释。从实用上本项目将扩展语言的表达式以提高语言的处理能力，提出无需替换的子类型判定算法以提高实际效率，和设计实用的可终止的类型推导算法以增强结果类型的精确度。项目的研究不仅有望能提高XML处理的效率、方便性和安全性，而且对结构数据的处理技术和程序设计语言的研究有积极意义。

Information sharing is more and more important to the various walks of life. Its basis is information standardization and normalization. Extensible Markup Language (XML) is a simple but flexible way to describe structured data, and thus becomes a current standard format for exchanging data. For a better processing, recently there emerge many statically typed XML processing languages. However, most of these languages lack parametric polymorphism or present it in a limited form, which limits their usefulness. XML processing also needs polymorphism. The applicant and his partners in their recent work have firstly proposed the definition of a polymorphic semantic subtyping relation and designed the basic framework of a polymorphic language. Based on this original work, this project will continue to study parametric polymorphism for structured data processing languages. Theoretically, we will investigate the convex model of the polymorphic type system and find a new semantic interpretation for parametricity. Practically, we will extend the expressions to improve the processing power of the polymorphic language, propose a subtyping algorithm without substitutions to improve the practical efficiency, and design a practical and terminable type inference algorithm to improve the precision of the result type. This work not only can improve efficiency, convenience and security for XML processing, but also has a positive meaning for the processing technique of structured data and the research on programming languages.