-
Data: 2017-09-21 12:10:48
Temat: Optymalizacja struktur danych dla programów funkcyjnych
Od: g...@g...com szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]Cześć,
jakiś czas temu wspominałem o pracy magisterskiej, którą pisałem.
Ponieważ właśnie ją obroniłem, niniejszym ją upubliczniam.
Praca dostępna jest pod adresem
https://github.com/panicz/master-thesis
Poniżej zamieszczam abstrakt w języku polskim, z zastrzeżeniem,
że praca jest w całości po angielsku.
Celem niniejszej pracy jest wypracowanie technik pozwalających
na efektywne wykonywanie programów napisanych w stylu funkcyjnym.
Praca składa się z dwóch części. W pierwszej przedstawione są klasyczne
techniki transformacji programów funkcyjnych do postaci imperatywnej
oraz podstawowe metody dowodzenia twierdzeń o własnościach programów.
W części drugiej proponowana jest metoda przekształcania pewnych klas
programów operujących na listach w równoważne programy operujące na
tablicach. Ponadto analizowane są warunki pozwalające na przekształcenie
funkcyjnej implementacji algorytmu sortowania szybkiego do optymalnej
postaci imperatywnej.
Wszystkie programy źródłowe oraz transformacje wyrażone są przy pomocy
czysto funkcyjnego podzbioru algorytmicznego języka Scheme, opisa\-nego
w rozdziale 2. Docelowym modelem obliczeń jest wariant maszyny RAM, której
model i zestaw instrukcji zostały dogłębnie opisane w rozdziale 3, wraz
z implementacją, wykorzystującą imperatywne składniki języka Sche\-me.
W rozdziale 4 zaprezentowane są klasyczne techniki
przekształcania programów wyrażonych w omówionym podzbiorze języka
Scheme w ciągi instrukcji dla maszyny RAM, w szczególności konwersja
programów do postaci przekazującej kontynuacje (ang. \textit{Continuation-Passing
Style}) oraz optymalizacja rekurencji ogonowej (ang. \textit{Tail-Call
Optimization}).
Rozdział 5 opisuje uproszczony wariant systemu Boyera-Moore'a wraz
z pełną listą aksjomatów służących do dowodzenia twierdzeń o programach
wyrażonych w zaprezentowanym podzbiorze języka Scheme. W przeciwieństwie
jednak do oryginalnego systemu Boyera i Moore'a, wypracowany system nie
jest w stanie samodzielnie dowodzić twierdzeń, i może jedynie służyć
do sprawdzania poprawności dowodów wprowadzonych przez użytkownika.
W rozdziale 6 wypracowana zostaje autorska metoda konwersji programów
funkcyjnych do postaci otrzymujących i przekazujących tablice. Językiem
źródłowym jest czysto funkcyjny podzbiór języka Scheme opisany w rozdziale
2, zaś językiem docelowym -- pełny język Scheme zawierajacy składniki
imperatywne. Wyprawcowana metoda konwersji ma jedynie szkicowy charakter
i z pewnością wymaga dopracowania.
Rozdział 7 podejmuje zagadnienie automatycznej konwersji funkcyjnego
wariantu algorytmu sortowania szybkiego do postaci imperatywnej,
jednak nie prezentuje działającego algorytmu konwersji.
Słowa kluczowe
struktury danych, transformacje programów, kompilacja, dowodzenie twierdzeń,
programowanie funkcyjne
Następne wpisy z tego wątku
- 21.09.17 19:44 wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU
- 21.09.17 20:49 g...@g...com
- 21.09.17 22:35 Roman Tyczka
- 21.09.17 22:41 M.M.
- 28.09.17 18:08 wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU
- 28.09.17 19:22 g...@g...com
- 28.09.17 19:54 wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU
- 28.09.17 21:14 fir
- 30.09.17 13:57 fir
- 30.09.17 16:58 g...@g...com
- 30.09.17 17:14 wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU
- 30.09.17 20:13 Szyk Cech
- 30.09.17 20:18 wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU
- 30.09.17 21:54 M.M.
- 02.10.17 14:20 Maciej Sobczak
Najnowsze wątki z tej grupy
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
- Ideologia Polskiego Programisty wer.3
Najnowsze wątki
- 2024-05-01 Wrocław => AI Specialist <=
- 2024-05-01 Bieruń => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-05-01 Kraków => Senior Rust Software Engineer <=
- 2024-05-01 Gdańsk => Senior PHP Developer (Symfony) <=
- 2024-05-01 Trzecia płeć 2
- 2024-05-01 Lublin => Java Full Stack Developer (AI area projects) <=
- 2024-05-01 Lublin => Java Full Stack Developer (projekty w obszarze AI) <=
- 2024-05-01 twardy dysk stuka
- 2024-04-30 Oclenie alkalicznych akumulatorów
- 2024-04-30 Zniknął dźwięk na tylnym panelu
- 2024-04-30 Białystok => Inżynier DevOps (projekt JP) <=
- 2024-04-30 Kraków => Mid PHP Developer (Laravel) <=
- 2024-04-30 Katowice => Junior HelpDesk <=
- 2024-04-30 trzecia plec
- 2024-04-30 Katowice => Junior HelpDesk <=