-
X-Received: by 10.31.130.213 with SMTP id e204mr92195vkd.8.1505988648717; Thu, 21 Sep
2017 03:10:48 -0700 (PDT)
X-Received: by 10.31.130.213 with SMTP id e204mr92195vkd.8.1505988648717; Thu, 21 Sep
2017 03:10:48 -0700 (PDT)
Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed2.atman.pl!newsfeed.atman.pl!go
blin3!goblin.stu.neva.ru!news.misty.com!border2.nntp.dca1.giganews.com!nntp.gig
anews.com!b1no1054265qtc.1!news-out.google.com!x15ni855qth.1!nntp.google.com!q8
no1053892qtb.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-m
ail
Newsgroups: pl.comp.programming
Date: Thu, 21 Sep 2017 03:10:48 -0700 (PDT)
Complaints-To: g...@g...com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=46.186.90.250;
posting-account=f7iIKQoAAAAkDKpUafc-4IXhmRAzdB5r
NNTP-Posting-Host: 46.186.90.250
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <c...@g...com>
Subject: Optymalizacja struktur danych dla programów funkcyjnych
From: g...@g...com
Injection-Date: Thu, 21 Sep 2017 10:10:48 +0000
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Lines: 79
Xref: news-archive.icm.edu.pl pl.comp.programming:211523
[ ukryj 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
- 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
- Ada-Europe Conference - 6 March Extended Final Deadline
- Szybkie pytanko do fachowców od Bourne shella
Najnowsze wątki
- 2024-04-18 (Ponownie) odkryto, że ładowanie pulsacyjne robi dobrze
- 2024-04-18 Warszawa => Inżynier DevOps (Kubernetes, AWS) <=
- 2024-04-18 Wrocław => Key Account Manager <=
- 2024-04-18 Kraków => Mid PHP Developer (Laravel) <=
- 2024-04-18 Miejsce na kopertę
- 2024-04-18 driver led ?
- 2024-04-17 Odzyskiwanie konta Google'a po utracie telefonu
- 2024-04-17 Domek na działce, zabezpieczenie tynku
- 2024-04-17 Zdalna rejestracja SIM
- 2024-04-17 Kraków => Regular - .Net Programmer <=
- 2024-04-17 Kraków => Senior PHP Developer (Symfony) <=
- 2024-04-17 Gdańsk => Technical Leader (Java Background) <=
- 2024-04-17 Warszawa => Sales Development Representative (SDR) <=
- 2024-04-17 Chrzanów => Administrator i wdrożeniowiec Lotus Notes/Domino <=
- 2024-04-17 Długość wtyku zasilającego ?5.5mm