计算机软件新技术-计算机科学国家重点实验联合学术研讨会

演讲人:Giuseppe Castagna

题目:Tackling parametric polymorphism for XML transformations

摘要:When working with XML data, there are several practical situations in which one would like to assign a parametric polymorphic type to a higher-order function. However, up to date, the solutions available are not completely satisfactory. The goal of our research is to define a type system with XML types, function types, and parametric polymorphism. Since XML types are regular tree languages, they can be encoded by union, intersection, negation, product, and recursive types. The problem can thus be rephrased as the definition of parametric polymorphism for recursive product and arrow type constructors in the presence of Boolean type combinators. In this talk I will first recall how to define a type system that includes products, arrows, and Boolean type combinators. Then I will explain why it is hard to extend it with parametric polymorphism. Finally I will hint at the avenues of research we are currently pursuing to solve this problem and the potential fallout on the study of parametricity.