Czy rachunek lambda i logika kombinacyjna są takie same?

26

Obecnie czytam „ Lambda-Calculus and Combinators ” Hindleya i Seldina. Nie jestem ekspertem, ale zawsze interesowałem się rachunkiem lambda ze względu na zaangażowanie w programowanie funkcjonalne (zaczynając od Lisp i SICP, a teraz od R i Haskell).

W „ Binary rachunek lambda i rachunek kombinatorów” , John Tromp stwierdza:

CL można postrzegać jako podzbiór rachunku lambda ... teorie są w dużej mierze takie same, stając się równoważne w obecności zasady ekstensywności.

W jakich warunkach należałoby zastosować logikę kombinacyjną zamiast rachunku lambda ?

Wszelkie referencje będą mile widziane.

Shane
źródło
Spójrz na „Rachunek Lambda: jego składnia i semantyka” autorstwa HP Barendregt.
Kaveh

Odpowiedzi:

15

To, co wyróżnia logikę kombinatoryczną, to brak zmiennej. Czasami jest to przydatne w metamatematyce i logice filozoficznej, gdzie status zmiennych jest trudny.

Może być również przydatny w implementacjach, ponieważ zarządzanie zmiennymi może być uciążliwe. Por. Np. Hughes, 1982, Super-kombinatory: nowa metoda implementacji języków aplikacji

Charles Stewart
źródło
3
Logika kombinacyjna nie jest już uważana za przydatną we wdrożeniach i nigdy nie była używana, ponieważ „zarządzanie zmiennymi może być problemem”. Kombinatory i warianty zostały użyte do zaimplementowania redukcji grafów dla leniwych języków, ale obecnie Haskell (najbardziej znany leniwy język) stosuje znacznie bardziej rozsądne techniki do implementacji redukcji grafów.
Blaisorblade,
Patrz np. S. Peyton Jones, 1992, „Wdrażanie leniwych języków funkcjonalnych na standardowym sprzęcie: bezgwiezdna maszyna Tagless G” - research.microsoft.com/copyright/accept.asp?path=/users/simonpj/…
Blaisorblade
2
@ Blaisorblade: Kombinatory i warianty zostały użyte do zaimplementowania redukcji wykresów dla leniwych języków - Uważaj: Haskell i ghc to nie to samo, a literatura zawiera kilka Haskellów opartych na superkombinatorze. Ale to prawda, że ​​najnowocześniejsze programowanie funkcjonalne odkryło zalety wydajności środowisk obsługi, które przewyższają jego złożoność. Nadal widzisz superkombinatory używane np. W programowaniu logiki wyższego rzędu, gdzie nie jest to prawdą. Superkombinatory pozostają częścią wykazu technik stosowanych przy wdrażaniu programowania wyższego rzędu.
Charles Stewart,
Superkombinatory unikają tylko zmiennych swobodnych, a nie zmiennych, więc IMHO nie można uznać za zastosowania logiki kombinacyjnej per se. Są to głównie specjalne warunki lambda. Istnieją znacznie mniejsze różnice między superkombinatorami, programami podnoszonymi przez lambda (jeśli istnieją, nie są pewne) i implementacją GHC (gdzie wskaźniki z zamknięcia do wolnych zmiennych można skopiować z funkcji hosta, dzięki czystości). Powiedziawszy to, myślałem również o najnowszym kompilatorze Utrechta Haskella, który jest bardzo podobny do GHC, ale IIRC stosuje podnoszenie lambda; wciąż to nie jest CL.
Blaisorblade,
Nie wiedziałem o programowaniu logiki wyższego rzędu - znalazłem na nim ten artykuł: springerlink.com/content/t68777w270713p5n . Niestety jest mało prawdopodobne, że będę miał czas to przeczytać.
Blaisorblade,
4

Odwoływanie się do komentarza Jana Tromp, chcę uwagą, że rachunek kombinatorów czuje się bardzo różni się od rachunku lambda. Ponieważ twoje zainteresowanie wynika z programowania funkcjonalnego, tak naprawdę nie chcesz wiedzieć zbyt wiele o logice kombinatorycznej.

Mój ulubiony samouczek na temat logiki kombinatorycznej znajduje się w tych notatkach z wykładów na Uniwersytecie Cambridge.

Zostały one jednak wprowadzone w celu wyjaśnienia implementacji tak zwanych leniwych (lub aplikacyjnych) języków; jak wspomniano w poprzednim komentarzu, takie techniki są obecnie nieaktualne.

Blaisorblade
źródło
Ponieważ języki kombinowane nie są już używane do implementacji języków leniwych / aplikacyjnych, jakie są obecnie najnowsze techniki? I czy istnieje nazwa / kategoria do sklasyfikowania tych technik?
CMCDragonkai
@CMCDragonkai Zobacz komentarze do cstheory.stackexchange.com/a/306/989 w celu dyskusji. Krótka praktyczna odpowiedź brzmi: „zapoznaj się z artykułami na temat tego, co robi GHC”: istnieje wiele różnych technik (w tym zarówno maszyna STG, jak i optymalizacje, takie jak analiza dokładności), które są łączone razem, aby programy leniwe działały szybko.
Blaisorblade,