Maszyna SECD

Maszyna SECD jest wysoce wpływową ( patrz: § wkład Landina ) maszyną wirtualną i maszyną abstrakcyjną , przeznaczoną jako cel dla kompilatorów funkcjonalnego języka programowania . Litery oznaczają stos , środowisko , sterowanie , zrzut — wewnętrzne rejestry maszyny. Rejestry Stack, Control i Dump wskazują na (niektóre realizacje) stosów , a Environment wskazuje na (pewne realizacje) tablica asocjacyjna .

Maszyna była pierwszą specjalnie zaprojektowaną do oceny wyrażeń rachunku lambda . Został pierwotnie opisany przez Petera J. Landina w „The Mechanical Evaluation of Expressions” w 1964 r. Opis opublikowany przez Landina był dość abstrakcyjny i pozostawił wiele możliwości implementacji (jak semantyka operacyjna ).

Lispkit Lisp był wpływowym kompilatorem opartym na maszynie SECD, a maszyna SECD była używana jako cel dla innych systemów, takich jak Lisp/370. W 1989 roku naukowcy z University of Calgary pracowali nad sprzętową implementacją maszyny.

wkład Landina

DA Turner (2012) zwraca uwagę, że The Revised Report on Algol 60 ( Naur 1963) określa wywołanie procedury przez regułę kopiowania, która pozwala uniknąć przechwytywania zmiennych z systematyczną zmianą identyfikatorów. Ta metoda działa w implementacji Algola 60, ale w funkcjonalnym języku programowania, w którym funkcje są obywatelami pierwszej klasy, wolna zmienna na stosie wywołań może zostać błędnie wyłuskana.

Turner zauważa, że ​​Landin rozwiązał to za pomocą swojej maszyny SECD, w której zamiast tego funkcja jest reprezentowana przez zamknięcie na stercie.

Nieformalny opis

Kiedy rozpoczyna się ocena wyrażenia, wyrażenie jest ładowane jako jedyny element kontrolki C . Środowisko E , stos S i zrzut D zaczynają być puste.

Podczas obliczania C jest konwertowane do odwróconej notacji polskiej (RPN) z ap (dla apply ) jako jedynym operatorem. Na przykład wyrażenie F (GX) (pojedynczy element listy) jest zmieniane na listę X:G:ap:F:ap .

Ocena C przebiega podobnie do innych wyrażeń RPN. Jeśli pierwszy element w C jest wartością, jest odkładany na stos S . Dokładniej, jeśli element jest identyfikatorem, wartość umieszczona na stosie będzie powiązaniem dla tego identyfikatora w bieżącym środowisku E . Jeśli element jest abstrakcją, zamknięcie , aby zachować powiązania jego wolnych zmiennych (które znajdują się w E ) i to właśnie zamknięcie jest odkładane na stos.

Jeśli elementem jest ap , dwie wartości są zdjęte ze stosu i aplikacja jest zakończona (pierwsza zastosowana do drugiej). Jeśli wynikiem zastosowania jest wartość, jest ona umieszczana na stosie.

Jeśli jednak aplikacja jest abstrakcją do wartości, spowoduje to wyrażenie rachunku lambda, które samo w sobie może być aplikacją (a nie wartością), a zatem nie może zostać odłożone na stos. W tym przypadku bieżąca zawartość S , E i C jest wypychana na zrzut D (który jest stosem tych trójek), S jest ponownie inicjowany do opróżnienia, a C jest ponownie inicjowany do wyniku aplikacji z E zawierające środowisko dla wolnych zmiennych tego wyrażenia, uzupełnione o wiązanie, które wynikało z aplikacji. Następnie ocena przebiega jak powyżej.

Zakończona ocena jest wskazywana przez puste C , w którym to przypadku wynik będzie na stosie S . Ostatni zapisany stan oceny na D jest następnie zdejmowany, a wynik zakończonej oceny jest wypychany na zawartość stosu przywróconą z D . Ocena przywróconego stanu jest następnie kontynuowana jak powyżej.

Jeśli zarówno C , jak i D są puste, ogólna ocena została zakończona z wynikiem na stosie S .

Rejestry i pamięć

Maszyna SECD jest oparta na stosie . Funkcje pobierają swoje argumenty ze stosu. Argumenty instrukcji wbudowanych są kodowane bezpośrednio po nich w strumieniu instrukcji.

Podobnie jak wszystkie wewnętrzne struktury danych, stos jest listą, z rejestrem S wskazującym na początek lub nagłówek listy . Ze względu na strukturę listy stos nie musi być ciągłym blokiem pamięci, więc miejsce na stosie jest dostępne, o ile jest tylko jedna wolna komórka pamięci. Nawet jeśli wszystkie komórki zostały wykorzystane, wyrzucanie elementów bezużytecznych może zapewnić dodatkową wolną pamięć. Oczywiście, określone implementacje struktury SECD mogą implementować stos jako kanoniczną strukturę stosu, poprawiając w ten sposób ogólną wydajność maszyny wirtualnej, pod warunkiem ścisłego ograniczenia wymiaru stosu.

Rejestr C wskazuje początek kodu lub listy instrukcji, które będą oceniane. Po wykonaniu instrukcji C jest wskazywane na następną instrukcję na liście - jest to podobne do wskaźnika instrukcji (lub licznika programu ) w konwencjonalnych maszynach, z tym wyjątkiem, że kolejne instrukcje są zawsze określane podczas wykonywania i nie są domyślnie zawartych w kolejnych lokacjach pamięci, tak jak ma to miejsce w przypadku maszyn konwencjonalnych.

