8
$\begingroup$

How do statically typed programming languages build CFGs for programs containing expression-level control flow (e.g. ternary expressions, match expressions) which require transformation or extra information (i.e. type information, etc.)?

Here’s a concrete example:

let foo = "bar"
let k = match foo {
    "bar" -> 1,
    _ -> 0,
 }
print(foo, k)

My assumption is that the CFG for the whole program is first built and then patched afterwards when enough information becomes available for these kinds of expressions. I am just not sure how correct this is or how well it works in practice for efficiency reasons.

$\endgroup$
1
  • 5
    $\begingroup$ Welcome to the site! This is a good question, but can you be a bit clearer about how your concrete example shows extra information (e.g. type information) being needed? $\endgroup$
    – kaya3
    Dec 31, 2023 at 11:21

1 Answer 1

10
$\begingroup$

The simple answer is that many don't. Production compiler typically lower the initial AST into a simpler subset of the language (often more than once). In many cases, typechecking and linting and other analysis steps that might require constructing a CFG happen after one or more of these lowering phases. A consequence of lowering is that expression-level control flow blocks (and other syntactic sugar) are removed.

For example, your code sample might be rewritten as such:

let foo = “bar”
let k; // k is declared, but not assigned yet
match foo {
    “bar” -> k = 1,
    _ -> k = 0,
}
print(foo, k)

From there, it should be more obvious as to how a CFG would be constructed.

The Rust compiler has a good, fairly straightforward overview of this process. You can start reading about it here if you wish. Check out the sections on lowering, and try exploring some of the source code (it is very well documented).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .