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