Postanowiłem wrzucić na bloga moją pracę magisterską (analiza implementacji leniwych języków funkcyjnych – PDF), jaką broniłem około 7 lat temu. Wydaje mi się, że wpisuje się ona w ogólną tematykę jaką chciałem na blogu przyjąć, ale o tym innym razem…

Teraz nieco zareklamuję treść swojego „dzieła”… Co my tu mamy po kolei.

  1. Wprowadzenie do rachunku lambda (λ), czyli: term, β-redukcja, redeks, redukt, postać normalna, (słaba) postać czołowa normalna, własność Churcha-Rossera – czyli… klasyka gatunku ;-).
  2. Standardowe konstrukcje znane z języków programowania ich definicja w rachunku λ, czyli: liczebniki Churcha (1, 2, 3…), prawda/fałsz i operatory logiczne, konstrukcja warunkowa i teraz coś lepszego: tzw. wartości algebraiczne czyli para, lista, uogólnienie na dowolne konstruktory, projekcje itp., dalej idą operacje arytmetyczne – tu już trzeba pokombinować – dodawanie, odejmowanie, mnożenie, ale już do dzielenia będzie potrzebna rekurencja – czyli operator punktu stałego (Y).
  3. Po tym wprowadzeniu – teraz zaczyna się ciekawa część. Czym się różni strategia ewaluacji (redukcji) gorliwa od leniwej, czym się różni gorliwe wołanie przez wartość (call by value), wołanie przez nazwę (call by name) oraz te właściwe dla leniwości – wołanie zgodnie z potrzebą (call by need). Otóż zostaje podana formalna definicja w czystym rachunku λ. Gdzie indziej tego nie dostaniecie!
  4. Kolejna mocna rzecz – odśmiecanie (garbage-collection) zdefiniowane formalnie w rachunku lambda. Po powyższych strategiach ewaluacji to było już proste – jednolinijkowa definicja i gotowe.
  5. Dalej jest o języku Haskell – jego uproszczonym podzbiorze i konwersji na konstrukcje w rachunku lambda. Tu z ciekawszych rzeczy jest wzajemnie rekurencyjna konstrukcja let i jej rozbicie na warstwy (tzw. stratyfikacja).
  6. Druga część pracy jest bardziej standardowa – wprowadzenie i omówienie implementacji leniwych języków funkcyjnych. Z ciekawszych fragmentów tutaj: związek większej siły wyrazu z trudniejszą implementacją – na przykładzie systemu typów z rekurencyjnym polimorfizmem w Haskellu i potrzebnym do tego nieograniczonym rozmiarze kręgosłupa (spine).
  7. Po tych dwóch częściach wprowadzenia – właściwy atak i krytyka leniwości jako takiej (mamy już aparat w ręku aby się tym zająć): problem wycieku pamięci w czystych leniwych językach funkcyjnych. Ten problem jest poza naszą kontrolą, w grę wchodzą takie zagadnienia jak: analiza gorliwości, analiza uaktualniania, tania gorliwość, optymistyczna ewaluacja, ewaluator sekwencyjny, leniwa rekurencja ogonowa itp. Podane są trywialne przykłady, na jakich widać problemy niezależne od przyjętej implementacji leniwości. Nawet standardowe funkcje z Haskell Prelude powodują wycieki pamięci.
  8. Ogólny mój wniosek jest taki – leniwość nie nadaje się do użycia w praktyce, bo nie można kontrolować i zapobiegać efektowi wycieku pamięci. Co więcej – nie jest nawet możliwe powstanie  w przyszłości implementacji pozbawionej tej wady. To jest wbudowana cecha leniwości. Super siła wyrazu na papierze, w praktyce – bezużyteczna.

Liczę, że ktoś może kiedyś będzie szukał czegoś na temat (tak jak ja 9 lat temu) i trafi szczęśliwie na ten wpis. Chętnie podyskutuję na temat lub wyjaśnię co trzeba – zapraszam do komentowania.

Poniżej zOCRowany i poprawiony (nieco) tekst ze streszczenia i wstępu do pracy – aby się to lepiej w wyszukiwarkach odnajdywało. Nawiasem mówiąc – dobrze wypozycjonowane w Google systemy OCR on-line są jednak bardzo mizerne – konwersje na PNG musiałem robić i sporo ręcznych poprawek – widać, że nawet słownika PL nie mają, choć niektóre polskie litery udaje im się (czasem) rozpoznać… Stosowanie w tych serwisach mechanizmu reCaptcha jako zabezpieczenia przed masowym skanowaniem przez boty, to już zakrawa na jakiś autoironiczny żart.

