Co to są kombinatory i jak są stosowane do projektów programistycznych? (praktyczne wyjaśnienie)

Co to są kombinatory?

Szukam:

• praktyczne wyjaśnienie
• przykłady ich wykorzystania
• przykłady tego, jak kombinatory poprawiają jakość / ogólność kodu

Nie szukam:

• objaśnienia dotyczące łączników, które nie pomagają mi w pracy (np. łącznik Y)

Z praktycznego punktu widzenia kombinatory są rodzajem konstrukcji programistycznych, które pozwalają łączyć logikę w ciekawe i często zaawansowane sposoby. Zazwyczaj ich użycie zależy od możliwości spakowania wykonywalnego kodu w obiektach, często nazywanych (z przyczyn historycznych) funkcjami lambda lub wyrażeniami lambda, ale przebieg może być różny.

Prostym przykładem (przydatnego) kombinatora jest taki, który przyjmuje dwie funkcje lambda bez parametrów i tworzy nową, która uruchamia je kolejno. Rzeczywisty kombinator wygląda w ogólnym pseudokodzie, takim jak ten:

func in_sequence(first, second):
  lambda ():
    first()
    second()

Kluczową rzeczą, która czyni z tego kombinatora, jest anonimowa funkcja (funkcja lambda) w drugim wierszu; kiedy zadzwonisz

a = in_sequence(f, g)

wynikowy obiekt a nie jest wynikiem uruchomienia najpierw f (), a następnie g (), ale jest to obiekt, który można wywołać później, aby wykonać kolejno f () i g ():

a() // a is a callable object, i.e. a function without parameters

Podobnie możesz mieć kombinator, który uruchamia równolegle dwa bloki kodu:

func in_parallel(first, second):
  lambda ():
    t1 = start_thread(first)
    t2 = start_thread(second)
    wait(t1)
    wait(t2)

I znowu

a = in_parallel(f, g)
a()

Fajne jest to, że „in_parallel” i „in_sequence” są kombinatorami tego samego typu / sygnatury, tzn. Oba pobierają dwa parametry funkcji bez parametrów i zwracają nowy. Możesz wtedy pisać takie rzeczy

a = in_sequence(in_parallel(f, g), in_parallel(h, i))

i działa zgodnie z oczekiwaniami.

Zasadniczo więc kombinatory pozwalają konstruować przepływ kontroli programu (między innymi) w sposób proceduralny i elastyczny. Na przykład, jeśli używasz kombinatora in_parallel (..) do uruchamiania równoległości w swoim programie, możesz dodać związane z tym debugowanie do implementacji samego kombinatora in_parallel. Później, jeśli podejrzewasz, że twój program ma błąd związany z równoległością, możesz po prostu ponownie zaimplementować in_parallel:

in_parallel(first, second):
  in_sequence(first, second)

a jednym pociągnięciem wszystkie równoległe sekcje zostały przekształcone w sekwencyjne!

Kombinatory są bardzo przydatne, gdy są właściwie stosowane.

Kombinator Y nie jest jednak potrzebny w prawdziwym życiu. Jest to kombinator, który pozwala tworzyć funkcje samorekurencyjne i można je łatwo tworzyć w dowolnym nowoczesnym języku bez kombinatora Y.

Błędem jest oznaczać kombinator Y jako coś, co „nie pomoże w wykonaniu pracy”. Znalazłem to bardzo przydatne przy wielu okazjach. Najbardziej oczywistym przypadkiem jest sytuacja, gdy trzeba szybko uruchomić jakiś wbudowany interpretowany język. Jeśli podasz minimalny zestaw prymitywów, a mianowicie sequence, select, call, consti closure allocationjest to już wystarczający do budowania kompletnego, arbitralne skomplikowanego języka. Nie jest wymagane specjalne wsparcie dla rekurencji - można je dodać za pomocą kombinatora punktów stałych. W przeciwnym razie będziesz potrzebował znacznie bardziej skomplikowanych prymitywów.

Innym oczywistym przypadkiem kombinatorów jest zaciemnianie. Kod przetłumaczony na rachunek SKI jest praktycznie nieczytelny. Jeśli naprawdę musisz zaciemnić implementację algorytmu, rozważ użycie kombinacji, oto przykład .

I oczywiście, kombinatory są ważnym narzędziem do implementacji języków funkcjonalnych. Najłatwiejszym podejściem (jak w powyższym przykładzie) jest SKI lub rachunek różniczkowy. Superkombinatory są używane w niektórych innych implementacjach. Ta książka mówi o tym dogłębnie.

To żart , ale żart wart bardzo uważnej lektury, ponieważ omówiono w nim wiele tajemnych technik programowania i teorii.

Przekopując się trochę, znalazłem pytanie StackOverflow, dobre wyjaśnienie „Kombinatorów” (dla nie matematyków), które jest bliskim kuzynem tego pytania. Jedna z odpowiedzi wskazywała na blog Reginalda Braithwaite'a, Homoiconic , który zawiera linki do kilku użytecznych przykładów kombinatorów w kodzie (np . Kombinator K , zaimplementowany metodą Ruby'ego Object#tap- przeczytaj stronę z przykładami, dlaczego jest przydatny).

Strona Wikipedii na temat logiki kombinatorycznej opisuje kombinatory bardziej globalnie.