Czy zbieranie śmieci jest potrzebne do wdrożenia bezpiecznych zamknięć?

14

Niedawno uczestniczyłem w kursie internetowym na temat języków programowania, w którym zaprezentowano między innymi zamknięcia. Zapisuję dwa przykłady zainspirowane tym kursem, aby podać kontekst, zanim zadam pytanie.

Pierwszym przykładem jest funkcja SML, która tworzy listę liczb od 1 do x, gdzie x jest parametrem funkcji:

fun countup_from1 (x: int) =
    let
        fun count (from: int) =
            if from = x
            then from :: []
            else from :: count (from + 1)
    in
        count 1
    end

W SML REPL:

val countup_from1 = fn : int -> int list
- countup_from1 5;
val it = [1,2,3,4,5] : int list

countup_from1Funkcja wykorzystuje zamknięcie pomocnika count, który przechwytuje i używa zmiennej xod jej kontekstu.

W drugim przykładzie, kiedy wywołuję funkcję create_multiplier t, zwracam funkcję (a właściwie zamknięcie), która zwielokrotnia jej argument przez t:

fun create_multiplier t = fn x => x * t

W SML REPL:

- fun create_multiplier t = fn x => x * t;
val create_multiplier = fn : int -> int -> int
- val m = create_multiplier 10;
val m = fn : int -> int
- m 4;
val it = 40 : int
- m 2;
val it = 20 : int

Zmienna mjest więc powiązana z zamknięciem zwróconym przez wywołanie funkcji i teraz mogę z niej korzystać do woli.

Teraz, aby zamknięcie działało poprawnie przez cały okres jego istnienia, musimy przedłużyć czas życia przechwyconej zmiennej t(w tym przykładzie jest ona liczbą całkowitą, ale może być wartością dowolnego typu). O ile mi wiadomo, w SML jest to możliwe dzięki wyrzucaniu elementów bezużytecznych: zamknięcie zachowuje odniesienie do przechwyconej wartości, która jest później usuwana przez moduł wyrzucający elementy bezużyteczne, gdy zamknięcie zostanie zniszczone.

Moje pytanie: czy ogólnie rzecz biorąc, czy usuwanie śmieci jest jedynym możliwym mechanizmem zapewniającym bezpieczeństwo zamknięć (możliwość wywołania przez cały okres ich użytkowania)?

Lub jakie są inne mechanizmy, które mogą zapewnić ważność zamknięć bez wyrzucania elementów bezużytecznych: Skopiuj przechwycone wartości i zapisz je w zamknięciu? Ogranicz czas życia samego zamknięcia, aby nie można go było wywoływać po wygaśnięciu przechwyconych zmiennych?

Jakie są najbardziej popularne podejścia?

EDYTOWAĆ

Nie sądzę, że powyższy przykład można wyjaśnić / wdrożyć, kopiując przechwycone zmienne (zmienne) do zamknięcia. Zasadniczo, przechwycone zmienne mogą być dowolnego typu, np. Mogą być powiązane z bardzo dużą (niezmienną) listą. Tak więc we wdrożeniu kopiowanie tych wartości byłoby bardzo nieefektywne.

Dla kompletności, oto kolejny przykład wykorzystujący odniesienia (i skutki uboczne):

(* Returns a closure containing a counter that is initialized
   to 0 and is incremented by 1 each time the closure is invoked. *)
fun create_counter () =
    let
        (* Create a reference to an integer: allocate the integer
           and let the variable c point to it. *)
        val c = ref 0
    in
        fn () => (c := !c + 1; !c)
    end

(* Create a closure that contains c and increments the value
   referenced by it it each time it is called. *)
val m = create_counter ();

W SML REPL:

val create_counter = fn : unit -> unit -> int
val m = fn : unit -> int
- m ();
val it = 1 : int
- m ();
val it = 2 : int
- m ();
val it = 3 : int

Tak więc zmienne mogą być również przechwytywane przez odniesienie i nadal są żywe po zakończeniu wywołania funkcji, która je utworzyła ( create_counter ()).

