Article

Free access

Soft typing with conditional types

Authors:

Alexander Aiken,

Edward L. Wimmers,

T. K. LakshmanAuthors Info & Claims

POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 163 - 173

https://doi.org/10.1145/174675.177847

Published: 01 February 1994 Publication History

Abstract

We present a simple and powerful type inference method for dynamically typed languages where no type information is supplied by the user. Type inference is reduced to the problem of solvability of a system of type inclusion constraints over a type language that includes function types, constructor types, union, intersection, and recursive types, and conditional types. Conditional types enable us to analyze control flow using type inference, thus facilitating computation of accurate types. We demonstrate the power and practicality of the method with examples and performance results from an implementation.

References

[1]

AIKEN, A., AND MURPHY, B. Implementing regular tree expressions. In Proceedings of the 1991 Conference on Functional Programming Languages and Computer Architecture (Aug. 1991), pp. 427-447.

Digital Library

[2]

AIKEN, A., AND MURPHY, B. Static type inference in a dynamically typed language. In Eighteenth Annual ACM Symposium on Principles of Programming Languages (Jan. 1991), pp. 279-290.

Digital Library

[3]

AIKEN, A., AND WIMMERS, E. Type inclusion constraints and type inference. In Proceedings of the 1993 Conference on Functional Programming Languages and Computer Architecture (Copenhagen, Denmark, June 1993), pp. 31-41.

Digital Library

[4]

BACKUS, J. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Commun. A CM 21, 8 (Aug. 1978), 613- 641.

Digital Library

[5]

BACKUS, J., WILLIAMS, J. H., WIMMERS, E. L., LU- CAS, P., AND AIKEN, A. The FL language manual parts I and 2. Tech. Rep. RJ 7100 (67163), IBM, 1989.

[6]

CARTWRIGHT, R., AND FAGAN, M. Soft typing. In Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Implementation (June 1991), pp. 278-292.

Digital Library

[7]

DAMAS, L., AND MILNER, R. Principle type-schemes for functional programs. In Ninth Annual A CM Symposium on Principles of Programming Languages (1982), pp. 207-212.

Digital Library

[8]

FREEMAN, T., AND PFENNING, F. Refinement types for ML. In Proceedings of the A CM SIGPLAN '91 Conference on Programming Language Design and Implementation (June 1991), ACM Press, pp. 268-277.

Digital Library

[9]

FUH, Y., AND MISHRA, P. Type inference with subtypes. In Proceedings of the 1988 European Symposium on Programming (1988), pp. 94-114.

Digital Library

[10]

GOMARD, C. Partial type inference for untyped functional programs (extended abstract). In Proceedings of the 1990 A CM Conference on Lisp and Functional Programming (1990), pp. 282-287.

Digital Library

[11]

HEINTZE, N. Set Based Program Analysis. PhD thesis, Carnegie Mellon University, 1992.

Digital Library

[12]

HENGLEIN, F. Dynamic typing. In Proceedings of the 1992 A CM Conference on Lisp and Functional Programming (july 1992), pp. 205-215.

Digital Library

[13]

jONES, N. D., AND MUCHNICK, S. S. Flow analysis and optimization of LISP-like structures. In Sixth Annual ACM Symposium on Principles of Programming Languages (Jan. 1979), pp. 244-256.

Digital Library

[14]

KOZEN, D., PALSBERG, J., AND SCHWARTZBACH, M. I. Efficient inference of partial types. In Foundations of Computer Science (Oct. 1992), pp. 363-371.

Digital Library

[15]

MACQUEEN, D., PLOTKIN, G., AND SETHI, R. An ideal model for recursive polymophic types. In Eleventh Annual A CM Symposium on Principles of Programming Languages (Jan. 1984), pp. 165-174.

Digital Library

[16]

MILNER, R. A theory of type polymorphism in programming. J. Comput. Syst. Sci. 17 (1978), 348-375.

[17]

MISHRA, P., AND REDDY, U. Declaration-free type checking. In Proceedings of the Twelfth Annual A CM Symposium on the Principles of Programming Languages (1985), pp. 7-21.

Digital Library

[18]

MITCHELL, J. Coercion and type inference (summary). in Eleventh Annual ACM Symposium on Principles of Programming Languages (Jan. 1984), pp. 175-185.

Digital Library

[19]

REYNOLDS, J. C. Automatic Computation of Data Set Definitions. Information Processing 68. North-Holland, 1969, pp. 456-461.

[20]

SHIVERS, O. Control flow analysis in scheme. In Proceedings of the A CM SIGPLAN '88 Conference on Programming Language Design and Implementation (June 1988), pp. 164-174.

Digital Library

[21]

THATTE, S. Type inference with partial types. In Automata, Languages and Programming: 15th international Colloquium (July 1988), Springer-Verlag Lecture Notes in Computer Science,vol. 317, pp. 615-629.

[22]

TOFTE, M. Operational Semantics and Polymorphic Type Inference. PhD thesis, University of Edinburgh, 1987.

[23]

