Czy naprawdę istnieje niezmienność w programowaniu funkcjonalnym?

Chociaż pracuję jako programista w swoim codziennym życiu i używam wszystkich modnych języków (Python, Java, C itp.), Nadal nie mam jasnego obrazu tego, czym jest programowanie funkcjonalne. Z tego, co przeczytałem, jedną właściwością języków funkcjonalnych jest to, że struktury danych są niezmienne . Dla mnie to samo rodzi wiele pytań. Ale najpierw napiszę trochę tego, co rozumiem o niezmienności, a jeśli się mylę, możesz mnie poprawić.

Moje rozumienie niezmienności:

• Po uruchomieniu programu ma ustalone struktury danych ze stałymi danymi
• Nie można dodawać nowych danych do tych struktur
• W kodzie nie ma żadnych zmiennych
• Możesz po prostu „skopiować” dane już obliczone lub dane aktualnie obliczone
• Z uwagi na powyższe niezmienność dodaje programowi ogromną złożoność przestrzeni

Moje pytania:

1. Jeśli struktury danych mają pozostać takie, jakie są (niezmienne), jak, do diabła, ktoś dodaje nowy element na liście?
2. Po co mieć program, który nie może uzyskać nowych danych? Załóżmy, że do komputera jest podłączony czujnik, który chce przesyłać dane do programu. Czy to oznacza, że ​​nigdzie nie możemy przechowywać przychodzących danych?
3. Jak w takim przypadku programowanie funkcjonalne jest przydatne do uczenia maszynowego? Ponieważ uczenie maszynowe opiera się na założeniu, że program „postrzega” rzeczy przez program - w ten sposób przechowuje nowe dane.

Po uruchomieniu programu ma ustalone struktury danych ze stałymi danymi

To trochę nieporozumienie. Ma ustaloną formę i stały zestaw reguł przepisywania, ale te reguły przepisywania mogą eksplodować w coś znacznie większego. Na przykład wyrażenie [1..100000000] w języku Haskell jest reprezentowane przez bardzo małą ilość kodu, ale jego normalna postać jest ogromna.

Nie można dodawać nowych danych do tych struktur

Tak i nie. Czysto funkcjonalny podzbiór języka takiego jak Haskell lub ML nie może pobierać danych ze świata zewnętrznego, ale każdy język do programowania praktycznego ma mechanizm wstawiania danych ze świata zewnętrznego do czysto funkcjonalnego podzbioru. W Haskell odbywa się to bardzo ostrożnie, ale w ML możesz to zrobić w dowolnym momencie.

W kodzie nie ma żadnych zmiennych

Jest to w zasadzie prawdą, ale nie myl tego z pomysłem, że nic nie można nazwać. Przez cały czas wymieniasz przydatne wyrażenia i ciągle je używasz. Również ML i Haskell, każdy Lisp, którego próbowałem, i hybrydy takie jak Scala, wszystkie mają sposób na tworzenie zmiennych. Po prostu nie są powszechnie używane. I znowu nie mają ich wyłącznie funkcjonalne podzbiory takich języków.

Możesz po prostu „skopiować” dane już obliczone lub dane aktualnie obliczone

Możesz wykonać obliczenia poprzez redukcję do normalnej postaci. Najlepszą rzeczą jest prawdopodobnie napisanie programów w funkcjonalnym języku, aby zobaczyć, jak faktycznie wykonują obliczenia.

Na przykład „suma [1..1000]” nie jest obliczeniem, które chcę wykonać, ale Haskell robi to dość łatwo. Daliśmy mu mały wyraz, który miał dla nas znaczenie, a Haskell podał nam odpowiednią liczbę. Więc zdecydowanie wykonuje obliczenia.

Jeśli struktury danych mają pozostać takie, jakie są (niezmienne), jak, do diabła, ktoś dodaje nowy element na liście?

