Marzenie o deklaratywnym programowaniu [zamknięte]

26

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.

davidk01
źródło
4
Nawiasem mówiąc, twój konkretny przykład jest już trochę dostępny: gkoberger.github.io/stacksort
Den
3
Czy słyszałeś o Prologu? Wystarczy wyszukać „Programowanie zestawu odpowiedzi”. Istnieje wiele systemów opartych na domyślnej logice.
Schlingel,
16
Cóż, na to pytanie można łatwo odpowiedzieć. Próba wdrożenia takiego systemu . Co powstrzymało cię przed zrobieniem tego z powodzeniem? Szanse są dobre, że cokolwiek cię zatrzymało, zatrzymało wszystkich.
Eric Lippert,
4
Kusi mnie, by uwierzyć, że to pytanie zasługuje na więcej uznania niż się dostaje. Kiedy spojrzysz na to na pierwszy rzut oka, możesz pomyśleć: Cóż, to proste! Musisz zaprogramować całą tę logikę, a komputery po prostu nie są tak inteligentne. ... Ale potem wrócisz i rzucisz okiem na to pytanie i jeszcze raz myślisz: Cóż, tak, to proste i musisz zaprogramować całą tę logikę - a komputery niekoniecznie są najostrzejszymi narzędziami w szopie, prawda - ale wyjaśnienie to ma o wiele więcej głębi niż to, co leży na powierzchni.
Panzercrisis,
3
Twój opis algorytmu sortowania jest deklaratywny, tak, ale na pewno nie jest skuteczny. Istnieją n!kombinacje sekwencji, aw najgorszym przypadku algorytm będzie musiał wypróbować je wszystkie, aby znaleźć posortowaną. Czas czynnikowy jest tak kiepski, jak algorytm do przetworzenia sekwencji.
Benjamin Hodgson,

Odpowiedzi:

8

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 .

XXX
źródło
2
+1 za pokazanie, w jaki sposób projekt deklaratywny może przejść od prostej abstrakcji do bardziej konkretnej implementacji poprzez iteracyjny proces projektowania.
itsbruce
1
@ Boris To dobra odpowiedź. Ta książka siedzi na mojej półce. Prawdopodobnie czas to otworzyłem.
davidk01,
1
@ davidk01 Jedna z lepszych książek. Zakłada się, że czujesz się całkiem dobrze z Prologiem i programowaniem w ogóle, ale podejście, które stosuje do programowania, jest zarówno pragmatyczne, jak i bardzo dokładne.
XXX,
2
@ Boris Wiem, że przykład nie jest skomplikowany, ale wydajność iteracyjnego procesu projektowania - prawdziwa siła deklaratywnych języków - i jego bardzo praktyczna wartość, jest kluczowa. Języki deklaratywne oferują jasne, spójne, rekurencyjne podejście do iteracyjnego doskonalenia. Języki imperatywne nie.
itsbruce
1
+1 za „wypełnij niejednoznaczne dyskusje na temat tego, co jest dobre, deklaratywny Prolog”… to prawda, że ​​nie zgadzamy się!
Daniel Lyons,
50

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?

Euforyk
źródło
6
Może pomóc wiedzieć, że słowo Golem לםולם faktycznie oznacza „surowiec”, tj. Najbardziej podstawowy stan, w którym może znajdować się maszyna / byt.
dotancohen
2
Języki deklaratywne nie są z natury przeszkodą dla niższych poziomów abstrakcji. Zarówno Haskell, jak i Standard ML, na różne sposoby, pozwalają na proste deklaratywne deklaracje dotyczące typów / funkcji w jednym miejscu, zapewniają szereg konkretnych i specyficznych implementacji funkcji w oddzielnym miejscu oraz sposoby dopasowania typów do implementacji w innym. Tymczasem najlepsza praktyka w językach OO / Imperative polega teraz na rozpoczynaniu od wysokiego / prostego, a następnie dodawaniu szczegółów implementacyjnych. Różnica polega na tym, że wysoka abstrakcja jest łatwiejsza w FP, a niski poziom jest łatwiejszy koniecznie.
itsbruce
2
Powinien powiedzieć, że możliwe jest również, w każdym z wymienionych języków, automatyczne wybranie konkretnej implementacji w oparciu o właściwości typu, a nie kodowanie konkretnych dopasowań, co w zasadzie zapewnia to, czego chce OP. W Haskell klasy typów byłyby do tego kluczowym narzędziem. W standardzie ML funktory.
itsbruce
22
@BAR Golem! = Golum Golem pochodzi z żydowskiego folkloru
Euphoric
10
Moja odpowiedź na to pytanie polega na napisaniu אמת na moim laptopie.
Dan J
45

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

