Marzenie o deklaratywnym programowaniu [zamknięte]

Dlaczego nie zrealizowano marzenia o deklaratywnym programowaniu? Jakie przeszkody stoją na przeszkodzie? Dla prostego przykładu, dlaczego nie mogę powiedzieć

sort(A) is defined by sort(A) in perm(A) && asc(sort(A))

i automatycznie pobiera z niego algorytm sortowania. permoznacza permutacje i ascoznacza rosnąco.

Istnieje kilka bardzo dobrych odpowiedzi. Spróbuję przyczynić się do dyskusji.

Na temat deklaratywnego programowania logicznego w Prologu znajduje się świetna książka „Craft of Prolog” Richarda O'Keefe . Chodzi o pisanie wydajnych programów przy użyciu języka programowania, który pozwala pisać bardzo nieefektywne programy. W tej książce, omawiając efektywne implementacje kilku algorytmów (w rozdziale „Metody programowania”), autor przyjmuje następujące podejście:

• zdefiniuj problem po angielsku
• napisz działające rozwiązanie, które będzie jak najbardziej deklaratywne; zazwyczaj oznacza to dokładnie to, co masz w swoim pytaniu, po prostu popraw Prolog
• stamtąd podejmij kroki, aby ulepszyć implementację, aby przyspieszyć

Najbardziej pouczająca (jak dla mnie) obserwacja, jaką udało mi się zrobić, przechodząc przez te:

Tak, ostateczna wersja implementacji jest znacznie wydajniejsza niż specyfikacja „deklaratywna”, od której zaczął autor. Jest nadal bardzo deklaratywny, zwięzły i łatwy do zrozumienia. To, co wydarzyło się w międzyczasie, polega na tym, że ostateczne rozwiązanie ujmuje właściwości problemu, dla którego pierwotne rozwiązanie było nieświadome.

Innymi słowy, wdrażając rozwiązanie, wykorzystaliśmy jak najwięcej naszej wiedzy na temat problemu. Porównać:

Znajdź permutację listy, tak aby wszystkie elementy były w porządku rosnącym

do:

Scalenie dwóch posortowanych list spowoduje posortowanie listy. Ponieważ mogą istnieć podlisty, które są już posortowane, użyj ich jako punktu wyjścia zamiast podlist o długości 1.

Odkładając na bok: definicja taka jak ta, którą podałeś, jest atrakcyjna, ponieważ jest bardzo ogólna. Nie mogę jednak uniknąć wrażenia, że ​​celowo ignoruje fakt, że permutacje są, no cóż, problemem kombinatorycznym. To już wiemy ! To nie jest krytyka, tylko spostrzeżenie.

Jeśli chodzi o prawdziwe pytanie: jak iść do przodu? Jednym ze sposobów jest dostarczenie tak dużej wiedzy na temat problemu, który zgłaszamy komputerowi.

Najlepsza znana mi próba rozwiązania tego problemu została przedstawiona w książkach współautorów Aleksandra Stepanowa, „Elementach programowania” i „Od matematyki do programowania ogólnego” . Niestety nie jestem w stanie streścić (a nawet w pełni zrozumieć) wszystkiego w tych książkach. Istnieje jednak podejście polegające na zdefiniowaniu wydajnych (lub nawet optymalnych) algorytmów bibliotecznych i struktur danych, pod warunkiem, że wszystkie odpowiednie właściwości danych wejściowych są znane z góry. Ostateczny wynik to:

• Każda dobrze zdefiniowana transformacja jest udoskonaleniem istniejących już ograniczeń (właściwości, które są znane);
• Pozwalamy komputerowi decydować, która transformacja jest optymalna na podstawie istniejących ograniczeń.

Jeśli chodzi o to, dlaczego jeszcze się to nie wydarzyło, cóż, informatyka jest naprawdę młodą dziedziną, a my wciąż sobie radzimy, naprawdę doceniając nowość większości z nich.

PS

Aby posmakować tego, co mam na myśli przez „dopracowanie implementacji”: weźmy na przykład prosty problem uzyskania ostatniego elementu listy, w Prologu. Kanonicznym rozwiązaniem deklaratywnym jest powiedzenie:

last(List, Last) :-
    append(_, [Last], List).

Tutaj deklaratywnym znaczeniem append/3jest:

List1AndList2jest konkatenacją List1iList2

