GLORIA

GEOMAR Library Ocean Research Information Access

X

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
Filter
  • Pavlinovic, Zvonimir  (3)
Material
Publisher
Person/Organisation
Language
Years
  • 1
    Online Resource
    Online Resource
    Data flow refinement type inference
    Association for Computing Machinery (ACM) ; 2021
    In:  Proceedings of the ACM on Programming Languages Vol. 5, No. POPL ( 2021-01-04), p. 1-31
    Details
    In: Proceedings of the ACM on Programming Languages, Association for Computing Machinery (ACM), Vol. 5, No. POPL ( 2021-01-04), p. 1-31
    Abstract: Refinement types enable lightweight verification of functional programs. Algorithms for statically inferring refinement types typically work by reduction to solving systems of constrained Horn clauses extracted from typing derivations. An example is Liquid type inference, which solves the extracted constraints using predicate abstraction. However, the reduction to constraint solving in itself already signifies an abstraction of the program semantics that affects the precision of the overall static analysis. To better understand this issue, we study the type inference problem in its entirety through the lens of abstract interpretation. We propose a new refinement type system that is parametric with the choice of the abstract domain of type refinements as well as the degree to which it tracks context-sensitive control flow information. We then derive an accompanying parametric inference algorithm as an abstract interpretation of a novel data flow semantics of functional programs. We further show that the type system is sound and complete with respect to the constructed abstract semantics. Our theoretical development reveals the key abstraction steps inherent in refinement type inference algorithms. The trade-off between precision and efficiency of these abstraction steps is controlled by the parameters of the type system. Existing refinement type systems and their respective inference algorithms, such as Liquid types, are captured by concrete parameter instantiations. We have implemented our framework in a prototype tool and evaluated it for a range of new parameter instantiations (e.g., using octagons and polyhedra for expressing type refinements). The tool compares favorably against other existing tools. Our evaluation indicates that our approach can be used to systematically construct new refinement type inference algorithms that are both robust and precise.
    Type of Medium: Online Resource
    ISSN: 2475-1421
    URL: Article
    DOI: 10.1145/3434300
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2021
    detail.hit.zdb_id: 2924207-1
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 2
    Online Resource
    Online Resource
    Finding minimum type error sources
    Association for Computing Machinery (ACM) ; 2014
    In:  ACM SIGPLAN Notices Vol. 49, No. 10 ( 2014-12-31), p. 525-542
    Details
    In: ACM SIGPLAN Notices, Association for Computing Machinery (ACM), Vol. 49, No. 10 ( 2014-12-31), p. 525-542
    Abstract: Automatic type inference is a popular feature of functional programming languages. If a program cannot be typed, the compiler typically reports a single program location in its error message. This location is the point where the type inference failed, but not necessarily the actual source of the error. Other potential error sources are not even considered. Hence, the compiler often misses the true error source, which increases debugging time for the programmer. In this paper, we present a general framework for automatic localization of type errors. Our algorithm finds all minimum error sources, where the exact definition of minimum is given in terms of a compiler-specific ranking criterion. Compilers can use minimum error sources to produce more meaningful error reports, and for automatic error correction. Our approach works by reducing the search for minimum error sources to an optimization problem that we formulate in terms of weighted maximum satisfiability modulo theories (MaxSMT). The reduction to weighted MaxSMT allows us to build on SMT solvers to support rich type systems and at the same time abstract from the concrete criterion that is used for ranking the error sources. We have implemented an instance of our framework targeted at Hindley-Milner type systems and evaluated it on existing OCaml benchmarks for type error localization. Our evaluation shows that our approach has the potential to significantly improve the quality of type error reports produced by state of the art compilers.
    Type of Medium: Online Resource
    ISSN: 0362-1340 , 1558-1160
    URL: Article
    DOI: 10.1145/2714064.2660230
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2014
    detail.hit.zdb_id: 2079194-X
    detail.hit.zdb_id: 282422-X
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
  • 3
    Online Resource
    Online Resource
    Practical SMT-based type error localization
    Association for Computing Machinery (ACM) ; 2015
    In:  ACM SIGPLAN Notices Vol. 50, No. 9 ( 2015-12-18), p. 412-423
    Details
    In: ACM SIGPLAN Notices, Association for Computing Machinery (ACM), Vol. 50, No. 9 ( 2015-12-18), p. 412-423
    Abstract: Compilers for statically typed functional programming languages are notorious for generating confusing type error messages. When the compiler detects a type error, it typically reports the program location where the type checking failed as the source of the error. Since other error sources are not even considered, the actual root cause is often missed. A more adequate approach is to consider all possible error sources and report the most useful one subject to some usefulness criterion. In our previous work, we showed that this approach can be formulated as an optimization problem related to satisfiability modulo theories (SMT). This formulation cleanly separates the heuristic nature of usefulness criteria from the underlying search problem. Unfortunately, algorithms that search for an optimal error source cannot directly use principal types which are crucial for dealing with the exponential-time complexity of the decision problem of polymorphic type checking. In this paper, we present a new algorithm that efficiently finds an optimal error source in a given ill-typed program. Our algorithm uses an improved SMT encoding to cope with the high complexity of polymorphic typing by iteratively expanding the typing constraints from which principal types are derived. The algorithm preserves the clean separation between the heuristics and the actual search. We have implemented our algorithm for OCaml. In our experimental evaluation, we found that the algorithm reduces the running times for optimal type error localization from minutes to seconds and scales better than previous localization algorithms.
    Type of Medium: Online Resource
    ISSN: 0362-1340 , 1558-1160
    URL: Article
    DOI: 10.1145/2858949.2784765
    Language: English
    Publisher: Association for Computing Machinery (ACM)
    Publication Date: 2015
    detail.hit.zdb_id: 2079194-X
    detail.hit.zdb_id: 282422-X
    Location Call Number Limitation Availability
    BibTip Others were also interested in ...
    Online Resource
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...