Status quo teorii kategorii i monad w teoretycznych badaniach informatycznych?

17

Tło . Jestem studentem studiów licencjackich, który interesuje się badaniami związanymi z teorią kategorii, monadami i Haskellem, i chcę znaleźć temat do mojej pracy licencjackiej w tej dziedzinie.

Spojrzałem na gazetę

i jeszcze niewiele z tego rozumiem. Prawdopodobnie będę potrzebować trochę czasu, aby w pełni to zrozumieć. Ale zanim spędzę więcej czasu na studiowaniu, chcę lepiej zrozumieć dziedzinę i jej potencjał badawczy. Niedawno rozmawiałem na ten temat z moim profesorem i powiedział mi, że monady były modne w środowisku naukowym w latach 90., ale obecnie nie są modne.

Dlatego teraz szukam najnowszych prac związanych z monadami i zastanawiam się:

  • W jakich obszarach informatyki teoretycznej prowadzone są obecnie badania związane z teorią kategorii i monadami?
  • Jakie badania zostały opracowane lub zaproponowane w pracy E. Moggi nad monadami w teorii programowania? Czy były jakieś dalsze lub trwające badania związane z jego pracą?
k.stm
źródło
Zanim odpowiemy na to pytanie: czyż nie jest to poziom badawczy? Może lepiej pasować do cs.stackexchange.com.
Andrej Bauer,
3
@AndrejBauer Moja praca licencjacka nie będzie na poziomie badawczym, ale moje pytanie dotyczy aktualnych badań lub przynajmniej badań przeprowadzonych w ostatniej dekadzie.
k.stm
9
@AndrejBauer Nie zgadzam się. Witryna siostrzana jest przeznaczona głównie do zadawania zadań domowych, podczas gdy tutaj potrzebna jest opinia eksperta.
Yuval Filmus,
@Kaveh To była dość drastyczna edycja, którą właśnie wprowadziłeś. Poprawiłeś niektóre punkty, ale teraz to nie jest pytanie, które zadawałem. Kiedy jutro będę mieć czas, cofnę niektóre zmiany. Na przykład ważne jest dla mnie, aby mieć tam tło. Powiedz mi, jakie zmiany uważasz za konieczne i dlaczego, więc wiem, czego nie wycofać.
k.stm
1
@Yuval, myślę, że wiele osób z informatyki zdecydowanie nie zgodziłoby się z twoim komentarzem, że dotyczy to głównie prac domowych i że eksperci nie są obecni w dziedzinie informatyki . W tym przypadku Andrej odpowiedział na ponad 100 pytań z zakresu informatyki .
Kaveh

Odpowiedzi:

15

Od czasu Eugenio Moggi nastąpił szereg zmian w zakresie wykorzystania monad w teorii obliczeń. Nie jestem w stanie podać wyczerpującego opisu, ale oto kilka punktów, które znam, inni mogą odpowiedzieć na ich odpowiedzi.

Konkretne przykłady monad

Nie musisz cały czas studiować teorii ogólnej. Istnieją przykłady monad, które są bardzo interesujące i wystarczająco skomplikowane, aby wypełnić całą pracę licencjacką.

Bardzo podoba mi się blog Dana Piponiego, na którym podaje niesamowite przykłady wykorzystania monad do łączenia programowania funkcjonalnego i matematyki. Szukaj na przykład swojej pracy na węzłach i warkocz przez monady.

Inny konkretny przykład mond, które warto studiować, podali Martin Escardo i Paulo Oliva w kontekście funkcjonałów selekcji, zobacz ich Funkcje selekcji, Rekurencja barów i Indukcja wsteczna , a może najpierw zainteresuj się, co przeczytają What Sequential Games, Tychonoff Theorem i the Double-Negation Shift mają wspólne (powiązane pliki Haskell i Agda tutaj ).

Tło matematyczne

Monady pochodzą z teorii kategorii i są znacznie starsze niż Eugenio Moggi. Możesz studiować teorię tła, jeśli masz matematyczne skłonności. Na przykład możesz zaatakować twierdzenie o monadyczności Becka . Teoretyczny informatyk nigdy nie zna zbyt dużej matematyki.

