W maszynie SECD, jak działa "rap"?

Question

Piszę simulator of the SECD machine w języku C# z przewodnikiem description on Wikipedia. Mam podstawowe operacje zakończone, ale nie jestem pewien, jak wdrożyć instrukcję rap.

Na Wikipedia mówi o rap:

rap działa jak AP, tylko, że zastępuje wystąpienie manekina środowiska z obecnym, a tym samym rekurencyjnych funkcji możliwe

a dla ap mówi:

ap powoduje zamknięcie i listę wartości parametrów ze stosu. Zamknięcie jest stosowane do parametrów, instalując środowisko jako bieżące, przesuwając listę parametrów przed tą, usuwając stos i ustawiając C na wskaźnik funkcji zamknięcia. Poprzednie wartości S, E i następna wartość C są zapisywane na zrzucie.

Oto moja realizacja 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; 
    } 

Zauważ, że List moja implementacja Lisp stylu "przeciw" komórki.

Co mnie dezorientuje, to czym różni się rap od ap? Na przykład, co dokładnie dzieje się z rejestrem środowiska (E)? Uważam, że definicja Wikipedii jest nieco niejednoznaczna i nie udało się znaleźć niczego innego, co by ją dobrze tłumaczyło.

Answer 1

SECD nie jest rekursywny, ale można zbudować a tail recursive SECD machine (PDF).

Instrukcja AP służy do kompilacji wiązania let, a instrukcja RAP służy do kompilowania wiązania letrec.

"letrec" różni się od "let", ponieważ można "zobaczyć" środowisko, w którym zdefiniowana jest funkcja rekursywna, dzięki czemu można go wywoływać rekurencyjnie (np. Zdefiniować funkcję "czynnikową" i może wywołać to w treści funkcji).

RAP modyfikuje środowisko, dzwoniąc do rplaca (podobnie jak w przypadku Sceny). Wcześniejsza instrukcja DUM dodaje samochód "dummy" do środowiska (który nigdy nie jest używany), a RAP usuwa ten "fałszywy" "samochód" w środowisku i zastępuje go odpowiednim.

przejścia państwowe są tak:

 
((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) 

Zobacz także Revisiting SECD and the power of Lisp, cytując:

Dyspozycja RAP jest używany w celu wspierania rekurencyjnych wywołań funkcji i prace zastępując uprzednio utworzoną obojętne środowisko na stosie , zwany OMEGA, przez taki, który zawiera wszystkie funkcje, które są widoczne w zakresie rekursywnym. Specyfikacja używa RPLACA do oznaczenia tej operacji wymiany i to jest ta, której używaliśmy w naszej implementacji SECD w Lisp: ...

i

Gdy próbuje wdrożyć RAP w Erlang, utknąłem ponieważ nie istnieją żadne destrukcyjne operacje na listach. Nie w standardowym interfejsie API, a także w interfejsie API systemu. Tak więc, Erlang SECD wygląda ładnie, tylko że nie działa.

Answer 2

Powinieneś naprawdę odebrać kopię pięknej książki Petera Hendersona "Zastosowanie i implementacja programowania funkcjonalnego". W nim skrupulatnie opisuje i buduje maszynę SECD oraz Lispkit Lisp.

Answer 3

Oprócz doskonałej, zaakceptowanej odpowiedzi, chciałem podać więcej wyjaśnień, dlaczego wymagane jest rap.

Środowisko (E w SECD) przechowuje wszystkie utrwalone elementy (funkcje, stałe, zmienne itp.). E jest zasadniczo zbiorem list. Rzeczy w E są ładowane na stos S, a następnie wykonywane lub używane przez polecenia w C. Wszystko w E otrzymuje identyfikator, dzięki czemu można się z nim później odwołać. Ten identyfikator jest zwykle krotką (x,y), gdzie x reprezentuje położenie listy na stosie, a y reprezentuje pozycję na tej liście.

W typowym wywołaniu funkcji, nowa lista jest popychany na E i teraz wszelkie zmienne lokalne mogą mieć identyfikatory jak (|E|, y), gdzie |E| oznacza rozmiar E. Jest to jednak bardzo problematyczne dla funkcji rekursywnych, ponieważ rozmiar stosu rośnie wraz z każdym wywołaniem funkcji, więc nie ma możliwości przypisania zmiennych użytecznych zmiennych lokalnych.

Aby rozwiązać ten problem, rap ma większość rzeczy ap robi, ale zamiast pchania nową listę na stos środowiska, zastępuje to, co jest w głowie E z nowej listy środowiska.