Nie dodajesz nowego elementu do listy, tworzysz nową listę ze starej. Ponieważ starego nie można zmutować, można go bezpiecznie używać na nowej liście lub w dowolnym innym miejscu. W tym schemacie można bezpiecznie udostępniać znacznie więcej danych.

Po co mieć program, który nie może uzyskać nowych danych? Załóżmy, że do komputera jest podłączony czujnik, który chce przesyłać dane do programu. Czy to oznacza, że ​​nigdzie nie możemy przechowywać przychodzących danych?

Jeśli chodzi o wprowadzanie danych przez użytkownika, każdy praktyczny język programowania ma sposób na uzyskanie wkładu użytkownika. To się stało. Istnieje jednak w pełni funkcjonalny podzbiór tych języków, w którym piszesz większość kodu i czerpiesz w ten sposób korzyści.

Jak w takim przypadku programowanie funkcjonalne jest przydatne do uczenia maszynowego? Ponieważ uczenie maszynowe opiera się na założeniu, że program „postrzega” rzeczy przez program - w ten sposób przechowuje nowe dane.

Tak byłoby w przypadku aktywnego uczenia się, ale większość uczenia maszynowego, z którym współpracowałem (pracuję jako małpa kodowa w grupie uczenia maszynowego i robiłem to przez kilka lat) ma jednorazowy proces uczenia się, w którym ładowane są wszystkie dane szkoleniowe od razu. Ale do aktywnego uczenia się nie można robić rzeczy w 100% czysto funkcjonalnych. Będziesz musiał przeczytać niektóre dane ze świata zewnętrznego.

Niezmienność lub zmienność nie są pojęciami, które mają sens w programowaniu funkcjonalnym.

Kontekst obliczeniowy

To bardzo dobre pytanie, które jest interesującą kontynuacją (a nie duplikatem) do innego ostatniego: Jaka jest różnica między przypisaniem, wyceną a przypisaniem nazwy?

Zamiast odpowiadać na twoje oświadczenia pojedynczo, staram się tutaj przedstawić uporządkowany przegląd tego, co jest zagrożone.

Aby odpowiedzieć na kilka pytań, należy rozważyć kilka kwestii, w tym:

• Co to jest model obliczeniowy i jakie pojęcia mają sens dla danego modelu

• Jakie jest znaczenie używanych słów i jak to zależy od kontekstu

Funkcjonalny styl programowania wydaje się głupi, ponieważ widzisz go bezwzględnym okiem programisty. Ale jest to inny paradygmat, a wasze imperatywne koncepcje i percepcja są obce, nie na miejscu. Kompilatory nie mają takich uprzedzeń.

Ale końcowy wniosek jest taki, że możliwe jest pisanie programów w sposób czysto funkcjonalny, w tym do uczenia maszynowego, myśląc, że programowanie funkcjonalne nie ma pojęcia przechowywania danych. Wydaje mi się, że nie zgadzam się w tej kwestii z innymi odpowiedziami.

W nadziei, że niektórzy będą zainteresowani pomimo długości tej odpowiedzi.

Paradygmaty obliczeniowe

Pytanie dotyczy programowania funkcjonalnego (inaczej programowania aplikacyjnego), specyficznego modelu obliczeń, którego teoretycznym i najprostszym przedstawicielem jest rachunek lambda.

Jeśli pozostaniesz na poziomie teoretycznym, istnieje wiele modeli obliczeń: maszyna Turinga, maszyna RAM i inne , rachunek lambda, logika kombinacyjna, teoria funkcji rekurencyjnych, systemy pół-Thue itp. Bardziej wydajne obliczenia modele okazały się równoważne pod względem tego, do czego mogą się odnieść, i to jest sedno tezy Kościoła-Turinga .