Wariacje na temat

Możesz spojrzeć na coś, co nie jest ściśle monadą.

Na przykład Idiomy Connora McBride'a i Rossa Patersona : programowanie aplikacyjne z efektami pokazuje, jak można uogólnić monady na coś, co jest praktycznie istotne i wnikliwe.

Możesz też spojrzeć na to, w jaki sposób comonady są używane do modelowania efektów obliczeniowych. Ktoś powinien zasugerować odniesienia do tego tematu, ale dobrym początkiem mogą być slajdy Davida Overtone .

Teoria typów modalnych

W teorii typów homotopii, a także ogólnie w teorii typów, monady pojawiają się w formie modalnej teorii typów . Ostatnio teoria typów modalnych została rozważona w teorii typów homotopii, ponieważ operatory obcięcia są przykładami operatorów modalnych. Następnie istnieje spójna teoria typu homotopii, w której operatory modalne (które są monadami) odgrywają istotną rolę.

Efekty algebraiczne i programy obsługi

[Uwaga: częściowo dmucham tutaj w swój własny róg.]

Jakiś czas temu Gordon Plotkin i John Power zauważyli, że wiele efektów obliczeniowych to nie tylko monady, ale specjalne monady wynikające z teorii algebraicznych. Doprowadziło to do zupełnie nowego traktowania efektów obliczeniowych znanych jako efekty algebraiczne . Później Gordon Plotkin i Matija Pretnar przedstawili moduły obsługi i razem z efektami algebraicznymi tworzą bardzo ładną teorię efektów obliczeniowych. Zaletą tego podejścia jest to, że teorie algebraiczne można łatwo łączyć, podczas gdy monady nie.

Możesz przestudiować, jak dokładnie efekty algebraiczne odnoszą się do monad. Możesz spojrzeć na to, jak ludzie implementowali efekty algebraiczne i procedury obsługi, powiedzmy w języku Eff lub w Haskell jako bibliotekę . To mniej więcej aktualne badania.

Andrej Bauer
źródło
Cześć, dzięki za odpowiedź! Kliknąłem twoją stronę o Eff i wygląda na to, że link do An Introduction to Algebraic Effects and Handlers jest nieaktualny, tzn eff-lang.org/handlers-tutorial.pdf. Brakuje pliku .
k.stm
1
Poprosiłem Matidię o naprawienie linku, tymczasem możesz zajrzeć na arxiv.org/abs/1203.1539 .
Andrej Bauer,
Już jestem. Czy możesz, na marginesie, podać krótki przegląd teorii tła, którą muszę przestudiować, aby zrozumieć twój artykuł? Znam pewną teorię kategorii, niepisany rachunek lambda i podstawową teorię obliczeń i elementarną teorię programowania (wiem, czym jest semantyka denotacyjna), ale jak dotąd niewiele więcej. Mogę na przykład już powiedzieć w części 3 twojego artykułu, że muszę przyjrzeć się regułom pisania na klawiaturze (więc może i wypisanemu rachunku lambda). Przepraszam, jeśli jestem natarczywy.
k.stm
3
Powinieneś wiedzieć trochę o algebrze uniwersalnej i / lub teorii teorii algebraicznej Lavwere'a. Jeśli nie znasz zasad pisania, możesz uczyć się ogólnego podręcznika na temat języków programowania, takiego jak TAPL Benjamina Pierce'a lub Praktyczne podstawy języków programowania Boba Harpera .
Andrej Bauer,
1

Ten artykuł zawiera kilka ważnych ostatnich prac z wykorzystaniem monad.

NietzscheanAI
źródło
1
Cześć, dzięki za odpowiedź. Byłbym wdzięczny za mały kontekst, to znaczy, jeśli możesz poświęcić czas na podanie szczegółów. (W rzeczywistości gazeta ma ładne wprowadzenie na temat jej zawartości, ale nadal chciałbym zobaczyć kontekst dla swojego otoczenia, na przykład, jeśli jest związana z tym praca.)
k.stm