Giorgio
źródło
2
Wszelkie zmienne, które są zamknięte, powinny być chronione przed odśmiecaniem, a wszelkie zmienne, które nie są zamknięte, powinny kwalifikować się do odśmiecania. Wynika z tego, że każdy mechanizm, który może niezawodnie śledzić, czy zmienna jest zamknięta, może również niezawodnie odzyskać pamięć zajmowaną przez zmienną.
Robert Harvey
3
@btilly: Ponowne liczenie jest tylko jedną z wielu różnych strategii wdrażania dla śmieciarza. Tak naprawdę nie ma znaczenia, w jaki sposób GC jest implementowany na potrzeby tego pytania.
Jörg W Mittag
3
@btilly: Co oznacza „prawdziwe” zbieranie śmieci? Przeliczanie rachunków to kolejny sposób implementacji GC. Śledzenie jest bardziej popularne, prawdopodobnie ze względu na trudności w zbieraniu cykli z przeliczaniem. (Zwykle i tak kończy się to oddzielnym śledzeniem GC, więc po co zawracać sobie głowę wdrażaniem dwóch GC, jeśli możesz sobie z nimi poradzić.) Są jednak inne sposoby radzenia sobie z cyklami. 1) Po prostu ich zabraniaj. 2) Po prostu je zignoruj. (Jeśli wykonujesz implementację szybkich, jednorazowych skryptów, dlaczego nie?) 3) Spróbuj je wyraźnie wykryć. (Okazuje się, że posiadanie dostępnego doładowania może to przyspieszyć.)
Jörg W Mittag
1
Zależy to przede wszystkim od tego, dlaczego chcesz zamknięcia. Jeśli chcesz wdrożyć, powiedzmy, pełną semantykę rachunku lambda, zdecydowanie potrzebujesz GC, kropka. Nie ma innej możliwości. Jeśli chcesz czegoś, co odlegle przypomina zamknięcia, ale nie jest zgodne z dokładną semantyką takich (jak w C ++, Delphi, cokolwiek) - rób co chcesz, używaj analizy regionu, używaj w pełni ręcznego zarządzania pamięcią.
SK-logic
2
@Mason Wheeler: Zamknięcia są tylko wartościami, generalnie nie można przewidzieć, w jaki sposób będą one przenoszone w czasie wykonywania. W tym sensie nie są niczym specjalnym, to samo dotyczy łańcucha, listy i tak dalej.
Giorgio

Odpowiedzi:

14

Język programowania Rust jest interesujący pod tym względem.

Rust jest językiem systemowym z opcjonalnym GC i od samego początku był projektowany z zamknięciami .

Podobnie jak inne zmienne, zamknięcia rdzy występują w różnych smakach. Zamknięcia stosu , najczęściej stosowane, są jednorazowe. Żyją na stosie i mogą odnosić się do wszystkiego. Posiadane zamknięcia przejmują własność przechwyconych zmiennych. Myślę, że żyją na tzw. „Stosie wymiany”, który jest globalnym stosem. Ich żywotność zależy od tego, kto jest ich właścicielem. Zarządzane zamknięcia są aktywne na stercie lokalnej zadania i są śledzone przez GC zadania. Nie jestem jednak pewien ich ograniczeń przechwytywania.

prędkościami
źródło
1
Bardzo interesujący link i odniesienie do języka Rust. Dzięki. +1.
Giorgio
1
Dużo myślałem, zanim zaakceptowałem odpowiedź, ponieważ uważam, że odpowiedź Masona jest również bardzo pouczająca. Wybrałem ten, ponieważ ma on zarówno charakter informacyjny, jak i przytacza mniej znany język z oryginalnym podejściem do zamykania.
Giorgio
Dziękuję za to. Jestem bardzo entuzjastycznie nastawiony do tego młodego języka i chętnie dzielę się zainteresowaniem. Nie wiedziałem, że bezpieczne zamknięcie jest możliwe bez GC, zanim dowiedziałem się o Rust.
barjak
9

Niestety, zaczynając od GC, jesteś ofiarą zespołu XY:

  • domknięcia wymagają niż zmienne, które zamykały na żywo tak długo, jak to wymaga (ze względów bezpieczeństwa)
  • za pomocą GC możemy wydłużyć czas życia tych zmiennych wystarczająco długo
  • Zespół XY: czy istnieją inne mechanizmy przedłużające żywotność?

