Jak działa @tailrec

Question

Użyłem i przeczytałem o adnotacji @tailrec, aby uzyskać metodę rekursywną ogona. Przeszedłem przez wiele linków, które to wyjaśniają. Na przykład działa tylko wtedy, gdy dla funkcji samodzielnego wywołania i nie powinien być nadpisywany itp.

Wszędzie wspomniano, że compiler optimizes. Ale jaką magię/koncepcję robi kompilator, aby uczynić ją rekurencyjną. W przypadku prostej funkcji poniżej, co robi kompilator zrobić:

@tailrec def fact(acc: Int, n: Int): Int = { 
    if (n <= 1) acc 
    else fact(n * acc, n - 1) 
} 
fact(1,10) 

Znaczy to przekształcić go w pętli, gdzie wielokrotnie nazywa go, a następnie zwraca wartość końcową? Czy istnieje jakiś związek do papieru, który wyjaśnia mu

Answer 1

Dodatkowo do mojego komentarza na swoje pytanie (repasting kod tutaj):

var acc = 1 
    var n = 10 
start: 
    if (n <= 1) return acc 
    else { 
    acc = n * acc 
    n = n - 1 
    goto start 
    } 

Próbowałem kompilacji metodę fact z ostatniej kompilacji ja akurat mam iz scalac -Xprint:all i jakoś kompilator wyemitował plik icode. To naprawdę ilustruje, jak optymalizuje on wywołanie ogona:

// methods 
    def fact(acc: Int (INT), n: Int (INT)): Int { 
    locals: value acc, value n, value _$this 
    startBlock: 1 
    blocks: [1,2,3,4,5] 

    1: 
    2 JUMP 2 

    2: // huynhjl's comment: IF condition is here 
    3 LOAD_LOCAL(value n) 
    3 CONSTANT(1) 
    3 CJUMP (INT)LE ? 3 : 4 

    3: // huynhjl's comment: first branch of IF, will return acc 
    3 LOAD_LOCAL(value acc) 
    3 JUMP 5 

    5: 
    2 RETURN(INT) 

    4: // huynhjl's comment: else branch of IF, update acc and n and jump back 
    4 LOAD_LOCAL(value n) 
    4 LOAD_LOCAL(value acc) 
    4 CALL_PRIMITIVE(Arithmetic(MUL,INT)) 
    4 LOAD_LOCAL(value n) 
    4 CONSTANT(1) 
    4 CALL_PRIMITIVE(Arithmetic(SUB,INT)) 
    4 STORE_LOCAL(value n) 
    4 STORE_LOCAL(value acc) 
    4 JUMP 2 

    } 

Answer 2

Oto miły Blog post na temat

@tailrec gwarantuje jedynie, że błąd jest wydawane jeśli optymalizacja ogon wywołanie nie mogą być wykonywane przez kompilator. Scala domyślnie przeprowadza optymalizację wywołań końcowych.

Gdy warunki opisane przez papier są spełnione, możliwe jest zachowanie ostatniej klatki zamiast stosu klatek i wykonanie pętli. Proces jest lepiej opisany here