Wskaźniki funkcji, zamknięcia i Lambda

Dopiero teraz dowiaduję się o wskaźnikach funkcji i kiedy czytałem rozdział K&R na ten temat, pierwszą rzeczą, która mnie uderzyła, było: „Hej, to jest trochę jak zamknięcie”. Wiedziałem, że to założenie jest w jakiś sposób fundamentalnie błędne i po wyszukiwaniu w Internecie nie znalazłem żadnej analizy tego porównania.

Dlaczego więc wskaźniki funkcji w stylu C zasadniczo różnią się od zamknięć lub lambd? O ile wiem, ma to związek z faktem, że wskaźnik funkcji nadal wskazuje zdefiniowaną (nazwaną) funkcję, w przeciwieństwie do praktyki anonimowego definiowania funkcji.

Dlaczego przekazywanie funkcji do funkcji jest postrzegane jako silniejsze w drugim przypadku, w którym nie jest ona nazwana, niż w pierwszym, w którym jest to zwykła, codzienna funkcja, która jest przekazywana?

Proszę, powiedz mi, jak i dlaczego się mylę, porównując te dwie rzeczy tak blisko.

Dzięki.

Lambda (lub zamknięcie ) hermetyzuje zarówno wskaźnik funkcji, jak i zmienne. Dlatego w C # możesz:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

Użyłem tam anonimowego delegata jako zamknięcia (jego składnia jest trochę jaśniejsza i bliższa C niż odpowiednik lambda), który przechwycił lessThan (zmienną stosu) do zamknięcia. Kiedy zamknięcie jest oceniane, lessThan (którego ramka stosu mogła zostać zniszczona) będzie nadal przywoływana. Jeśli zmienię mniej niż, to zmienię porównanie:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

W C byłoby to nielegalne:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

chociaż mógłbym zdefiniować wskaźnik funkcji, który przyjmuje 2 argumenty:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

Ale teraz muszę przekazać 2 argumenty, kiedy to oceniam. Gdybym chciał przekazać ten wskaźnik funkcji do innej funkcji, w której lessThan nie byłby objęty zakresem, musiałbym albo ręcznie utrzymać go przy życiu, przekazując go do każdej funkcji w łańcuchu, albo promując go do globalnej.

Chociaż większość języków głównego nurtu, które obsługują zamknięcia, używa funkcji anonimowych, nie jest to wymagane. Możesz mieć domknięcia bez funkcji anonimowych i funkcje anonimowe bez domknięć.

Podsumowanie: zamknięcie to połączenie wskaźnika funkcji + przechwyconych zmiennych.

Jako ktoś, kto napisał kompilatory języków zarówno z „prawdziwymi” zamknięciami, jak i bez nich, z szacunkiem nie zgadzam się z niektórymi z powyższych odpowiedzi. Zamknięcie Lisp, Scheme, ML lub Haskell nie tworzy dynamicznie nowej funkcji . Zamiast tego ponownie wykorzystuje istniejącą funkcję, ale robi to z nowymi wolnymi zmiennymi . Zbiór wolnych zmiennych jest często nazywany środowiskiem , przynajmniej przez teoretyków języków programowania.

Zamknięcie to po prostu agregat zawierający funkcję i środowisko. W kompilatorze Standard ML z New Jersey przedstawiliśmy jeden jako rekord; jedno pole zawierało wskaźnik do kodu, a inne pola zawierały wartości wolnych zmiennych. Kompilator dynamicznie utworzył nowe zamknięcie (nie funkcję) , przydzielając nowy rekord zawierający wskaźnik do tego samego kodu, ale z różnymi wartościami wolnych zmiennych.

Możesz to wszystko zasymulować w C, ale jest to upierdliwe. Popularne są dwie techniki:

1. Przekaż wskaźnik do funkcji (kodu) i oddzielny wskaźnik do wolnych zmiennych, tak aby zamknięcie zostało podzielone na dwie zmienne C.

2. Przekaż wskaźnik do struktury, gdzie struktura zawiera wartości wolnych zmiennych, a także wskaźnik do kodu.

Technika nr 1 jest idealna, gdy próbujesz zasymulować pewien rodzaj polimorfizmu w języku C i nie chcesz ujawniać typu środowiska - do reprezentowania środowiska używasz wskaźnika void *. Aby zobaczyć przykłady, spójrz na interfejsy C i implementacje Dave'a Hansona . Technika nr 2, która bardziej przypomina to, co dzieje się w kompilatorach kodu natywnego dla języków funkcyjnych, przypomina również inną znaną technikę ... obiekty C ++ z wirtualnymi funkcjami składowymi. Implementacje są prawie identyczne.

Ta obserwacja doprowadziła do dowcipu Henry'ego Bakera:

Ludzie w świecie Algol / Fortran przez lata narzekali, że nie rozumieją, jakie potencjalne zastosowanie zamknięć funkcji będzie miało w efektywnym programowaniu przyszłości. Potem nastąpiła rewolucja w programowaniu obiektowym, a teraz wszyscy programują używające domknięć funkcji, z tym wyjątkiem, że nadal nie chcą ich tak nazywać.

