односвязные списки

>Дотнетовский F# умеет (компилятор вставляет специальный тег .tail в генерируемый байт-код IL, а CLR о нем знает).

можно сразу простейший пример двух _нелокальных_ (public?) взаимнорекурсивных функций и тест их?

Среди реализаций CL умеет SBCL, если не ошибаюсь.

Очень сомневаюсь именно во взаиморекурсивности

Должен уметь и хаскелевский GHC, но специально не проверял.

Не удивлюсь если это так, но «один в поле не воин» =)

> можно сразу простейший пример двух _нелокальных_ (public?) взаимнорекурсивных функций и тест их?

Объявляешь функции в модуле.

>>Среди реализаций CL умеет SBCL, если не ошибаюсь.

>Очень сомневаюсь именно во взаиморекурсивности

Срабатывает. Как-то натыкался. Был приятно удивлен.

Тут дело не столько в самой взаимной рекурсивности, сколько в том, чтобы хвостовой вызов срабатывал для функции, определенной извне (именно поэтому я попросил сишные функции разнести по разным модулям компиляции). Это очень важно для продолжений. Очевидно, если такой хвостовой вызов работает, то и работает взаимная рекурсия, независимо от того, открыты или локальны функции (.NET налагает жесткое требование - такой вызов должен быть помечен атрибутом .tail в байт-коде).

В случае локальных функций компилятор F# может произвести жесткую оптимизацию и заменить всю рекурсию циклом, даже для нескольких зависимых функций. Но факт в том, что TCО будет работать даже без такой оптимизации (в свойствах проекта выставить свойство «TailCall», а сам проект компилировать в режиме «Debug»).

>Срабатывает. Как-то натыкался. Был приятно удивлен.

Хм, очень странно... Там jamp на funcall (или его «внутренний» аналог)?

Ладно, будет не лень - поковыряю...

В случае локальных функций компилятор F# может произвести жесткую оптимизацию и заменить всю рекурсию циклом, даже для нескольких зависимых функций.

для нелокальных функций это дублирование кода... Этим хотелось бы как-то управлять...

Но факт в том, что TCО будет работать даже без такой оптимизации (в свойствах проекта выставить свойство «TailCall», а сам проект компилировать в режиме «Debug»).

А без дебага TCO не работает?

> Хм, очень странно... Там jamp на funcall (или его «внутренний» аналог)?

Тоже есть сомнения. Но у меня почему-то сработало. Да и продолжения сработали в СL однажды как надо. Опять же в пользу. В общем, изучать надо отдельно :)

> для нелокальных функций это дублирование кода... Этим хотелось бы как-то управлять...

Почему дублирование? Должен получиться чистый и незаоптимизированный компилятором хвостовой вызов, который виртуальная машина и распознает.

Кстати, оптимизация TCO должна быть очень нетривиальной вещью. В .NET к ней шли долго (пришли ли ??). В четвертой версии для x64 срабатывает чаще, но медленней в тех случаях, в которых срабатывало раньше. А в mono хвостовой вызов работает ужасно медленно. По моим тестам разница на порядок (я измерял совсем другое, но все в итоге свелось именно к разнице в реализации TCO).

> А без дебага TCO не работает?

Если быть точнее, то нужно отключить оптимизацию кода, но поставить галочку напротив опции хвостовой рекурсии. Код проверял рефлектором. Компилятор F# ничего такого особенного уже не делает, в циклы рекурсию не превращает, но добавляет к хвостовому вызову атрибут .tail. Мне самому тогда было интересно. Да и многого недопонимал тогда в этом вопросе :)

> А без дебага TCO не работает?

В общем, эти вещи независимы в F#. Хотя в релизе компилятор может превратить даже взаимную локальную рекурсию в цикл.

>Почему дублирование? Должен получиться чистый и незаоптимизированный компилятором хвостовой вызов, который виртуальная машина и распознает.

а, я «для локальных» не заметил =)

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

ну для умного компилятора это то как раз не диво... Диво, что умеющих TCO (а не просто зацикливание хвостовой рекурсии) меньше, чем пальцев на одной руке...

> а, я «для локальных» не заметил =)

Будет и для них, если отключишь оптимизацию кода (один тег в файле проекта). Без оптимизации почти все остается как есть. Но с TCO ;)