<div dir="ltr"><div>I think it didn't do the tail call properly. This is the relevant stub from the ; version:<br></div><br><div>(123,1,<br> Let<br> [Let [Op (Const 0) []; Op (Const 0) []; Op (Const 0) []]<br> (If<br> (Op (EqualInt 1)<br> [Op El [Op (Const 1) []; Op (Const 0) []]])<br> (Call 1 NONE<br> [Op (Const 0) []; Var 3; Op (Const 0) [];<br> Op El [Op (Const 0) []; Op (Const 0) []]] NONE)<br> (Call 0 (SOME 53)<br> [Op (Const 0) []; Var 3; Op (Const 0) []] NONE))]<br> (If (Op (TagLenEq 1 0) [Var 0])<br> <b> (Let<br> [Call 1 (SOME 119) [Op (Cons 0) []] NONE;<br> Call 1 (SOME 123)<br> [Let<br> [Op (Const 1) []; Op (Const 0) []; Op (Const 0) []]<br> (If<br> (Op (EqualInt 1)<br> [Op El [Op (Const 1) []; Op (Const 0) []]])<br> (Call 1 NONE<br> [Op (Const 1) []; Var 4; Op (Const 0) [];<br> Op El [Op (Const 0) []; Op (Const 0) []]]<br> NONE)<br> (Call 0 (SOME 53)<br> [Op (Const 1) []; Var 4; Op (Const 0) []]<br> NONE))] NONE] (Var 1))</b> (Op (Cons 0) [])))<br><br></div><div>This is the stub from the let val foo = ... version:<br><br>(123,1,<br> Let<br> [Let [Op (Const 0) []; Op (Const 0) []; Op (Const 0) []]<br> (If<br> (Op (EqualInt 1)<br> [Op El [Op (Const 1) []; Op (Const 0) []]])<br> (Call 1 NONE<br> [Op (Const 0) []; Var 3; Op (Const 0) [];<br> Op El [Op (Const 0) []; Op (Const 0) []]] NONE)<br> (Call 0 (SOME 53)<br> [Op (Const 0) []; Var 3; Op (Const 0) []] NONE))]<br> (If (Op (TagLenEq 1 0) [Var 0])<br> <b>(Let [Call 1 (SOME 119) [Op (Cons 0) []] NONE]<br> (Call 1 (SOME 123)<br> [Let<br> [Op (Const 1) []; Op (Const 0) []; Op (Const 0) []]<br> (If<br> (Op (EqualInt 1)<br> [Op El [Op (Const 1) []; Op (Const 0) []]])<br> (Call 1 NONE<br> [Op (Const 1) []; Var 5; Op (Const 0) [];<br> Op El [Op (Const 0) []; Op (Const 0) []]]<br> NONE)<br> (Call 0 (SOME 53)<br> [Op (Const 1) []; Var 5; Op (Const 0) []]<br> NONE))] NONE))</b> (Op (Cons 0) [])))<br></div><div><br></div><div>In bvl_to_bvi, it seems like bvi_let is only called on Let [] _s that are behind a marker.<br></div><div><br></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Fri, Apr 21, 2017 at 8:15 PM, Magnus Myreen <span dir="ltr"><<a href="mailto:magnus.myreen@gmail.com" target="_blank">magnus.myreen@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Hmm, bvi_let ought to move it into tail position. It changes the<br>
variable lookups to match the new position. There must be something<br>
that mangles the Let [..; ..] (Var 1) on the way from patLang to BVI.<br>
<span class="HOEnZb"><font color="#888888">-- Magnus<br>
</font></span><div class="HOEnZb"><div class="h5"><br>
On 22 April 2017 at 02:08, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
> Ah right, I had in mind that the transformation would still work because foo<br>
> isn't mentioned in the loop, I guess that is a bad transformation because it<br>
> will require changing the variable indexes.<br>
><br>
> On Fri, Apr 21, 2017 at 8:02 PM, Ramana Kumar <<a href="mailto:Ramana.Kumar@cl.cam.ac.uk">Ramana.Kumar@cl.cam.ac.uk</a>><br>
> wrote:<br>
>><br>
>> Regarding point 1, the term is not ground because it has free variables<br>
>> "n" and "loop" in it.<br>
>><br>
>> On 22 April 2017 at 09:42, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
>>><br>
>>> Ah, I guess that's bvi_let. I'll have a look at whether it's actually<br>
>>> doing it.<br>
>>><br>
>>> On Fri, Apr 21, 2017 at 7:37 PM, Magnus Myreen <<a href="mailto:magnus.myreen@gmail.com">magnus.myreen@gmail.com</a>><br>
>>> wrote:<br>
>>>><br>
>>>> Hi Yong Kiam,<br>
>>>><br>
>>>> There is (or was meant to be) a phase around BVL or BVI that aims to<br>
>>>> turn Let xs (Var (LENGTH xs - 1)) into the desired code with last of xs<br>
>>>> moved into tail position.<br>
>>>><br>
>>>> Cheers,<br>
>>>> Magnus<br>
>>>> On Sat, 22 Apr 2017 at 05:48, Yong Kiam <<a href="mailto:tanyongkiam@gmail.com">tanyongkiam@gmail.com</a>> wrote:<br>
>>>>><br>
>>>>> Hi dev,<br>
>>>>><br>
>>>>> I'm trying to get this benchmark running:<br>
>>>>> <a href="https://raw.githubusercontent.com/MLton/mlton/master/benchmark/tests/tailfib.sml" rel="noreferrer" target="_blank">https://raw.githubusercontent.<wbr>com/MLton/mlton/master/<wbr>benchmark/tests/tailfib.sml</a><br>
>>>>> on a recent build of the bootstrapped compiler<br>
>>>>><br>
>>>>> I ran into this strange scenario:<br>
>>>>><br>
>>>>> Writing the loop like the following makes CakeML run out of stack (I<br>
>>>>> think it fails to optimize the tail call because increasing the stack limit<br>
>>>>> manually works):<br>
>>>>><br>
>>>>> val doit =<br>
>>>>> fn n =><br>
>>>>> let<br>
>>>>> fun loop n =<br>
>>>>> if n = 0<br>
>>>>> then ()<br>
>>>>> else (doit();loop(n-1))<br>
>>>>> in loop (n * 1000000)<br>
>>>>> end;<br>
>>>>><br>
>>>>> On the other hand, making the ; explicit:<br>
>>>>><br>
>>>>> val doit =<br>
>>>>> fn n =><br>
>>>>> let<br>
>>>>> fun loop n =<br>
>>>>> if n = 0<br>
>>>>> then ()<br>
>>>>> else (let val foo = doit() in loop(n-1) end)<br>
>>>>> in loop (n * 1000000)<br>
>>>>> end;g<br>
>>>>><br>
>>>>> works fine.<br>
>>>>><br>
>>>>> I checked out the compilation down to patLang, and the only difference<br>
>>>>> between the two is that the first is compiled to a Seq while the second is<br>
>>>>> compiled to a Let.<br>
>>>>><br>
>>>>> There are actually two things of interest:<br>
>>>>><br>
>>>>> 1) The ground check in exh_to_pat incorrectly says that (let val foo =<br>
>>>>> doit() in loop(n-1) end) is not ground, and does not compile it to doit() ;<br>
>>>>> loop (n-1)<br>
>>>>><br>
>>>>> 2) pat_to_clos compiles Seqs to Let [compile e1;compile e2] (Var 1)<br>
>>>>> while the Lets go to Let [compile e1] (compile e2)<br>
>>>>><br>
>>>>> I think the issue is that the tail call detector cannot / does not<br>
>>>>> detect the first tail call shape.<br>
>>>>><br>
>>>>> I'm not sure what the best fix is here, is the multiple-argument Let<br>
>>>>> compilation of Seq important? If so, I guess the tail call detector in<br>
>>>>> bvi_to_data should be updated to detect those shapes too.<br>
>>>>> ______________________________<wbr>_________________<br>
>>>>> Developers mailing list<br>
>>>>> <a href="mailto:Developers@cakeml.org">Developers@cakeml.org</a><br>
>>>>> <a href="https://lists.cakeml.org/listinfo/developers" rel="noreferrer" target="_blank">https://lists.cakeml.org/<wbr>listinfo/developers</a><br>
>>><br>
>>><br>
>>><br>
>>> ______________________________<wbr>_________________<br>
>>> Developers mailing list<br>
>>> <a href="mailto:Developers@cakeml.org">Developers@cakeml.org</a><br>
>>> <a href="https://lists.cakeml.org/listinfo/developers" rel="noreferrer" target="_blank">https://lists.cakeml.org/<wbr>listinfo/developers</a><br>
>>><br>
>><br>
><br>
</div></div></blockquote></div><br></div>