Article

Free access

On the complexity of type inference with coercion

Authors:

FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture

Pages 293 - 298

https://doi.org/10.1145/99370.99394

Published: 01 November 1989 Publication History

PDF eReader

References

[1]

CaxdeUi, L. "Basic Polymorphic Typechecking,~ Polymorphism Newsletter ~,1 (Jan, 1985). Also appeared as Computing Sdence Tech. Rep. 119, AT~T Bell Laboratories, Murray Hill, NJ.

Google Scholar

[2]

Clement, D., Despeyroux, J., Despeyroux, T., and Kahn, G. "A Simple Applicative Language: Mini-ML' Proc. 1986 A CM Syrup. on Lizp and Functional Programming, 13-27.

Digital Library

Google Scholar

[3]

Fuh, Y.-C., and Mizhra, P. ~Type Inference with Subtypes,' Proc. European Symposium on Programming (19- 88), 94-114.

Digital Library

Google Scholar

[4]

Hindley, R. "The Principal Type-Scheme of an Object in Combinatory Logic," Trans. Am. Math. Soc. 146 (1969) 29-60.

Google Scholar

[5]

Jategaonkar, L.A., and Mitchell, J.C. XML with Extended Pattern Matching and Subtypes," Proc. 1988 A CM Conf. on Lisp and Functional Programming, 198- 211

Digital Library

Google Scholar

[6]

Kanellakis, P.C., and Mitchell, J.C. ~Polymorphic Unification and ML Typing" Conf. Rec. 16th Ann. A CM Syrup. on Principles of Programming Languages (1989), 105-115.

Digital Library

Google Scholar

[7]

Milner, R. "A Theory of Type Polymorphism in Programming,' J. Comp. E4 Sys. Sci. 17 (1978), 348-375.

Google Scholar

[8]

Mitchell, J.C. ~Coercion and Type Inference (summary)," Conf. Rec. 11th Ann. ACM Syrup. on Principles of Programming Languages (1984), 175-185.

Digital Library

Google Scholar

Cited By

View all

Schöpp UXu C(2022)Inferring Region Types via an Abstract Notion of Environment TransformationProgramming Languages and Systems10.1007/978-3-031-21037-2_3(45-64)Online publication date: 25-Nov-2022
https://doi.org/10.1007/978-3-031-21037-2_3
Blankertz BWeiermann A(2017)How to characterize provably total functionsGödel '9610.1017/9781316716939.015(205-213)Online publication date: 23-Mar-2017
https://doi.org/10.1017/9781316716939.015
Traytel DBerghofer SNipkow T(2011)Extending hindley-milner type inference with coercive structural subtypingProceedings of the 9th Asian conference on Programming Languages and Systems10.1007/978-3-642-25318-8_10(89-104)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25318-8_10
Show More Cited By

Index Terms

On the complexity of type inference with coercion
1. Mathematics of computing
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness
  2. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Coercion and type inference
POPL '84: Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

A simple semantic model of automatic coercion is proposed. This model is used to explain four rules for inferring polymorphic types and providing automatic coercions between types. With the addition of a fifth rule, the rules become semantically ...
On the power of coercion abstraction
POPL '12

Erasable coercions in System F-eta, also known as retyping functions, are well-typed eta-expansions of the identity. They may change the type of terms without changing their behavior and can thus be erased before reduction. Coercions in F-eta can model ...
On the power of coercion abstraction
POPL '12: Proceedings of the 39th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Erasable coercions in System F-eta, also known as retyping functions, are well-typed eta-expansions of the identity. They may change the type of terms without changing their behavior and can thus be erased before reduction. Coercions in F-eta can model ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture

November 1989

395 pages

ISBN:0897913280

DOI:10.1145/99370

Chairman:
Joseph E. Stoy

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

FPCA89

Sponsor:

SIGPLAN
IFIP WG 2.8
SIGARCH

FPCA89: The International Conference on Functional Programming Languages & Computer Architectures

September 11 - 13, 1989

Imperial College, London, United Kingdom

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
332
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)5

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Schöpp UXu C(2022)Inferring Region Types via an Abstract Notion of Environment TransformationProgramming Languages and Systems10.1007/978-3-031-21037-2_3(45-64)Online publication date: 25-Nov-2022
https://doi.org/10.1007/978-3-031-21037-2_3
Blankertz BWeiermann A(2017)How to characterize provably total functionsGödel '9610.1017/9781316716939.015(205-213)Online publication date: 23-Mar-2017
https://doi.org/10.1017/9781316716939.015
Traytel DBerghofer SNipkow T(2011)Extending hindley-milner type inference with coercive structural subtypingProceedings of the 9th Asian conference on Programming Languages and Systems10.1007/978-3-642-25318-8_10(89-104)Online publication date: 5-Dec-2011
https://dl.acm.org/doi/10.1007/978-3-642-25318-8_10
Hell PNešetřil J(2008)SurveyComputer Science Review10.1016/j.cosrev.2008.10.0032:3(143-163)Online publication date: 1-Dec-2008
https://dl.acm.org/doi/10.1016/j.cosrev.2008.10.003
Hell P(2006)From Graph Colouring to Constraint Satisfaction: There and Back AgainTopics in Discrete Mathematics10.1007/3-540-33700-8_20(407-432)Online publication date: 2006
https://doi.org/10.1007/3-540-33700-8_20
Volpano DSmith G(2005)A type-based approach to program securityTAPSOFT '97: Theory and Practice of Software Development10.1007/BFb0030629(607-621)Online publication date: 20-Jun-2005
https://doi.org/10.1007/BFb0030629
Wright D(2005)A new technique for strictness analysisTAPSOFT '9110.1007/3540539816_70(235-258)Online publication date: 6-Jul-2005
https://doi.org/10.1007/3540539816_70
Benke M(2005)Efficient type reconstruction in the presence of inheritanceMathematical Foundations of Computer Science 199310.1007/3-540-57182-5_19(272-280)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57182-5_19
Tiuryn JWand M(2005)Type reconstruction with recursive types and atomic subtypingTAPSOFT'93: Theory and Practice of Software Development10.1007/3-540-56610-4_98(686-701)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-56610-4_98
Smith G(2005)Polymorphic type inference with overloading and subtypingTAPSOFT'93: Theory and Practice of Software Development10.1007/3-540-56610-4_97(671-685)Online publication date: 28-May-2005
https://doi.org/10.1007/3-540-56610-4_97
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Coercion and type inference

On the power of coercion abstraction

On the power of coercion abstraction