AFAIK, Pierwsze dowody używania funkcji wyższego rzędu sięgają artykułu Schönfinkela z 1924 r .: „O elementach logiki matematycznej” - gdzie pozwalał przekazywać funkcje jako argumenty innym funkcjom.

To wydaje się interesujące. Jednak wszystko, co czytałem o jego pracy (i Curry'ego z rozszerzenia) zdaje się nawiązywać do jednej rzeczy w takiej czy innej formie: [funkcje wyższego rzędu] ... eliminuje to potrzebę powiązania zmiennych ...

To, czego nie byłem w stanie owinąć wokół głowy, to - o co chodzi? Dlaczego ówcześni logicy i matematycy się tym przejmowali? Czy my, teoretycy, troszczymy się o to dzisiaj? Dlaczego „przełomowe” było pozbycie się zmiennych powiązanych i jaki wpływ (lub ma) na obliczenia (teoretycznie), jakie znamy?

PS: Zdaję sobie sprawę z tego, jak jego praca utorowała drogę dla -calculus i wpływu „it” na obliczenia i programowanie funkcjonalne w ogóle. Moje pytanie dotyczy głównie czasu „przed” stworzeniem -calculus i „po” pracy Schönfinkela. Fakt, że Curry samodzielnie podjął tę linię pracy, która później była znana jako „logika kombinatoryczna”, zbytnio nawiązuje do znaczenia dzieła Schönfinkela.$\lambda$$\lambda$

TL; DR. Metamatyka matematyki wiązania jest subtelna : wydaje się trywialna, ale nie jest - czy masz do czynienia z logiką (wyższego rzędu) czy order-rachunek różniczkowy. Są tak subtelne, że wiążące reprezentacje tworzą otwartą dziedzinę badań, z konkurencją ( wyzwanie POPLmark ) kilka lat temu. Ludzie w branży żartują nawet na temat złożoności podejść do wiązania.

Tak więc, jeśli zależy ci na metamatematyce (a większość matematyków nie), musisz poradzić sobie z wiązaniem. Ale wielu matematyków może bezpiecznie traktować formalizację wiązania jako problem „fundamentalny”.

Inną kwestią jest to, że wiązanie było jedynym „nowym” problemem w językach z funkcjami wyższego rzędu, ponieważ teoria języków z wiązaniem to po prostu algebra (dla stałych) + wiązanie. „Podstawy języków programowania” Mitchella faktycznie przedstawiają rzeczy w tej kolejności i są raczej pouczające.

Zdaję sobie sprawę z tego, jak jego praca utorowała drogę dla rachunku λ i jego wpływu na obliczenia i programowanie funkcjonalne w ogóle. Moje pytanie dotyczy głównie czasu „przed” stworzeniem rachunku λ i „po” pracy Schönfinkela.

Coś mi brakuje, ale ta uwaga wydaje się nie mieć znaczenia. Wiązanie w logice wyższego rzędu i wiązanie w rachunku λ wydaje się równie trudne, więc dopóki ludzie dbali o logikę wyższego rzędu, musieli sobie radzić z wiązaniem. Jestem stronniczy, stosując dowody oparte na izomorfizmie Curry'ego-Howarda, które implementują logikę, po prostu implementując teorię typów (gdzie typy są formułami, a programy to terminy próbne), więc po prostu mam do czynienia z wiązaniem raz.

Z drugiej strony, IIRC, w tamtym czasie rzeczywiście niewielu dbało o twórczość Schönfinkela - częściowo z powodu tego, jak (nie) ją opublikował - artykuły były w większości pisane przez kolegów na podstawie przeprowadzonych przez niego badań (patrz tutaj , strona 4) ; Curry następnie odkrył teorię niezależnie.

Zastrzeżenie: Nie jestem historykiem, ale doktorantem PL, więc moja jest nowoczesną (i mam nadzieję dokładną) perspektywą na ten temat.

EDYTOWAĆ:

Dlaczego wiązanie jest subtelne, nieco bardziej konkretne

Są dwa aspekty - po pierwsze, wdrożenie go jest trudne. Po drugie, metamatematyka jest matematyką manipulacji dowodami: ta manipulacja jest zazwyczaj automatyczna, to znaczy jest algorytmem - więc w gruncie rzeczy napotykasz wszystkie trudności związane z implementacją, a także przedstawiasz dowody na ich temat. Poniżej podaję przykłady. Przykłady mają nowoczesną perspektywę - dotyczą faktycznie sformalizowanych dowodów. Jednak niektóre trudności dotyczyłyby dokładnych ręcznych dowodów - o ile nie zdradzasz szczegółów.

To pokazuje, że Schönfinkel po prostu dał pierwsze rozwiązanie tego problemu, ale było to dalekie od ostatecznego.

Wdrożenie jest subtelne z powodu zacienienia

$(\lambda f. f~1 + f~2) (\lambda x . x)$$(\lambda x . x)~1 + (\lambda x . x)~2$$(\lambda f x. f (f x))\ (\lambda g y . g~y)\ z$$(\lambda g y . g~y)\ (\lambda g y . g~y)\ z$$(\lambda y . (\lambda g y . g~y)~y)\ \ z$

$\lambda x y. x$$y$$\lambda y. y$$\lambda y'. y$

Co gorsza, kontrprzykłady naiwnych algorytmów są trudne do zbudowania, gdy znasz już problem, a co dopiero, gdy go nie znasz. Błędy w prawie poprawnych algorytmach często pozostają niewykryte przez lata. Słyszę, że nawet dobrzy studenci zwykle nie wymyślają (we własnym zakresie) prawidłowej definicji substytucji unikającej chwytania. W rzeczywistości doktoranci (w tym ja) i profesorowie nie są zwolnieni z tego problemu.

To jeden z powodów, dla których niektóre (w tym jeden z najlepszych podręczników na temat języków programowania, typów i języków programowania autorstwa Benjamina Pierce'a) zalecają bezimienną reprezentację (niezupełnie logika kombinacyjna, nawet jeśli została użyta, ale raczej indeksy deBrujin).

Dowody na to są subtelne

Okazuje się, że dowody na wiązanie nie są prostsze niż implementacja, jak wspomniano powyżej. Oczywiście istnieją poprawne algorytmy i istnieją dowody na ich istnienie - ale bez zaawansowanej maszynerii, dla każdego języka używającego wiązania musisz powtórzyć proofy, a te dowody są po prostu bardzo duże i irytujące, jeśli użyjesz definicji bindowania na papierze i długopisie .

$B$$A$$A$$B$$B$

Następnie sprawdziłem mój najlepszy przykład „co się stanie, jeśli spróbujesz sformalizować standardową definicję”. Russell O'Connor (który jest na tej stronie) sformalizował pierwsze twierdzenie Gödela o niekompletności w Coq (prover twierdzenia rodzaju wspomnianego powyżej) - i to twierdzenie obejmuje logikę (z wszystkimi odpowiednimi algorytmami) w innej logice (ze składnią pierwsza logika zakodowana jako liczby). Użył definicji używanych na papierze i sformalizował je bezpośrednio. Wyszukaj „podstawienie” lub „zmienną” i policz, jak często pojawiają się w związku z problemami, aby uzyskać wrażenie. http://r6.ca/Goedel/goedel1.html

Nigdy nie używam tych definicji w mojej pracy, ale każde alternatywne podejście ma swoje wady.