Generate algebraic expression at compile time in D

Let's consider a function defined as follows:

f(n, x) = F(n, x, f(n-1, x))
f(0, x) = g(x)

In my program the value of n is always known at compile time. I want to optimize my program and avoid loops or recursive calls in this function. Whole expression for f(n, x) should be generated at compile time in order to allow compiler optimize it.

The direct solution is "manually" generate a string containing this expression and use mixin statement. I don't like this way.

Is compiler able/supposed to unfold a recursion with known depth?

I.e. will the following function be optimized in the way I want:

double f(uint n)(double x)
{
    static if(n == 0)
        return g(x);
    else
        return F(n, x, f!(n-1)(x));
}

Solution

There is no guarantees for optimizations in language specification as far as I know. Though your examples looks pretty trivial to optimize for compiler.

Simple experiment: I have written stub functions g() and F() that do some simple calculations. Compiled with dmd -gc -O -inline". Checked with objdump:

0000000000426860 <_Dmain>:
  426860:   55                      push   %rbp
  426861:   48 8b ec                mov    %rsp,%rbp
  426864:   f2 48 0f 10 05 2b a7    rex.W movsd 0x2a72b(%rip),%xmm0        # 450f98 <_IO_stdin_used+0x38>
  42686b:   02 00 
  42686d:   be 0a 00 00 00          mov    $0xa,%esi
  426872:   48 bf 28 10 66 00 00    movabs $0x661028,%rdi
  426879:   00 00 00 
  42687c:   e8 6f 01 00 00          callq  4269f0 <_D3std5stdio4File14__T5writeTdTaZ5writeMFdaZv>
  426881:   31 c0                   xor    %eax,%eax
  426883:   5d                      pop    %rbp
  426884:   c3                      retq

As you can see, everything was actually calculated during compilation and replaced with single numeric value that gets immediately printed as an argument to writeln. I have also checked modification where x get read at run-time and there are no calls to f() either. ASM listing is rather long there so I won't copy it.

Also, if your parameters are known at compile-time, then, probably, CTFE ( Compile Time Function Evaluation ) is a better solution as it is guaranteed.