Ixrec
źródło
3
Wspomnę GNU Make, XSLT, Angular.js jako powszechnie używane rzeczy, które również są deklaratywne (chociaż angular może przesuwać nieco definicję).
Mark K Cowan,
Pozwól mi dodać wyrażenia regularne do tej listy.
Schwern,
7
Ludzie zapominają, że języki deklaratywne są powszechne . Zwykle nie są to języki kompletne. Dodaj wyrażenie regularne do tej listy.
slebetman
Trochę pedantyczny, ale nadal: Nie każda baza danych ma DDL, wystarczy pomyśleć o ogromnej liczbie baz danych NoSQL bez schematów. Może istnieć każda relacyjna baza danych, ale nie każda baza danych.
Przywróć Monikę - dirkk
1
@dirkk Nie pomyślał o tym. Poprawiłem moją odpowiedź.
Ixrec,
17

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.

Piotr jest
źródło
Chociaż to, co mówisz, jest w gruncie rzeczy prawdą, zła wydajność nie jest oznaką nieszczelnej abstrakcji, chyba że interfejs / umowa zapewnia Ci np. Czas realizacji.
valenterry
3
Peters nie twierdzi, że zła wydajność jest oznaką nieszczelnej abstrakcji, @valenterry. Wręcz przeciwnie: mówi, że w celu osiągnięcia dobrej wydajności szczegóły implementacji są zmuszone do wycieku.
itsbruce
2
Myślę, że mylące jest twierdzenie, że abstrakcje są nieszczelne tylko dlatego, że musisz zrozumieć implementację, aby zrozumieć, jak wpływa ona na wydajność. Celem abstrakcji nie jest ochrona przed koniecznością myślenia o wydajności.
Doval,
1
@jamesqf W programowaniu deklaratywnym wystarczy stwierdzić, że coś jest posortowane. Można zadeklarować, że kolejność sortowania jest powiązana z jakąś zmienną / właściwością. I tak by było. Nie ma potrzeby jawnego wywoływania sortowania za każdym razem, gdy dodawane są nowe dane lub zmiany kolejności sortowania.
hyde
1
@jamesqf Naprawdę nie widzisz sensu bez próbowania siebie (polecam QML z Qt do zabawy z deklaratywnymi pomysłami). Wyobraź sobie kogoś, kto zna tylko programowanie imperatywne, i próbuje zrozumieć punkt OOP lub programowanie funkcjonalne, nie próbując go naprawdę.
hyde
11

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.

Dibbeke
źródło
2
„Negatywne klasy CSS celowo nie są dodawane do języka z powodu problemów NP-zupełnych” - czy możesz to rozwinąć?
John Dvorak,
To trochę ćwiczenie, ale przy negatywnych selektorach CSS można je przepisać do problemu 3SAT (ostatnia klauzula to DOM), który wymagałby wypróbowania wszystkich możliwych kombinacji, aby sprawdzić, czy pasuje.
Dibbeke
1
Mały dodatek. W CSS 3 i 4 dozwolone są selektory ujemne, ale: nie pseudoklasy nie mogą być zagnieżdżone.
Dibbeke
2

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ą.

Paddy3118
źródło
1

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.

m3th0dman
źródło
3
Modelowanie danych? Wybrałeś rzecz, w której imperatywy są najgorsze. Deklaratywne języki funkcjonalne, takie jak Haskell i ML, przodują w modelowaniu danych. Algebraiczne typy danych i rekurencyjne typy danych, na przykład, zwykle można zazwyczaj kompleksowo zdefiniować w jednym lub dwóch wierszach. Jasne, nadal masz funkcje do pisania, ale ich kod wynika nieuchronnie z definicji typu i jest przez nią ograniczony. Dziwne porównanie do zrobienia.
itsbruce
1
@itsbruce Rzecz w tym, że najbardziej prawdziwe dane nie są łatwo mapowane na ADT; pomyśl o tym, jak działa większość baz danych. Jako Prolog - Erlang, masz rację, są to różne języki. Wspomniałem, że jeden jest funkcjonalny, a drugi logiczny, ale najlepiej, jeśli usunę całe porównanie.
m3th0dman
1
@ m3th0dman Baza danych to tylko tona krotek / rekordów. Haskell jest tam trochę kaleką, ponieważ brakuje w nim rekordów, ale ma krotki, a ML ma oba. W przypadku Haskella ilość płyty kotłowej potrzebnej do zadeklarowania nowego typu danych pseudo-rekordowych jest wciąż znacznie mniejsza niż potrzeba do stworzenia faux-struktury w przeciętnym statycznym języku OOP. Czy potrafisz wyjaśnić, w jaki sposób większość danych nie jest łatwo mapowana na ADT?
Doval
1
@ m3th0dman Ah, dlatego schematy baz danych są zdefiniowane w języku imperatywnym, dobrze dopasowanym do zadania. Och, nie, to byłyby deklaratywne DDL. W rzeczywistości ogólny proces modelowania danych dotyczy aplikacji, która będzie z nim współpracować, przepływów danych i struktur, a nie języka implementującego aplikację. Czasami są one zniekształcone, aby pasowały do ​​funkcji OO języka i tego, co obsługuje jego ORM, ale zwykle jest to zła rzecz, a nie funkcja. Języki deklaratywne lepiej nadają się do wyrażania koncepcyjnego / logicznego modelu danych.
itsbruce
1
@itsbruce Nie mówiłem, że paradygmat proceduralny jest lepszy niż deklaratywny przy definiowaniu danych; Mówiłem, że paradygmat deklaratywny nie jest lepszy (ani gorszy) od paradygmatu proceduralnego (dla języków ogólnego przeznaczenia). Jeśli chodzi o manipulowanie danymi, deklaratywna część SQL nie wystarcza do rzeczywistych aplikacji; w przeciwnym razie nikt nie wymyśliłby i nie zastosowałby rozszerzeń proceduralnych. Jeśli chodzi o artykuł, nie zgadzam się z nim w streszczeniu, w którym przeczy Brooks; opierał swoje pomysły na prawdziwych projektach, podczas gdy ci faceci nie budowali niczego wyjątkowego, aby udowodnić swoją teorię.
m3th0dman
0

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.

