Logic in Computer Science (LICS 2003)

Paper: A Constraint-Based Presentation and Generalization of Rows (at LICS 2003)

Authors: François Pottier

Abstract

We study the combination of possibly conditional non-structural subtyping constraints with rows. We give a new presentation of rows, where row terms disappear; instead, we annotate constraints with filters. We argue that, in the presence of subtyping, this approach is simpler and more general. In the case where filters are finite or cofinite sets of row labels, we give a constraint solving algorithm whose complexity is O(nm log m), where is the size of the constraint and m is the number of row labels that appear in it. We point out that this allows efficient type inference for record concatenation. Furthermore, by varying the nature of filters, we obtain several natural generalizations of rows.

BibTeX

  @InProceedings{Pottier-AConstraintBasedPre,
    author = 	 {François Pottier},
    title = 	 {A Constraint-Based Presentation and Generalization of Rows},
    booktitle =  {Proceedings of the Eighteenth Annual IEEE Symp. on Logic in Computer Science, {LICS} 2003},
    year =	 2003,
    editor =	 {Phokion G. Kolaitis},
    month =	 {June}, 
    pages =      {331--},
    location =   {Ottawa, Canada}, 
    publisher =	 {IEEE Computer Society Press}
  }