Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 10,000 papers for “Type inference”

Local type inference

Haruo Hosoya, Benjamin C. Pierce, Haruo Hosoya et al. · 1998

A partial type inference technique should come with a simple and precise specification, so that users predict its behavior and understand the error messages it produces. Local type inference techniques attain this simplicity by inferring missing type information only from the types of adjacent syntax nodes, without using global mechanisms such as unification variables. The paper reports on our experience with programming in a full-featured programming language including higher-order polymorphism, subtyping, parametric datatypes, and local type inference. On the positive side, our experiments on several nontrivial examples confirm previous hopes for the practicality of the type inference method. On the negative side, some proposed extensions mitigating known expressiveness problems turn out to be unsatisfactory on close examination. 1

Cited by 0

Polymorphic Type Inference

Michael I. Schwartzbach · 1995

reluctantly sacrifice some good expressions. This happens because we require our type system to ensure that only good expressions are typable. However, since type checking must be decidable, it is clear that some good expressions are not typable. The following diagram illustrates this situation. . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . fi fi . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . Q Q T T ` ` \\Xi \\Xi . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . ( ( . . . . . . . . . . . . . . . . . . . . P P / / c c . . . . . . . . . . . . . . . . . . . . . . . . . S S \\Xi \\Xi . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . .. . .

Cited by 0

Natural type inference

Vlassi Pandi, Eirene · ERA · 2023

Recently, dynamic language users have started to recognize the value of types in their code. To fulfil this need, many popular dynamic languages have adopted extensions that support type annotations. A prominent example is that of TypeScript which offers a module system, classes, interfaces, and an optional type system on top of JavaScript. However, providing usable (not too verbose, or complex) types via traditional type inference is more challenging in optional type systems. Motivated by this, we redefine the goal of type inference for optionally typed languages as: infer the maximally natural and sound type, instead of the most general one. By the maximally natural and sound, we refer to a type that (1) is derivable in the type system, and (2) maximally reflects the intention of the programmer with respect to a learnt model. We formally devise a type inference problem that aids the inference of the maximally natural type. Towards this goal, our problem asks to combine information derived from two sources: (1) from algorithmic type systems using deductive logic-based techniques; and (2) from the source code text using inductive machine learning techniques. To tackle our formulated problem, we develop two frameworks that combine the two sources of information using mathematical optimization. In the first framework, we formulate the inference problem as a problem in numerical optimization. In the second framework, we map the inference problem into popular problems in discrete optimization: maximum satisfiability (MaxSAT) and Integer Linear Programming (ILP). Both frameworks are built to be consistent with information derived from the different sources. Moreover, through formal proofs, we validate the soundness and completeness of the developed framework for a core lambda-calculus with named types. To assess the efficacy of the developed frameworks, we implement them in a tool named Optyper that realizes natural type inference for TypeScript. We evaluate Optyperon TypeSript programs obtained from real world projects. By evaluating our theoretical frameworks we show that, in practice, the combination of logical and natural constraints yields a large improvement in performance over either kind of information individually. Further, we demonstrate that our frameworks out-perform state-of-the-art techniques in type inference to produce natural and sound types.

Cited by 0Open access

Type Inference Logics

Denis Carnier, François Pottier, Steven Keuchel · Proceedings of the ACM on Programming Languages · 2024

Type inference is essential for statically-typed languages such as OCaml and Haskell. It can be decomposed into two (possibly interleaved) phases: a generator converts programs to constraints; a solver decides whether a constraint is satisfiable. Elaboration, the task of decorating a program with explicit type annotations, can also be structured in this way. Unfortunately, most machine-checked implementations of type inference do not follow this phase-separated, constraint-based approach. Those that do are rarely executable, lack effectful abstractions, and do not include elaboration. To close the gap between common practice in real-world implementations and mechanizations inside proof assistants, we propose an approach that enables modular reasoning about monadic constraint generation in the presence of elaboration. Our approach includes a domain-specific base logic for reasoning about metavariables and a program logic that allows us to reason abstractly about the meaning of constraints. To evaluate it, we report on a machine-checked implementation of our techniques inside the Coq proof assistant. As a case study, we verify both soundness and completeness for three elaborating type inferencers for the simply typed <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"> <mml:mi>λ</mml:mi> </mml:math> -calculus with Booleans. Our results are the first demonstration that type inference algorithms can be verified in the same form as they are implemented in practice: in an imperative style, modularly decomposed into constraint generation and solving, and delivering elaborated terms to the remainder of the compiler chain.

Cited by 3Open access

Type inference generalises type checking

Lunjin Lu, Andy King · 2002

Abstract. This paper presents a backward type analysis for logic programs. Given type signatures for a collection of selected predicates such as builtin or library predicates, the analysis infers type signatures for other predicates such that the execution of any query satisfying the inferred type signatures will not violate the type signatures for the selected predicates. Thus, the backward type analysis generalises type checking in which the programmer manually specifies type signatures for all predicates that are checked for consistency by a type checker. 1

Cited by 0

Type Inference with Generic Type Schemes

Andreas Kind · 2007

this paper is to investigate the usefulness of generic type schemes for type inference in polymorphic programming languages. In particular, we are not interested in types of variables, but in types of variable references [11]. A variable may have different types in different program branches, e.g. in the term if (nump x) x x, variable x is numerical in the then-branch, but guaranteed to be non-numerical in the else-branch. Thus, there is a need for an adequate type representation for predicate functions like nump.

Cited by 0

Type inference in applied type system

Chiyan Chen, Hongwei Xi · 2006

Programming is error-prone. Type systems have been demonstrated to be a powerful tool for the construction of reliable programs. Applied Type System ( ATS ) is a recently proposed framework to facilitate the design and formalization of advanced type systems. In ATS , many advanced language features can be naturally expressed and various commonly studied type systems can be readily formalized. In particular, ATS can provide support for dependent types in the presence of realistic language features such as general recursion, effects (references and exceptions), input/output, etc. However, given the expressiveness and complexity of ATS , it is a challenging task to design a practical programming language based on ATS as we need to provide succinct and convenient concrete syntax as well as to support decidable and effective type-checking. In this context, the problem of type inference arises naturally in ATS . This thesis focuses on developing solutions to the problem of type inference in ATS . We study λATS, which is a generic applied type system in ATS , as an internal language, and then develop ATS as an external language for λATS to support practical programming. We present a set of rules for elaborating programs from ATS to λATS, which is often called elaboration. In particular, we identify the difficulties resulting from the need for directly supporting existential types, and then develop novel elaboration techniques to properly address these difficulties. We establish the soundness of the elaboration, that is, a given program in ATS and its elaboration in λATS are guaranteed to have the same dynamic semantics, which constitutes a major technical contribution of this thesis. We expect that this work will not only offer some guidelines for implementing type inference algorithms for type systems based on ATS , but also provide a solid basis for justifying the soundness of such algorithms.

Cited by 2

Type inclusion constraints and type inference

Alex Aiken, Edward L. Wimmers · 1993

Article Free Access Share on Type inclusion constraints and type inference Authors: Alexander Aiken View Profile , Edward L. Wimmers View Profile Authors Info & Claims FPCA '93: Proceedings of the conference on Functional programming languages and computer architectureJuly 1993 Pages 31–41https://doi.org/10.1145/165180.165188Published:01 July 1993Publication History 180citation992DownloadsMetricsTotal Citations180Total Downloads992Last 12 Months115Last 6 weeks29 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Cited by 260

Type Inference for MLj

Bruce Mcadam Andrew, Andrew Kennedy, Nick Benton · 2000

MLj is an extension of the Standard ML language which allows interoperation with Java. It has a type system which combines ML&amp;apos;s parametric polymorphism and type inference with Java&amp;apos;s subtyping (class hierarchy) and arbitrary overloading of methods. In this paper, we discuss some of the difficulties in implementing type inference for MLj and outline our progress on the implementation. In particular we note that MLj programs do not necessarily have principal type schemes and that a branching constraint solver is required.

Cited by 0

Type Inference Logics - Artifact

Carnier, Denis, Pottier, François, Keuchel, Steven · Zenodo (CERN European Organization for Nuclear Research) · 2024

This release accompanies our paper Type Inference Logics presented at OOPSLA24. The sources file contains a `README.md` for the source code with instructions on how to get started. The image file contains a Docker image compiled for AMD64 with all the necessary dependencies to check the code with the Coq proof assistant and GHC. Paper abstract: Type inference is essential for statically-typed languages such as OCaml and Haskell. It can be decomposed into two (possibly interleaved) phases: a generator converts programs to constraints; a solver decides whether a constraint is satisfiable. Elaboration, the task of decorating a program with explicit type annotations, can also be structured in this way. Unfortunately, most machine-checked implementations of type inference do not follow this phase-separated, constraint-based approach. Those that do are rarely executable, lack effectful abstractions, and do not include elaboration. To close the gap between common practice in real-world implementations and mechanizations inside proof assistants, we propose an approach that enables modular reasoning about monadic constraint generation in the presence of elaboration. Our approach includes a domain-specific base logic for reasoning about metavariables, and a program logic that allows us to reason abstractly about the meaning of constraints. To evaluate it, we report on a machine-checked implementation of our techniques inside the Coq proof assistant. As a case study, we verify both soundness and completeness for three type inferencers for the simply typed 𝜆-calculus with Booleans. Our results are the first demonstration that type inference algorithms can be verified in the same form as they are implemented in practice: in an imperative style, modularly decomposed into constraint generation and solving, and delivering elaborated terms to the remainder of the compiler chain. Acknowledgements This research is partially funded by the Research Fund KU Leuven, the Cybersecurity Research Program Flanders, and by ERC grant (UniversalContracts, 101040088). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.

Cited by 0Open access

Gradual liquid type inference

Niki Vazou, Éric Tanter, David Van Horn · Proceedings of the ACM on Programming Languages · 2018

Refinement types allow for lightweight program verification by enriching types with logical predicates. Liquid typing provides a decidable refinement inference mechanism that is convenient but subject to two major issues: (1) inference is global and requires top-level annotations, making it unsuitable for inference of modular code components and prohibiting its applicability to library code, and (2) inference failure results in obscure error messages. These difficulties seriously hamper the migration of existing code to use refinements. This paper shows that gradual liquid type inference –a novel combination of liquid inference and gradual refinement types–addresses both issues. Gradual refinement types, which support imprecise predicates that are optimistically interpreted, can be used in argument positions to constrain liquid inference so that the global inference process effectively infers modular specifications usable for library components. Dually, when gradual refinements appear as the result of inference, they signal an inconsistency in the use of static refinements. Because liquid refinements are drawn from a finite set of predicates, in gradual liquid type inference we can enumerate the textitsafe concretizations of each imprecise refinement, i.e., the static refinements that justify why a program is gradually well-typed. This enumeration is useful for static liquid type error explanation, since the safe concretizations exhibit all the potential inconsistencies that lead to static type errors. We develop the theory of gradual liquid type inference and explore its pragmatics in the setting of Liquid Haskell. To demonstrate the utility of our approach, we develop an interactive tool, GuiLT, for gradual liquid type inference in Liquid Haskell that both infers modular types and explores safe concretizations of gradual refinements. We report on the use of GuiLT for error reporting and discuss a case study on the migration of three commonly-used Haskell list manipulation libraries into Liquid Haskell.

Cited by 6Open access