W C nie możesz zdefiniować funkcji inline, więc nie możesz tak naprawdę utworzyć zamknięcia. Wszystko, co robisz, to przekazywanie odniesienia do jakiejś predefiniowanej metody. W językach, które obsługują anonimowe metody / zamknięcia, definicje metod są znacznie bardziej elastyczne.

Mówiąc najprościej, wskaźniki funkcji nie mają skojarzonego z nimi zakresu (chyba że policzysz zasięg globalny), podczas gdy domknięcia obejmują zakres metody, która je definiuje. Za pomocą lambd można napisać metodę, która zapisuje metodę. Zamknięcia pozwalają ci na powiązanie „niektórych argumentów z funkcją i uzyskanie w rezultacie funkcji o niższej wartości”. (zaczerpnięte z komentarza Thomasa). Nie możesz tego zrobić w C.

EDYCJA: Dodanie przykładu (zamierzam użyć składni ActionScript, ponieważ właśnie o tym teraz myślę):

Powiedzmy, że masz metodę, która przyjmuje inną metodę jako argument, ale nie zapewnia sposobu przekazania żadnych parametrów do tej metody, gdy jest ona wywoływana? Na przykład pewna metoda, która powoduje opóźnienie przed uruchomieniem metody, którą ją przekazałeś (głupi przykład, ale chcę, aby był prosty).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Teraz powiedzmy, że chcesz, aby użytkownik runLater () opóźnił przetwarzanie obiektu:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

Funkcja, którą przekazujesz do process (), nie jest już jakąś statycznie zdefiniowaną funkcją. Jest generowany dynamicznie i może zawierać odwołania do zmiennych, które znajdowały się w zakresie, gdy metoda została zdefiniowana. Tak więc może uzyskać dostęp do „o” i „objectProcessor”, nawet jeśli nie są one objęte zakresem globalnym.

Mam nadzieje że to miało sens.

Zamknięcie = logika + środowisko.

Na przykład rozważmy tę metodę C # 3:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

Wyrażenie lambda nie tylko hermetyzuje logikę („porównaj nazwę”), ale także środowisko, w tym parametr (tj. Zmienna lokalna) „nazwa”.

Aby uzyskać więcej informacji na ten temat, zajrzyj do mojego artykułu o domknięciach, który przeprowadzi Cię przez C # 1, 2 i 3, pokazując, jak domknięcia ułatwiają.

W języku C wskaźniki funkcji mogą być przekazywane jako argumenty do funkcji i zwracane jako wartości z funkcji, ale funkcje istnieją tylko na najwyższym poziomie: nie można zagnieżdżać definicji funkcji wewnątrz siebie. Pomyśl o tym, czego wymagałoby C, aby obsługiwał funkcje zagnieżdżone, które mają dostęp do zmiennych funkcji zewnętrznej, a jednocześnie nadal mogą wysyłać wskaźniki funkcji w górę iw dół stosu wywołań. (Aby postępować zgodnie z tym wyjaśnieniem, powinieneś znać podstawy implementacji wywołań funkcji w języku C i większości podobnych języków: przejrzyj wpis stosu wywołań w Wikipedii).

Jaki obiekt jest wskaźnikiem do funkcji zagnieżdżonej? Nie może to być po prostu adres kodu, ponieważ jeśli go wywołasz, w jaki sposób uzyskuje dostęp do zmiennych funkcji zewnętrznej? (Pamiętaj, że z powodu rekurencji może być jednocześnie aktywnych kilka różnych wywołań funkcji zewnętrznej). Nazywa się to problemem funarg i istnieją dwa podproblemy: problem z funargami w dół i problem z funargami w górę.

Problem z funargami w dół, tj. Wysyłanie wskaźnika funkcji „w dół stosu” jako argumentu funkcji, którą wywołujesz, w rzeczywistości nie jest niekompatybilny z C, a GCC obsługuje funkcje zagnieżdżone jako funargi w dół. W GCC, kiedy tworzysz wskaźnik do funkcji zagnieżdżonej, naprawdę otrzymujesz wskaźnik do trampoliny , dynamicznie skonstruowanego fragmentu kodu, który ustawia statyczny wskaźnik łącza, a następnie wywołuje rzeczywistą funkcję, która używa statycznego wskaźnika łącza, aby uzyskać dostęp zmienne funkcji zewnętrznej.

Problem z funargami w górę jest trudniejszy. GCC nie zapobiega pozostawieniu wskaźnika trampoliny po tym, jak zewnętrzna funkcja nie jest już aktywna (nie ma rekordu na stosie wywołań), a wtedy statyczny wskaźnik łącza może wskazywać na śmieci. Rekordy aktywacji nie mogą już być przydzielane na stosie. Typowym rozwiązaniem jest umieszczenie ich na stercie i pozostawienie obiektu funkcji reprezentującego funkcję zagnieżdżoną po prostu wskazania rekordu aktywacji funkcji zewnętrznej. Taki obiekt nazywa się zamknięciem . Wtedy język będzie zazwyczaj musiał obsługiwać czyszczenie pamięci, aby rekordy mogły zostać zwolnione, gdy nie będzie już żadnych wskazujących na nie wskaźników.

