Problemy z wdrażaniem zamknięć w ustawieniach niefunkcjonalnych

18

W językach programowania zamknięcia są popularną i często pożądaną funkcją. Wikipedia mówi (moje podkreślenie):

W informatyce zamknięcie (...) jest funkcją wraz ze środowiskiem odniesienia dla zmiennych nielokalnych tej funkcji. Zamknięcie umożliwia funkcji dostęp do zmiennych poza jej bezpośrednim zakresem leksykalnym.

Zatem zamknięcie jest zasadniczo (anonimową?) Wartością funkcji, która może wykorzystywać zmienne poza swoim zakresem. Z mojego doświadczenia wynika, że ​​może on uzyskiwać dostęp do zmiennych, które są objęte zakresem w punkcie definicji.

W praktyce koncepcja wydaje się rozbieżna, przynajmniej poza programowaniem funkcjonalnym. Różne języki wdrażają różne semantyki, a nawet wydaje się, że toczą się wojny o opinie. Wielu programistów wydaje się nie wiedzieć, czym są zamknięcia, postrzegając je jako niewiele więcej niż anonimowe funkcje.

Ponadto wydaje się, że istnieją poważne przeszkody przy wdrażaniu zamknięć. Najważniejsze, że Java 7 miała je zawierać, ale funkcja została przeniesiona z powrotem do przyszłej wersji.

Dlaczego zamknięcia są tak trudne (do zrozumienia i) do zrealizowania? To pytanie jest zbyt ogólne i niejasne, więc skupię się bardziej na tych powiązanych ze sobą pytaniach:

  • Czy występują problemy z wyrażaniem zamknięć we wspólnych formalizmach semantycznych (mały krok, duży krok ...)?
  • Czy istniejące systemy typów nie nadają się do zamknięć i nie można ich łatwo rozbudować?
  • Czy problematyczne jest dostosowanie zamknięć do tradycyjnego tłumaczenia procedur opartego na stosie?

Zauważ, że pytanie dotyczy głównie języków proceduralnych, obiektowych i skryptowych. O ile mi wiadomo, języki funkcjonalne nie mają żadnych problemów.

Raphael
źródło
Dobre pytanie. Zamknięcia zostały zaimplementowane w Scali, a Martin Odersky napisał kompilator Java 1.5, więc nie jest jasne, dlaczego nie ma ich w Javie 7. C # ma je. (Spróbuję napisać lepszą odpowiedź później.)
Dave Clarke
4
Zanieczyszczone języki funkcjonalne, takie jak Lisp i ML, doskonale nadają się do zamykania, więc nie może istnieć żaden istotny semantyczny powód, dla którego mogłyby być problematyczne.
Gilles „SO- przestań być zły”
Dołączyłem ten przedmiot, ponieważ starałem się wyobrazić sobie, jak semantyczny krok może wyglądać dla zamknięć. Może się zdarzyć, że zamknięcia same w sobie nie stanowią problemu, ale włączenie ich w języku, który nie został zaprojektowany z myślą o nich, jest trudne.
Raphael
1
Spójrz na pdfs.semanticscholar.org/73a2/… - autorzy Lua zrobili to bardzo sprytnie i dyskutują również ogólne problemy związane z wdrażaniem zamknięć
Bulat

Odpowiedzi:

10

Czy mogę skierować Cię na stronę wikipedii dotyczącą problemu Funarg ? Przynajmniej w taki sposób ludzie kompilatora odwoływali się do problemu implementacji zamknięcia.

Zatem zamknięcie jest zasadniczo (anonimową?) Wartością funkcji, która może wykorzystywać zmienne poza swoim zakresem. Z mojego doświadczenia wynika, że ​​może on uzyskiwać dostęp do zmiennych, które są objęte zakresem w punkcie definicji.

