2

Functional programming has to deal with the same aspects of programming as every other paradigm. Nothing just disappears but is hidden through different abstractions. I often read that control flow is exclusively connected to statements and therefore FP exhibits none. I consider this statement misleading.

There is an entire type class to model imperative control flows (Monad). Operators have precedence and associativity, other ad-hoc types adhere to further arithmetic laws (by convention). There are if/then/else and case statements. Lazyness has to be taken into account.

Associativity has probably the greatest impact on control flow, because it is common and allows computations in parallel. So even though the control flow isn't so obvious anymore there is still one, right?

But maybe I am just conflating evaluation and execution order. Hoping this question isn't too broad.

Improve this question
1
  • Well in lambda calculus, the theoretical framework behind FP, the evaluation order does not matter for the correct result (en.wikipedia.org/wiki/Lambda_calculus#Reduction_strategies). Of course one evaluation strategy over the other can result in more reductions (so "computations" if you want). Commented Jul 25, 2020 at 10:58

1 Answer 1

Reset to default
3

In theory, pure functional programming allows to evaluate expressions using multiple strategies. Different language implementations can decide to use different strategies to reduce expressions. For instance, in e1 + e2 we might evaluate e1 first, e2 first, or even evaluate both in parallel.

To evaluate if guard then e1 else e2 we can evaluate guard first, and then evaluate only the corresponding branch. In principle, we could even start evaluating all of guard, e1, and e2 in parallel, and kill the thread corresponding to the non-taken branch. Or we could even use a more bizarre approach, where we try to prove that guard terminates using static analysis: if that succeeds, and the parallel evaluation of e1 and e2 terminate before guard to two equal values, we just return that and kill the thread which is still evaluating guard because we discovered we do not need that after all.

There are several papers on how to perform "optimal reduction" in the lambda calculus, using graph-reduction techniques.

Since these different strategies ultimately reach the same result, choosing between them is irrelevant except for performance reasons.

In practice, GHC reduction strategy is not so aggressive. It does not automatically parallelize anything. It does not follow an"optimal reduction" algorithm, if I recall correctly, but a more direct one with a bunch of optimizations and tricks to exploit modern hardware. GHC used to adopt a push/enter abstract machine, but has since then switched to a more straightforward eval/apply one when it became faster.

The GHC abstract machine (STG machine) uses a strategy that causes expressions like if then else to have a fixed evaluation order. You can think of that as "control flow", if you wish: the guard is always evaluated first, then only the selected branch is evaluated.

Knowing the employed strategy helps in assessing the complexity of a program (even if that still remains a kind of hard task in GHC Haskell due to laziness). For that, we need to know the "control flow" used by the strategy, in a sense.

However, the strategy does not matter when assessing the correctness of a program. If we want to prove our program correct, we do not need to assume a specific evaluation strategy, since all the them will produce the same result.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for patiently answering my basic questions.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.