Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Well-Typed Logic Programs Are not Wrong
| |
|
Well-Typed Logic Programs Are not Wrong
Pierre Deransart6 and Jan-Georg Smaus7 
| (6) |
INRIA-Rocquencourt, BP105, 78153, Le Chesnay Cedex, France |
| (7) |
CWI, Kruislaan 413, 1098 SJ Amsterdam, The Netherlands |
Abstract
We consider prescriptive type systems for logic programs (as in Gödel or Mercury). In such systems, the typing is static,
but it guarantees an operational property: if a program is “well-typed”, then all derivations starting in a “well-typed” query
are again “well-typed”. This property has been called subject reduction. We show that this property can also be phrased as a property can also be phrased as a property of the proof-theoretic semantics of logic programs, thus abstracting from the usual operational (top-down) semantics. This proof-theoretic view
leads us to questioning a condition which is usually considered necessary for subject reduction, namely the head condition. It states that the head of each clause must have a type which is a variant (and not a proper instance) of the declared type.
We provide a more general condition, thus reestablishing a certain symmetry between heads and body atoms. The condition ensures
that in a derivation, the types of two unified terms are themselves unifiable. We discuss possible implications of this result.
We also discuss the relationship between the head condition and polymorphic recursion, a concept known in functional programming.
Acknowledgements We thank Franìcois Fages for interesting discussions. Jan-Georg Smaus was supported by an ERCIM fellowship.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|