Ważną koncepcją jest redukowanie do siebie modeli, które są podstawą do ustalenia równoważności, które prowadzą do tezy Kościoła-Turinga. Patrząc z perspektywy programisty, redukcja jednego modelu do drugiego jest w zasadzie tak zwanym kompilatorem. Jeśli weźmiesz programowanie logiczne za model obliczeń, różni się ono znacznie od modelu dostarczonego przez komputer kupiony w sklepie, a kompilator tłumaczy programy napisane w języku programowania logicznego na model obliczeniowy reprezentowany przez komputer (prawie komputer RAM).

Nie oznacza to jednak, że oba modele działają w ten sam sposób, lub że pojęcie istotne dla jednego z nich można przenieść jako takie na inne. Zazwyczaj krok obliczeniowy w bazie TM ma niewielki związek z ($\beta$-) krok redukcji w rachunku Lambda Calculus, chociaż są one możliwe do przetłumaczenia. Koncepcja optymalnej oceny ekspresji lambda jest dość odległa od problemów związanych ze złożonością modeli TM.

W praktyce używane przez nas języki programowania łączą koncepcje z różnych teoretycznych źródeł, starając się to zrobić, aby wybrane części programów mogły korzystać z właściwości niektórych modeli tam, gdzie jest to właściwe. Podobnie ludzie budujący systemy mogą wybierać różne języki dla różnych komponentów, aby najlepiej dopasować język do danego zadania.

Dlatego rzadko widzi się paradygmat programowania w czystym stanie w języku programowania. Języki programowania są nadal klasyfikowane zgodnie z dominującym paradygmatem, ale właściwości języka mogą ulec zmianie, gdy w grę wchodzą pojęcia z innych paradygmatów, często zacierając rozróżnienia i problemy pojęciowe.

Zazwyczaj języki takie jak Haskell i ML lub CAML są uważane za funkcjonalne, ale mogą pozwalać na zachowanie w trybie rozkazującym ... Inaczej dlaczego miałoby się mówić o „ czysto funkcjonalnym podzbiorze ”?

Następnie można twierdzić, że można to zrobić w moim funkcjonalnym języku programowania, ale tak naprawdę nie jest to odpowiedź na pytanie dotyczące programowania funkcjonalnego, gdy polega ono na czymś, co można uznać za niefunkcjonalne.

Odpowiedzi powinny być bardziej precyzyjnie powiązane z określonym paradygmatem, bez dodatków.

Co to jest zmienna?

Kolejnym problemem jest stosowanie terminologii. W matematyce zmienna jest bytem, ​​który reprezentuje nieokreśloną wartość w niektórych domenach. Jest używany do różnych celów. Używany w równaniu może oznaczać dowolną wartość taką, że równanie jest weryfikowane. Tę wizję stosuje się w programowaniu logicznym pod nazwą „ zmienna logiczna ”, prawdopodobnie dlatego, że zmienna nazwy miała już inne znaczenie, gdy opracowywano programowanie logiczne.

W tradycyjnym programowaniu imperatywnym zmienna jest rozumiana jako pewien rodzaj kontenera (lub lokalizacji pamięci), który może zapamiętać reprezentację wartości i ewentualnie zastąpić jej bieżącą wartość inną.

W programowaniu funkcjonalnym zmienna ma ten sam cel, co w matematyce, jako symbol zastępczy dla pewnej wartości, która ma dopiero zostać podana. W tradycyjnym programowaniu imperatywnym rolę tę w rzeczywistości pełni stała (nie mylić z literałami, które są ustaloną wartością wyrażoną notacją charakterystyczną dla tej dziedziny wartości, takimi jak 123, prawda, ["abdcz", 3.14]).

Zmienne dowolnego rodzaju, jak również stałe, mogą być reprezentowane przez identyfikatory.

Zmienna imperatywna może mieć zmienioną wartość i jest to podstawa zmienności. Zmienna funkcjonalna nie może.

Języki programowania zwykle pozwalają na tworzenie większych jednostek z mniejszych w języku.

Języki imperatywne pozwalają, aby takie konstrukcje zawierały zmienne, i to daje zmienne dane.

