Ага, они так и не заметили, что Nemerle развернул рекурсию в цикл, и, соответственно, работы префикса .tail в .NET они там пронаблюдать никак не могли.
> Эм... Хвостовую рекурсию вроде оптимизирует компилятор, а не виртуальная машина.
вот этот пункт по ссылке мене просто добил, тоже. Они не предполагают что компилятор может сворачивать не хвосотвую рекурсию в хвостовую, используя ассоциативности и нулевые/еденичные элементы, поэтому и выдвинули херню про поддержку оной непосредственно в .net.
> поэтому и выдвинули херню про поддержку оной непосредственно в .net.
Это не херня. .NET поддерживает хвостовые вызовы (вовсе не обязательно рекурсивные), см. префикс .tail.
При этом, компилятор далеко не всегда может развернуть хвостовой вызов в цикл - например: (define (f g x) (g (something x)))
Здесь вызов g хвостовой, но g в момент компиляции неизвестно. Для таких случаев и необходима поддержка хвостовых вызовов со стороны VM. И то, что говножабка этого не умеет - огромный минус для неё.
Но естественно, в их примитивном примере компилятор всё прекрасно разворачивает в один цикл.
> Не понятно почему это не всегда можно развернуть в цикл, на то она и хвостовая, и что в этом примере помешает комплятору сделать это?
Посмотри внимательнее - g неизвестно, это аргумент функции. В .net это может быть вызов виртуального метода объекта (какого - заранее неизвестно), или даже Calli на intptr (возможно даже где-то в unmanaged коде). Это не рекурсивный вызов, это просто хвостовой вызов. Который, однако, может быть и рекурсивным, если эта неизвестная g где-то там вызывает f. И на этапе компиляции раскрыть все эти возможные пути в один гигантских размеров метод просто невозможно - если только ты весь код не приводишь в один метод с кучей goto и с симуляцией стека вызовов.
> Не понятно почему это не всегда можно развернуть в цикл, на то она и хвостовая, и что в этом примере помешает комплятору сделать это?
например то, что в этом примере рекурсии нет.
(либо она может быть, например если 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();;
Я видел разложение этой функции в циклы на Си. Как - уже не помню деталей. Работало оно немного дольше рекурсивного алгоритма и потребляло столько же памяти :D