Czy * dowolne * zadanie programu może być wyrażone bez stanu?


13

To pytanie teoretyczne, ale po wielu latach programowania w tym, co teraz zdaję sobie sprawę, że jest to „normalna” technika imperatywna, wykorzystująca głównie C ++, odkryłem ten inny świat programowania funkcjonalnego, na który przypadkiem natknąłem się podczas przypadkowej nauki JavaScript.

Doprowadziło mnie to do zastanowienia się, czy można technicznie zastąpić dowolny kompletny program zorientowany na państwo inną implementacją, która jest czysto funkcjonalna i bez stanu?

To intrygujący pomysł i muszę przyznać, że w funkcjonalnym programowaniu jest jasność i elegancja, które naprawdę zaskoczyły mnie.


1
Odpowiednia odpowiedź StackOverflow: stackoverflow.com/questions/3722084/…
jfriend00

To, czy istnieje stan, który utrzymuje się od jednego momentu do następnego, nie zależy od używanego paradygmatu programowania, ale od tego, jaki problem lub zadanie kodujesz. Jeśli liczysz liczbę kliknięć przycisku, to oczywiście istnieje stan, aby zarejestrować ten licznik i nie ma znaczenia, jakiej techniki kodowania używasz, musi istnieć stan, aby śledzić liczbę podczas procesu. Tak więc to konkretne zadanie nie może zostać wykonane bez stanu po drodze, bez względu na to, jak je kodujesz.
jfriend00

6
Jeśli chcesz omówić stan; wyraźny stan jest wymagany, choćby dla samego programu. Wygląda na to, że myślisz o stanie zmiennym vs. niezmiennym - możesz wskazać, co masz na myśli w pytaniu.
Billy ONeal

1
To tak, jakby zapytać, czy wszystkie programy można przekonwertować na prawdziwe maszyny Turinga. Technicznie tak, nawet programy, które zapisują i ładują z bazy danych, jednak symulacja tego zachowania w maszynie Turinga staje się coraz trudniejsza. Podobnie, możesz mieć program, którego strona kontrolera w architekturze MVC jest usunięta i wykonujesz wszystkie wywołania, choć znowu staje się to o wiele trudniejsze do opanowania (w zasadzie stajesz się kontrolerem, aby program stał się bezpaństwowcem).
Neil

Odpowiedzi:


17

Krótka odpowiedź: tak. Według Wikipedii równoważność rachunku lambda do maszyn Turinga jako uniwersalnego modelu obliczeń wykazał w 1937 r. Alan Turing. Model obliczeniowy maszyny Turinga jest tym, o czym zwykle myślisz, mówiąc o programowaniu imperatywnym lub stanowym, a rachunek lambda jest matematyczną formalizacją „czysto funkcjonalnego programowania”.

Przypuszcza się, że każdy skuteczny model obliczeń jest w stanie wykonać te same obliczenia co maszyna Turinga i odwrotnie. Nazywa się to tezą Turinga . Nie można jednak udowodnić tego przypuszczenia z powodu mniej lub bardziej intuicyjnego terminu „efektywny model obliczeń” (może ktoś wymyśli nowy model w przyszłości?)


2
Ten sam argument można cofnąć, mówiąc, że rachunek lamba jest równoważny z maszynami turystycznymi, każde obliczenie musi mieć (mniej lub bardziej ukryty) stan. Niezależnie od tego, czy jest reprezentowane jako zewnętrzne względem kodu (za pomocą zmiennych), czy wewnętrzne w przepływie (za pomocą wywołania funkcji opartej na stosie), zawsze „stan” jest.
Emilio Garavaglia

3
Rachunek lambda ma stan; jego ograniczeniem jest to, że państwo jest niezmienne. Niezmienny stan jest nadal stanem. Parametry funkcji, w tym lambda, są nadal stanowe; przypuszczalnie chcesz, aby funkcja miała inne zachowanie z uwagi na różne parametry.
Billy ONeal

@emilio Stwierdzenie, że istnieje rozwiązanie problemu oparte na stanie (jak to opisujesz) nie jest dowodem na to, że nie istnieje wersja bezstanowa tego rozwiązania.
Billy ONeal

2
@EmilioGaravaglia odnosisz się do stanu interpretera rachunku lambda. Podczas wnioskowania w rachunku lambda nie ma potrzeby wnioskowania o stanie. Również aspekt „Zmienności” jest inny.
wirrbel

