10
$\begingroup$

How do I compile a self-referencing function to perform iterative tasks?

The naive approach doesn't seem to work. Here is a simple example to illustrate the problem:

SetSystemOptions["CompileOptions" -> "CompileReportExternal" -> True];

f = Compile[{{r, _Integer}, {x, _Complex}},
      Which[
        r == 0,  x,
        True,    x*f[r - 1, x/2]
      ]
     , {{f[__], _Complex}}, 
       CompilationOptions -> {"InlineExternalDefinitions" -> True}
     ]

Compile::extscalar : $f\big[r-1,\frac{x}{2}\big]$ cannot be compiled and will by evaluated externally. The result is assumed to be type Complex. >>

$\endgroup$
3
$\begingroup$

Leonid Shifrin's answer here may be useful (not just for your current problem, but for many, many compilation questions) as it gives advice for what can and what cannot be compiled. Recursion is explicitly called out as not a candidate. However procedural functions are identified as candidates.

So, yeah, if you completely change the intention (from recursion to iteration), no problem...

f[0, x_] := x;
f[r_Integer /; r > 0, x_] := fc[r, x];
fc = Compile[{{r, _Integer}, {x, _Complex}},
    Module[{answer, rCurr, xCurr},
        answer = 1 + 0 I;
        rCurr = r;
        xCurr = x;
        While[rCurr > 0, 
            answer *= xCurr;
            rCurr--;
            xCurr /= 2;
        ];
        answer
    ], 
    {{answer, _Complex}}
];

Then

<< CompiledFunctionTools`
CompilePrint[fc]
(*
    2 arguments
    1 Boolean register
    7 Integer registers
    2 Real registers
    6 Complex registers
    Underflow checking off
    Overflow checking off
    Integer overflow checking on
    RuntimeAttributes -> {}

    I0 = A1
    C0 = A2
    I2 = 0
    C1 = 0. + 1. I
    I6 = 2
    I1 = 1
    R1 = 0.
    Result = C4

1   R0 = I2
2   C2 = R0 + R1 I
3   C2 = C2 * C1
4   R0 = I1
5   C4 = R0 + R1 I
6   C4 = C4 + C2
7   I3 = I0
8   C2 = C0
9   B0 = I2 < I3
10  if[ !B0] goto 19
11  C5 = C4 * C2
12  C4 = C5
13  I4 = I3
14  I5 = Subtract[ I4, I1]
15  I3 = I5
16  C5 = Divide[ C2, I6]
17  C2 = C5
18  goto 9
19  Return@
*)
$\endgroup$
7
$\begingroup$

I haven't found a way to compile recursive functions to WVM, but you can do it if you compile to C: the trick is to use

CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> False}

along with

CompilationTarget -> "C"

If you then evaluate the following code twice, you will see that f calls a LibraryFunction, which tells you that it has been compiled:

f = Compile[{{r, _Integer}, {x, _Complex}},
  If[
    r == 0,
    x,
    x*f[r - 1, x/2]
  ], 
   CompilationOptions -> {"InlineExternalDefinitions" -> True,
                         "InlineCompiledFunctions" -> False},
   CompilationTarget -> "C"
 ]

The part specifying the return value of f is not needed as MMA figures it out, and I changed the Which to an If since you only test one thing.

$\endgroup$
  • $\begingroup$ "InlineCompiledFunctions" -> False isn't necessary actually :) $\endgroup$ – xzczd Oct 7 '15 at 4:04
  • $\begingroup$ This is very a helpful workaround. It is unfortunate that recursively defined functions cannot be compiled to WVM $\endgroup$ – QuantumDot Oct 9 '15 at 21:59
  • 1
    $\begingroup$ To Marius answer: this will not really do the job. The point is that the compiled function you create in the second run of the compilation will actually refer to the one compiled in the first run. The later in turn will invoke MainEvaluate. You can indeed model something like compiled recursion this way if there is predefined (and) small maximal recursion depth that you need. For recursion depth r you need to compile r times to avoid MainEvaluate at runtime. The final executable code quickly becomes heavy though. $\endgroup$ – Ivan Protopopov Dec 19 '17 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.