Strzałka (informatyka)

W informatyce strzałki lub śruby są klasami typów używanymi w programowaniu do opisywania obliczeń w czysty i deklaratywny sposób. Po raz pierwszy zaproponowane przez informatyka Johna Hughesa jako uogólnienie monad , strzałki zapewniają referencyjnie przejrzysty sposób wyrażania relacji między logicznymi kroki w obliczeniach. W przeciwieństwie do monad, strzałki nie ograniczają kroków do jednego i tylko jednego wejścia. W rezultacie znalazły zastosowanie między innymi w funkcjonalnym programowaniu reaktywnym , programowaniu bezpunktowym i parserach .

Motywacja i historia

Podczas gdy strzały były w użyciu, zanim zostały uznane za odrębną klasę, dopiero w 2000 roku John Hughes po raz pierwszy opublikował badania skupiające się na nich. Do tego czasu monady okazywały się wystarczające dla większości problemów wymagających połączenia logiki programu w czystym kodzie. Jednak niektóre przydatne biblioteki , takie jak biblioteka Fudgets dla graficznych interfejsów użytkownika i niektóre wydajne parsery, opierały się przepisaniu w formie monadycznej.

Formalna koncepcja strzałek została opracowana w celu wyjaśnienia tych wyjątków kodu monadycznego, aw trakcie tego procesu same monady okazały się podzbiorem strzałek . Od tego czasu strzały były aktywnym obszarem badań. Ich podstawowe prawa i operacje zostały udoskonalone kilka razy, a ostatnie sformułowania, takie jak rachunek strzałek, wymagały tylko pięciu praw.

Związek z teorią kategorii

W teorii kategorii kategorie Kleisliego wszystkich monad tworzą odpowiedni podzbiór strzałek Hughesa. Chociaż przez pewien czas uważano, że kategorie Freyda są równoważne strzałom, od tego czasu udowodniono, że strzały są jeszcze bardziej ogólne. W rzeczywistości strzały są nie tylko równoważne, ale bezpośrednio równe wzbogaconym kategoriom Freyda.

Definicja

Podobnie jak wszystkie klasy typów, strzałki można traktować jako zestaw cech, które można zastosować do dowolnego typu danych . W języku programowania Haskell strzałki umożliwiają łączenie funkcji (reprezentowanych w języku Haskell przez symbol -> ) w zreifikowaną formę. Jednak rzeczywisty termin „strzałka” może również wynikać z faktu, że niektóre (ale nie wszystkie) strzałki odpowiadają morfizmom (znane również jako „strzałki” w teorii kategorii) różnych kategorii Kleisliego. Jako stosunkowo nowa koncepcja, nie ma jednej, standardowej definicji, ale wszystkie sformułowania są logicznie równoważne, zawierają pewne wymagane metody i ściśle przestrzegają pewnych praw matematycznych.

Funkcje

Opis używany obecnie przez standardowe biblioteki Haskell wymaga tylko trzech podstawowych operacji:

Konstruktor typu arr , który pobiera funkcje -> z dowolnego typu s do innego t i podnosi te funkcje do strzałki A między dwoma typami.

                 arr  (  s  ->  t  )  ->  A  s  t

Najpierw metoda potokowa , która pobiera strzałkę między dwoma typami i konwertuje ją na strzałkę między krotkami . Pierwsze elementy w krotkach reprezentują część danych wejściowych i wyjściowych, która jest zmieniona, podczas gdy drugie elementy to trzeci typ u opisujący niezmienioną część, która omija obliczenia.

                pierwszy  (  A  s  t  )  ->  ZA  (  s  ,  u  )  (  t  ,  u  )

Ponieważ wszystkie strzałki muszą być kategoriami , dziedziczą one trzecią operację z klasy kategorii: Operator kompozycji >>> , który może dołączyć drugą strzałkę do pierwszej, o ile dane wyjściowe pierwszej funkcji i dane wejściowe drugiej mają pasujące typy.

                 A  s  t  >>>  A  t  u  ->  A  s  u

Chociaż tylko te trzy procedury są absolutnie niezbędne do zdefiniowania strzały, można wyprowadzić inne metody, aby ułatwić pracę ze strzałami w praktyce i teorii.

Jeszcze jedną pomocną metodę można wyprowadzić z arr i first (i z której można wyprowadzić pierwszą ):

Operator łączący *** , który pobiera dwie strzałki, prawdopodobnie z różnymi typami danych wejściowych i wyjściowych, i łączy je w jedną strzałkę między dwoma typami złożonymi. Operator scalania niekoniecznie jest przemienny .

                 A  s  t  ***  Au  v  -  >  ZA  (  s  ,  u  )  (  t  ,  v  )

Prawa strzałek

Oprócz pewnych dobrze zdefiniowanych procedur, strzały muszą przestrzegać pewnych zasad dla wszystkich typów, do których mogą być stosowane:

identyfikator tożsamości wszystkich typów (zasadniczo definicje wszystkich wartości dla wszystkich typów w ramach kategorii).

                   arr  id  ==  id

Podczas łączenia dwóch funkcji f & g wymagane operacje na strzałkach muszą być rozłożone na kompozycje z lewej strony.

                   
                  arr  (  f  >>>  g  )  ==  arr  f  >>>  arr  g  pierwszy  (  f  >>>  g  )  ==  pierwszy  f  >>>  pierwszy  g

