Функциональный Rust: Готовим говядину

[@torkve]

В Rust конечно же есть оптимизация хвостовой рекурсии, вот простейший пример (no_mangle исключительно для читаемости):

0 ➜ cat a.rs 
#[no_mangle]
pub fn test(a: i32) -> i32 {
    if a == 0 {
        42
            
    } else if a == 7 {
        43
    } else {
        test(a - 1)
    }
}
0 ➜ rustc --crate-type dylib --emit llvm-ir -O a.rs

0 ➜ cat a.ll
; ModuleID = 'a.cgu-0.rs'
source_filename = "a.cgu-0.rs"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

; Function Attrs: nounwind readnone uwtable
define i32 @test(i32) unnamed_addr #0 {
start:
  br label %tailrecurse

tailrecurse:                                      ; preds = %bb4, %start
  %.tr = phi i32 [ %0, %start ], [ %1, %bb4 ]
  switch i32 %.tr, label %bb4 [
    i32 0, label %bb7.loopexit
    i32 7, label %bb7.loopexit2
  ]

bb4:                                              ; preds = %tailrecurse
  %1 = add i32 %.tr, -1
  br label %tailrecurse

bb7.loopexit2:                                    ; preds = %tailrecurse
  br label %bb7

bb7.loopexit:                                     ; preds = %tailrecurse
  br label %bb7

bb7:                                              ; preds = %bb7.loopexit, %bb7.loopexit2
  %_0.0 = phi i32 [ 43, %bb7.loopexit2 ], [ 42, %bb7.loopexit ]
  ret i32 %_0.0
}

attributes #0 = { nounwind readnone uwtable }

Другое дело, что из вашего кода непонятно, то ли вы его неправильно написали, так как первоначальный вариант функции execute содержит точку с запятой в самом конце, что подразумевает, что последняя инструкция не новый execute(...), а просто (), пустая инструкция, такой код вообще по идее не должен скомпилироваться, потому что возвращаемое значение не совпадает с сигнатурой функции. То ли по какой-то иной причине не отработала оптимизация.

[@Virviil]

Точка с запятой — это опечатка. Уже исправил.

Но вот этот кода то выдаёт stack overflow: click. Обьясните тогда, что же делать?

[@unsafePtr]

Так а где увас выход из рекурсии в примере?

if i == 0 {
        1
    }

А из маин вы подаете count(1), таким образом мы не сможем выйти из рекурсии

[@Virviil]

Оптимизатор не может и не должен об этом знать.

Что к примеру я мог написать так:

fn count(i: i32) -> i32 {
    if i == 0 {
        1
    }
    else {
        println!("{}", i);
        count(%рандомное число от 0 до 2**32%)
    }
}

и получил бы stack overflow, хотя в идеале он должен писать в консоль до тех пор, пока не нарандомит 0.

[@torkve]

Конкретно у этого примера, как вам правильно заметили, нет никакого условия выхода. Если на него внимательно посмотреть, то получается, что такой код завязан на переполнение i32 (не помню, есть ли в Rust про это какой-то стандарт, а в C это называлось бы UB), т.е. ваш код выйдет, когда мы переполним i32 и дойдём до 0 с отрицательной стороны. При таких условиях компилятор имеет право нарисовать на экране котика вместо заданного кода. Например, если убрать ваш println!, то вся функция при компиляции превратится в одну строчку: ret i32 1.

Если же говорить о вашем цикле из статьи, то вероятно, что ему тоже просто необходимо корректное условие выхода из цикла, потому что в функции execute его вообще нет. Мне лень лезть в код, но я подозреваю, что у вас предполагается, что в какой-то момент получение следующей инструкции выкинет панику или прямо сделает abort(), но это как раз плохой и нефункциональный подход.

[@Virviil]

Я не эксперт, но на самом деле я понимаю TCO вот так:
Видим, что функция возвращает вызов функции — не добавляем переход на эту функцию в стек вызовов.
И в этом случае что бы там не падало, или падало, или не важно — переполнения стека быть не может. Что угодно — но не это.
Возможно, я конечно ошибаюсь.

[@Akon32]

Видим, что функция возвращает вызов функции — не добавляем переход на эту функцию в стек вызовов.

Какой ещё "возврат вызова функции"?

Правило такое: Последовательность call addr ; ret заменяем на jmp addr.
(";" здесь — разделитель инструкций)

[@torkve]

Я тоже ненастоящий сварщик, но в моём понимании у функции должно быть место, в котором она говорит ret и вызывающему коду возвращается то, что лежит в соответствующем регистре. При TCO бесконечного цикла в коде просто не остаётся ret, который можно было бы позвать. Можно пытаться его как-то эмулировать, воткнув никогда не вызываемый ret после джампа, но это нелегально, потому что у нас нет никакого значения заявленного типа (CowVM), которое можно положить в регистр для возврата.

При этом можно явно заявить функцию, как не возвращающую значение:

#[no_mangle]
pub fn test(a: i32) -> ! {
    println!("a");
    test(a + 1)
}

И тогда компилятор штатно сгенерирует в конце функции:

...
  %6 = add i32 %0, 1
  tail call void @test(i32 %6)
  unreachable

