Co rozumie teoria kategorii, nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu?

Czytając Uday Reddy za odpowiedź na Jaka jest relacja między funktorów w SML i teorii kategorii? Stwierdza Uday

Teoria kategorii nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu. Pewnego dnia to zrobi.

Ponieważ myślałem, że teoria kategorii może służyć jako podstawa matematyki, powinna istnieć możliwość uzyskania wszystkich funkcji matematycznych i wyższych rzędów.

Co więc rozumie teoria kategorii, nie wie jeszcze, jak radzić sobie z funkcjami wyższego rzędu? Czy warto rozważyć teorię kategorii jako podstawę matematyki?

functional-programming category-theory Guy Coder
źródło

Ta dyskusja byłaby idealna dla cstheory.stackexchange.com .

Martin Berger,

Odpowiedzi:

Problem z funkcjami wyższego rzędu jest wystarczająco prosty do stwierdzenia.

Konstruktor typu, taki jak nie jest funktorem. To powinno być. $T(X) = [X \to X]$
Funkcja polimorficzna, taka jak nie jest naturalną transformacją. To powinno być. ${\it twice}_X : T(X) \to T(X) = \lambda f.\, f \circ f$

Jeśli czytasz Eilenberg and MacLane za oryginalny papier teorii kategorii , (PDF) intuicje one obecne pokrycie tych przypadkach. Ale ich teoria nie. Ich była świetna gazeta na 1945 rok! Ale dzisiaj potrzebujemy więcej.

Reakcja teoretyków kategorii na te problemy jest nieco kłopotliwa. Działają tak, jakby operacje wyższego rzędu tworzyły ideę informatyki; nie mają one wpływu na matematykę. Jeśli tak, to podstawa matematyki nie byłaby wystarczająca dla podstaw informatyki.

Ale nie wierzę w to poważnie. Uważam, że funkcje wyższego rzędu byłyby również bardzo ważne dla matematyki. Ale nie zostały poważnie zbadane. Mam nadzieję, że pewnego dnia zostaną one zbadane i zostaną spełnione ograniczenia teorii kategorii.

Uday Reddy
źródło

To zdumiewające, że nie uważają interesujących funkcji wyższego rzędu za interesujące, biorąc pod uwagę głębokości, które przechodzą podczas eksploracji algebry wyższego wymiaru, teorii kategorii n i tym podobnych. Dla porównania, funkcje wyższego rzędu wydają się tak przyziemne. Zwłaszcza jeśli ta ziemia obejmuje programy Haskella.

Dave Clarke

n

$n$

A ≅ A^{*}

$A \cong A^*$

A ≅ A^{* *}

$A \cong A^{**}$

T (X)

$T(X)$

A \to B

$A \to B$

+1 To jest naprawdę interesujące. Czy znasz jakieś odniesienia, które bardziej szczegółowo omawiają te problemy?

Kaveh

λ

$\lambda$

π

$\pi$

π

$\pi$

[Ta druga odpowiedź przedstawia zarys tego, jak mogłaby wyglądać „Teoria kategorii 2.0”, która prawidłowo obsługuje funkcje wyższego rzędu.]

Od dawna wiemy, jak radzić sobie z funkcjami wyższego rzędu w ich uzasadnieniu.

Kiedy struktura algebraiczna ma operacje wyższego rzędu, homomorfizmy nie działają. Zamiast tego musimy użyć relacji logicznych . Innymi słowy, musimy przejść od „ funkcji zachowujących strukturę” do „ relacji zachowujących strukturę”.
Mówiąc o przekształceniach „jednolitych” lub „równoczesnych” na typach wyższego rzędu, naturalność nie działa. Zamiast tego musimy zastosować parametryczną relację . Innymi słowy, musimy przejść od „rodzin zachowujących wszystkie morfizmy ” do „rodzin zachowujących wszystkie logiczne relacje ”.
$\to$

Szybkie wprowadzenie do tych zagadnień znajduje się w sekcji Petera O'Hearn'a „Parametryzacja relacyjna” w Domenach i Denotational Semantics: Historia, osiągnięcia i otwarte problemy (CiteSeerX) .

Pierwsza próba zbudowania „Teorii kategorii 2.0” jest w O'Hearn i Tennent's Parametricity and Local Variables (CiteSeerX) .
Praca doktorska Briana Dunphy'ego: Parametryzacja jako pojęcie jednolitości grafów refleksyjnych (CiteSeerX) opiera się na ich ramach i aksjatyzuje strukturę relacyjną potrzebną do uzyskania wyników parametryczności. Poleciłbym tezę Dunphy'ego, aby uzyskać dobry przegląd wszystkich problemów.
Dla kompletności powinienem również wspomnieć o rozprawie doktorskiej Claudio Hermidy : Fibracje, predykaty logiczne i nieokreślone (PDF) , która jako pierwsza badała logiczne relacje w kategoriach teoretycznych, ale jego leczenie może być zbyt techniczne dla większości ludzi.

Mógłbym również dodać, że rozumowanie o stanie to miejsce, w którym funkcje wyższego rzędu pojawiają się w widocznym miejscu. Teoretycy automatów jako pierwsi zauważyli, że homomorfizmy nie działają poprawnie, w historycznym artykule zatytułowanym Produkty automatów i problem pokrycia . Używali terminów takich jak „słaby homomorfizm” i „relacje obejmujące” w odniesieniu do relacji logicznych. W stosownym czasie zastosowano do nich określenia takie jak „symulacja” i „bisimulacja”. Artykuł z ankiety Davide Sangiorgi: O początkach bisimulacji i koindukcji obejmuje całą tę wczesną historię i nie tylko.

W szczególności potrzeba rozumowania relacyjnego pojawia się wielokrotnie w uzasadnieniu stanu programowaniu imperatywnym . Bardzo niewiele osób zauważa, że skromny „średnik” jest operacją wyższego rzędu. Tak więc nie możesz od razu zacząć myśleć o programach imperatywnych, nie wiedząc, jak radzić sobie z funkcjami wyższego rzędu. Ignorujemy kwestie programowania stanowego i imperatywnego w błędnym przekonaniu, że matematyka ma wszystkie odpowiedzi. Tak więc, jeśli matematycy nie rozumieją stanu, to nie może być dobrze! Nic nie może być dalej od prawdy. Stan jest w centrum informatyki. Będziemy ogólnie rozwijać naukę, pokazując ludziom, jak postępować z państwem!

Uday Reddy
źródło

@ GuyCoder, myślę, że to dobry pomysł. Nawiasem mówiąc, myślę, że to i to pytanie będzie dotyczyło również Teoretycznej Informatyki, na wypadek gdybyś wolał je tam zamieścić.

Kaveh

Po rozmowie z Udayem nie będzie specjalnie zadawane nowe pytanie dotyczące tej drugiej odpowiedzi. :)

Guy Coder

Państwo jest relatywistyczne.

Shelby Moore III