W poprzednich przepisach orurowanie można zastosować bezpośrednio do funkcji, ponieważ kolejność musi być nieistotna, gdy orurowanie i podnoszenie występują razem.

               arr  (  pierwszy  f  )  ==  pierwszy  (  arr  f  )

Pozostałe prawa ograniczają zachowanie metody potokowej, gdy kolejność kompozycji jest odwrócona, pozwalając również na uproszczenie wyrażeń :

Jeśli tożsamość jest łączona z drugą funkcją w celu utworzenia strzałki, dołączenie jej do funkcji potokowej musi być przemienne.

                           arr  (  id  ***  g  )  >>>  pierwsza  f  ==  pierwsza  f  >>>  arr  (  id  ***  g  )

Rurociąg funkcji przed uproszczeniem typu musi być równoważny uproszczeniu typu przed połączeniem z funkcją bez potoku.

                        pierwszy  f  >>>  arr  ((  s  ,  t  )  ->  s  )  ==  arr  ((  s  ,  t  )  ->  s  )  >>>  f

Na koniec dwukrotne potokowanie funkcji przed ponownym skojarzeniem wynikowej krotki, która jest zagnieżdżona, powinno być takie samo, jak ponowne skojarzenie zagnieżdżonej krotki przed dołączeniem pojedynczego obejścia funkcji. Innymi słowy, ułożone w stos obejścia można spłaszczyć, najpierw łącząc razem te elementy, które nie zostały zmienione przez funkcję.

              
             pierwszy  (  pierwszy  f  )  >>>  arr  (  ((  s  ,  t  ),  u  )  ->  (  s  , (  t  ,  u  ))  )  ==  arr  (  ( (  s  ,  t  ),  u  )  ->  (  s  , (  t  ,  u  ))  )  >>>  pierwszy  f

Aplikacje

Strzałki można rozszerzyć, aby pasowały do określonych sytuacji, definiując dodatkowe operacje i ograniczenia. Powszechnie używane wersje obejmują strzałki z wyborem, które umożliwiają obliczeniu podejmowanie warunkowych , oraz strzałki ze sprzężeniem zwrotnym , które pozwalają krokowi przyjąć własne wyjścia jako dane wejściowe. Inny zestaw strzałek, znany jako strzałki z aplikacją, jest rzadko używany w praktyce, ponieważ w rzeczywistości są odpowiednikami monad.

Pożytek

Strzałki mają kilka zalet, głównie wynikających z ich zdolności do tworzenia jasnej, ale zwięzłej logiki programu. Oprócz unikania skutków ubocznych , programowanie czysto funkcjonalne stwarza więcej możliwości statycznej analizy kodu . To z kolei może teoretycznie prowadzić do lepszych optymalizacji kompilatora , łatwiejszego debugowania i funkcji takich jak cukier składniowy .

Chociaż żaden program nie wymaga ściśle strzałek, uogólniają one większość gęstej funkcji przechodzącej , której wymagałby czysty, deklaratywny kod. Mogą również zachęcać do ponownego wykorzystania kodu , nadając wspólnym powiązaniom między krokami programu własne definicje klas. Możliwość ogólnego stosowania do typów również przyczynia się do ponownego użycia i upraszcza interfejsy .

Strzały mają pewne wady, w tym początkowy wysiłek polegający na zdefiniowaniu strzały, która spełnia prawa dotyczące strzał. Ponieważ monady są zwykle łatwiejsze do zaimplementowania, a dodatkowe funkcje strzałek mogą być niepotrzebne, często lepiej jest używać monad. Innym problemem, który dotyczy wielu funkcjonalnych konstrukcji programistycznych, jest wydajne kompilowanie kodu ze strzałkami do stylu imperatywnego używanego w zestawach instrukcji komputerowych . ^{[ potrzebne źródło ]}

Ograniczenia

Ze względu na konieczność zdefiniowania funkcji arr w celu podniesienia czystych funkcji, zastosowanie strzałek jest ograniczone. Na przykład przekształceniami dwukierunkowymi nie mogą być strzałki, ponieważ przy użyciu arr należałoby podać nie tylko czystą funkcję, ale także jej odwrotność . Ogranicza to również użycie strzałek do opisywania reaktywnych ram opartych na wypychaniu, które zatrzymują niepotrzebną propagację. Podobnie użycie par do krotki wartości razem skutkuje trudnym stylem kodowania, który wymaga dodatkowych kombinatorów do przegrupowania wartości i rodzi fundamentalne pytania dotyczące równoważności strzałek pogrupowanych na różne sposoby. Te ograniczenia pozostają otwartym problemem, a rozszerzenia, takie jak Generalized Arrows i N-ary FRP, badają te problemy.

Znaczna część użyteczności strzał jest podporządkowana bardziej ogólnym klasom, takim jak Profunctor (który wymaga jedynie wstępnej i końcowej kompozycji z funkcjami), które mają zastosowanie w optyce. Strzała jest zasadniczo silnym profunktorem, który jest również kategorią, chociaż prawa są nieco inne.

Linki zewnętrzne

Strzałki: ogólny interfejs do obliczeń
A New Notation for Arrows , Ross Paterson, w ICFP, wrzesień 2001.
Notacja strzałkowa podręcznik ghc