Optimizing the runtime processing of types in polymorphic logic programming languages

Gopalan Nadathur, Xiaochu Qi

Research output: Contribution to journalConference articlepeer-review

5 Scopus citations


The traditional purpose of types in programming languages of providing correctness assurances at compile time is increasingly being supplemented by a direct role for them in the computational process. In the context of typed logic programming, this is manifest in their effect on the unification operation. Their influence takes two different forms. First, in a situation where polymorphism is permitted, type information is needed to determine if different occurrences of the same name in fact denote an identical constant. Second, type information may determine the form of bindings for variables. When types are needed for the second purpose as in the case of higher-order unification, these have to be available with every variable and constant. However, in situations such as first-order and higher-order pattern unification, types have no impact on the variable binding process. As a consequence, type examination is needed in these situations only for the first of the two purposes described and even here a careful preprocessing can considerably reduce their run-time footprint. We develop a scheme for treating types in these contexts that exploits this observation. Under this scheme, type information is elided in most cases and is embedded into term structure when this is not entirely possible. Our approach obviates types when properties known as definitional genericity and type preservation are satisfied and has the advantage of working even when these conditions are violated.

Original languageEnglish (US)
Pages (from-to)110-124
Number of pages15
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3835 LNAI
StatePublished - Dec 1 2005
Event12th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, LPAR 2005 - Montego Bay, Jamaica
Duration: Dec 2 2005Dec 6 2005


Dive into the research topics of 'Optimizing the runtime processing of types in polymorphic logic programming languages'. Together they form a unique fingerprint.

Cite this