Streszczenie

Praca przedstawia analizę implementacji leniwych języków funkcyjnych. Większość istotnych z punktu widzenia pracy cech języków funkcyjnych – takich jak leniwość czy gorliwość – jest przedstawiona w uogólnieniu dla rachunku λ (lambda). Następnie przedstawione są wybrane, używane w praktyce implementacje leniwych języków funkcyjnych. W ostatniej części pracy omówione są problemy związane z efektywnością leniwych języków funkcyjnych, a w szczególności problemy z zarządzaniem pamięcią. Praca wskazuje na właściwe źródło tych problemów, które nie jest związane z implementacjami leniwości, ale z samą naturą leniwości, czy może nieodpowiednim jej zdefiniowaniem.

Wstęp

Tematyka tej pracy ewaluowała od pomysłu stworzenia efektywnej implementacji leniwego języka funkcyjnego, inspirowanej maszyną STG (w tym kierunku początkowo kierowały się badania), do swojej aktualnej postaci, czyli prezentacji leniwej ewaluacji – od wprowadzenia, przez przykładowe implementacje, do zaawansowanych zagadnień i problemów pojawiających się w praktyce.

Początkowe poszukiwania wyrażeń, z którymi maszyna STG nie najlepiej sobie radzi (takie wyrażenia ukazują obszary implementacji maszyny STG, które można by poprawić) doprowadziły do natknięcia się na poważne problemy wynikające z samej istoty leniwej ewaluacji również konkretne wady i problemy samej maszyny STG i innych maszyn).
Co ciekawe, napotkane problemy, choć stawiają pod znakiem zapytania praktyczne wykorzystanie języków leniwych, nie są nawet wspomniane w różnych dokumentach opisujących języki leniwe i ich implementacje. Większość dokumentów o językach leniwych (wprowadzenia, podręczniki, raporty itp.) koncentruje się na zaletach – sile wyrazu, czystości (w sensie braku odstępstw od paradygmatu funkcyjnego), walorach edukacyjnych i silnemu związkowi z informatyką teoretyczną (rachunek λ).

Istniejące prace na temat wad leniwości zakładają, zaawansowany poziom czytelników (brak jest prac zaczynających od wprowadzenia w temat) i duża wiedzę teoretyczna. Prace te tworzą bardzo wąski nurt poboczny, nie istniejący w świadomości większości osób zajmujących się językami leniwymi amatorsko, w tym również nauczycieli akademickich uczących o leniwych językach funkcyjnych. Dokumenty z głównego – popularyzatorskiego – nurtu obiecują wiele, pokazując same zalety leniwości, jednak można dostrzec jak to się kończy np. przeglądając listy na grupach dyskusyjnych dotyczących języków leniwych.

Użytkownicy, którzy napotkają problem od strony praktycznej, czyli podczas tworzenia własnych programów, najczęściej nie mogą, niestety, liczyć na pomoc. Rozwiązania bądź wyjaśnienia podawane przez innych (często zaawansowanych) użytkowników są często błędne i jednocześnie ukazują niedostatki wiedzy na ten temat (wynikające z braku szerokiego dostępu do odpowiednich publikacji).

Ta praca jest przykładem dokumentu, który ma za zadanie trafić w opisana dziurę. Praca zaczyna się od wprowadzenia teoretycznego (od rachunku λ), a kończy na wyjaśnianiu podłoża niektórych problemów leniwości. Wprowadzenie w temat ogranicza się do niezbędnego minimum i jednocześnie służy późniejszemu pogłębieniu zrozumienia opisywanych zjawisk. Od teoretycznego wstępu praca płynnie przechodzi do przedstawienia konkretnych implementacji z dyskusją pewnych ich elementów (pod kątem efektywności). Przedstawiono m.in. metodę analizowania wykonania programu w celu zidentyfikowania w nim źródła niepożądanych zachowań.

