Implementing polymorphic typing in a logic programming language

Keehang Kwon, Gopalan Nadathur, Debra Sue Wilson

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

Introducing types into a logic programming language leads to the need for typed unification within the computation model. In the presence of polymorphism and higher-order features, this aspect forces analysis of types at run-time. We propose extensions to the Warren Abstract Machine (WAM) that permit such analysis to be done with reasonable efficiency. Much information about the structures of types is present at compile-time, and we show that this information can be used to considerably reduce the work during execution. We illustrate our ideas in the context of a typed version of Prolog. We describe a modified representation for terms, new instructions and additional data areas that in conjunction with existing WAM structures suffice to implement this language. The nature of compiled code is illustrated through examples, and the kind of run-time overheads that are incurred for processing types is analyzed, especially in those cases where others have shown that type checking can be eliminated during execution. The ideas presented here are being used in an implementation of the higher-order language called λ Prolog.

Original languageEnglish (US)
Pages (from-to)25-42
Number of pages18
JournalComputer Languages
Volume20
Issue number1
DOIs
StatePublished - Mar 1994
Externally publishedYes

Keywords

  • implementation
  • logic programming
  • run-time type checking
  • typing

Fingerprint Dive into the research topics of 'Implementing polymorphic typing in a logic programming language'. Together they form a unique fingerprint.

Cite this