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

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

17 голосов
/ 14 мая 2011

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

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

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

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

Ответы [ 3 ]

10 голосов
/ 15 мая 2011

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

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

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

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: Не-хвостовая рекурсия будет по-прежнему потреблять память, даже если она не находится в стеке.

4 голосов
/ 15 мая 2011

Если вас интересуют методы реализации переводчиков, есть нет способа обойти книгу Кристиана Квиннека "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

имеет немало статей по оптимизации хвостовых вызовов.

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

4 голосов
/ 15 мая 2011

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

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

...