Binding-time analysis and the taming of C pointers

ABSTRACT

The aim of binding-time analysis is to determine when variables, expressions, statements, etc. in a program can be evaluated by classifying these into static (compile-time) and dynamic (run-time). Explicit separation of binding times has turned out to be crucial for successful self-application of partial evaluators, and apparently, it is also an important stepping-stone for profitable specialization of imperative languages with pointers and dynamic memory allocation. In this paper we present an automatic binding-time analysis for a substantial subset of the C language. The paper has two parts. In the first part, the semantic issues of binding-time separation is discussed with emphasis on pointers and classification of these. This leads to the introduction of a two-level C language where binding times are explicit in the syntax. Finally, well-annotatedness rules are given which excludes non-consistently annotated programs. In the second part, an automatic binding-time analysis based on constraint system solving is developed. The constraints capture the binding-time dependencies between expressions and subexpressions, and a solution to the system gives the binding times of all variables and expressions. We give rules for the generation of constraints, provide normalization rules, and describe how a solution can be found. Given the binding times of expressions, a well-annotated two-level version of the program can easily be constructed. A two-level program can e.g. be input to an offline partial evaluator.

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Procedures, functions, and subroutines

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Syntax
      D.3.2 Language Classifications

          Nouns: C
      D.3.4 Processors

  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.3 Studies of Program Constructs

General Terms:
Algorithms, Design, Languages, Performance, Theory