nie używa się garbage collector w implementacji Scheme/Lisp

Dla mojego projektu klasy, muszę zaimplementować (prosty) kompilator Scheme.nie używa się garbage collector w implementacji Scheme/Lisp

W tym momencie mam burzę mózgów, w jaki sposób mogę wdrożyć różne funkcje.

Dlaczego typowe wdrożenia Schematu zawracają sobie głowę skomplikowanym GC? Jeśli kod jest naprawdę funkcjonalny (brak efektów ubocznych), wówczas nieistniejąca funkcja nie może utrzymać przydzielonej pamięci. Zawsze! (chyba że jest to przeciek!)

Dlatego też, po prostu nie używaj strategii, której używają najbardziej niezbędne języki, np. C, czyli alokacji stosów. Za każdym razem, gdy wprowadzany jest nowy kontekst leksykalny (np. (define (foo ..) lub (letrec ...), przydziel pamięć zmiennych na stosie, a następnie po prostu dostosuj wskaźnik stosu po wyjściu kontekstu.

Ponieważ schemat nie ma wartości malloc() i umożliwia przydzielanie tylko wstępnie zdefiniowanych typów, prosta implementacja może korzystać z puli lub alokacji stref, więc "stos" nigdy nie powinien być fragmentowany.

Nie muszę wdrażać zamknięć, ale myślę, że nawet te można zrobić w tym samym duchu, kopiując powiązane wartości do osobnego stosu, który jest używany wyłącznie do śledzenia stanów zamknięcia.

Myśli?

Źródło

2013-04-26 Folksvagen

Ale kod nie jest naprawdę funkcjonalny, operacje, które modyfikują stan, takie jak 'set!', 'Set-car!' I 'set-cdr!' Są częścią standardowej implementacji Schematu. Jeśli twój (prosty) kompilator Scheme nie pozwala na te operacje i nie musisz implementować zamknięć, to prostsza strategia GC może być możliwa. –

Pomyśl o prostym przykładzie: funkcja zwraca listę, która jest przekazywana do innego funkcja, która tworzy nową listę z co drugiego elementu z oryginalnej listy. W jaki sposób twoja analiza regionu wnioskuje, która część oryginalnych elementów listy nie jest już wymagana po zakończeniu drugiej funkcji? Nie ma absolutnie żadnego sposobu, aby wywnioskować regiony dla nawet najbardziej podstawowego rachunku lambda. –

Kwestie związane z implementacją "prostego" (twojego słowa, nie mojego) Kompilator schematu jest daleko, daleko od problemów z implementacją odśmiecacza systemu wykonawczego Scheme. Najpierw skoncentruj się na "prostym" kompilatorze. – GoZoner

Nawet bez zamknięć, aliasing jest trudny. W szczególności, przypuśćmy, że procedura tworzy uporządkowaną część danych, a następnie zwraca jej część? Jak ustalić, które części są darmowe? Jeśli potrafisz rozwiązać ten problem ... cóż, właśnie wymyśliłeś ponownie garbage collection.

Jeśli chodzi o nieco inne podejście, warto rzucić okiem na Rust (www.rust-lang.org), język na poziomie systemu, który pozwala programistom unikać wszystkich GC przy użyciu regionów i wymagając od programistów do jawnego śledzenia własności za pomocą różnych typów wskaźników.

Źródło

2013-04-26 16:43:19

OP nie chce używać GC.Więc nie uwalniasz żadnej jego części: P. Nie różni się to od tego, co zrobiłbyś w innych językach bez GC i na pewno nie musisz ponownie wymyślać GC. Tak jak nie potrzebowali programistów C/C++. – MasterMastic

W językach takich jak C & C++ programista zazwyczaj odpowiada za zwalnianie pamięci za pomocą funkcji free(). Tak więc, jeśli nie proponujesz schematu za darmo() (lub, być może, (za darmo)), lub języka, który po prostu nigdy nie zwalnia pamięci, twoja odpowiedź nie ma dla mnie sensu. –

Taka bezpłatna funkcja jest dokładnie tym, co mówię. Jeśli nie używasz GC, to w końcu jedyny sposób, w jaki osobiście wiem, aby zwolnić pamięć. I nie, nie zaproponowałbym języka, który nigdy nie zwalnia pamięci. – MasterMastic

Funkcje kończące wykonywanie zwracanych obiektów na ich wywołującym. Obiekty te nie mogą być przydzielane w ramkach stosów tych funkcji.

Tak więc albo musisz zakazać zwracania wartości (w takim przypadku masz procedury, które nie są programowaniem funkcjonalnym: i zrobić coś użytecznego, te procedury będą musiały mieć efekty uboczne).

Albo musisz zrobić wszystko według wartości: gdy obiekt jest zwracany, jest kopiowany z ramki stosu funkcji zwracającej (która jest następnie zwalniana), do ramki stosu osoby wywołującej.

Systemy o niedostatecznej wartości mają ograniczenia wydajności i semantyczne.

Źródło

2013-04-26 18:03:07 Kaz

nie używa się garbage collector w implementacji Scheme/Lisp

Odpowiedz

Powiązane problemy