Jak czytać program

Program jest zasadniczo abstrakcyjnym opisem twojego algorytmu. Jest to jakiś język, czy to pragmatyczny projekt, czy paradygmatycznie czysty język.

Zasadniczo możesz przyjąć każde stwierdzenie w sposób abstrakcyjny. Następnie kompilator przetłumaczy to na odpowiednią formę do uruchomienia przez komputer, ale to nie jest twój problem w pierwszym przybliżeniu.

Oczywiście rzeczywistość jest nieco trudniejsza i często dobrze jest mieć pojęcie o tym, co się dzieje, aby uniknąć struktur, z którymi kompilator nie będzie wiedział, jak sobie poradzić w celu wydajnego wykonania. Ale to już jest optymalizacja ... dla których kompilatory mogą być bardzo dobre, często lepsze niż programiści.

Programowanie funkcjonalne i zmienność

Zmienność opiera się na istnieniu imperatywnych zmiennych, które mogą zawierać wartości, które można zmieniać poprzez przypisanie. Ponieważ nie istnieją one w programowaniu funkcjonalnym, wszystko można uznać za niezmienne.

Programowanie funkcyjne dotyczy wyłącznie wartości.

Twoje pierwsze cztery stwierdzenia dotyczące niezmienności są w większości poprawne, ale opisz z imperatywnym poglądem coś, co nie jest konieczne. To trochę jak opisywanie kolorami w świecie, w którym każdy jest ślepy. Używasz pojęć, które są obce programowaniu funkcjonalnemu.

Masz tylko czyste wartości, a tablica liczb całkowitych jest czystą wartością. Aby uzyskać inną tablicę, która różni się tylko jednym elementem, musisz użyć innej wartości tablicy. Zmiana elementu to po prostu koncepcja, która nie istnieje w tym kontekście. Możesz mieć funkcję, która ma tablicę i niektóre indeksy jako argument, i zwraca wynik, który jest prawie identyczną tablicą, która różni się tylko tam, gdzie wskazują na to indeksy. Ale nadal jest to niezależna wartość tablicy. Jak te wartości są reprezentowane, nie jest twoim problemem. Być może „dużo się dzielą” w tłumaczeniu imperatywnym komputera… ale to jest zadanie kompilatora… a ty nawet nie chcesz wiedzieć, jaką architekturę maszyny kompiluje.

Nie kopiujesz wartości (to nie ma sensu, to koncepcja obcych). Po prostu używasz wartości istniejących w domenach, które zdefiniowałeś w swoim programie. Albo je opisujesz (jako literały), albo wynikają one z zastosowania funkcji do niektórych innych wartości. Możesz nadać im nazwę (definiując w ten sposób stałą), aby upewnić się, że ta sama wartość jest używana w różnych miejscach programu. Zauważ, że aplikacja funkcji nie powinna być postrzegana jako obliczenie, ale jako wynik zastosowania do podanych argumentów. Pisanie 5+2lub pisanie 7to tyle samo. Co jest zgodne z poprzednim akapitem.

Nie ma zmiennych imperatywnych. Zadanie nie jest możliwe. Możesz powiązać nazwy tylko z wartościami (w celu utworzenia stałych), w przeciwieństwie do języków imperatywnych, w których można przypisać nazwy do zmiennych, które można przypisać.

To, czy ma to złożony koszt, jest całkowicie niejasne. Po pierwsze, odniesienie do złożoności dotyczy imperatywnych paradygmatów. Nie jest zdefiniowane jako takie dla programowania funkcjonalnego, chyba że zdecydujesz się odczytać swój program funkcjonalny jako program imperatywny, co nie jest intencją projektanta. Rzeczywiście widok funkcjonalny ma na celu nie martwić się o takie problemy i skoncentrować się na tym, co jest obliczane. To trochę jak specyfikacja kontra implementacja.

