В частности, если у меня есть следующий код:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + n) }
}
Компилятор Swift оптимизирует его до цикла? И делает это в более интересном случае ниже?
func isOdd(n: Int) -> Bool {
if n == 0 { return false; }
else { return isEven(n - 1) }
}
func isEven(n: Int) -> Bool {
if n == 0 { return true }
else { return isOdd(n - 1) }
}
Лучший способ проверить - изучить код языка ассемблера, сгенерированный компилятором. Я взял код выше и скомпилировал его с помощью:
swift -O3 -S tco.swift >tco.asm
Соответствующая часть вывода
.globl __TF3tco3sumFTSiSi_Si
.align 4, 0x90
__TF3tco3sumFTSiSi_Si:
pushq %rbp
movq %rsp, %rbp
testq %rdi, %rdi
je LBB0_4
.align 4, 0x90
LBB0_1:
movq %rdi, %rax
decq %rax
jo LBB0_5
addq %rdi, %rsi
jo LBB0_5
testq %rax, %rax
movq %rax, %rdi
jne LBB0_1
LBB0_4:
movq %rsi, %rax
popq %rbp
retq
LBB0_5:
ud2
.globl __TF3tco5isOddFSiSb
.align 4, 0x90
__TF3tco5isOddFSiSb:
pushq %rbp
movq %rsp, %rbp
testq %rdi, %rdi
je LBB1_1
decq %rdi
jo LBB1_9
movb $1, %al
LBB1_5:
testq %rdi, %rdi
je LBB1_2
decq %rdi
jo LBB1_9
testq %rdi, %rdi
je LBB1_1
decq %rdi
jno LBB1_5
LBB1_9:
ud2
LBB1_1:
xorl %eax, %eax
LBB1_2:
popq %rbp
retq
.globl __TF3tco6isEvenFSiSb
.align 4, 0x90
__TF3tco6isEvenFSiSb:
pushq %rbp
movq %rsp, %rbp
movb $1, %al
LBB2_1:
testq %rdi, %rdi
je LBB2_5
decq %rdi
jo LBB2_7
testq %rdi, %rdi
je LBB2_4
decq %rdi
jno LBB2_1
LBB2_7:
ud2
LBB2_4:
xorl %eax, %eax
LBB2_5:
popq %rbp
retq
В сгенерированном коде нет инструкций по вызову, только условные переходы (je/jne/jo/jno). Это наглядно демонстрирует, что Swift выполняет оптимизацию вызовов в обоих случаях.
Кроме того, функции isOdd/isEven интересны тем, что компилятор не только выполняет TCO, но и строит другую функцию в каждом случае.
Да, быстрый компилятор в некоторых случаях выполняет оптимизацию хвостового вызова:
func sum(n: Int, acc: Int) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc: acc + 1) }
}
В качестве глобальной функции это будет использовать постоянное пространство стека на уровне "Самый быстрый" (-O).
Если он внутри структуры, он все равно будет использовать постоянное пространство стека. Внутри класса, однако, компилятор не выполняет tco, потому что метод может быть переопределен во время выполнения.
Clang также поддерживает tco для Objective-C, но часто ARC вызывает release после рекурсивного вызова, тем самым предотвращая эту оптимизацию, см. в этой статье Джонатана Маха для более подробной информации.
ARC также, кажется, предотвращает TCO в Swift:
func sum(n: Int, acc: Int, s: String?) -> Int {
if n == 0 { return acc }
else { return sum(n - 1, acc + 1, s) }
}
В моих тестах не было проведено TCO.