Поиск ссылок, описывающих оптимизацию хвостовой рекурсии через исключения - PullRequest
2 голосов
/ 24 сентября 2011

Я реализовал небольшой интерпретатор lisp (sapid lisp в google code) в самом python и sapid lisp. Возможно, его основной характеристикой является реализация хвостовой и взаимной рекурсии с помощью исключений. Подробности реализации здесь https://sites.google.com/site/sapidlisp/recursion-optimization.

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

Я нашел похожую технику, используемую в декораторе Python (http://code.activestate.com/recipes/474088/). Теперь, чтобы поместить технику в ее контекст, я ищу ссылки, описывающие такую ​​технику для lisp или других интерпретируемых языков. Любая информация?

Ответы [ 2 ]

4 голосов
/ 25 сентября 2011

См. Ответ Илии. Но, чтобы добавить немного больше контекста, Бейкер Чейни о технике MTA был хорошо известным приемом для реализации правильной рекурсии хвоста, которая использовала стек C в качестве детского (как в GC поколений) для кадров продолжения и других объекты. Вместо того, чтобы держать стек небольшим (как это делают большинство реализаций хвостовой рекурсии), этот метод позволяет стеку некоторое время расти, а затем очищает его большим скачком (longjmp, execption, что угодно) время от времени. И прежде чем очистить стек, вы копируете все живые вещи из него в кучу.

Это прекрасно работает, если вы можете и хотите отслеживать стек и копировать объекты из стека в кучу. В статье Eli cited (Продолжение обобщенной проверки стека) рассказывается об адаптации трюка к «управляемым» платформам, где вы не можете проверить стек напрямую.

3 голосов
/ 25 сентября 2011

См. Продолжения Обобщенной проверки стеков Петтиджоном и др. И связанное приложение Джо Маршалла.

("интерпретировано", что бы это ни значило в наши дни, не имеет ничего общего с предметом.)

...