Czy wszystkie języki funkcjonalne używają funkcji wyrzucania elementów bezużytecznych?

32

Czy istnieje funkcjonalny język, który pozwala stosować semantykę stosu - automatyczne deterministyczne zniszczenie na końcu zakresu?

użytkownik467799
źródło
Deterministyczne zniszczenie jest naprawdę pomocne tylko przy skutkach ubocznych. W kontekście czystego programowania funkcjonalnego oznacza to po prostu zapewnienie, że pewne (monadyczne) działania zawsze działają na końcu sekwencji. Nawiasem mówiąc, łatwo jest napisać funkcjonalny język konkatenacyjny , który nie wymaga wyrzucania elementów bezużytecznych.
Jon Purdy,
Interesuje mnie treść pytania, co można zrobić z tym innym?
mattnz
1
W funkcjonalnym języku bez wyrzucania elementów bezużytecznych nie widzę możliwości strukturalnego udostępniania niezmiennych struktur danych. Możliwe jest stworzenie takiego języka, ale nie używałbym go.
dan_waterworth
Rdza ma wiele funkcji powszechnie określanych jako „funkcjonalne” (przynajmniej są one powszechnie poszukiwane w niefunkcjonalnych językach jako funkcje funkcjonalne). Jestem ciekawa, czego brakuje. Immut domyślnie, zamknięcia, func passing, zasadnicze przeciążenie, ADT (jeszcze nie GADT), dopasowanie wzorca, wszystko bez GC. Co jeszcze?
Noein

Odpowiedzi:

10

Nie o tym wiem, choć nie jestem ekspertem od programowania funkcjonalnego.

Zasadniczo wydaje się to dość trudne, ponieważ wartości zwracane z funkcji mogą zawierać odwołania do innych wartości, które zostały utworzone (na stosie) w ramach tej samej funkcji, lub równie łatwo mogły zostać przekazane jako parametr lub do których odwołuje się coś przekazanego jako parametr. W C problem ten rozwiązuje się, pozwalając, aby zwisające wskaźniki (a ściślej niezdefiniowane zachowanie) mogły wystąpić, jeśli programista nie naprawi problemu. To nie jest rozwiązanie, które akceptują funkcjonalni projektanci języków.

Istnieją jednak potencjalne rozwiązania. Jednym z pomysłów jest uczynienie okresu istnienia wartości częścią typu wartości, wraz z odniesieniami do niej, oraz zdefiniowanie reguł opartych na typach, które zapobiegną zwracaniu wartości przypisanych do stosu lub odwoływaniu się do czegoś zwróconemu z funkcjonować. Nie zastanawiałem się nad implikacjami, ale podejrzewam, że byłoby to okropne.

W przypadku kodu monadycznego istnieje inne rozwiązanie, które jest (właściwie lub prawie) monadyczne i może dać rodzaj automatycznie deterministycznie zniszczonej IORef. Zasadą jest zdefiniowanie działań „zagnieżdżających”. W połączeniu (za pomocą operatora asocjacyjnego) definiują one przepływ kontrolny zagnieżdżania - myślę, że „element XML”, z skrajnie lewymi wartościami zapewniającymi zewnętrzną parę tagów początkowych i końcowych. Te „znaczniki XML” definiują po prostu kolejność monadycznych działań na innym poziomie abstrakcji.

W pewnym momencie (po prawej stronie łańcucha kompozycji asocjacyjnej) potrzebujesz pewnego rodzaju terminatora, aby zakończyć zagnieżdżanie - czegoś, co wypełni dziurę w środku. Potrzeba terminatora jest tym, co prawdopodobnie oznacza, że ​​operator kompozycji zagnieżdżonej nie jest monadyczny, chociaż znowu, nie jestem do końca pewien, ponieważ nie przepracowałem szczegółów. Ponieważ wszystko, co robi terminator, polega na przekształceniu operacji zagnieżdżania w skutecznie skomponowaną normalną akcję monadyczną, a może nie - niekoniecznie wpływa to na operator kompozycji zagnieżdżania.

Wiele z tych akcji specjalnych miałoby zerowy krok „znacznika końcowego” i utożsamiałby krok „znacznika początku” z prostą akcją monadyczną. Ale niektóre reprezentowałyby deklaracje zmienne. Reprezentowałyby one konstruktor ze znacznikiem początkowym, a destruktor ze znacznikiem końcowym. Więc dostajesz coś takiego ...

act = terminate ((def-var "hello" ) >>>= \h ->
                 (def-var " world") >>>= \w ->
                 (use-val ((get h) ++ (get w)))
                )

