Оптимизация хвостовой рекурсии

и? по ссылке куча нубья, что дальше?

Ага, они так и не заметили, что Nemerle развернул рекурсию в цикл, и, соответственно, работы префикса .tail в .NET они там пронаблюдать никак не могли.

я совсем тупой наверное но дизассемблированного
кода немерле по ссылке не вижу.

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

не на чем проверять

Эм... Хвостовую рекурсию вроде оптимизирует компилятор, а не виртуальная машина.

> Эм... Хвостовую рекурсию вроде оптимизирует компилятор, а не виртуальная машина.

вот этот пункт по ссылке мене просто добил, тоже. Они не предполагают что компилятор может сворачивать не хвосотвую рекурсию в хвостовую, используя ассоциативности и нулевые/еденичные элементы, поэтому и выдвинули херню про поддержку оной непосредственно в .net.

> поэтому и выдвинули херню про поддержку оной непосредственно в .net.

Это не херня. .NET поддерживает хвостовые вызовы (вовсе не обязательно рекурсивные), см. префикс .tail.

При этом, компилятор далеко не всегда может развернуть хвостовой вызов в цикл - например: (define (f g x) (g (something x)))

Здесь вызов g хвостовой, но g в момент компиляции неизвестно. Для таких случаев и необходима поддержка хвостовых вызовов со стороны VM. И то, что говножабка этого не умеет - огромный минус для неё.

Но естественно, в их примитивном примере компилятор всё прекрасно разворачивает в один цикл.

> При этом, компилятор далеко не всегда может развернуть хвостовой вызов в цикл - например: (define (f g x) (g (something x)))

Не понятно почему это не всегда можно развернуть в цикл, на то она и хвостовая, и что в этом примере помешает комплятору сделать это?

> Не понятно почему это не всегда можно развернуть в цикл, на то она и хвостовая, и что в этом примере помешает комплятору сделать это?

Посмотри внимательнее - g неизвестно, это аргумент функции. В .net это может быть вызов виртуального метода объекта (какого - заранее неизвестно), или даже Calli на intptr (возможно даже где-то в unmanaged коде). Это не рекурсивный вызов, это просто хвостовой вызов. Который, однако, может быть и рекурсивным, если эта неизвестная g где-то там вызывает f. И на этапе компиляции раскрыть все эти возможные пути в один гигантских размеров метод просто невозможно - если только ты весь код не приводишь в один метод с кучей goto и с симуляцией стека вызовов.

>> например: (define (f g x) (g (something x)))

> Не понятно почему это не всегда можно развернуть в цикл, на то она и хвостовая, и что в этом примере помешает комплятору сделать это?

например то, что в этом примере рекурсии нет.

(либо она может быть, например если something где-то вызывает f,
но это может быть неизвестно на этапе компиляции, например если
something это параметр)

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

Рекурсию, насколько я знаю, _всегда_ можно развернуть в цикл. Но
>нередко такие циклы получаются не менее затратны, чем чистая
>рекурсия :)

Пример, скажем, функция Аккермана:

let rec a n x y =
    match (n, y) with
        (0, y) -> x+1
      | (1, 0) -> x
      | (2, 0) -> 0
      | (3, 0) -> 1
      | (n, 0) -> 2
      | (n, y) -> (a (n-1) (a n x (y-1)) x)
    ;;


print_int(a 3 8 8);
print_newline();;

> Пример, скажем, функция Аккермана
> let rec a n x y =
> { ... }

Насколько я понимаю, это можно разложить в n вложенных циклов.

> разложить в n вложенных циклов

но ведь n параметр функции?

>> разложить в n вложенных циклов

> но ведь n параметр функции?

Я видел разложение этой функции в циклы на Си. Как - уже не помню деталей. Работало оно немного дольше рекурсивного алгоритма и потребляло столько же памяти :D

На Lisp можно написать макрос ;)