В SECD Machine, как работает "рэп"? - PullRequest
Новая
       68

В SECD Machine, как работает "рэп"?

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

Я пишу симулятор 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 это моя реализация ячейки "cons" в стиле Lisp.

Что меня смущает, так это то, чем rap отличается от ap?Например, что именно происходит с регистром среды (E)?Я нахожу определение в Википедии несколько двусмысленным и не смог найти ничего другого, что бы это хорошо объясняло.

Ответы [ 3 ]

8 голосов
/ 02 октября 2011

SECD не является хвостовой рекурсией, хотя вы можете построить хвостовую рекурсивную машину SECD (PDF) .

Инструкция AP используется для компиляции привязки let, тогда как инструкция RAP используется для компиляции привязки letrec.

«letrec» ​​отличается от «let», потому что вы можете «видеть» среду, в которой определена рекурсивная функция, так что вы можете вызывать ее рекурсивно (например, вы определяете функцию 'factorial' и можете вызовите его в теле функции).

RAP изменяет среду, вызывая rplaca (аналогично setcar! В схеме). Предыдущая инструкция DUM добавляет в среду «фиктивный» автомобиль (который никогда не используется), а RAP удаляет этот «фиктивный» автомобиль в среде и заменяет его на соответствующий.

Переходы состояний выглядят так: 

((c'.e')v.s) e               (AP.c)  d         =>
NIL          (v.e')          c'      (s e c.d)

((c'.e')v.s) (?.e)           (RAP.c) d         =>
NIL          (setcar! e',v)  c'      (s e c.d)

См. Также Пересмотр SECD и мощности Lisp , цитата:

Инструкция RAP используется для поддержки рекурсивных вызовов функций и работает путем замены ранее созданной фиктивной среды в стеке, называемой OMEGA, на ту, которая содержит все функции, видимые в рекурсивной области. Спецификация использует RPLACA для обозначения этой операции замены, и это то, что мы использовали в нашей реализации SECD на Lisp:

и

При попытке реализовать RAP в Erlang я застрял, потому что в списках нет разрушительных операций. Не в стандартном API и, похоже, не в системном API. Итак, Erlang SECD выглядит красиво, только не запускается.
4 голосов
/ 02 октября 2011

Вы действительно должны взять копию замечательной маленькой книги Питера Хендерсона "Применение и внедрение функционального программирования". В ней он тщательно описывает и создает SECD-машину и Lispkit Lisp.

2 голосов
/ 19 октября 2016

В дополнение к превосходному принятому ответу, я хотел бы дать больше объяснения, почему rap требуется.

Среда (E в SECD) хранит все постоянные объекты (функции, константы, переменные и т. Д.). E - это, по сути, стек списков. Вещи в E загружаются в стек S и затем выполняются или используются командами в C. Все в E имеет идентификатор, чтобы на него можно было ссылаться позже. Этот идентификатор обычно является кортежем (x,y), где x представляет местоположение списка в стеке, а y представляет позицию в этом списке.

При типичном вызове функции новый список помещается на E, и теперь любые локальные переменные могут иметь идентификаторы, например (|E|, y), где |E| обозначает размер E. Однако это очень проблематично для рекурсивных функций, поскольку размер стека увеличивается с каждым вызовом функции, поэтому нет возможности назначить локальным переменным идентификаторы, которые можно использовать.

Чтобы решить эту проблему, rap выполняет большинство действий ap, но вместо того, чтобы помещать новый список в стек среды, он заменяет все, что находится в начале E, на новый список среды. ,

...