-
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
- Do czego nadaje się QDockWidget z bibl. Qt?
- 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?
Najnowsze wątki
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=
- 2024-05-18 Łódź => Handlowiec - Systemy CRM <=
- 2024-05-17 ZŁOMNIK o pracy w TVN TURBO, nowych przepisach i współczesnej motoryzacji. Turbo Taryfa!
- 2024-05-17 Białystok => DevOps Engineer Conexa First (Contractor) <=
- 2024-05-17 Warszawa => Starszy inżynier oprogramowania (Rust) <=
- 2024-05-17 Zabrze => Junior HelpDesk <=