Ponieważ w drugim argumencie append/3mamy listę zawierającą tylko jeden element, a pierwszy argument jest ignorowany (podkreślenie), otrzymujemy podział pierwotnej listy, który odrzuca przód listy ( List1w kontekście append/3) i żąda, aby back ( List2w kontekście append/3) jest rzeczywiście listą zawierającą tylko jeden element: więc jest to ostatni element.

Faktyczna realizacja zapewnia SWI-Prolog jednak mówi:

last([X|Xs], Last) :-
    last_(Xs, X, Last).

last_([], Last, Last).
last_([X|Xs], _, Last) :-
    last_(Xs, X, Last).

To wciąż jest bardzo deklaratywne. Czytaj od góry do dołu, mówi:

Ostatni element listy ma sens tylko dla listy przynajmniej jednego elementu. Ostatnim elementem dla pary ogona i głowy listy jest zatem: głowa, gdy ogon jest pusty, lub ostatni niepusty ogon.

Powodem, dla którego ta implementacja jest zapewniona, jest obejście praktycznych problemów związanych z modelem wykonania Prologu. Idealnie nie powinno mieć znaczenia, która implementacja jest używana. Podobnie moglibyśmy powiedzieć:

last(List, Last) :-
    reverse(List, [Last|_]).

Ostatni element listy jest pierwszym elementem listy odwróconej.

Jeśli chcesz wypełnić niejednoznaczne dyskusje na temat tego, co jest dobre, deklaratywne Prolog, po prostu przejrzyj niektóre pytania i odpowiedzi w tagu Prolog na Stack Overflow .

Języki logiczne już to robią. Możesz zdefiniować sortowanie podobnie, jak to robisz.

Głównym problemem jest wydajność. Komputery mogą być świetne w obliczaniu wielu rzeczy, ale z natury są głupie. Każda „sprytna” decyzja, jaką może podjąć komputer, została zaprogramowana przez programistę. Ta decyzja jest zwykle opisywana nie przez to, jak wygląda efekt końcowy, ale przez to, jak krok po kroku osiągnąć ten wynik końcowy.

Wyobraź sobie historię Golema . Jeśli spróbujesz wydać mu abstrakcyjne polecenie, w najlepszym wypadku zrobi to nieefektywnie, aw najgorszym razie zrani samego siebie, ciebie lub kogoś innego. Ale jeśli opisujesz to, co chcesz w najdrobniejszych szczegółach, masz gwarancję, że zadanie zostanie wykonane skutecznie i wydajnie.

Zadaniem programisty jest określenie, jakiego poziomu abstrakcji użyć. Jeśli chodzi o twoją aplikację, czy zamierzasz przejść na wyższy poziom i opisać ją w sposób abstrakcyjny, wziąć wydajność lub obniżyć i ubrudzić, poświęcić na nią 10 razy więcej czasu, ale uzyskać algorytm, który jest 1000 razy bardziej wydajny?

Oprócz doskonałego punktu Euphoric , chciałbym dodać, że już używamy języków deklaratywnych w wielu miejscach, w których działają one dobrze, tj. Opisując stan, który prawdopodobnie nie zmieni się, lub żądając czegoś, dla którego komputer może wygenerować wydajny kod samemu:

• HTML deklaruje, jaka jest zawartość strony internetowej.

• CSS deklaruje, jak powinny wyglądać różne typy elementów na stronie internetowej.

• Każda relacyjna baza danych ma język definicji danych, który deklaruje strukturę bazy danych.

• SQL jest znacznie bliższy deklaratywnemu niż imperatywnemu, ponieważ mówisz mu, co chcesz zobaczyć, a planista zapytań bazy danych wymyśli, jak to zrobić.

• Można argumentować, że większość plików konfiguracyjnych (.vimrc, .profile, .bashrc, .gitconfig) używa języka specyficznego dla domeny, który jest w dużej mierze deklaratywny

Abstrakcje są nieszczelne

Możesz wdrożyć system deklaratywny, w którym deklarujesz, co chcesz, a kompilator lub tłumacz ustala kolejność wykonywania. Teoretyczna korzyść polega na tym, że uwalnia Cię od myślenia o tym, jak to zrobić, i nie musisz szczegółowo opisywać tej implementacji. Jednak w praktyce do obliczeń ogólnego przeznaczenia wciąż trzeba myśleć o „jak” i pisać wszelkiego rodzaju sztuczki, pamiętając o tym, jak to zostanie zaimplementowane, ponieważ w przeciwnym razie kompilator może (i często wybierze) implementację, która będzie bardzo, bardzo, bardzo wolne (np. n! operacje, w których wystarczyłoby n).

