Sound and decidable type inference for functional dependencies

Gregory J. Duck; Simon Peyton-Jones; Peter J. Stuckey; Martin Sulzmann

doi:10.1007/978-3-540-24725-8_5

Sound and decidable type inference for functional dependencies

Gregory J. Duck, Simon Peyton-Jones, Peter J. Stuckey, Martin Sulzmann

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

14 Citations (Scopus)

Abstract

Functional dependencies are a popular and useful extension to Haskell style type classes. In this paper, we give a reformulation of functional dependencies in terms of Constraint Handling Rules (CHRs). In previous work, CHRs have been employed for describing user-programmable type extensions in the context of Haskell style type classes. Here, we make use of CHRs to provide for the first time a concise result that under some sufficient conditions, functional dependencies allow for sound and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions.

Original language	English
Title of host publication	Programming Languages and Systems
Subtitle of host publication	13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings
Editors	David Schmidt
Place of Publication	Berlin Germany
Publisher	Springer
Pages	49-63
Number of pages	15
ISBN (Print)	3540213139
DOIs	https://doi.org/10.1007/978-3-540-24725-8_5
Publication status	Published - 1 Dec 2004
Externally published	Yes
Event	European Symposium on Programming 2004 - Barcelona, Spain Duration: 29 Mar 2004 → 2 Apr 2004 Conference number: 13th https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b96702 (Proceedings)

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2986
ISSN (Print)	0302-9743

Conference

Conference	European Symposium on Programming 2004
Abbreviated title	ESOP 2004
Country/Territory	Spain
City	Barcelona
Period	29/03/04 → 2/04/04
Internet address	https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b96702 (Proceedings)

Access to Document

10.1007/978-3-540-24725-8_5

Cite this

Duck, G. J., Peyton-Jones, S., Stuckey, P. J., & Sulzmann, M. (2004). Sound and decidable type inference for functional dependencies. In D. Schmidt (Ed.), Programming Languages and Systems: 13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings (pp. 49-63). (Lecture Notes in Computer Science; Vol. 2986). Springer. https://doi.org/10.1007/978-3-540-24725-8_5

Duck, Gregory J. ; Peyton-Jones, Simon ; Stuckey, Peter J. et al. / Sound and decidable type inference for functional dependencies. Programming Languages and Systems: 13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings. editor / David Schmidt. Berlin Germany : Springer, 2004. pp. 49-63 (Lecture Notes in Computer Science).

@inproceedings{b88a8c042d9c4a638a54a90f6623c343,

title = "Sound and decidable type inference for functional dependencies",

abstract = "Functional dependencies are a popular and useful extension to Haskell style type classes. In this paper, we give a reformulation of functional dependencies in terms of Constraint Handling Rules (CHRs). In previous work, CHRs have been employed for describing user-programmable type extensions in the context of Haskell style type classes. Here, we make use of CHRs to provide for the first time a concise result that under some sufficient conditions, functional dependencies allow for sound and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions.",

author = "Duck, {Gregory J.} and Simon Peyton-Jones and Stuckey, {Peter J.} and Martin Sulzmann",

year = "2004",

month = dec,

day = "1",

doi = "10.1007/978-3-540-24725-8_5",

language = "English",

isbn = "3540213139",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "49--63",

editor = "David Schmidt",

booktitle = "Programming Languages and Systems",

note = "European Symposium on Programming 2004, ESOP 2004 ; Conference date: 29-03-2004 Through 02-04-2004",

url = "https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/b96702",

}

Duck, GJ, Peyton-Jones, S, Stuckey, PJ & Sulzmann, M 2004, Sound and decidable type inference for functional dependencies. in D Schmidt (ed.), Programming Languages and Systems: 13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings. Lecture Notes in Computer Science, vol. 2986, Springer, Berlin Germany, pp. 49-63, European Symposium on Programming 2004, Barcelona, Spain, 29/03/04. https://doi.org/10.1007/978-3-540-24725-8_5

Sound and decidable type inference for functional dependencies. / Duck, Gregory J.; Peyton-Jones, Simon; Stuckey, Peter J. et al.
Programming Languages and Systems: 13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings. ed. / David Schmidt. Berlin Germany: Springer, 2004. p. 49-63 (Lecture Notes in Computer Science; Vol. 2986).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - Sound and decidable type inference for functional dependencies

AU - Duck, Gregory J.

AU - Peyton-Jones, Simon

AU - Stuckey, Peter J.

AU - Sulzmann, Martin

N1 - Conference code: 13th

PY - 2004/12/1

Y1 - 2004/12/1

N2 - Functional dependencies are a popular and useful extension to Haskell style type classes. In this paper, we give a reformulation of functional dependencies in terms of Constraint Handling Rules (CHRs). In previous work, CHRs have been employed for describing user-programmable type extensions in the context of Haskell style type classes. Here, we make use of CHRs to provide for the first time a concise result that under some sufficient conditions, functional dependencies allow for sound and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions.

AB - Functional dependencies are a popular and useful extension to Haskell style type classes. In this paper, we give a reformulation of functional dependencies in terms of Constraint Handling Rules (CHRs). In previous work, CHRs have been employed for describing user-programmable type extensions in the context of Haskell style type classes. Here, we make use of CHRs to provide for the first time a concise result that under some sufficient conditions, functional dependencies allow for sound and decidable type inference. The sufficient conditions imposed on functional dependencies can be very limiting. We show how to safely relax these conditions.

UR - http://www.scopus.com/inward/record.url?scp=35048853069&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-24725-8_5

DO - 10.1007/978-3-540-24725-8_5

M3 - Conference Paper

AN - SCOPUS:35048853069

SN - 3540213139

T3 - Lecture Notes in Computer Science

SP - 49

EP - 63

BT - Programming Languages and Systems

A2 - Schmidt, David

PB - Springer

CY - Berlin Germany

T2 - European Symposium on Programming 2004

Y2 - 29 March 2004 through 2 April 2004

ER -

Duck GJ, Peyton-Jones S, Stuckey PJ, Sulzmann M. Sound and decidable type inference for functional dependencies. In Schmidt D, editor, Programming Languages and Systems: 13th European Symposium on Programming, ESOP 2004 Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2004 Barcelona, Spain, March 29 – April 2, 2004 Proceedings. Berlin Germany: Springer. 2004. p. 49-63. (Lecture Notes in Computer Science). doi: 10.1007/978-3-540-24725-8_5

Sound and decidable type inference for functional dependencies

Abstract

Publication series

Conference

Access to Document

Other files and links

Cite this