Przekładając na kompozycję monadyczną o następującej kolejności wykonania, każdy tag (nie element) staje się normalną akcją monadyczną ...

<def-var val="hello">  --  construction
  <def-var val=" world>  --  construction
    <use-val ...>
      <terminator/>
    </use-val>  --  do nothing
  </def-val>  --  destruction
</def-val>  --  destruction

Takie reguły mogą pozwolić na implementację RAII w stylu C ++. Odwołania podobne do IORef nie mogą uciec przed swoim zasięgiem z podobnych powodów, dla których normalne IORef nie mogą uciec od monady - reguły składu asocjacyjnego nie pozwalają na ucieczkę odniesienia.

EDYCJA - prawie zapomniałem powiedzieć - jest określony obszar, którego nie jestem pewien. Ważne jest, aby upewnić się, że zmienna zewnętrzna nie może odwoływać się do zmiennej wewnętrznej, w zasadzie, więc muszą istnieć ograniczenia, co możesz zrobić z tymi odwołaniami podobnymi do IORef. Znów nie przepracowałem wszystkich szczegółów.

Dlatego konstrukcja może np. Otworzyć plik, który zniszczenie zamyka. Konstrukcja może otworzyć gniazdo, które zamyka zniszczenie. Zasadniczo, podobnie jak w C ++, zmienne stają się menedżerami zasobów. Ale w przeciwieństwie do C ++, nie ma obiektów przydzielanych do sterty, których nie można automatycznie zniszczyć.

Mimo że ta struktura obsługuje RAII, nadal potrzebujesz śmietnika. Chociaż akcja zagnieżdżania może przydzielić i zwolnić pamięć, traktując ją jako zasób, wciąż istnieją wszystkie odniesienia do (potencjalnie współdzielonych) wartości funkcjonalnych w tej części pamięci i gdzie indziej. Biorąc pod uwagę, że pamięć może być po prostu przydzielona na stosie, unikając konieczności korzystania ze sterty, rzeczywiste znaczenie (jeśli istnieje) ma znaczenie dla innych rodzajów zarządzania zasobami.

Osiąga to oddzielenie zarządzania zasobami w stylu RAII od zarządzania pamięcią, przynajmniej w przypadku, gdy RAII opiera się na prostym zakresie zagnieżdżania. Nadal potrzebujesz śmietnika do zarządzania pamięcią, ale dostajesz bezpieczne i terminowe automatyczne deterministyczne oczyszczanie innych zasobów.

Steve314
źródło
Nie rozumiem, dlaczego GC jest niezbędny we wszystkich językach funkcjonalnych. jeśli masz framework RAII w stylu C ++, kompilator może również użyć tego mechanizmu. Wspólne wartości nie stanowią problemu dla platform RAII (patrz C ++ shared_ptr<>), nadal zachowuje się deterministyczne zniszczenie. Jedyną trudną rzeczą dla RAII są odwołania cykliczne; RAII działa czysto, jeśli graf własności jest Directed Acyclic Graph.
MSalters
Chodzi o to, że funkcjonalny styl programowania jest praktycznie oparty na zamknięciach / lambdach / funkcjach anonimowych. Bez GC nie masz takiej samej swobody korzystania z zamknięć, więc Twój język staje się znacznie mniej funkcjonalny.
Zbliża się burza
@comingstorm - C ++ ma lambdas (od C ++ 11), ale nie ma standardowego śmietnika. Jagnięta przenoszą również swoje środowisko w zamknięciu - a elementy w tym środowisku mogą być przekazywane przez odniesienie, a także możliwość przekazywania wskaźników przez wartość. Ale, jak napisałem w drugim akapicie, C ++ dopuszcza możliwość zawieszania wskaźników - to na programistach (a nie na kompilatorach lub środowiskach wykonawczych) spoczywa odpowiedzialność za zapewnienie, że to się nigdy nie wydarzy.
Steve314,
@MSalters - ponoszenie kosztów wiąże się z zapewnieniem, że nie można nigdy utworzyć cykli odniesienia. Dlatego uczynienie języka odpowiedzialnym za to ograniczenie przynajmniej nietrywialnym. Przypisanie wskaźnika prawdopodobnie stanie się operacją o czasie innym niż stały. Chociaż w niektórych przypadkach może to być najlepsza opcja. Śmieciowanie pozwala uniknąć tego problemu przy różnych kosztach. Innym jest uczynienie programisty odpowiedzialnym. Nie ma silnego powodu, dla którego zwisające wskaźniki powinny być poprawne w imperatywnych, ale nie funkcjonalnych językach, ale nadal nie polecam pisania pointer-dangling-Haskell.
Steve314,
Twierdziłbym, że ręczne zarządzanie pamięcią oznacza, że ​​nie masz takiej samej swobody w używaniu zamknięć C ++ 11, jak w przypadku zamknięć Lisp lub Haskell. (Właściwie jestem bardzo zainteresowany zrozumieniem szczegółów tego kompromisu, ponieważ chciałbym napisać funkcjonalny język programowania systemów ...)
nadchodząca burza
3

