Zrozumienie STG

Masz rację co do "Spineless", to jest to, jeśli mam rację. Jest ona zasadniczo opisana w artykule Burna, Peyton-Jonesa i Robsona z 1988 roku, "The Spineless G-Machine". Czytałem, ale nie jest tak świeży w moim umyśle. Zasadniczo na maszynie G wszystkie wpisy stosu wskazują węzeł aplikacji, z wyjątkiem tego na górze, który wskazuje na główkę wyrażenia. Te węzły aplikacji sprawiają, że dostęp do argumentów jest pośredni, a w niektórych opisach G-Machine, przed zastosowaniem funkcja stos jest przestawiany tak, że ostatnie węzły N na stosie mają wskazywać na argument zamiast węzła aplikacji. Jeśli się nie mylę, część "Spineless" polega na unikaniu posiadania tych węzłów aplikacji (które są nazywane kręgosłupem grafu) na stosie w ogóle, unikając w ten sposób tego ponownego ułożenia przed każdą redukcją.

Co do części "bez tagów", to teraz masz więcej racji niż kiedyś, ale... Używanie znaczników na węzłach jest bardzo, bardzo starą rzeczą. Can myślisz o tym, jak zaimplementowano dynamicznie pisany język, taki jak LISP? Każda komórka musi mieć swoją wartość i znacznik, który mówi Typ. Jeśli chcesz czegoś, musisz zbadać tag i postępować zgodnie z nim. W przypadku Haskella stan oceny jest ważniejszy niż typ, Haskell jest typowany statycznie.

W maszynie STG znaczniki nie są używane. Znaczniki zostały zastąpione, być może w wyniku inspiracji oo lanaguages, zestawem wskaźników funkcji. Gdy chcesz mieć wartość węzła, który ma nie został obliczony, funkcja obliczy go. Gdy jest już obliczona, funkcja zwraca ją. Pozwala to na dużą kreatywność w tym, co ta funkcja może zrobić, nie czyniąc kodu klienta bardziej skomplikowanym.

Ta część "bez tagów" jest opisana w artykule" implementacja języków funkcyjnych na stockowym sprzęcie " autorstwa SPJ.

Istnieje również sprzeciw wobec tego" bez znaczników". Zasadniczo obejmuje to Wskaźniki funkcji, które są pośrednim skokiem w architekturze komputera warunki. A skoki pośrednie są przeszkodą do przewidywania gałęzi, a tym samym do pipelining w ogóle. Ponieważ albo Architektura uważa, że istnieje zależność danych od argumentu jump, co powoduje zatrzymanie potoku, albo Architektura zakłada, że nie zna on miejsca docelowego i zatrzymuje potok.

Chcesz przeczytać książkę SPJ o funkcjonalnej implementacji PL:

• http://research.microsoft.com/en-us/um/people/simonpj/papers/slpj-book-1987/index.htm

ODPOWIEDŹ migle jest dokładnie tym, co oznacza bezinteresowność i bezinteresowność stgm. Dziś nie warto próbować zrozumieć nazw dwóch funkcji, ponieważ nazwy pochodzą z historii technologii redukcji grafów: od G-machine, bezgłośnej g-machine oraz bezgłośnej i bezgłośnej g-machine.

G-machine używa zarówno kręgosłupa, jak i znaczników. Kręgosłup jest listą krawędzi od węzła głównego aplikacji funkcji do węzła funkcji. Na przykład funkcja zastosowanie "f e1 e2 ... en " jest reprezentowane jako

root = AP left_n en
left_n = AP left_n-1 en-1 ...
left_2 = AP left_1 e1
left_1 = FUN f

W G-maszynie, a więc kręgosłup jest listą krawędzi składającą się z left_n- > left_n-1 ->... - >left_2 - > left_1. Jest to dosłownie kręgosłup aplikacji funkcji!

W tej samej aplikacji funkcyjnej znajdują się tagi AP i FUN.

W następnej zaawansowanej maszynie G, tzw. maszynie G Bezrękawnikowej, nie ma takiego kręgosłupa, reprezentując taką aplikację funkcji w sąsiednim bloku, którego pierwszy slot wskazuje na f, drugi slot wskazuje na e1, ..., A N+1-ten slot wskazuje na en. W tej reprezentacji nie potrzebujemy kręgosłupa. Ale blok uruchamia specjalny znacznik oznaczający liczbę slotów i tak dalej.

W najbardziej zaawansowanej maszynie G, tzw. maszynie bezdętkowej, taki znacznik jest zastępowany wskaźnikiem funkcji. Aby ocenić aplikację funkcji, należy przejść do kodu za pomocą wskaźnika funkcji.

Niefortunnie okazuje się, że papier STGM Simone Peyton Jones nie podaj zasady kompilacji/oceny na jakimś abstrakcyjnym poziomie, a więc jest to bardzo naturalne dla ludzi, aby nie byli łatwymi do zrozumienia istotą STGM.