Chociaż ta definicja ma sens, nie pomaga opisać problemu implementacji pierwszorzędnych funkcji w tradycyjnym języku opartym na stosie wykonawczym. Jeśli chodzi o kwestie związane z implementacją, funkcje pierwszej klasy można z grubsza podzielić na dwie klasy:

  • Zmienne lokalne w funkcjach nigdy nie są używane po powrocie funkcji.
  • Zmiennych lokalnych można użyć po powrocie funkcji.

Pierwszy przypadek (obniżenie wartości) nie jest trudny do wdrożenia i można go znaleźć nawet w starszych językach proceduralnych, takich jak Algol, C i Pascal. C omija ten problem, ponieważ nie zezwala na funkcje zagnieżdżone, ale Algol i Pascal wykonują niezbędną księgowość, aby umożliwić funkcjom wewnętrznym odwoływanie się do zmiennych stosu funkcji zewnętrznej.

Drugi przypadek (funargs w górę) wymaga natomiast zapisania rekordów aktywacyjnych poza stosem, na stosie. Oznacza to, że bardzo łatwo jest przeciekać zasoby pamięci, chyba że środowisko uruchomieniowe języka zawiera moduł czyszczenia pamięci. Podczas gdy prawie wszystko jest dziś zbierane śmieci, wymaganie jednego z nich jest nadal znaczącą decyzją projektową, a jeszcze bardziej jeszcze jakiś czas temu.


Jeśli chodzi o konkretny przykład Javy, o ile dobrze pamiętam, głównym problemem nie była możliwość implementacji zamknięć, ale sposób wprowadzenia ich do języka w sposób, który nie był zbędny z istniejącymi funkcjami (jak anonimowe klasy wewnętrzne) i które nie kolidowały z istniejącymi funkcjami (jak sprawdzone wyjątki - problem, który nie jest ciekawostką do rozwiązania i o którym większość ludzi na początku nie myśli).

Mogę również pomyśleć o innych rzeczach, które sprawiają, że funkcje pierwszej klasy są mniej trywialne w implementacji, takich jak decydowanie o tym, co zrobić z „magicznymi” zmiennymi, takimi jak ta , self lub super, oraz jak wchodzić w interakcje z istniejącymi operatorami przepływu sterowania, takimi jak break i return (czy chcemy zezwalać na nielokalne zwroty, czy nie?). Ale ostatecznie popularność funkcji pierwszej klasy wydaje się wskazywać, że języki, które ich nie mają, robią to głównie ze względów historycznych lub z powodu jakiejś znaczącej decyzji projektowej na wczesnym etapie.

