6
$\begingroup$

I am trying to do something similar to this, namely to make a Compile'd function outer that itself calls a Compile'd function inner which accesses a variable defined in outer. Copy-pasting the example Leonid gives in the link, I get no errors. However in my case, I want inner to be a recursive function.

So far I have tried (the functions are toy examples):

Clear[inner];
inner = Compile[ {{i, _Integer}, {j, _Integer}},
If[i >= j, Return[], AppendTo[bag, list]; inner[i + 1, j]];
,CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> False} ]

and

Clear[outer];
outer = Compile[{{i, _Integer}},
Block[{list = Table[{0, 0}, {i}], bag},
bag = {list};
inner[1, i];
bag
]
, CompilationOptions -> {"InlineExternalDefinitions" -> True, 
"InlineCompiledFunctions" -> True}
]

Trying to execute this last piece results in the error message:

Compile::cret : The type of return values in (...) are different.
Evaluation will use the uncompiled function.

I have a hard time interpreting the output of CompilePrint in this case, so I cannot pinpoint the error in order to move further with this. Since I am able to create compiled recursive functions just fine in general, and the link provides a "hack" to make inner see the variables in outer, I think it should be possible to do this, but perhaps not...

EDIT: I have verified that the lingering MainEvaluate is not due AppendTo or some-such, by making the function inner even more basic. I have also tried all possible combinations of True/False for the CompilationOptions for both inner and outer with no success. So it seems to me that it's possible to compile either a recursive function, or a compiled function modifying a "global" variable when called from another compiled function, but not both =(

$\endgroup$
  • $\begingroup$ As far as I know, so far it's not possible to define a recursive compiled function. (This question is slightly related.) I hope I'm wrong. $\endgroup$ – xzczd Apr 1 '15 at 9:04
  • 1
    $\begingroup$ What about this? LevelsNeeded=Compile[ {{b,_Integer},{M,_Integer},{x,_Integer}}, If[M<=(x*b+Quotient[x(x-1),2]),x,LevelsNeeded[b,M,x+1]] ,{{_LevelsNeeded,_Integer}} ,CompilationOptions->{"InlineExternalDefinitions"->True,"InlineCompiledFunctions"->False} ,CompilationTarget->"C",RuntimeOptions->"Speed" ]; If I call this twice, I see no MainEvaluate-calls, and it's very fast. $\endgroup$ – Marius Ladegård Meyer Apr 1 '15 at 9:14
  • 1
    $\begingroup$ Quite interesting! BTW, the code can be simplified to LevelsNeeded = Compile[{{b, _Integer}, {M, _Integer}, {x, _Integer}}, If[M <= (x*b + Quotient[x (x - 1), 2]), x, LevelsNeeded[b, M, x + 1]], {{_LevelsNeeded, _Integer}}, CompilationOptions -> {"InlineExternalDefinitions" -> True}, CompilationTarget -> C];. $\endgroup$ – xzczd Apr 1 '15 at 9:31
  • 1
    $\begingroup$ Perhaps related: Compile recursive function modifying global variables. $\endgroup$ – István Zachar Apr 7 '15 at 9:49
  • 1
    $\begingroup$ @IstvánZachar Yes, it's virtually the same question. Have you been able to make it work? $\endgroup$ – Marius Ladegård Meyer Apr 7 '15 at 20:19
1
$\begingroup$

This seems to work. Use With to "inject" the inner definition into outer.

Clear[inner];
inner = Compile[{{i, _Integer}, {j, _Integer}},
   If[i >= j,
    0,
    AppendTo[bag, list];
    inner[i + 1, j]]];

Clear[outer];
outer = With[{inner = inner}, Compile[{{i, _Integer}},
    Block[{list = ConstantArray[0, {i, 2}], bag},
     bag = {list};
     inner[1, i];
     bag]]];

In[123]:= outer[5]

(* Out[123]= {{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 
   0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 
   0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0,
    0}, {0, 0}, {0, 0}}} *)

There may of course be other variants that work e.g. using the inline capabilities of Compile. I did not have success going that route but maybe was doing something not quite right. And Compile can be grumpy at times. [Edit: but see full edit below.]


Edit

This version seems sleeker. Still unable to avoid external evaluation though.

Clear[inner];
inner[i_, j_] :=
 If[i >= j,
  0,
  AppendTo[bag, list];
  inner[i + 1, j]]
Clear[outer];
outer = Compile[{{i, _Integer}},
   Block[{list = ConstantArray[0, {i, 2}], bag},
    bag = {list};
    inner[1, i];
    bag],
   CompilationOptions -> {"InlineExternalDefinitions" -> True, 
     "InlineCompiledFunctions" -> True}];

In[163]:= outer[5]

(* Out[163]= {{{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 
   0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 
   0}}, {{0, 0}, {0, 0}, {0, 0}, {0, 0}, {0, 0}}, {{0, 0}, {0, 0}, {0,
    0}, {0, 0}, {0, 0}}} *)

I think to make it fast one needs to use Internal`StuffBag or some such. I don't see AppendTo as being good for speed.

$\endgroup$
  • 1
    $\begingroup$ But this still calls MainEvaluate…… $\endgroup$ – xzczd Apr 8 '15 at 6:47
  • $\begingroup$ The proper edit-trick is to do it the other way around. Wrap the code that contains a back-tick into two backticks. If your code ends in a backtick, you need to make a space between the closing two backticks, like in JLink` which is written as ''JLink' '' (I used quotes here..) $\endgroup$ – halirutan Apr 8 '15 at 16:10
  • $\begingroup$ @halirutan Thx. $\endgroup$ – Daniel Lichtblau Apr 8 '15 at 17:21
  • $\begingroup$ @DanielLichtblau Indeed, my plan was to switch to Internal`Bag after getting rid of calls to MainEvaluate, but I didn't want to clutter the problem description with this detail, as I don't have complete understanding of how to use Bags under Compile yet (that's next on my TODO) ;) $\endgroup$ – Marius Ladegård Meyer Apr 9 '15 at 9:19
  • $\begingroup$ Just to be clear, the call to MainEvaluate does not stem from using AppendTo, right? $\endgroup$ – Marius Ladegård Meyer Apr 9 '15 at 9:20

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.