Lambdy ( funkcje anonimowe ) to tak naprawdę osobny problem, ale zazwyczaj język, który pozwala definiować funkcje anonimowe w locie, pozwala również zwracać je jako wartości funkcji, więc ostatecznie są zamknięciami.

Lambda to anonimowa funkcja definiowana dynamicznie . Po prostu nie możesz tego zrobić w C ... jeśli chodzi o domknięcia (lub zwołanie tych dwóch), typowy przykład seplenienia wyglądałby podobnie do:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

W języku C można powiedzieć, że środowisko leksykalne (stos) get-counterjest przechwytywane przez funkcję anonimową i modyfikowane wewnętrznie, jak pokazano w poniższym przykładzie:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Zamknięcia implikują, że jakaś zmienna z punktu definicji funkcji jest związana razem z logiką funkcji, tak jak możliwość zadeklarowania miniobiektu w locie.

Jednym z ważnych problemów z C i domknięciami jest to, że zmienne przydzielone na stosie zostaną zniszczone po opuszczeniu bieżącego zakresu, niezależnie od tego, czy wskazywało na nie zamknięcie. Doprowadziłoby to do tego rodzaju błędów, które ludzie otrzymują, gdy beztrosko zwracają wskaźniki do zmiennych lokalnych. Zamknięcia zasadniczo implikują, że wszystkie istotne zmienne są albo zliczanymi ponownie, albo elementami zebranymi na stosie.

Nie czuję się komfortowo przyrównywanie lambdy z zamknięciem, ponieważ nie jestem pewien, czy lambdy we wszystkich językach są domknięciami, czasami myślę, że lambdy były lokalnie zdefiniowanymi anonimowymi funkcjami bez wiązania zmiennych (Python przed 2.1?).

W GCC można symulować funkcje lambda za pomocą następującego makra:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Przykład ze źródła :

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

Użycie tej techniki oczywiście eliminuje możliwość współpracy aplikacji z innymi kompilatorami i jest najwyraźniej „niezdefiniowanym” zachowaniem, więc YMMV.

Zamknięcie przechwytuje zmienne wolne w środowisku . Środowisko będzie nadal istniało, mimo że otaczający go kod może już nie być aktywny.

Przykład w Common Lisp, gdzie MAKE-ADDERzwraca nowe zamknięcie.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Korzystanie z powyższej funkcji:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Zauważ, że DESCRIBEfunkcja pokazuje, że obiekty funkcji dla obu zamknięć są takie same, ale środowisko jest inne.

Common Lisp sprawia, że ​​zarówno domknięcia, jak i czyste obiekty funkcyjne (te bez środowiska) są jednocześnie funkcjami i można je wywołać w ten sam sposób, używając tutaj FUNCALL.

Główna różnica wynika z braku leksykalnego zakresu w C.

Wskaźnik funkcji to po prostu wskaźnik do bloku kodu. Każda zmienna niebędąca stosem, do której się odwołuje, jest globalna, statyczna lub podobna.

Zamknięcie, OTOH, ma swój własny stan w postaci „zmiennych zewnętrznych” lub „wartości podwyższonych”. mogą być tak prywatne lub udostępniane, jak chcesz, używając leksykalnego zakresu. Możesz utworzyć wiele zamknięć z tym samym kodem funkcji, ale różnymi instancjami zmiennych.

Kilka domknięć może współdzielić niektóre zmienne, a więc może to być interfejs obiektu (w sensie OOP). aby to uczynić w C, musisz powiązać strukturę z tabelą wskaźników funkcji (to właśnie robi C ++, z klasą vtable).

w skrócie, zamknięcie jest wskaźnikiem funkcji PLUS jakimś stanem. to konstrukcja wyższego poziomu

Większość odpowiedzi wskazuje, że zamknięcia wymagają wskaźników do funkcji, prawdopodobnie do funkcji anonimowych, ale jak napisał Mark, zamknięcia mogą istnieć z nazwanymi funkcjami. Oto przykład w Perlu:

{
    my $count;
    sub increment { return $count++ }
}

Zamknięcie to środowisko, które definiuje $countzmienną. Jest dostępna tylko dla incrementpodprogramu i pozostaje między wywołaniami.

W języku C wskaźnik funkcji to wskaźnik, który wywoła funkcję, gdy ją wyłuskujesz, zamknięcie to wartość, która zawiera logikę funkcji i środowisko (zmienne i wartości, z którymi są powiązane), a lambda zwykle odnosi się do wartości, która jest właściwie nienazwaną funkcją. W C funkcja nie jest wartością pierwszej klasy, więc nie można jej przekazać, więc zamiast tego musisz przekazać do niej wskaźnik, jednak w językach funkcjonalnych (takich jak Scheme) możesz przekazywać funkcje w ten sam sposób, w jaki przekazujesz każdą inną wartość