В SECD Machine как работает рэп?
Я пишу симулятор SECD-машины на C#, руководствуясь описанием в Википедии. У меня завершены основные операции, но я не уверен, как реализовать rap инструкция.
В Википедии говорится о rap:
рэп работает как ap, только то, что заменяет вхождение фиктивной среды на текущую, что делает возможными рекурсивные функции
И для ap это говорит:
ap открывает закрытие и список значений параметров из стека. Замыкание применяется к параметрам, устанавливая его окружение как текущее, выдвигая перед ним список параметров, очищая стек и устанавливая C для указателя функции замыкания. Предыдущие значения S, E и следующее значение C сохраняются в дампе.
Вот моя реализация ap
public void ap()
{
Push(S, ref D);
Push(E, ref D);
Push(C, ref D);
List closure = Pop(ref S);
List paramlist = Pop(ref S);
E = closure.Tail;
Push(paramlist, ref E);
C = closure.Head;
S = List.Nil;
}
Обратите внимание, что List моя реализация "против" ячейки в стиле Lisp.
Что смущает меня именно как rap отличается от ap? Например, что именно происходит с регистром среды (E)? Я нахожу определение в Википедии несколько двусмысленным и не смог найти ничего другого, что бы это хорошо объясняло.
3 ответа
SECD is not tail recursive, although you can build a tail recursive SECD machine (PDF).
The AP instruction is used to compile a 'let' binding whereas the RAP instruction is used to compile a 'letrec' binding.
'letrec' is different from 'let' because you can 'see' the environment where the recursive function is defined, so that you can call it recursively (so, for instance, you define a 'factorial' function and you can call it in the body of the function).
RAP изменяет среду, вызывая rplaca (аналогично setcar! В схеме). Предыдущая инструкция DUM добавляет в среду "фиктивный" автомобиль (который никогда не используется), а RAP удаляет этот "фиктивный" автомобиль в среде и заменяет его соответствующим.
Состояния переходов таковы:
((c'.e ') vs) e (AP.c) d => NIL (v.e') c' (s e cd) ((c'.e ') vs) (?.e) (RAP.c) d => NIL (setcar! E ', v) c' (sed)
Смотрите также Revisiting SECD и мощь Lisp, цитируя:
Инструкция RAP используется для поддержки рекурсивных вызовов функций и работает путем замены ранее созданной фиктивной среды в стеке, называемой OMEGA, на ту, которая содержит все функции, видимые в рекурсивной области. Спецификация использует RPLACA для обозначения этой операции замены, и это то, что мы использовали в нашей реализации SECD на Lisp:
а также
При попытке реализовать RAP в Erlang я застрял, потому что в списках нет разрушительных операций. Не в стандартном API и, похоже, не в системном API. Итак, Erlang SECD выглядит красиво, только не запускается.
Вы действительно должны взять копию замечательной маленькой книги Питера Хендерсона "Применение и внедрение функционального программирования". В нем он тщательно описывает и создает SECD-машину и Lispkit Lisp.
В дополнение к превосходному принятому ответу, я хотел бы дать больше объяснения того, почему rap необходимо.
Окружающая среда (E в SECD) хранит все постоянные объекты (функции, константы, переменные и т. д.). E по сути, это стек списков. Вещи в E загружаются в стек S а затем выполняется или используется командами в C, Все в E дается идентификатор, чтобы на него можно было ссылаться позже. Этот идентификатор обычно является кортежем (x,y), где x представляет местоположение списка в стеке, и y представляет позицию в этом списке.
При типичном вызове функции добавляется новый список E и теперь любые локальные переменные могут иметь идентификаторы, такие как (|E|, y), где |E| обозначает размер E, Однако это очень проблематично для рекурсивных функций, поскольку размер стека увеличивается с каждым вызовом функции, поэтому нет возможности назначить локальным переменным идентификаторы, которые можно использовать.
Для решения этой проблемы, rap делает большинство вещей ap делает, но вместо того, чтобы помещать новый список в стек среды, он заменяет все, что находится во главе E с новым списком среды.