Na tą pracę można spojrzeć jeszcze pod innym kątem. Ukazuje ona mianowicie dualność pomiędzy siłą wyrazu (i innymi zaletami, które można określić jako składniowe czy statyczne), a problemami implementacyjnymi i efektywnością działania  (a więc tym, co można określić jako cechy dynamiczne). Jednym z przykładów takiej dualności jest omawiany podział języków funkcyjnych na gorliwe   (więc o mniejszej sile wyrazu, ale jednocześnie efektywniejsze) i leniwe (o większej sile wyrazu, ale z wieloma poważnymi i nierozwiązanymi problemami implementacyjnymi). Drugim z przykładów może być dyskusja na temat związku siły systemu typów i możliwości stosowania pewnych technik optymalizacyjnych (zaprezentowane na przykładzie rozszerzenia systemu typów o polimorfizm rekurencyjny).

Zapoznając się z tą pracą można odnieść wrażenie, że praca ta jest w głównej mierze opracowaniem, skomponowanym ze starannie dobranych materiałów, w celu trafienia w opisana dziurę. Należy jednak podkreślić, że jest to wrażenie pozorne. Owszem, mamy tu do czynienia z pewnym zakresem materiału, zbiorem pojęć, abstrakcyjnych tworów, implementacji itp., które powstały przed rozpoczęciem tworzenia tej pracy. Praca ta nie rozszerza tego zbioru o istotne nowe pojęcia itp., ale komentuje i wyciąga wnioski z już istniejących dokonań. Właśnie to zebranie pewnej porcji materiału na określony temat i wnikliwe zapoznanie się z nim, pozwoliło na wyciągnięcie wniosków niemożliwych do wyciągnięcia bez zestawienia ze sobą wyników pracy różnych autorów. Samo skojarzenie i zestawienie odpowiednich wyników z różnych prac było efektem świadomego poszukiwania i niebanalnej pracy intelektualnej (której nie można zrównać z kompilacja innych prac na poziomie przetwarzania zdań, akapitów i rozdziałów w spójną całość kompozycyjną).

Istotna część treści pracy nie powstała na podstawie literatury, którą jest tu cytowana. Często fragmenty pracy były formułowane najpierw, a odpowiednia literatura, która dotyczyła tych samych, bądź analogicznych zagadnień, odnajdywana później. Jak już wcześniej wspomniano, trudno jest dotrzeć do odpowiedniej literatury i często było to możliwe dopiero po sformułowaniu problemu (wtedy wiadomo już czego szukać). Odnaleziona w ten sposób (po fakcie samodzielnego napisania) literatura do konkretnych fragmentów pracy stanowiła potwierdzenie słuszności przeprowadzonego samodzielnie rozumowania i wyciągniętych wniosków.

knpswPzatirr
,rpeopaouebddnrleopskknmpbtotiayrulweyz
ewjezdodyisinsmtntazazapzemrwwwwnleiiiajmaua,de,zozpgnnrntdaeleail
ni
y zzzimje
en,
ieilofmpuwnhakpadmiltwljnlea,iyimeze
yrnmnkoan
,t.ojs.thew
,azi
jPaynSjfakiu
rmtloluere
wiknena
lisief.wzuw
njyN
ynnis
kakhhe
osatynje
,ejue,,ip{izzje,nyytkkaehlnooe.a
wpwi
zrWhzfufe lujdnaoamnsskk
t
ai
,lyweynjenaniitwzn
ujr
oheoh
s.azd,,eaW l,s
ae
wzniiyetw,iypkwbg
srohszaszro
nleypi
e
w,ro,o
imusbzgtzy
_aoeyl{mnwnijyaooesnw
z_s
heeti,

Advertisements
Komentarze
  1. Janusz pisze:

    Wnioskuję, że to odśmiecanie aktualnie obrabianego drzewa wywołuje wycieki pamięci. Co ze sprytnymi wskaźnikami użytymi w polu kontrolnym obiektów odkładanych na drzewa?

    W programowaniu przybliżam się do leniwego programowania funkcyjnego z pamięcią. Na razie nie miałem kłopotów z wyciekami, raczej z implementacją.
    Być może z uwagi na struktury: kartoteka, w której każda pamiętana dłużej wartość lub część argumentów mają bajt kontrolny zawierający sprytny wskaźnik, typ i długość. Mam 4 typy, z których 3 w pewnych warunkach można utożsamić. Błędna konstrukcja zwraca samą siebie, prawidłowa zupełnie inny obiekt.
    Podejście leniwe i interakcyjne zmiany wykonywania algorytmów są źródłem nowych odkryć.

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s