W twoim przykładzie otrzymasz algorytm sortowania A - nie oznacza to, że dostaniesz dobry, a nawet nieco użyteczny. Podana definicja, jeśli zostanie zaimplementowana dosłownie (prawdopodobnie byłby to kompilator), spowoduje http://en.wikipedia.org/wiki/Bogosort, który nie nadaje się do większych zestawów danych - jest technicznie poprawny, ale potrzebuje wieczności, aby posortować tysiące liczb .

W niektórych ograniczonych domenach możesz pisać systemy, które prawie zawsze dobrze sobie radzą w ustalaniu dobrej implementacji, na przykład SQL. W przypadku obliczeń ogólnego przeznaczenia, które nie działają szczególnie dobrze - możesz pisać systemy, powiedzmy, w Prologu, ale musisz wizualizować, w jaki sposób dokładnie twoje deklaracje zostaną ostatecznie przekonwertowane na bezwzględną kolejność wykonywania, i która traci wiele z oczekiwanych deklaratywnych korzyści programistyczne.

Decydowalność obliczeniowa jest najważniejszym powodem, dla którego programowanie deklaratywne nie okazało się tak łatwe, jak się wydaje.

Wiele problemów, które są stosunkowo łatwe do stwierdzenia, okazało się nierozstrzygalne lub mają złożoną NP do rozwiązania. Dzieje się tak często, gdy bierzemy pod uwagę ujemne klasy i klasyfikację, policzalność i rekurencję.

Chciałbym to wyjaśnić w przypadku niektórych dobrze znanych domen.

Decyzja, której klasy CSS użyć, wymaga znajomości i uwzględnienia wszystkich reguł CSS. Dodanie nowych reguł może unieważnić wszystkie inne decyzje. Negatywne klasy CSS celowo nie są dodawane do języka z powodu problemów z NP-zupełnością, ale brak klas negatywnych komplikuje decyzje projektowe CSS.

W optymalizatorze zapytań (SQL) istnieje kłopotliwy problem z decyzją, w jakiej kolejności dołączyć, jakie indeksy użyć i jaką pamięć przydzielić do jakich wyników tymczasowych. Jest to znany problem NP-zupełny i komplikuje projektowanie baz danych i formułowanie zapytań. Aby sformułować inaczej: podczas projektowania bazy danych lub zapytania projektant musi znać działania i kolejność działań, które prawdopodobnie podejmie optymalizator zapytań. Doświadczony inżynier potrzebuje wiedzy na temat heurystyki wykorzystywanej przez głównych dostawców baz danych.

Pliki konfiguracyjne są deklaratywne, ale niektóre konfiguracje są trudne do zadeklarowania. Na przykład, aby poprawnie skonfigurować funkcje, należy wziąć pod uwagę wersjonowanie, wdrożenie (i historię wdrażania), możliwe ręczne zastąpienia i możliwe konflikty z innymi ustawieniami. Prawidłowe sprawdzenie poprawności konfiguracji może stać się problemem związanym z NP.

W rezultacie komplikacje te zaskakują początkujących, przełamują „piękno” deklaratywnego programowania i powodują, że niektórzy inżynierowie szukają innych rozwiązań. Migracja niedoświadczonych inżynierów z SQL do NoSQL mogła zostać wywołana przez złożoność relacyjnych baz danych.

Mamy różnicę w deklaratywności języków programowania, która jest dobrze wykorzystywana do weryfikacji logiki cyfrowej.

Zwykle logika cyfrowa opisywana jest na poziomie transferu rejestru (RTL), gdzie definiowany jest poziom logiki sygnałów między rejestrami. Aby sprawdzić, czy coraz częściej dodajemy właściwości zdefiniowane w bardziej abstrakcyjny i deklaratywny sposób.

Jeden z bardziej deklaratywnych języków / podzbiorów językowych nosi nazwę PSL dla języka specyfikacji właściwości. Podczas testowania modelu RTL multiplikatora, w którym należy na przykład określić wszystkie operacje logiczne przesunięcia i dodania w wielu cyklach zegara; możesz napisać właściwość w sposób assert that when enable is high, this output will equal the multiplication of these two inputs after no more than 8 clock cycles. Opis PSL można następnie sprawdzić razem z RTL w symulacji, lub można formalnie udowodnić, że PSL utrzymuje się dla opisu RTL.

Bardziej deklaratywny model PSL zmusza do opisania tego samego zachowania, co opis RTL, ale w wystarczająco inny sposób, który można automatycznie sprawdzić w stosunku do RTL, aby sprawdzić, czy się zgadzają.

