Control-flow analysis: Difference between revisions

Revision as of 23:58, 2 January 2013

Revision as of 15:30, 22 February 2013

Line 1:

In [[computer science]], '''Controlcontrol flow analysis''' is a [[static code analysis]] technique for determining the [[control flow]] of a program. The control flow is expressed as a [[control flow graph]] (CFG). The term "control flow analysis" was introduced independently by [[Neil D. Jones]]<ref>{{citation

For many languages, the control flow of a program is explicit in a program's source code. As a result, control-flow analysis implicitly usually refers to a [[static analysis]] technique for determining the receiver(s) of function or method calls in computer programs written in a [[higher-order programming language]]. For both [[functional programming language]]s and [[object-oriented programming language]]s, the term CFA refers to an algorithm that computes control flow.

The term '''control flow analysis''' was introduced independently by Neil D. Jones<ref>{{citation

| author = Neil D. Jones

| title = Flow analysis of lambda expressions

Line 10 ⟶ 6:

| doi = 10.1007/3-540-10843-2_10

| pages = 114–128

}}</ref> and [[Olin Shivers]].<ref>{{citation

| last = Shivers

| first = Olin

Line 22 ⟶ 18:

| year = 1988

| doi = 10.1145/53990.54007

}}</ref> For both [[functional programming language]]s and [[object-oriented programming language]]s, the term CFA, and elaborations such as ''k''-CFA, refer to specific algorithms that compute control flow.

}}</ref>

In a programming language with [[higher-order functions]] like [[Scheme (programming language)|Scheme]], the target of a function call may not be explicit. For example in the isolated expression:

(lambda (f) (f x))

For many languages, the control flow of a program is explicit in a program's source code. As a result, control-flow analysis implicitly usually refers to a [[static analysis]] technique for determining the receiver(s) of function or method calls in computer programs written in a [[higher-order programming language]]. In Fora bothprogramming language with [[functionalhigher-order programming languagefunctions]]s andlike [[object-orientedScheme (programming language)|Scheme]]s, the termtarget CFAof refersa tofunction ancall algorithmmay thatnot computesbe control flowexplicit. For example in the isolated expression:

<source lang="scheme">

(lambda (f) (f x))

</source>

it is unclear to which procedure <code>f</code> may refer. To determine the possible targets, a control-flow analysis must consider where this expression could be invoked, and what argument it may receive.

Techniques such as [[Abstractabstract interpretation]], [[constraint solving]] and [[type system]]s may be used to compute control-flow analysis.

==References==