Luther Woodrum
źródło
1
To naprawdę nie odpowiada na pierwotne pytanie. W jaki sposób spójność i kompletność wpływają na fakt, że większość programów wciąż ma charakter proceduralny, a nie deklaratywny?
Jay Elston,
Twój akapit początkowy wydaje się być odpowiedzią na pytanie zawarte w odpowiedzi arnaud programmers.stackexchange.com/a/275839/67057 , a nie na samo pytanie. Powinien to być komentarz (na moim ekranie twoja odpowiedź nie jest już poniżej jego, z jednej strony). Myślę, że reszta twojej odpowiedzi jest ilustracją tego, jak niewielka ilość deklaratywnego kodu może wygenerować dużą ilość równoważnego kodu imperatywnego, ale nie jest to jasne. Twoja odpowiedź wymaga uporządkowania, szczególnie w odniesieniu do najważniejszych punktów.
itsbruce
-3

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.

Dagnele
źródło
2
Nie kupuję tego Dlaczego twój przykład nie jest deklaratywny? Czy to if/ else, w którym przypadku wyglądałaby deklaratywna alternatywa? Z pewnością nie są to części read/ write/ call, ponieważ są ładnymi deklaratywnymi listami wartości (jeśli sugerujesz, że są zawinięte {...; ...}, dlaczego nie sugerujesz, że są zawinięte [..., ...]?) Oczywiście, lista to tylko darmowe monoidy; wielu innych też by to zrobiło. Nie rozumiem, dlaczego monady są tutaj ważne; są tylko interfejsem API. Haskell przeszedł ze strumieni -> monad, aby pomóc w ręcznym komponowaniu, ale języki logiczne mogą automatycznie tworzyć listy w kolejności.
Warbo,
2
-1 dla samych Monad. 1. Nie są tak naprawdę egzotyczne (listy i zestawy to Monady i wszyscy ich używają). 2. Oni nie mają nic wspólnego z zmuszając rzeczy do zrobienia w określonej kolejności (Haskell zrobić notacji wygląda bezwzględnym ale nie jest). Języki deklaratywne / funkcjonalne określają relacje i zależności. Jeśli funkcja X wymaga wejścia Y, Y zostanie wygenerowane przed X. Popraw zależności i właściwa sekwencja zdarzeń sama się zdefiniuje. Wiele interakcji jest sterowanych zdarzeniami , a nie w jednej określonej sekwencji. Języki deklaratywne nie utrudniają reagowania na wydarzenia.
itsbruce
Lenistwo komplikuje niektóre z nich, ale lenistwo nie jest częścią definicji języków deklaratywnych, z których większość nie korzysta. A w tych przypadkach sposób zagwarantowania oceny nie ma nic wspólnego z monadami. Na przykład, gdy deklaratywny język jest używany wyłącznie do interakcji, a nie do obliczeń abstrakcyjnych, nie określa kolejności, ale dba o to, by właściwe rzeczy zachodziły w sekwencji, nie szukaj dalej niż Puppet DSL. Ma to tę zaletę, że zdarzają się tylko niezbędne rzeczy - nie jest to łatwe w języku imperatywnym.
itsbruce
1
Oprócz przykładu @itsbruce programowanie reaktywne jest uważane za deklaratywne i dotyczy interakcji z otoczeniem.
Maciej Piechotka,