Jeśli uważasz C ++ za język funkcjonalny (ma lambdas), to jest to przykład języka, który nie korzysta ze śmiecia.

BЈовић
źródło
8
Co jeśli nie uważasz C ++ za język funkcjonalny (IMHO tak nie jest, chociaż możesz napisać za jego pomocą program funkcjonalny, możesz również napisać za jego pomocą niektóre niefunkcjonalne (działające ...) programy)
mattnz
@mattnz To chyba nie dotyczy odpowiedzi. Nie jestem pewien, co dzieje się w innych językach (np. Haskel)
BЈовић
9
Powiedzenie, że C ++ działa, jest jak powiedzenie, że Perl jest zorientowany obiektowo ...
Dynamiczny
Przynajmniej kompilatory c ++ mogą sprawdzać efekty uboczne. (via const)
tp1
@ tp1 - (1) Mam nadzieję, że nie będzie to regresją do tego, kto jest najlepszym językiem, i (2) to nie jest tak naprawdę prawda. Po pierwsze, naprawdę ważnymi efektami są głównie operacje wejścia / wyjścia. Po drugie, nawet dla efektów na zmienną pamięć, const nie blokuje ich. Nawet jeśli założymy, że nie ma możliwości obalenia systemu typów (ogólnie rozsądne w C ++), istnieje problem logicznej ciągłości i „zmiennego” słowa kluczowego C ++. Zasadniczo nadal możesz mieć mutacje pomimo const. Oczekuje się, że wynik będzie nadal „logicznie” taki sam, ale niekoniecznie taki sam.
Steve314,
2

Muszę powiedzieć, że pytanie jest nieco źle zdefiniowane, ponieważ zakłada, że ​​istnieje standardowa kolekcja „języków funkcjonalnych”. Prawie każdy język programowania obsługuje pewną ilość programowania funkcjonalnego. I prawie każdy język programowania obsługuje pewną liczbę programów imperatywnych. Gdzie można wytyczyć linię, która mówi, który jest językiem funkcjonalnym, a który jest językiem imperatywnym, innym niż kierowanie się uprzedzeniami kulturowymi i popularnym dogmatem?

Lepszym sposobem sformułowania pytania byłoby „czy możliwe jest wsparcie programowania funkcjonalnego w pamięci przydzielonej na stosie”. Odpowiedź jest, jak już wspomniano, bardzo trudna. Funkcjonalny styl programowania promuje alokację struktur danych rekurencyjnych do woli, co wymaga pamięci sterty (niezależnie od tego, czy śmieci są gromadzone, czy liczone referencje). Istnieje jednak dość wyrafinowana technika analizy kompilatora zwana analizą pamięci opartą na regionie, za pomocą której kompilator może dzielić stertę na duże bloki, które można alokować i zwalniać automatycznie, w sposób podobny do alokacji stosu. Strona Wikipedii wymienia różne implementacje tej techniki, zarówno dla języków „funkcjonalnych”, jak i „imperatywnych”.

Uday Reddy
źródło
1
Liczenie referencji IMO to odśmiecanie, a posiadanie sterty nie oznacza, że ​​i tak są to jedyne opcje. C malloc i mfrees używają sterty, ale nie ma (standardowego) modułu wyrzucania elementów bezużytecznych i zlicza tylko referencje, jeśli napiszesz do tego kod. C ++ jest prawie taki sam - ma (standardowo w C ++ 11) inteligentne wskaźniki z wbudowanym liczeniem referencji, ale nadal możesz ręcznie wprowadzać nowe i usuwać, jeśli naprawdę potrzebujesz.
Steve314,
Częstym powodem twierdzenia, że ​​zliczanie referencji nie jest odśmiecanie, jest to, że nie zbiera cykli referencyjnych. Z pewnością dotyczy to prostych implementacji (prawdopodobnie obejmujących inteligentne wskaźniki C ++ - nie sprawdziłem), ale nie zawsze tak jest. Co najmniej jedna wirtualna maszyna Java (IBM, IIRC) wykorzystywała liczenie referencji jako podstawę do wyrzucania elementów bezużytecznych.
Steve314,