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

Комментарии (4)

  • 22 мая 2017 в 12:34

    +1

    ↑

    ↓

    В 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 (…), а просто (), пустая инструкция, такой код вообще по идее не должен скомпилироваться, потому что возвращаемое значение не совпадает с сигнатурой функции. То ли по какой-то иной причине не отработала оптимизация.

    • 22 мая 2017 в 12:58

      0

      ↑

      ↓

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


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

      • 22 мая 2017 в 13:09

        0

        ↑

        ↓

        Так, а где увас выход из рекурсии в примере? 
        if i == 0 {
        1
    }

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

  • 22 мая 2017 в 13:15

    0

    ↑

    ↓

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

© Habrahabr.ru