Polyvariance

In program analysis, a polyvariant or context-sensitive analysis (as opposed to a monovariant or context-insensitive analysis) analyzes each function multiple times—typically once at each call site—to improve the precision of the analysis.[1] Polyvariance is common in data-flow and pointer analyses.

Forms of polyvariance include:

  • Call-site sensitivity[2]
  • The Cartesian product algorithm[3]
  • Object sensitivity[2]
  • Type sensitivity[2]

The first two are more often used for dataflow analyses, the latter two are more frequently used for pointer analyses.

References

  1. ^ Palsberg, Jens; Pavlopoulou, Christina (2001). "From Polyvariant Flow Information to Intersection and Union Types". Proceedings of the 25th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '98). 11 (3): 197–208. CiteSeerX 10.1.1.36.4441. doi:10.1017/S095679680100394X. S2CID 16895848.
  2. ^ a b c Smaragdakis & Balatsouras 2015.
  3. ^ Gilray, Thomas; Adams, Michael D.; Might, Matthew (2016-09-04). "Allocation characterizes polyvariance: A unified methodology for polyvariant control-flow analysis". Proceedings of the 21st ACM SIGPLAN International Conference on Functional Programming. ICFP 2016. New York, NY, USA: Association for Computing Machinery. pp. 407–420. doi:10.1145/2951913.2951936. ISBN 978-1-4503-4219-3. S2CID 7768606.

Sources

  • Smaragdakis, Yannis; Balatsouras, George (2015). "Pointer Analysis" (PDF). Foundations and Trends in Programming Languages. 2 (1): 1–69. doi:10.1561/2500000014. Retrieved May 30, 2019.
  • v
  • t
  • e
Program analysis
Key concepts
  • Control-flow graph
  • Correctness
  • Hyperproperties
  • Invariants
  • Path explosion
  • Polyvariance
  • Rice's theorem
  • Runtime verification
  • Safety and liveness
  • Undefined behavior
A simple control-flow graph
Semantics
Types
  • Axiomatic
  • Denotational
    • Categorical semantics
  • Operational
    • Big-step
    • Small-step
Models
Analyses
Static
Dynamic
Formal methods
Concepts
Logics
Data structures
Tools
Constraint solvers
Lightweight
Proof assistants
  • Category
  • Outline
  • Glossary


Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

  • v
  • t
  • e