Anonymous
Вот это я понимаю точность
kitsu
https://github.com/chrisdickinson/git-rs
Антон
Спасибо
Д.
Полную оптимизацию хвостового вызова даже Scala не умеет из-за JVM. Так, она совершенно не умеет оптимизировать косвенные хвостовые вызовы, когда рекурсивный вызов передается опосредованно через лямбду. F# иногда умеет, а иногда нет в зависимости от машины .NET. Haskell - конечно, умеет TCO. Это само собой, как и разные версии Схемы умеют. Сама идея TCO описана в книге PAIP, но это совсем не так, как работают вызовы в языке С. Так что, я бы абсолютно не расчитывал на LLVM. Если очень нужно, то можно использовать технику трамплина, что, например, у меня в коде и происходит, но уже в силу специфики самой задачи из моей прикладной области.
Alexander
Полную оптимизацию хвостового вызова даже Scala не умеет из-за JVM. Так, она совершенно не умеет оптимизировать косвенные хвостовые вызовы, когда рекурсивный вызов передается опосредованно через лямбду. F# иногда умеет, а иногда нет в зависимости от машины .NET. Haskell - конечно, умеет TCO. Это само собой, как и разные версии Схемы умеют. Сама идея TCO описана в книге PAIP, но это совсем не так, как работают вызовы в языке С. Так что, я бы абсолютно не расчитывал на LLVM. Если очень нужно, то можно использовать технику трамплина, что, например, у меня в коде и происходит, но уже в силу специфики самой задачи из моей прикладной области.
Для TCO нужен просто jump (aka goto). В JVM нет джампа вообще. В .NET раньше тоже не было, сейчас не знаю. А в x86(-64), куда компилируется Rust, jump есть. 😊
Alexander
Но TCO нет когда он нужен по причинам, описанным выше.
Sergey
Konstantin
tail call optimization?
Sergey
Sergey
Аббревиатуру не знал
Alexander
В этом чате нужно помнить две главные аббревиатуры: TCO и HKT - то, чего в Rust не будет никогда. 😂
roomba
Я ведь правильно понимаю, этот TCO делает jmp в начало функции (вместо call), а потом как только делается ret, управление сразу идёт туда, откуда нашу рек. функу вызывали?
roomba
Тогда передавать можно только примитивы и поинтеры на кучу ибо подобная функция не может иметь стека
Cat
roomba
Или может?
red75prime
Должно быть достаточно одного stack frame
Alexander
Или может?
Проще прочитать про реализацию разных вариантов tail call, чем изобретать самому в чате. 😉
red75prime
fn foo(_: &mut u32) { let mut u = 0u32; foo(&mut u) } вроде как не может быть оптимизирована.
roomba
Хм, если много регистров используется, надо некоторые забекапить. Наверное, в начале функи есть пуш, а jmp прыгает после этого 1-разового бекапа. Потом только перед ret их восстанавливать
Berkus
Bogdan
roomba
Berkus
Berkus
Bogdan
Полную оптимизацию хвостового вызова даже Scala не умеет из-за JVM. Так, она совершенно не умеет оптимизировать косвенные хвостовые вызовы, когда рекурсивный вызов передается опосредованно через лямбду. F# иногда умеет, а иногда нет в зависимости от машины .NET. Haskell - конечно, умеет TCO. Это само собой, как и разные версии Схемы умеют. Сама идея TCO описана в книге PAIP, но это совсем не так, как работают вызовы в языке С. Так что, я бы абсолютно не расчитывал на LLVM. Если очень нужно, то можно использовать технику трамплина, что, например, у меня в коде и происходит, но уже в силу специфики самой задачи из моей прикладной области.
В дотнете в байткоде есть tail call, но компилятор имеет право его проигнорить
Bogdan
Про ллвм, в принципе он не обязан, это мог-бы делать rustc, заменяя на цикл
Bogdan
Банально переприсвоить входные параметры, и сделать jump
Bogdan
Хотя, я бы больше хотел сжатых указателей, чем ТСО
red75prime
Berkus
Alexander
Berkus
red75prime
if u == 100 { println!() } else { foo(&mut u) } - хвостовой
Alexander
red75prime
Если есть ссылки только на предыдущий stack frame, то да - можно оптимизировать.
Alexander
red75prime
Ну да - это понятно.
Alexander
Ну так никаких других ссылок быть не может - нельзя ссылаться на будущий фрейм! 😃
Alexander
Alexander
Просто нарисуйте на бумажке структуру стекового кадра и посмотрите что в нём нужно поменять. Ничего нового создавать не нужно - в нём уже всё есть. 😊
red75prime
В общем случае оптимизатору придётся вводить динамически растущий массив. Что скорее всего будет пессимизацией
red75prime
Ссылку можно сохранить с любого уровня вложенности.
Alexander
А учитывая, что аргументы можно (и часто так и происходит) передавать через регистры, на стеке только local и будет лежать.
Alexander
Alexander
Alexander
А вообще, было бы продуктивнее, если бы участники перестали переизобретать TCO, и просто прочитали бы как оно делается в разных случаях. Уверен, случаи разобраны и описаны самые безумные. 😃
Berkus
Alexander
Это я к тому, что часть вины лежит на системе образования.
Cat
Alexander
Alexander
Либо это не tail position.
red75prime
fn foo(refs: Vec<&u32>) -> u32 {
let local = 0;
refs.push(&local);
if end {refs.sum() } else { foo(refs) }
}
red75prime
Или single linked list вместо Vec. В общем когда стек используется как растущий массив.
red75prime
Хотя такое лучше сразу писать циклом, конечно
Alexander
В случае типа return n*fac(n-1) можно сказать, что "стек используется как растущий массив", но это не хвостовой вызов.
Alexander
Вообще, разница между итеративными и ветвящимися вычислительными процессами была очень чётко объяснена на первых страницах SICP. Как и то, что циклы и хвостовые вызовы - всего лишь два разных способа описывать итеративные процессы.
red75prime
Roma
red75prime
red75prime
Alexander
Давно читал PAIP. Там не просто jump, а другое соглашение о вызовах, что даже через передачу рекурсивного вызова в лямбде не будет расти стек. Дателей не помню уже, но мне кажется, что это идет в разрез с текущим соглашением о вызовах в языке С, а его точно не будут менять ради TCO. Другие языки как Haskell могут позволить себе иметь свое собственное соглашение, но не C.
Не знаю, что там в PAIP, но, во-первых, в C используется не менее 4 соглашений о вызовах (c-call, pascall-call, win-call, fast-call), во-вторых, это существенно только для вызова функций из библиотек, а внутри библиотеки/бинарника компилятор может вызывать как хочет, в-третьих, компиляторы C/C++ таки активно делают TCO. Правда, насчёт аргументов не уверен на 100%.
Д.
Лакмусовая бумажка для определения того, есть TCO или нет: умеет ли компилятор оптимизировать косвенную рекурсию, когда хвостовой вызов передается опосредованно через лямбду, а не напрямую вызывается? Все остальное - это пиар.
red75prime
Berkus
Berkus
точнее, ссылки на разные значения
Alexander
То, что поведение компилятора будет противоречить интуиции или намерениям программиста - не новость, и необязательно проблема компилятора. 😃
Berkus