Należy jednak pamiętać, niż idea przedłużające żywotność zmiennej nie jest konieczne dla zamknięcia; właśnie przyniósł GC; pierwotne oświadczenie dotyczące bezpieczeństwa mówi, że zmienne „zamknięte” powinny żyć tak długo, jak zamknięcie (a nawet to jest niepewne, moglibyśmy powiedzieć, że powinny żyć do ostatniego wywołania zamknięcia).

Zasadniczo istnieją dwa podejścia, które widzę (i można je potencjalnie połączyć):

  1. Wydłuż czas życia zamkniętych zmiennych (jak na przykład GC)
  2. Ogranicz czas życia zamknięcia

To ostatnie jest tylko symetrycznym podejściem. Nie jest często używany, ale jeśli, podobnie jak Rust, masz system typowania dla regionu, to z pewnością jest to możliwe.

Matthieu M.
źródło
7

Odśmiecanie nie jest potrzebne do bezpiecznego zamykania podczas przechwytywania zmiennych według wartości. Jednym z wybitnych przykładów jest C ++. C ++ nie ma standardowego wyrzucania elementów bezużytecznych. Lambdy w C ++ 11 są zamknięciami (przechwytują zmienne lokalne z otaczającego zakresu). Każdą zmienną przechwyconą przez lambda można określić, aby była przechwytywana przez wartość lub przez odniesienie. Jeśli zostanie przechwycony przez odniesienie, możesz powiedzieć, że nie jest bezpieczny. Jeśli jednak zmienna zostanie przechwycona przez wartość, to jest bezpieczna, ponieważ przechwycona kopia i oryginalna zmienna są oddzielne i mają niezależne okresy istnienia.

W podanym przykładzie SML wyjaśnienie jest proste: zmienne są przechwytywane według wartości. Nie ma potrzeby „przedłużania żywotności” żadnej zmiennej, ponieważ można po prostu skopiować jej wartość do zamknięcia. Jest to możliwe, ponieważ w ML zmiennych nie można przypisać. Więc nie ma różnicy między jedną kopią a wieloma niezależnymi kopiami. Chociaż SML ma wyrzucanie elementów bezużytecznych, nie ma to związku z przechwytywaniem zmiennych przez zamknięcia.

Odśmiecanie nie jest również potrzebne do bezpiecznego zamykania podczas przechwytywania zmiennych przez referencję (rodzaj). Jednym z przykładów jest rozszerzenie Apple Blocks do języków C, C ++, Objective-C i Objective-C ++. W C i C ++ nie ma standardowego wyrzucania elementów bezużytecznych. Bloki domyślnie przechwytują zmienne. Jeśli jednak deklarowana jest zmienna lokalna __block, bloki przechwytują je pozornie „przez odniesienie” i są bezpieczne - można ich używać nawet po zakresie, w którym blok został zdefiniowany. To, co się tutaj dzieje, polega na tym, że __blockzmienne są w rzeczywistości specjalna struktura pod spodem, a kiedy bloki są kopiowane (bloki muszą zostać skopiowane, aby użyć ich poza zakresem w pierwszej kolejności), „przesuwają” strukturę__block zmienna w stercie, a blok zarządza pamięcią, jak sądzę poprzez liczenie referencji.