Kompilator musi zająć się implementacją i musi być wystarczająco inteligentny, aby jak najlepiej dostosować to, co należy zrobić do sprzętu, który to zrobi, cokolwiek to jest.

Nie twierdzę, że programiści nigdy się tym nie przejmują. Nie twierdzę też, że języki programowania i technologia kompilatora są tak dojrzałe, jak byśmy sobie tego życzyli.

Odpowiedzi na pytania

1. Nie modyfikujesz istniejącej wartości (koncepcja obcych), ale obliczasz nowe wartości, które różnią się w razie potrzeby, być może mając jeden dodatkowy element, jest to lista.

2. Program może uzyskać nowe dane. Chodzi o to, jak wyrażasz to w języku. Możesz na przykład rozważyć, że program działa z jedną określoną wartością, być może nieograniczoną wielkością, która nazywa się strumieniem wejściowym. Jest to wartość, która powinna tam siedzieć (to, czy jest już w pełni znana, czy nie, nie jest twoim problemem). Następnie masz funkcję, która zwraca parę złożoną z pierwszego elementu strumienia i reszty strumienia.

   Możesz użyć tego do budowy sieci komunikujących się komponentów w sposób czysto aplikacyjny (coroutines)

3. Uczenie maszynowe to po prostu kolejny problem, gdy trzeba gromadzić dane i modyfikować wartości. W programowaniu funkcjonalnym tego nie robisz: po prostu obliczasz nowe wartości, które odpowiednio różnią się w zależności od danych treningowych. Powstała maszyna również będzie działać. Martwisz się czasem obliczeniowym i wydajnością przestrzeni. Ale znowu jest to inna kwestia, którą najlepiej rozwiązać kompilator.

Uwagi końcowe

Z komentarzy lub innych odpowiedzi jasno wynika, że ​​praktyczne funkcjonalne języki programowania nie są czysto funkcjonalne. Jest to odzwierciedlenie faktu, że nasza technologia musi być wciąż ulepszana, szczególnie w przypadku kompilacji.

Czy można pisać w czysto aplikacyjnym stylu? Odpowiedź jest znana od około 40 lat i brzmi „tak”. Celem semantyki denotacyjnej, która pojawiła się w latach siedemdziesiątych, było właśnie tłumaczenie (kompilacja) języków na czysto funkcjonalny styl, uważany za lepiej rozumiany matematycznie, a tym samym uważany za lepszą podstawę do zdefiniowania semantyki programów.

Ciekawym aspektem jest to, że imperatywna struktura programowania, w tym zmienne, może zostać przełożona na styl funkcjonalny poprzez wprowadzenie odpowiednich domen wartości, takich jak magazyn danych. I pomimo stylu funkcjonalnego, pozostaje on zaskakująco podobny do kodu rzeczywistych kompilatorów napisanych w stylu imperatywnym.

Jest to błędne przekonanie, że programy funkcjonalne nie mogą przechowywać danych i nie sądzę, aby odpowiedź Jakesa wyjaśniła to bardzo dobrze.

Programy funkcjonalne, podobnie jak inne programy, naprawdę działają na mapowanie liczb całkowitych na liczby całkowite. Każdy program imperatywny działający na zmiennych strukturach danych ma funkcjonalny odpowiednik. To tylko kolejny sposób na osiągnięcie tego samego celu.

Funkcjonalnym sposobem przechowywania danych eksperymentu z jakiegoś źródła byłoby wywołanie funkcji przechowywania ze strukturą danych jako argumentem i wyprowadzenie konkatenacji istniejącej struktury danych i nowych danych, a tym samym dane są przechowywane bez pojęcia zmiennych danych.

Z własnego doświadczenia sądzę, że koncepcja niezmiennych struktur danych skłania konwencjonalnych programistów do myślenia, że ​​istnieją pewne rzeczy, które są niepraktyczne lub wręcz niemożliwe do zrobienia w funkcjonalnych warunkach. Nie o to chodzi.