hugomg
źródło
1
Czy znasz jakieś języki, które odróżniają przypadki w górę i w dół? W językach .NET ogólna metoda, która spodziewała się otrzymać funkcję tylko w dół, mogłaby otrzymać strukturę typu ogólnego wraz z delegatem, który otrzymałby taką strukturę jak byref (w C # „ refparametr”). Jeśli osoba dzwoniąca zamknie wszystkie zainteresowane zmienne w strukturze, delegat może być w pełni statyczny, co pozwoli uniknąć potrzeby przydzielania sterty. Kompilatory nie oferują żadnej przyjemnej pomocy dla takich konstrukcji, ale Framework może je obsługiwać.
supercat
2
@ superupat: Rdza ma wiele typów zamknięć, które pozwalają wymusić w czasie kompilacji, jeśli funkcja wewnętrzna będzie musiała użyć sterty. Nie oznacza to jednak, że implementacja nie może uniknąć alokacji sterty bez zmuszania użytkownika do dbania o wszystkie te dodatkowe typy. Kompilator może próbować wywnioskować czasy życia funkcji lub może użyć kontroli czasu wykonywania w celu leniwego zapisywania zmiennych na stercie tylko wtedy, gdy jest to bezwzględnie potrzebne (szczegółowe informacje można znaleźć w sekcji „Zakres leksykalny” dokumentu Ewolucja Lua )
hugomg
5

Możemy spojrzeć na sposób implementacji zamknięć w C #. Skala transformacji, które wykonuje kompilator C #, wyraźnie pokazuje, że ich sposób implementacji zamknięć jest dość pracochłonny. Mogą istnieć łatwiejsze sposoby implementacji zamknięć, ale sądzę, że zespół kompilatora C # byłby tego świadomy.

Rozważmy następujący pseudo-C # (wyciąłem trochę rzeczy specyficznych dla C #):

int x = 1;
function f = function() { x++; };
for (int i = 1; i < 10; i++) {
    f();
}
print x; // Should print 9

Kompilator przekształca to w coś takiego:

class FunctionStuff {
   int x;
   void theFunction() {
       x++;
   }
}

FunctionStuff theClosureObject = new FunctionStuff();
theClosureObject.x = 1;
for (int i = 1; i < 10; i++) {
    theClosureObject.theFunction();
}
print theClosureObject.x; // Should print 9

(w rzeczywistości zmienna f nadal będzie tworzona, gdzie f jest „delegatem” (= wskaźnik funkcji), ale ten delegat jest nadal powiązany z obiektem theClosureObject - pozostawiłem tę część dla jasności dla tych, którzy nie są zaznajomieni z C #)

Ta transformacja jest dość masywna i trudna: rozważ zamknięcia w zamknięciach i współdziałanie zamknięć z pozostałymi funkcjami języka C #. Mogę sobie wyobrazić, że ta funkcja została wypchnięta z powrotem dla Javy, ponieważ Java 7 ma już całkiem sporo nowych funkcji.

Alex ten Brink
źródło
Widzę, dokąd to zmierza; mając wiele zamknięć i dostęp do głównego zakresu ta sama zmienna będzie bałagan.
Raphael
Szczerze mówiąc, jest to bardziej związane z wykorzystaniem istniejącej struktury OO do implementacji zamknięć niż z jakimkolwiek rzeczywistym problemem z nimi. Inne języki po prostu alokują zmienne w osobnej, pozbawionej metod strukturze, a następnie pozwalają wielu zamknięciom udostępniać je, jeśli chcą.
hugomg
@Raphael: co sądzisz o zamknięciach wewnątrz zamknięć? Poczekaj, pozwól, że to dodam.
Alex ten Brink
5

Aby odpowiedzieć na część twojego pytania. Formalizm opisany przez Morrisetta i Harpera obejmuje dużą i małą semantykę języków polimorficznych wyższego rzędu zawierających zamknięcia. Przed nimi są artykuły przedstawiające rodzaje semantyki, których szukasz. Spójrz na przykład na maszynę SECD . Dodawanie zmiennych odwołań lub zmiennych lokalnych do tej semantyki jest proste. Nie widzę żadnych problemów technicznych w zapewnieniu takiej semantyki.

Dave Clarke
źródło
Dziękuję za referencje! Wydaje się, że nie nadaje się do lekkiego czytania, ale prawdopodobnie należy się tego spodziewać po pracy semantycznej.
Raphael
1
@Raphael: Prawdopodobnie są prostsze. Spróbuję coś znaleźć i skontaktuję się z Tobą. W każdym razie rysunek 8 ma semantykę, której szukasz.
Dave Clarke
Może możesz podać ogólny zarys lub. główne idee w twojej odpowiedzi?
Raphael
2
@Raphael. Być może mógłbym odnieść się do moich notatek z wykładów, których używam na kurs języków programowania, który daje krótkie wprowadzenie. Proszę sprawdzić materiały informacyjne 8 i 9.
Uday Reddy
1
Łącze to wydaje się martwe lub kryje się za niewidzialnym uwierzytelnieniem. ( cs.cmu.edu/afs/cs/user/rwh/public/www/home/papers/gcpoly/tr.pdf ). Dostaję 403 zabronione.
Ben Fletcher