użytkownik102008
źródło
4
„Śmieci nie są potrzebne do zamknięć.”: Pytanie brzmi, czy jest potrzebne, aby język mógł wymusić bezpieczne zamknięcia. Wiem, że mogę pisać bezpieczne zamknięcia w C ++, ale język ich nie wymusza. W przypadku zamknięć, które przedłużają żywotność przechwyconych zmiennych, zobacz edycję mojego pytania.
Giorgio
1
Przypuszczam, że można przeredagować pytanie na: dla bezpiecznych zamknięć .
Matthieu M.
1
Tytuł zawiera termin „bezpieczne zamknięcia”. Czy myślisz, że mógłbym go sformułować w lepszy sposób?
Giorgio
1
Czy możesz poprawić drugi akapit? W SML zamknięcia wydłużają żywotność danych, do których odnoszą się przechwycone zmienne. Ponadto prawdą jest, że nie można przypisywać zmiennych (zmieniać ich wiązania), ale istnieją zmienne dane (poprzez refs). Tak, OK, można dyskutować, czy wdrożenie zamknięć jest związane z odśmiecaniem, czy nie, ale powyższe stwierdzenia powinny zostać poprawione.
Giorgio
1
@Giorgio: Co powiesz teraz? Ponadto, w jakim sensie uważasz, że moje stwierdzenie, że zamknięcia nie muszą przedłużyć żywotności przechwyconej zmiennej, jest nieprawidłowe? Kiedy mówimy o zmiennych danych, mówimy o typach referencyjnych ( reftablicach itp.), Które wskazują na strukturę. Ale wartością jest samo odniesienie, a nie rzecz, na którą wskazuje. Jeśli masz var a = ref 1i robisz kopię var b = ai używasz b, czy to oznacza, że ​​nadal używasz a? Masz dostęp do tej samej struktury, na którą wskazuje a? Tak. Tak właśnie działają te typy w SML i nie mają nic wspólnego z zamknięciami
102008
6

Odśmiecanie nie jest konieczne do wdrożenia zamknięć. W 2008 r. Język Delphi, który nie jest śmieciami, dodał implementację zamknięć. Działa to tak:

Kompilator tworzy pod maską obiekt funktora, który implementuje interfejs reprezentujący zamknięcie. Wszystkie zamknięte zmienne lokalne zostają zmienione z lokalnych dla procedury zamykania na pola w obiekcie funktora. Zapewnia to zachowanie stanu tak długo, jak jest funktor.

Ograniczeniem tego systemu jest to, że jakikolwiek parametr przekazany przez odwołanie do funkcji zamykającej, a także wartość wyniku funkcji, nie mogą zostać przechwycone przez funktor, ponieważ nie są lokalnymi, których zakres jest ograniczony do zakresu funkcji zamykającej.

Funktor odnosi się do odwołania zamknięcia, używając cukru syntaktycznego, aby wyglądał na programistę jak wskaźnik funkcji zamiast interfejsu. Używa systemu zliczania referencji Delphi dla interfejsów, aby upewnić się, że obiekt funktora (i cały jego stan) pozostaje „żywy” tak długo, jak to konieczne, a następnie zostaje uwolniony, gdy liczba kont spadnie do zera.

Mason Wheeler
źródło
1
Ach, więc możliwe jest tylko przechwycenie zmiennej lokalnej, a nie argumentów! To wydaje się rozsądnym i sprytnym kompromisem! +1
Giorgio
1
@Giorgio: Może przechwytywać argumenty, ale nie te, które są parametrami var .
Mason Wheeler,
2
Tracisz także możliwość posiadania 2 zamknięć, które komunikują się za pośrednictwem wspólnego państwa prywatnego. Nie spotkasz tego w podstawowych przypadkach użycia, ale ogranicza to twoją zdolność do robienia skomplikowanych rzeczy. Nadal świetny przykład tego, co jest możliwe!
btilly,
3
@btilly: W rzeczywistości, jeśli umieścisz 2 zamknięcia w tej samej funkcji zamykającej, jest to całkowicie legalne. Ostatecznie dzielą ten sam obiekt funktora, a jeśli zmodyfikują ten sam stan, zmiany w jednym zostaną odzwierciedlone w drugim.
Mason Wheeler,
2
@MasonWheeler: "Nie. Odśmiecanie ma charakter niedeterministyczny; nie ma gwarancji, że jakikolwiek obiekt zostanie kiedykolwiek zebrany, nie mówiąc już o tym, kiedy to się stanie. Ale liczenie referencji jest deterministyczne: kompilator gwarantuje, że obiekt zostanie uwolniony natychmiast po tym, jak liczba spadnie do 0. ”. Gdybym miał dziesięciocentówkę za każdym razem, gdy słyszałam, że mit się utrwala. OCaml ma deterministyczny GC. Bezpieczeństwo wątków C ++ shared_ptrjest niedeterministyczne, ponieważ czynniki niszczące ścigają się do zera.
Jon Harrop