Bieżące środowisko zmiennych jest zarządzane przez rejestr E , który wskazuje na listę list. Każda pojedyncza lista reprezentuje jeden poziom środowiska: parametry bieżącej funkcji znajdują się w nagłówku listy, zmienne, które są wolne w bieżącej funkcji, ale są powiązane z otaczającą funkcją, znajdują się w innych elementach E .

Zrzut, na którego czele wskazuje rejestr D , służy do tymczasowego przechowywania wartości innych rejestrów, na przykład podczas wywołań funkcji. Można to porównać do stosu zwrotnego innych maszyn.

Organizacja pamięci maszyny SECD jest podobna do modelu używanego przez większość funkcjonalnych tłumaczy języka : pewna liczba komórek pamięci, z których każda może pomieścić albo atom ( prosta wartość, na przykład 13 ), albo reprezentować pustą lub nie- pusta lista. W tym drugim przypadku komórka zawiera dwa wskaźniki do innych komórek, jeden reprezentujący pierwszy element, a drugi reprezentujący listę z wyjątkiem pierwszego elementu. Te dwa wskaźniki są tradycyjnie nazywane car i cdr — ale bardziej nowoczesne terminy to head i tail są często używane zamiast nich. Różne typy wartości, które komórka może przechowywać, są rozróżniane za pomocą znacznika . Często rozróżnia się również różne typy atomów (liczby całkowite, łańcuchy itp.).

Tak więc lista zawierająca liczby 1 , 2 i 3 , zwykle zapisywana jako (1 2 3) , może być przedstawiona w następujący sposób: 

Zawartość znacznika adresu (wartość dla liczb całkowitych, samochód i cdr dla list) 9 [ liczba całkowita | 2 ] 8 [ liczba całkowita | 3 ] 7 [ lista | 8 | 0 ] 6 [ lista | 9 | 7 ] ... 2 [ lista | 1 | 6 ] 1 [ liczba całkowita | 1 ] 0 [ zero ]

Komórki pamięci od 3 do 5 nie należą do naszej listy, której komórki mogą być rozmieszczone losowo w pamięci. Komórka 2 jest nagłówkiem listy, wskazuje na komórkę 1, która zawiera wartość pierwszego elementu oraz listę zawierającą tylko 2 i 3 (zaczynając od komórki 6). Komórka 6 wskazuje na komórkę zawierającą 2 i na komórkę 7, która reprezentuje listę zawierającą tylko 3 . Robi to, wskazując komórkę 8 zawierającą wartość 3 i wskazując na pustą listę ( nil ) jako kmdr. W maszynie SECD komórka 0 zawsze niejawnie reprezentuje pustą listę, więc nie jest potrzebna żadna specjalna wartość znacznika, aby zasygnalizować pustą listę (wszystko, co może po prostu wskazywać na komórkę 0).

Zasada, że ​​cdr w komórce listy musi wskazywać na inną listę, jest tylko konwencją. Jeśli zarówno car, jak i cdr wskazują na atomy, otrzymamy parę, zwykle zapisaną jako (1 . 2)

Instrukcje

  • nil umieszcza zerowy wskaźnik na stosie
  • ldc umieszcza stały argument na stosie
  • ld odkłada wartość zmiennej na stos. Zmienna jest wskazywana przez argument, parę. Samochód pary określa poziom, cdr pozycję. Tak więc (1 . 3) daje trzeci parametr bieżącej funkcji (poziom 1).
  • sel oczekuje dwóch argumentów listy i pobiera wartość ze stosu. Pierwsza lista jest wykonywana, jeśli wyskakująca wartość była różna od zera, druga lista w przeciwnym razie. Zanim jeden z tych wskaźników listy zostanie utworzony nowy C , wskaźnik do instrukcji następującej po na zrzucie
  • join wyskakuje odwołanie do listy ze zrzutu i czyni to nową wartością C . Ta instrukcja występuje na końcu obu alternatyw sel .
  • ldf przyjmuje jeden argument listowy reprezentujący funkcję. Konstruuje zamknięcie (parę zawierającą funkcję i bieżące środowisko) i umieszcza je na stosie.
  • ap wyskakuje zamknięcie i listę wartości parametrów ze stosu. Zamknięcie jest stosowane do parametrów poprzez zainstalowanie jego środowiska jako bieżącego, wysunięcie listy parametrów przed nim, wyczyszczenie stosu i ustawienie C na wskaźnik funkcji zamknięcia. Poprzednie wartości S , E i następna wartość C są zapisywane na zrzucie.
  • ret zdejmuje jedną zwracaną wartość ze stosu, przywraca S , E i C ze zrzutu i umieszcza zwróconą wartość na bieżącym stosie.
  • dum wypycha „manekin”, pustą listę, przed listą środowiska.
  • rap działa jak , tyle że zastępuje wystąpienie atrapy środowiska bieżącym, umożliwiając w ten sposób funkcje rekurencyjne p {\ displaystyle ap

Istnieje wiele dodatkowych instrukcji dla podstawowych funkcji, takich jak car, cdr, konstrukcja listy, dodawanie liczb całkowitych, I/O itp. Wszystkie pobierają niezbędne parametry ze stosu.

Zobacz też

Dalsza lektura

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=SECD_machine&oldid=1105244250 ”