λ-wiki

λ-wiki :: tracing

www!k! v.20120610

λ-wiki :: éditeur

_h1 tracing tail recursion
_p Testing the factorial written in tail recursion :
{pre °°
{define myfact :p :i :n =
    (if (greaterthen :i :n) 
        then :p 
        else (myfact (mult :i :p) (add :i 1) :n) 
    )
}
°°} - >
{define myfact :p :i :n =
    (if (greaterthen :i :n) 
        then :p 
        else (myfact (mult :i :p) (add :i 1) :n) 
    )
}
{hr}
°°{myfact 1 1 6}°° - >
{hr}

°°
{if false then 1 else {if false then 1 else {if false then 2 else {if false then 6 else {if false then 24 else {if false then 120 else {if true then 720 else {if true then 5040 else {if {greaterthen 9 6} then 40320 else {myfact {mult 9 40320} {add 9 1} 6} } } } } } } } } } 
°°
{hr}
 ... {b doesn't work !} But manually writing the following sequence :
{hr}
°°
{if false then 1 else 
{if false then 1 else 
{if false then 2 else 
{if false then 6 else 
{if false then 24 else 
{if false then 120 else 
{if true then 720 else (myfact {mult :i :p} {add :i 1} :n)
} } } } } } }
°°
{hr}
- > 
{if false then 1 else 
{if false then 1 else 
{if false then 2 else 
{if false then 6 else 
{if false then 24 else 
{if false then 120 else 
{if true then 720 else (myfact {mult :i :p} {add :i 1} :n) 
} } } } } } } {b does work !}
_p When the boolean becomes true, in the first call,the then_term contains the good answer ({b 720}) and it can be seen that when, in the sequence, the else_term {b °°{myfact {mult :i :p} {add :i 1} :n}°°} is changed in {b °°(myfact {mult :i :p} {add :i 1} :n)°°}, the loop stops and returns the good result.
_p Looking in the [[parser|meca/parser.js]]'s code, the {b if} special function is written (see line 812) :
{pre
var str = (ouinon === 'true')?
          activate( trim( temp[0] ) )     // then_term
        : desactivate( trim( temp[1] ) ); // else_term
    return str;
}
_p so that the desactivation is applied to the else_term in order to prevent its evaluation, and in this case, to prevent the call to the next factorial and to enter in an infinit loop. But actually it doesn't work at all as expected ! 
_p Why ?