Analyzing the environment structure of higher-order languages using frame strings

Academic Article


  • Reasoning about program behaviour in programming languages based on the λ calculus requires reasoning in a unified way about control, data and environment structure. Previous analysis work has done an inadequate job on the environment component of this task. We develop a new analytic framework, ΔCFA, which is based on a new abstraction: frame strings, an enriched variant of procedure strings that can be used to model both control flow and environment allocation. This abstraction enables new environment-sensitive analyses and transformations that have not been previously attainable. We state the critical theorems needed to establish correctness of the entire technology suite, with their proofs. © 2007 Elsevier Ltd. All rights reserved.
  • Authors

    Published In

    Digital Object Identifier (doi)

    Pubmed Id

  • 22551396
  • Author List

  • Might M; Shivers O
  • Start Page

  • 137
  • End Page

  • 168
  • Volume

  • 375
  • Issue

  • 1-3