Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Automatic Inference of Loop Complexity Through Polynomial Interpolation Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Type Inference for GADTs and Anti-unification

verfasst von : Adelaine Gelain, Cristiano Vasconcellos, Carlos Camarão, Rodrigo Ribeiro

Erschienen in: Programming Languages

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Nowadays the support of generalized algebraic data types (GADTs) in extensions of Haskell allows functions defined over GADTs to be written without the need for type annotations in some cases and requires type annotations in other cases. In this paper we present a type inference algorithm for GADTs that is based on a closed-world approach to overloading and uses anti-unification and constraint-set satisfiability to infer the relationship between the types of function arguments and result. Through some examples, we show how the proposed algorithm allows more functions defined over GADTs to be written without the need for type annotations.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Automatic Inference of Loop Complexity Through Polynomial Interpolation
Nächstes Kapitel Preserving Lexical Scoping When Dynamically Embedding Languages
Literatur
1.
Camarão, C., Figueiredo, L.: Type inference for overloading without restrictions, declarations or annotations. In: Middeldorp, A., Sato, T. (eds.) FLOPS 1999. LNCS, vol. 1722, pp. 37–52. Springer, Heidelberg (1999) CrossRef
2.
Camarão, C., Figueiredo, L., Vasconcellos, C.: Constraint-set Satisfiability for Overloading. In: Proceedings of the 6th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming, pp. 67–77. ACM (2004)
3.
Chang, C.C., Keisler, H.J.: Model Theory: Dover Books on Mathematics, 3rd edn. North-Holland Press, New York (2012)
4.
Demoen, B., de la Banda, M.G., Stuckey, P.J.: Type Constraint Solving for Parametric and Ad-hoc Polymorphism. In: Proceedings of the 22nd Australasian Computer Science Conference (1999)
5.
Jones, M.: Simplifying and Improving Qualified Types. In: Proceedings of ACM Conference on Functional Programming and Computer Architecture, FPCA 1995, pp. 160–169 (1995)
6.
Jones, S.P., Vytiniotis, D., Weirich, S., Washburn, G.: Simple unification-based type inference for GADTs. SIGPLAN Not. 41(9), 50–61 (2006)CrossRef
7.
8.
Lin, C.K.: Practical type inference for the GADT type system. Ph.D. thesis, Portland State University, Portland, OR, USA (2010)
9.
Lin, C.K., Sheard, T.: Pointwise generalized algebraic data types. In: Proceedings of the 5th ACM SIGPLAN Workshop on Types in Language Design and Implementation, TLDI 2010, pp. 51–62. ACM, New York (2010)
10.
Plotkin, G.D.: A note on inductive generalisation. Mach. intell. 5(1), 153–163 (1970)MATH
11.
Plotkin, G.D.: A further note on inductive generalisation. Mach. Intell. 6, 101–124 (1971)MATH
12.
Pottier, F., Régis-Gianas, Y.: Stratified type inference for generalized algebraic data types. SIGPLAN Not. 41(1), 232–244 (2006)CrossRef
13.
Ribeiro, R., Camarão, C.: Ambiguity and context-dependent overloading. J. Braz. Comput. Soc. 19(3), 313–324 (2013)MathSciNetCrossRef
14.
Ribeiro, R., Camarão, C., Figueiredo, L.: Terminating constraint set satisfiability and simplification algorithms for context-dependent overloading. J. Braz. Comput. Soc. 19(4), 423–432 (2013)MathSciNetCrossRef
15.
Schrijvers, T., Jones, S.P., Sulzmann, M., Vytiniotis, D.: Complete and decidable type inference for GADTs. SIGPLAN Not. 44(9), 341–352 (2009)CrossRefMATH
16.
Smith, G.: Polymorphic type inference for languages with overloading and subtyping. Ph.D. thesis, Cornell University (1991)
17.
Smith, G.: Principal type schemes for functional programs with overloading and subtyping. Sci. Comput. Program. 23(2–3), 197–226 (1994)MathSciNetCrossRefMATH
18.
Stuckey, P., Sulzmann, M.: A Theory of overloading. In: Proceedings of the 7th ACM International Conference on Functional Programming, pp. 167–178 (2002)
19.
Sulzmann, M., Schrijvers, T., Stuckey, P.J.: Type Inference for GADTs via Herbrand Constraint Abduction (2008)
20.
Team, G., et al.: The Glorious Glasgow Haskell Compilation System User’s Guide, Version 7.10.1 (2015)
21.
Vasconcellos, C.: Inferência de tipos com suporte para sobrecarga baseada no sistema CT. Ph.D. thesis, Universidade Federal de Minas Gerais, Minas Gerais, Brasil (2004)
22.
Vytiniotis, D., Jones, S.P., Schrijvers, T., Sulzmann, M.: OutsideIn(X): modular type inference with local assumptions. J. Funct. Program. 21(4–5), 333–412 (2011)MathSciNetCrossRefMATH
Metadaten
Titel
Type Inference for GADTs and Anti-unification
verfasst von
Adelaine Gelain
Cristiano Vasconcellos
Carlos Camarão
Rodrigo Ribeiro
Copyright-Jahr
2015
Buch
Programming Languages

Print ISBN: 978-3-319-24011-4

Electronic ISBN: 978-3-319-24012-1

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-24012-1_2