1
@EmilioGaravglia: Stan w programowaniu imperatywnym jest konfiguracją pamięci na raz, tutaj przestrzeń parametrów jest podawana przez wszystkie możliwe wartości pamięci, a stan to jedna konfiguracja na raz (pasmo maszyny Turinga). Podczas pisania programu w rachunku lambda nie ma bezpośredniego elementu, takiego jak pole pamięci. Wykonywanie programu polega na zastosowaniu transformacji lambda. Kroki pośrednie mogą przypominać „stan”, ale są tylko równoważnymi wyrażeniami o tej samej wartości. Podczas oceny nic się nie zmienia, wyrażenia są po prostu przepisywane i przetwarzane w „prostszą” formę.
wirrbel

14

W jakimkolwiek systemie dynamicznym „stan” sprawia, że ​​na teraźniejszość ma wpływ przeszłość lub przyszłość (strzała czasu nie jest zagadnieniem matematycznym, tylko ograniczeniem fizycznym).

Czy masz coś do zapamiętania, czy to zależy od tego, co zrobiłeś, masz stan.

System bez stanu nie jest „dynamiczny”: jest tylko funkcją kombinatoryczną. To może nie mieć stanu, ale - aby uzyskać różne wyniki - potrzebuje stanu, który w jakiś sposób zostanie dostarczony.

Teraz, w zależności od modelu obliczeniowego, do którego się odwołujesz, stan może być reprezentowany jawnie (w postaci zmiennej) lub niejawnie (w postaci „adresów zwrotnych”).

kiedy to robisz, fna(fnb(x))podajesz stan fnb, który z kolei wytworzy stan dla fna. Wynika to z faktu, że xistnieje przed wywołaniem fnb (więc pochodzi z własnej „przeszłości”).

To nie jest kwestia „stanu wyjścia” lub „stanu nie istnieje”. Jest to kwestia „zależy mi” lub „nie”.


0

Stan oznacza zdolność do reagowania na obecny bodziec w sposób zależny od bodźców z przeszłości, a nie tylko od bodźca obecnego.

Czysto funkcjonalne programy to tylko funkcje. Tak więc dla praktycznych zastosowań czysto funkcjonalny program wprowadza parę (old_state * present_stimulus) i wyprowadza parę (new_state * present_response). Potrzebny jest zewnętrzny, stanowy „looper”, aby czekać na następny bodziec i propagować stan.

Czysto funkcjonalny program nie ma własnego stanu i nie może być używany bezpośrednio w praktycznych aplikacjach.

Dlatego żadnego programu zorientowanego na państwo nie można zastąpić inną implementacją, która jest czysto funkcjonalna i bez stanu.


0

Możesz uniknąć jawnego stanu zmiennego, o ile nie będziesz musiał wchodzić w interakcje ze światem zewnętrznym.

W JavaScript, aby Twój program miał efekt wykraczający poza podejmowanie cykli procesora, musisz zmodyfikować obiekt Dom lub Window, a te API są stanowe. Ale przypuszczam, że można utworzyć opakowanie, które przekazuje obiekty Dom i Window jako parametry do kodu JavaScript, a następnie otrzymuje nowe dane wyjściowe Dom / Window. To izolowałoby kod JavaScript od stanu zmiennego.

Oczywiście nadal polegasz na stanie, ponieważ okno przeglądarki i DOM są z natury stanowe. Każda aplikacja interaktywna jest z natury stanowa, ale nadal możesz tak ustrukturyzować swój kod, aby zminimalizować jawny stan.

Inne pytanie dotyczy tego, czy to dobry pomysł. Nawet Haskell, który z założenia jest czysto funkcjonalnym językiem, zawiera monadę „stanową”, która pozwala symulować stan zmienny. To pokazuje, że jawny stan mutable czasami jest naprawdę pożądanym wzorcem.


0

Zastanów się, jak zaimplementujesz „maszynę stanową” w języku programowania bez stanu.

Prawdopodobnie mógłbyś to zrobić, ale ostatecznie użyłbyś nazw funkcji jako pamięci. Skończyło się na gobblyday:

if (sm.atBegining()) sm.start() else if (sm.done()) sm.stop() ) else sm.progress()
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.