What's the difference between partial evaluation and function inlining in a functional language?

Question

I know that:

1. Function inlining is to replace a function call with the function definition.
2. Partial evaluation is to evaluate the known (static) parts of a program at compile time.

There is a distinction between the two in imperative languages like C, where operators are distinct from functions. However, is there any difference between the two in functional languages like Haskell where operators are functions too?

Is the only difference between the two that function inlining can be performed on selective parts of a program whereas partial evaluation is performed on the entire program (i.e. ∃ vs ∀)?

What are the semantic differences between the two optimization techniques?

Answer 1

There is a difference between

• evaluating constant expressions over a given set of operators and functions known by the compiler (or even preprocessor), which happens at compile time . E.g. the compiler compiles print(2*2) as print(4). This needs by no means to be limited to operator expressions, as you seem to imply (e.g. print(sqrt(2.0))
• partial evaluation, which is a broader concept. A compiler could realise that print(myfunc(2)) could be transformed into print(c) where c is the result of calling myfunc(2). It could then (at "specialisation time") call myfunc(2) to determine c. Of course, this will go badly wrong if myfunc has side-effects, like wiping one's own hard disk instead of the program user's. Hence the compiler needs some sort of annotation or attribute to know when this is allowed/desired (e.g. C++11's constexpr)

Inlining is an unrelated concept. Inlining a function call means replacing the call by the body of the called function. This body is not evaluated.

There is a distinction between the two in imperative languages like C, where operators are distinct from functions. However, is there any difference between the two in functional languages like Haskell where operators are functions too?

This distinctness (operators vs. functions) is purely syntactic, and is unrelated to the difference between inlining and partial evaluation:

Both function calls and expressions with operators can be inlined and compile-time evaluated in C. Compile-time evaluation is restricted to expressions over a fixed set of operators and functions (mostly operators, but that is historical accident)

Both concepts make sense and are distinct in Haskell.

• Inlining: ghc has {-# INLINE f #-}, where f cannot be recursive, for obvious reasons,
• Partial evaluation: this is usually generalised to Supercompilation where not only expressions of base type are transformed, but even functions, e.g. transforming map f (map g xs) into map (f . g) xs). It can (but need not) do inlining as well. Template Haskell is another way to (explicitely) evaluate part of a program at compile-time.

The answer to your title's question is thus: the difference between inlining and partial evaluation has nothing to do with the difference between functions and operators, and is much the same in functional languages as it is in C. Partial evaluation is probably more difficult in C because of side effects (cf the wiped hard disk above)

Answer 2

Consider the following code:

map f xs = case xs of [] -> []; (x:xs') -> f x : map f xs'
f x y = if x % 2 == 0 then y + x / 2 else y + x

main = map (f 3) [1..100]

After partial evaluating f 3:

f3 y = if 3 % 2 == 0 then y + 3 / 2 else y + 3
main = map f3 [1..100]

And then after constant folding 3 % 2 == 0:

f3 y = y + 3
main = map f3 [1..100]

Now let's consider inlining f:

NOTICE: f in f 3 will not be inlined since it is not a fully application, but we can adjust f's definition to make it happen, for more detail, see the ghc doc here

f x = \y -> if x % 2 == 0 then y + x / 2 else y + x

main = map (\y -> if 3 % 2 == 0 then y + 3 / 2 else y + 3) [1..100]

And then after constant folding 3 % 2 == 0:

main = map (\y -> y + 3) [1..100]

The above example shows that, both inlining and partial evaluation can provide extra optimization opportunities, but they are still very different:

1. when the special version (f 3 in the above example) appears many times, inlining will produce very many duplicated codes.
2. partial evaluation still works when the first argument is not a static constant, but inlining will not.

For the second point, consider the following example:

main = [f x y | x <- [1..10], y <- [1..100]]

In this case, partial evaluation can generate 10 specialized version for f x dynamically, but inlining can do nothing.