Каковы некоторые хорошие способы реализации исключения хвостовых вызовов?

Я написал небольшой интерпретатор Scheme в безобразной смеси C/C++, но мне еще предстоит реализовать правильные хвостовые вызовы.

Я знаю о классическом Чейни о алгоритме MTA, но есть ли другие хорошие способы реализации этого? Я знаю, что мог бы поместить стек Scheme в кучу, но это все равно не будет правильным исключением, так как стандарт говорит, что нужно поддерживать неограниченное количество активных оконечных вызовов.

Я также возился с longjmps, но до сих пор думаю, что это будет хорошо работать только для невзаимных рекурсивных хвостовых вызовов.

Как основные схемы на основе C реализуют правильную хвостовую рекурсию?

Источник

3 ответа

Решение

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

Сначала вам придется написать все в стиле продолжения, что может быть странно думать и делать на C/C++. Учебное пособие Дэна Фридмана по ParentheC поможет вам преобразовать высокоуровневую рекурсивную программу в форму, которая может быть переведена машиной на C.

В конце концов, вы по существу реализуете простую виртуальную машину, где вместо обычных вызовов функций для выполнения eval, applyProc и т. Д. Вы передаете аргументы, устанавливая глобальные переменные, а затем выполняете goto к следующему аргументу (или используйте цикл верхнего уровня и программный счетчик)...

return applyProc(rator, rand)

становится

reg_rator = rator
reg_rand = rand
reg_pc = applyProc
return

То есть все ваши функции, которые обычно вызывают друг друга рекурсивно, сводятся к псевдосборке, в которой они являются просто блоками кода, которые не повторяются. Цикл верхнего уровня управляет программой:

for(;;) {
  switch(reg_pc) {
    case EVAL:
      eval();
      break;
    case APPLY_PROC:
      applyProc();
      break;
    ...
  }
}

Редактировать: я прошел тот же процесс для моего хобби интерпретатора Scheme, написанного на JavaScript. Я воспользовался многими анонимными процедурами, но это может помочь в качестве конкретной ссылки. Посмотрите историю коммитов FoxScheme, начиная с 2011-03-13 (30707a0432563ce1632a) и заканчивая 2011-03-15 (5dd3b521dac582507086).

Редактировать ^2: нехвостовая рекурсия будет по-прежнему использовать память, даже если она не находится в стеке.

Источник

Не зная, что у вас есть, я бы сказал, что самый простой (и самый поучительный) способ сделать это - реализовать компилятор схемы и виртуальную машину из Dybvig "Три модели реализации для схемы".
Я сделал это здесь, в Javascript (там же есть копия PDF-файла Дибвига): https://github.com/z5h/zb-lisp

проверьте src/compiler.js: compileCons и реализацию "кодов операций" в src/vm.js

Источник

Если вы заинтересованы в методах реализации интерпретаторов, нет пути обойти книгу Кристиана Квиннека "LiSP - Лисп в маленьких частях". Это объясняет все аспекты реализации системы Scheme очень тщательно с полным кодом. Это прекрасная книга.

http://www.amazon.com/exec/obidos/ASIN/0521562473/qid=945541473/sr=1-2/002-2995245-1849825

Но не забудьте проверить документы на ReadScheme.org.

Секция

Технология компиляции / Методы реализации и оптимизации http://library.readscheme.org/page8.html

Есть довольно много работ по оптимизации хвостового вызова.

Среди прочего вы найдете ссылку на тезис Дибвига (классический), который очень хорошо написан. Это объясняет и мотивирует все очень четко.

Источник
Другие вопросы по тегам