WANG, E., AND HrLFINGER, P. N. Analysis of recursive types in Lisp-like languages. In Proceedings of the 1992 A CM Conference on Lisp and Functional Programming (June 1992), pp. 216-225.

Digital Library

Cited By

Ramsay SWalpole C(2024)Ill-Typed Programs Don’t EvaluateProceedings of the ACM on Programming Languages10.1145/36329098:POPL(2010-2040)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632909
Greenman BDimoulas CFelleisen M(2023)Typed–Untyped Interactions: A Comparative AnalysisACM Transactions on Programming Languages and Systems10.1145/357983345:1(1-54)Online publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1145/3579833
Parreaux LChau C(2022)MLstruct: principal type inference in a Boolean algebra of structural typesProceedings of the ACM on Programming Languages10.1145/35633046:OOPSLA2(449-478)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563304
Show More Cited By

Index Terms

Soft typing with conditional types
1. Theory of computation
  1. Semantics and reasoning
    1. Program constructs
      1. Type structures

Recommendations

Gradual typing with union and intersection types

We propose a type system for functional languages with gradual types and set-theoretic type connectives and prove its soundness. In particular, we show how to lift the definition of the domain and result type of an application from non-gradual types to ...
Practical soft typing
Soft typing
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

Type systems are designed to prevent the improper use of program operations. They can be classified as either static or dynamic depending on when they detect type errors. Static type systems detect potential type errors at compile-time and prevent ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '94: Proceedings of the 21st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

February 1994

492 pages

ISBN:0897916360

DOI:10.1145/174675

Chairmen:
Hans-J. Boehm
Xerox PARC
,
Bernard Lang
INRIA Rocquencourt
,
Daniel Yellin
IBM Watson Research Center

Copyright © 1994 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 February 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

POPL94

Sponsor:

POPL94: 21st ACM SIGPLAN/SIGACT Symposium on Principles of Programming Languages

January 16 - 19, 1994

Oregon, Portland, USA

Acceptance Rates

POPL '94 Paper Acceptance Rate 39 of 173 submissions, 23%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

151
Total Citations
View Citations
711
Total Downloads

Downloads (Last 12 months)72
Downloads (Last 6 weeks)15

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ramsay SWalpole C(2024)Ill-Typed Programs Don’t EvaluateProceedings of the ACM on Programming Languages10.1145/36329098:POPL(2010-2040)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632909
Greenman BDimoulas CFelleisen M(2023)Typed–Untyped Interactions: A Comparative AnalysisACM Transactions on Programming Languages and Systems10.1145/357983345:1(1-54)Online publication date: 5-Mar-2023
https://dl.acm.org/doi/10.1145/3579833
Parreaux LChau C(2022)MLstruct: principal type inference in a Boolean algebra of structural typesProceedings of the ACM on Programming Languages10.1145/35633046:OOPSLA2(449-478)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563304
Kazerounian MFoster JMin B(2021)SimTyper: sound type inference for Ruby using type equality predictionProceedings of the ACM on Programming Languages10.1145/34854835:OOPSLA(1-27)Online publication date: 15-Oct-2021
https://dl.acm.org/doi/10.1145/3485483
Wallace SPapoutsaki ATan NGuo HHuang J(2021)Case Studies on the Motivation and Performance of Contributors Who Verify and Maintain In-Flux Tabular DatasetsProceedings of the ACM on Human-Computer Interaction10.1145/34795925:CSCW2(1-25)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3479592
Cai JWohn D(2021)After Violation But Before Sanction: Understanding Volunteer Moderators' Profiling Processes Toward Violators in Live Streaming CommunitiesProceedings of the ACM on Human-Computer Interaction10.1145/34795545:CSCW2(1-25)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3479554
BHUIYAN MWhitley HHorning MLee SMitra T(2021)Designing Transparency Cues in Online News Platforms to Promote Trust: Journalists' & Consumers' PerspectivesProceedings of the ACM on Human-Computer Interaction10.1145/34795395:CSCW2(1-31)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3479539
Cirstea HLermusiaux PMoreau P(2021)Static analysis of pattern-free propertiesProceedings of the 23rd International Symposium on Principles and Practice of Declarative Programming10.1145/3479394.3479404(1-13)Online publication date: 6-Sep-2021
https://dl.acm.org/doi/10.1145/3479394.3479404
Soubutts EAyobi AEardley RCater KO'Kane A(2021)Aging in Place Together: The Journey Towards Adoption and Acceptance of Stairlifts in Multi-Resident HomesProceedings of the ACM on Human-Computer Interaction10.1145/34760615:CSCW2(1-26)Online publication date: 18-Oct-2021
https://dl.acm.org/doi/10.1145/3476061
Abdulla PAtig MBouajjani AKumar KSaivasan P(2021)Deciding reachability under persistent x86-TSOProceedings of the ACM on Programming Languages10.1145/34343375:POPL(1-32)Online publication date: 4-Jan-2021
https://dl.acm.org/doi/10.1145/3434337
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents