The Experts below are selected from a list of 51075 Experts worldwide ranked by ideXlab platform
Jens Palsberg - One of the best experts on this subject based on the ideXlab platform.
-
Type Inference for record concatenation and subtyping
Information and Computation, 2004Co-Authors: Jens Palsberg, Tian ZhaoAbstract:Record concatenation, multiple inheritance, and multiple-object cloning are closely related and part of various language designs. For example, in Cardelli's unTyped Obliq language, a new object can be constructed from several existing objects by cloning followed by concatenation; an error is given in case of field name conflicts. Type systems for record concatenation have been studied by Wand, Harper and Pierce, Remy, and others; and Type Inference for the combination of record concatenation and subtyping has been studied by Sulzmann and by Pottier. In this paper we present a Type Inference algorithm for record concatenation, subtyping, and recursive Types. Our example language is the Abadi-Cardelli object calculus extended with a concatenation operator. Our algorithm enables Type checking of Obliq programs without changing the programs at all. We prove that the Type Inference problem is NP-complete.
-
Type Inference with non-structural subtyping
Formal Aspects of Computing, 1997Co-Authors: Jens Palsberg, Mitchell Wand, Patrick O'keefeAbstract:We present an O(n^3) time Type Inference algorithm for a Type system with a largest Type Τ , a smallest Type ⊥, and the usual ordering between function Types. The algorithm infers Type annotations of least shape, and it works equally well for recursive Types. For the problem of typability, our algorithm is simpler than the one of Kozen, Palsberg, and Schwartzbach for Type Inference without ⊥. This may be surprising, especially because the system with ⊥ is strictly more powerful.
-
Type Inference with SelfType
BRICS Report Series, 1995Co-Authors: Jens PalsbergAbstract:The metavariable self is fundamental in object-oriented languages.<br />Typing self in the presence of inheritance has been studied by Abadi<br />and Cardelli, Bruce, and others. A key concept in these developments<br />is the notion of selfType, which enables flexible Type annotations that<br />are impossible with recursive Types and subtyping. Bruce et al. demonstrated<br />that, for the language TOOPLE, Type checking is decidable.<br />Open until now is the problem of Type Inference with selfType.<br />In this paper we present a Type Inference algorithm for a Type<br />system with selfType, recursive Types, and subtyping. The example<br />language is the object calculus of Abadi and Cardelli, and the Type<br />Inference algorithm runs in nondeterministic polynomial time.
-
Type Inference with Non-structural Subtyping
BRICS Report Series, 1995Co-Authors: Jens Palsberg, Mitchell Wand, Patrick O'keefeAbstract:We present an O(n^3) time Type Inference algorithm for a Type<br />system with a largest Type !, a smallest Type ?, and the usual ordering<br />between function Types. The algorithm infers Type annotations of<br />minimal size, and it works equally well for recursive Types. For the<br />problem of typability, our algorithm is simpler than the one of Kozen,<br />Palsberg, and Schwartzbach for Type Inference without ?. This may<br />be surprising, especially because the system with ? is strictly more<br />powerful.
-
Safety Analysis versus Type Inference
Information and Computation, 1995Co-Authors: Jens Palsberg, Michael I. SchwartzbachAbstract:Safety analysis is an algorithm for determining if a term in an unTyped lambda calculus with constants is safe, i.e., if it does not cause an error during evaluation. This ambition is also shared by algorithms for Type Inference. Safety analysis and Type Inference are based on rather different perspectives, however. Safety analysis is global in that it can only analyze a complete program. In contrast, Type Inference is local in that it can analyze pieces of a program in isolation. In this paper we prove that safety analysis is sound, relative to both a strict and a lazy operational semantics. We also prove that safety analysis accepts strictly more safe lambda terms than does Type Inference for simple Types. The latter result demonstrates that global program analyses can be more precise than local ones.
Michael I. Schwartzbach - One of the best experts on this subject based on the ideXlab platform.
-
Type Inference of Turbo Pascal
BRICS Report Series, 1995Co-Authors: Ole Ildsgaard Hougaard, Michael I. Schwartzbach, Hosein AskariAbstract:Type Inference is generally thought of as being an exclusive property of the functional programming paradigm. We argue that such a feature may be of significant benefit for also standard imperative languages. We present a working tool (available by WWW) providing these benefits for a full version of Turbo Pascal. It has the form of a preprocessor that analyzes programs in which the Type annotations are only partial or even absent. The resulting program has full Type annotations, will be accepted by the standard Turbo Pascal compiler, and has polymorphic use of procedures resolved by means of code expansion. Keywords: imperative languages, Type Inference.
-
Safety Analysis versus Type Inference
Information and Computation, 1995Co-Authors: Jens Palsberg, Michael I. SchwartzbachAbstract:Safety analysis is an algorithm for determining if a term in an unTyped lambda calculus with constants is safe, i.e., if it does not cause an error during evaluation. This ambition is also shared by algorithms for Type Inference. Safety analysis and Type Inference are based on rather different perspectives, however. Safety analysis is global in that it can only analyze a complete program. In contrast, Type Inference is local in that it can analyze pieces of a program in isolation. In this paper we prove that safety analysis is sound, relative to both a strict and a lazy operational semantics. We also prove that safety analysis accepts strictly more safe lambda terms than does Type Inference for simple Types. The latter result demonstrates that global program analyses can be more precise than local ones.
-
Safety Analysis versus Type Inference
DAIMI Report Series, 1992Co-Authors: Jens Palsberg, Michael I. SchwartzbachAbstract:<p>Safety analysis is an algorithm for determining if a term in the unTyped lambda calculus with constants is <em>safe</em>, i.e., if it does not cause an error during evaluation. This ambition is also shared by algorithms for Type Inference. Safety analysis and Type Inference are based on rather different perspectives, however. Safety analysis is based on closure analysis, whereas Type Inference attempts to assign a Type to all subterms.</p><p>In this paper we prove that safety analysis is <em>sound</em>, relative to both a strict and a lazy operational semantics, and <em>superior</em> to Type Inference, in the sense that it accepts strictly more safe lambda terms.</p><p>The latter result may indicate the relative potentials of static program analyses based on respectively closure analysis and Type Inference.</p>
-
Making Type Inference Practical
DAIMI Report Series, 1992Co-Authors: Nicholas Oxhøj, Jens Palsberg, Michael I. SchwartzbachAbstract:We present the implementation of a Type Inference algorithm for unTyped object-oriented programs with inheritance, assignments, and late binding.The algorithm significantly improves our previous one, presented at OOPSLA'91, since it can handle collection classes, such as {\bf List}, in a useful way. Also, the complexity has been dramatically improved, from exponential time to low polynomial time. The implementation uses the techniques of incremental graph construction and constraint template instantiation to avoid representing intermediate results, doing superfluous work, and recomputing Type information. Experiments indicate that the implementation Type checks as much as 100 lines pr. second. This results in a mature product, on which a number of tools can be based, for example a safety tool, an image compression tool, a code optimization tool, and an annotation tool. This may make Type Inference for object-oriented languages practical.
-
TAPSOFT, Vol.1 - Type Inference with inequalities
TAPSOFT '91, 1991Co-Authors: Michael I. SchwartzbachAbstract:Type Inference can be phrased as constraint-solving over Types. We consider an implicitly Typed language equipped with recursive Types, multiple inheritance, 1st order parametric polymorphism, and assignments. Type correctness is expressed as satisfiability of a possibly infinite collection of (monotonic) inequalities on the Types of variables and expressions. A general result about systems of inequalities over semilattices yields a solvable form. We distinguish between deciding typability (the existence of solutions) and Type Inference (the computation of a minimal solution). In our case, both can be solved by means of nondeterministic finite automata; unusually, the two problems have different complexities: polynomial vs. exponential time.
Tian Zhao - One of the best experts on this subject based on the ideXlab platform.
-
Polymorphic Type Inference for scripting languages with object extensions
ACM SIGPLAN Notices, 2012Co-Authors: Tian ZhaoAbstract:This paper presents a polymorphic Type Inference algorithm for a small subset of JavaScript. The goal is to prevent accessing undefined members of objects. We define a Type system that allows explicit extension of objects through add operation and implicit extension through method calls. The Type system also permits strong updates and unrestricted extensions to new objects. The Type Inference algorithm is modular so that each function definition is only analyzed once and larger programs can be checked incrementally.
-
Type Inference for record concatenation and subtyping
Information and Computation, 2004Co-Authors: Jens Palsberg, Tian ZhaoAbstract:Record concatenation, multiple inheritance, and multiple-object cloning are closely related and part of various language designs. For example, in Cardelli's unTyped Obliq language, a new object can be constructed from several existing objects by cloning followed by concatenation; an error is given in case of field name conflicts. Type systems for record concatenation have been studied by Wand, Harper and Pierce, Remy, and others; and Type Inference for the combination of record concatenation and subtyping has been studied by Sulzmann and by Pottier. In this paper we present a Type Inference algorithm for record concatenation, subtyping, and recursive Types. Our example language is the Abadi-Cardelli object calculus extended with a concatenation operator. Our algorithm enables Type checking of Obliq programs without changing the programs at all. We prove that the Type Inference problem is NP-complete.
-
LICS - Efficient Type Inference for record concatenation and subtyping
Proceedings 17th Annual IEEE Symposium on Logic in Computer Science, 1Co-Authors: Jens Palsberg, Tian ZhaoAbstract:Record concatenation, multiple inheritance, and multiple-object cloning are closely related and part of various language designs. For example, in Cardelli's unTyped Obliq language, a new object can be constructed from several existing objects by cloning followed by concatenation; an error is given in case of field name conflicts. Type systems for record concatenation have been studied by M. Wand (1991), R. Harper and B. Pierce (1991), D. Remy (1992), and others; and Type Inference for the combination of record concatenation and subtyping has been studied by M. Sulzmann (1997) and by F. Pottier (2000). In this paper we present the first polynomial-time Type Inference algorithm for record concatenation, subtyping, and recursive Types. Our example language is the Abadi-Cardelli object calculus extended with a concatenation operator The Type Inference algorithm runs in O(n/sup 5/) time where n is the size of the program. Our algorithm enables efficient Type checking of Obliq programs without changing the programs at all.
Kexin Pei - One of the best experts on this subject based on the ideXlab platform.
-
python probabilistic Type Inference with natural language support
Foundations of Software Engineering, 2016Co-Authors: Xiangyu Zhang, Lin Chen, Kexin PeiAbstract:We propose a novel Type Inference technique for Python programs. Type Inference is difficult for Python programs due to their heavy dependence on external APIs and the dynamic language features. We observe that Python source code often contains a lot of Type hints such as attribute accesses and variable names. However, such Type hints are not reliable. We hence propose to use probabilistic Inference to allow the beliefs of individual Type hints to be propagated, aggregated, and eventually converge on probabilities of variable Types. Our results show that our technique substantially outperforms a state-of-the-art Python Type Inference engine based on abstract interpretation.
-
SIGSOFT FSE - Python probabilistic Type Inference with natural language support
Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, 2016Co-Authors: Xiangyu Zhang, Lin Chen, Kexin PeiAbstract:We propose a novel Type Inference technique for Python programs. Type Inference is difficult for Python programs due to their heavy dependence on external APIs and the dynamic language features. We observe that Python source code often contains a lot of Type hints such as attribute accesses and variable names. However, such Type hints are not reliable. We hence propose to use probabilistic Inference to allow the beliefs of individual Type hints to be propagated, aggregated, and eventually converge on probabilities of variable Types. Our results show that our technique substantially outperforms a state-of-the-art Python Type Inference engine based on abstract interpretation.
James Geddes - One of the best experts on this subject based on the ideXlab platform.
-
pType: probabilistic Type Inference
Data Mining and Knowledge Discovery, 2020Co-Authors: Taha Ceritli, Christopher K. I. Williams, James GeddesAbstract:Type Inference refers to the task of inferring the data Type of a given column of data. Current approaches often fail when data contains missing data and anomalies, which are found commonly in real-world data sets. In this paper, we propose pType , a probabilistic robust Type Inference method that allows us to detect such entries, and infer data Types. We further show that the proposed method outperforms existing methods.
-
pType: Probabilistic Type Inference
Data Mining and Knowledge Discovery, 2020Co-Authors: Taha Ceritli, Christopher K. I. Williams, James GeddesAbstract:Type Inference refers to the task of inferring the data Type of a given column of data. Current approaches often fail when data contains missing data and anomalies, which are found commonly in real-world data sets. In this paper, we propose pType, a probabilistic robust Type Inference method that allows us to detect such entries, and infer data Types. We further show that the proposed method outperforms the existing methods.