Problemem jest głównie sposób modelowania danych; a programowanie deklaratywne tu nie pomaga. W imperatywnych językach masz już mnóstwo bibliotek, które robią dla ciebie wiele rzeczy, więc musisz tylko wiedzieć, jak zadzwonić. W szczególny sposób można rozważyć to deklaratywne programowanie (prawdopodobnie najlepszym tego przykładem jest Stream API w Javie 8 ). Dzięki temu abstrakcja jest już rozwiązana, a programowanie deklaratywne nie jest konieczne.

Jak już powiedziano, języki programowania logiki już teraz robią dokładnie to, co chcesz. Można powiedzieć, że problemem jest wydajność, ale dzięki dzisiejszemu sprzętowi i badaniom w tej dziedzinie można poprawić sytuację, aby była gotowa do użytku produkcyjnego; właściwie Prolog jest używany do sztucznej inteligencji, ale wierzę tylko w środowisko akademickie.

Należy zauważyć, że dotyczy to języków programowania ogólnego zastosowania. W przypadku języków specyficznych dla domeny języki deklaratywne są znacznie lepsze; SQL jest prawdopodobnie najlepszym przykładem.

Wygląda to mniej więcej tak: {(cokolwiek => przeczytaj plik i wywołaj adres URL) | wywołaj adres URL i przeczytaj plik} Są to jednak działania, które należy wykonać, a stan systemu zmienia się w wyniku, ale nie jest to oczywiste ze źródła.

Deklaratywne mogą opisywać maszynę skończoną i jej przejścia. FSM jest przeciwieństwem deklaratywnych bez akcji, nawet jeśli jedynym działaniem jest zmiana stanu na następny.

Zaletą korzystania z tej metody jest to, że przejścia i działania można określać za pomocą predykatów, które dotyczą wielu przejść, a nie tylko jednego.

Wiem, że to brzmi trochę dziwnie, ale w 2008 roku napisałem generator programu, który korzysta z tej metody, a wygenerowany C ++ jest od 2 do 15 razy większy niż źródło. Mam teraz ponad 75 000 linii C ++ z 20 000 linii wejściowych. Dwie rzeczy są z tym związane: spójność i kompletność.

Spójność: Żadne dwa predykaty, które mogą być prawdziwe jednocześnie, nie mogą sugerować niespójnych działań, ponieważ zarówno x = 8 i x = 9, ani różne kolejne stany.

Kompletność: Logika dla każdego przejścia stanu jest określona. Może to być trudne do sprawdzenia dla systemów z N podstatkami z> 2 ** stanami N, ale istnieją ciekawe metody kombinatoryczne, które mogą wszystko zweryfikować. W 1962 roku napisałem pierwszą fazę sortowania systemowego dla maszyn 7070, używając tego rodzaju warunkowego generowania kodu i kombinatorycznego debugowania. Z 8 000 wierszy tego rodzaju liczba błędów od pierwszego wydania na zawsze wynosiła zero!

Druga tego rodzaju faza, 12 000 linii, zawierała ponad 60 błędów w ciągu pierwszych dwóch miesięcy. Jest wiele więcej do powiedzenia na ten temat, ale to działa. Gdyby producenci samochodów zastosowali tę metodę do sprawdzenia oprogramowania układowego, nie widzielibyśmy awarii, które widzimy teraz.

Nie wszystko można przedstawić w sposób deklaratywny.

Często wyraźnie chcesz kontrolować przebieg wykonywania

Na przykład następujący pseudo-kod: if whatever read a file call an URL else call an URL write a file Jak byś go reprezentował?

Pewnie, istnieją prawdopodobnie egzotyczne sposoby na zrobienie tego. Jak monady . Ale zwykle są one bardziej kłopotliwe, skomplikowane i znacznie mniej intuicyjne niż ich część proceduralna.

Wszystko sprowadza się do tego, że „interakcja” ze środowiskiem / systemem nie jest deklaratywna. Wszystko, co dotyczy I / O, jest zasadniczo proceduralne. Musisz dokładnie powiedzieć, kiedy i co powinno się zdarzyć oraz w jakiej kolejności.

Deklaratywna jest świetna do wszystkiego, co jest wyłącznie związane z obliczeniami. Jak gigantyczna funkcja, wstawiasz X i dostajesz Y. To świetnie. Przykładem tego jest HTML, dane wejściowe to tekst, dane wyjściowe są widoczne w przeglądarce.