И при этом компилятор как раз предупредит о проблеме:

warning: function cannot return without recurring
 --> a.rs:2:1
  |
2 | / pub fn test(a: i32) -> ! {
3 | |     println!("a");
4 | |     test(a + 1)
5 | | }
  | |_^
  |
  = note: #[warn(unconditional_recursion)] on by default
note: recursive call site
 --> a.rs:4:5
  |
4 |     test(a + 1)
  |     ^^^^^^^^^^^
  = help: a `loop` may express intention better if this is on purpose

[@Virviil]

Но в функции же есть возврат — если аргумент равно нулю!
Другое дело, что до этого места никогда не доходит, но откуда об этом может знать компилятор?
Посмотрите пример с рандомом из соседней ветки — там даже есть реальный выход из функции, другое дело что переполнение стека по идее наступит раньше.

[@torkve]

откуда об этом может знать компилятор?

Он умный, такие проверки уже сто лет как есть.

там даже есть реальный выход из функции

Вероятно, это баг или разработчики ещё не оптимизировали это место в компиляторе. Попробуйте им зарепортить.

[@DarkEld3r]

не помню, есть ли в Rust про это какой-то стандарт, а в C это называлось бы UB

Стандарта у раста (пока) в принципе нет, но сейчас поведение определено следующим образом: в дебаге переполнения паникуют, в релизе поведение определено как "two's complement".

[@Akon32]

TCO, внезапно, нет и в Common Lisp (из-за динамических областей видимости, насколько я понимаю).

[@kez]

TCO не требуется по стандарту, но популярные реализации (тот же SBCL, CCL) имеют TCO.

Чуть подробнее по ссылке.

[@potan]

Я пытался поиграться с TCO — похоже, Rust его умеет, если ему не мешает RAII. То есть перед хвостовым вызовом надо сказать явно drop на все переменные, которые этот вызов не забирает. Но не уверен, что это гарантировано.

[@ozkriff]

https://github.com/rust-lang/rfcs/pull/1888 — без этого или аналогичного RFC сам язык гарантий не будет давать, все на милость LLVM.

[@Virviil]

Так в результате, это уже работает, или ещё нет? А то баг висит, РФЦ висит, но никто ничего не мержит и не принимает… Хотя было бы круто

[@ozkriff]

не работает, это даже еще не принятый RFC

[@splav_asv]

Видите эти 4 закрывающие скобочки вконце? Выглядят страшно. Не зря всётаки многие функциональные языки не пользуются скобками. Бррр…

С if let… {} else {} было бы на один уровень вложенности меньше.

[@ozkriff]

или можно вместо None => { CowVM{... было бы написать None => CowVM{...

[@Virviil]

Это не "пофункциональному". В некоторых языках if вообще нету

[@red75prim]

Полностью функционально без сборки мусора всё-равно не получится. Так почему-бы не использовать то, что есть?

[@Virviil]

Я не понял, при чём тут сборка мусора.

Но в любом случае задача была "сделать максимально по функциональному феншую"

[@ozkriff]

Я не понял, при чём тут сборка мусора.

Я вот не знаю ни одного чистого функционального языка общего назначения без сборки мусора — как оно работать-то должно?

[@Virviil]

Ну программу я же как-то написал. Все "нефункциональные вещи" — это заменил рекурсию на луп изза отсутствия ТСО, да ещё в массив писал через переменную.
Какая в общем то разница, как оно там внутри работает?

Вся фишка и программы и этой статьи — "пишем максимально по феншую, авось заработает. Надеемся что ниразу не придётся ни мутить переменную, ни писать лайфтаймы, на имплементить трейты"

[@ozkriff]

Но это же очень простая программа, я бы не экстраполировал сильно.

По моим наблюдениям за ржавой экосистемой и экспериментами людей — чем кода будет больше и чем он будет сложнее, тем в общем случае больше головной боли будут приносить попытки писать на ржавчине в чистом функциональном стиле. Язык-то таки задуман как императивный, просто с элементами функциональщины.

Неизменяемые структуры данных без GC или аналога, к примеру, очень быстро перестают быть хоть немного практичными.

И, кстати, типы высшего порядка так и не завезли все еще и не факт что вообще звезут, как раз из-за отсутствия сборки мусора :( .

[@splav_asv]

Если и завезут, то ATC судя по всему.

[@Virviil]

Так то ООП заносит ещё больше головной боли, как по мне.

Осталось только понять, как на нём писать. Я слишком молод, знаю только два подхода — либо ФП либо ООП. И ни один в Расте нормально почему-то не работает.

[@splav_asv]

А если не секрет, как основной функциональный язык? Я из функциональных только Хаскель более менее хорошо знаю, и после него и C++ гибридный вариант очень даже нравится. Как раз получается писать на верхнем уровне используя идеи ООП, а внизу пользоваться многими плюсам функционального подхода. Крупные проекты довольно хорошо иллюстрируют этот подход.

[@Virviil]

F#, Erlang/Elixir, Elm — из тех на чём писал. Вроде все работает пока что.

[@ozkriff]

если что, if let это просто тонкий сахар над match — https://doc.rust-lang.org/book/if-let.html