From Monomorphic to Polymorphic Well-Typings and Beyond

Tom Schrijvers, Maurice Bruynooghe, John Patrick Gallagher

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

Type information has many applications; it can e.g. be used in optimized compilation, termination analysis and error detection. However, logic programs are typically untyped. A well-typed program has the property that it behaves identically on well-typed goals with or without type checking. Hence the automatic inference of a well-typing is worthwhile. Existing inferences are either cheap and inaccurate, or accurate and expensive. By giving up the requirement that all calls to a predicate have types that are instances of a unique polymorphic type but instead
allowing multiple polymorphic typings for the same predicate, we obtain a novel strongly-connected-component-based analysis that provides a good compromise between accuracy and computational cost.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)152-167
Number of pages16
ISSN0302-9743
Publication statusPublished - 2009
EventLogic-Based Program Synthesis and Transformation, LOPSTR 2008 - Valencia, Spain
Duration: 17 Jul 200818 Jul 2008
Conference number: 18

Conference

ConferenceLogic-Based Program Synthesis and Transformation, LOPSTR 2008
Number18
CountrySpain
CityValencia
Period17/07/200818/07/2008

Keywords

  • type inference
  • logic programming

Cite this

@inproceedings{6c3bee6016cc11de8600000ea68e967b,
title = "From Monomorphic to Polymorphic Well-Typings and Beyond",
abstract = "Type information has many applications; it can e.g. be used in optimized compilation, termination analysis and error detection. However, logic programs are typically untyped. A well-typed program has the property that it behaves identically on well-typed goals with or without type checking. Hence the automatic inference of a well-typing is worthwhile. Existing inferences are either cheap and inaccurate, or accurate and expensive. By giving up the requirement that all calls to a predicate have types that are instances of a unique polymorphic type but instead allowing multiple polymorphic typings for the same predicate, we obtain a novel strongly-connected-component-based analysis that provides a good compromise between accuracy and computational cost.",
keywords = "type inference, logic programming",
author = "Tom Schrijvers and Maurice Bruynooghe and Gallagher, {John Patrick}",
note = "Volumne: 5438",
year = "2009",
language = "English",
pages = "152--167",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Physica-Verlag",

}

From Monomorphic to Polymorphic Well-Typings and Beyond. / Schrijvers, Tom; Bruynooghe, Maurice; Gallagher, John Patrick.

In: Lecture Notes in Computer Science, 2009, p. 152-167.

Research output: Contribution to journalConference articleResearchpeer-review

TY - GEN

T1 - From Monomorphic to Polymorphic Well-Typings and Beyond

AU - Schrijvers, Tom

AU - Bruynooghe, Maurice

AU - Gallagher, John Patrick

N1 - Volumne: 5438

PY - 2009

Y1 - 2009

N2 - Type information has many applications; it can e.g. be used in optimized compilation, termination analysis and error detection. However, logic programs are typically untyped. A well-typed program has the property that it behaves identically on well-typed goals with or without type checking. Hence the automatic inference of a well-typing is worthwhile. Existing inferences are either cheap and inaccurate, or accurate and expensive. By giving up the requirement that all calls to a predicate have types that are instances of a unique polymorphic type but instead allowing multiple polymorphic typings for the same predicate, we obtain a novel strongly-connected-component-based analysis that provides a good compromise between accuracy and computational cost.

AB - Type information has many applications; it can e.g. be used in optimized compilation, termination analysis and error detection. However, logic programs are typically untyped. A well-typed program has the property that it behaves identically on well-typed goals with or without type checking. Hence the automatic inference of a well-typing is worthwhile. Existing inferences are either cheap and inaccurate, or accurate and expensive. By giving up the requirement that all calls to a predicate have types that are instances of a unique polymorphic type but instead allowing multiple polymorphic typings for the same predicate, we obtain a novel strongly-connected-component-based analysis that provides a good compromise between accuracy and computational cost.

KW - type inference

KW - logic programming

M3 - Conference article

SP - 152

EP - 167

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -