Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #30700 > unrolled thread

Optymalizacja struktur danych dla programów funkcyjnych

Back to article view | Back to pl.comp.programming

Contents

  Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-09-21 03:10 -0700
    Re: Optymalizacja struktur danych dla programów funkcyjnych wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU <NOSPAMtestowanije@go2.pl> - 2017-09-21 19:44 +0200
      Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-09-21 11:49 -0700
        Re: Optymalizacja struktur danych dla programów funkcyjnych Roman Tyczka <noemail@because.no> - 2017-09-21 22:35 +0200
        Re: Optymalizacja struktur danych dla programów funkcyjnych "M.M." <mmarszik@gmail.com> - 2017-09-21 13:41 -0700
        Re: Optymalizacja struktur danych dla programów funkcyjnych wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU <NOSPAMtestowanije@go2.pl> - 2017-09-28 18:08 +0200
          Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-09-28 10:22 -0700
            Re: Optymalizacja struktur danych dla programów funkcyjnych wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU <NOSPAMtestowanije@go2.pl> - 2017-09-28 19:54 +0200
            Re: Optymalizacja struktur danych dla programów funkcyjnych fir <profesor.fir@gmail.com> - 2017-09-28 12:14 -0700
    Re: Optymalizacja struktur danych dla programów funkcyjnych fir <profesor.fir@gmail.com> - 2017-09-30 04:57 -0700
      Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-09-30 07:58 -0700
        Re: Optymalizacja struktur danych dla programów funkcyjnych wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU <NOSPAMtestowanije@go2.pl> - 2017-09-30 17:14 +0200
          Re: Optymalizacja struktur danych dla programów funkcyjnych Szyk Cech <szyk100@o2.pl> - 2017-09-30 20:13 +0200
            Re: Optymalizacja struktur danych dla programów funkcyjnych wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU <NOSPAMtestowanije@go2.pl> - 2017-09-30 20:18 +0200
        Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-02 05:20 -0700
          Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-02 11:00 -0700
            Re: Optymalizacja struktur danych dla programów funkcyjnych Roman Tyczka <noemail@because.no> - 2017-10-03 11:35 +0200
              Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-03 10:52 -0700
            Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-03 09:56 -0700
              Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-03 11:01 -0700
                Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-03 15:21 -0700
                  Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-03 23:15 -0700
                    Re: Optymalizacja struktur danych dla programów funkcyjnych "M.M." <mmarszik@gmail.com> - 2017-10-04 09:36 -0700
                      Re: Optymalizacja struktur danych dla programów funkcyjnych Roman Tyczka <noemail@because.no> - 2017-10-04 20:02 +0200
                        Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-04 11:58 -0700
                    Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-04 16:37 -0700
                      Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-04 23:28 -0700
                        Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-05 04:48 -0700
                          Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-05 09:58 -0700
                            Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-06 05:01 -0700
                              Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-06 10:59 -0700
                                Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-07 14:22 -0700
                                  Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-08 01:47 -0700
                                    Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-08 14:30 -0700
                                      Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-08 22:58 -0700
                                        Re: Optymalizacja struktur danych dla programów funkcyjnych Maciej Sobczak <see.my.homepage@gmail.com> - 2017-10-09 05:25 -0700
                                          Re: Optymalizacja struktur danych dla programów funkcyjnych fir <profesor.fir@gmail.com> - 2017-10-09 09:12 -0700
                                          Re: Optymalizacja struktur danych dla programów funkcyjnych godek.maciek@gmail.com - 2017-10-09 10:47 -0700
      Re: Optymalizacja struktur danych dla programów funkcyjnych "M.M." <mmarszik@gmail.com> - 2017-09-30 12:54 -0700

Page 1 of 2  [1] 2  Next page →

#30700 — Optymalizacja struktur danych dla programów funkcyjnych

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

[toc] | [next] | [standalone]

#30701

domyślam się, że na politechnice warszawskiej?
w którym punkcie zawarłeś wnioski końcowe?

[toc] | [prev] | [next] | [standalone]

#30702

W dniu czwartek, 21 września 2017 19:44:20 UTC+2 użytkownik wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU napisał:
> domyślam się, że na politechnice warszawskiej?

akurat strona tytułowa jest po polsku.
możesz sprawdzić, nie musisz się domyślać

[toc] | [prev] | [next] | [standalone]

#30703

On Thu, 21 Sep 2017 11:49:58 -0700 (PDT), godek.maciek@gmail.com wrote:

>> domyślam się, że na politechnice warszawskiej?
> 
> akurat strona tytułowa jest po polsku.
> możesz sprawdzić, nie musisz się domyślać

Z tym, że do niego fakty nie docierają, wszystko opiera o domysły i
fantazję, dlatego bywa taki zabawny.

-- 
pozdrawiam
Roman Tyczka

[toc] | [prev] | [next] | [standalone]

#30704

On Thursday, September 21, 2017 at 8:50:00 PM UTC+2, godek....@gmail.com wrote:
> W dniu czwartek, 21 września 2017 19:44:20 UTC+2 użytkownik wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU napisał:
> > domyślam się, że na politechnice warszawskiej?
> 
> akurat strona tytułowa jest po polsku.
> możesz sprawdzić, nie musisz się domyślać

Jakbyś wnioski opisał na grupie, to też bym przeczytał z ogromnym
zaciekawieniem, a może i bym skomentował.
Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#30706

gdańsk... morskie powietrze dobrze wpływa na tamtejsze dziewczyny, 
niestety nie miałem okazji sprawdzić, bo mnie tam nie przyjęli (wiadomo, 
nie zasłużyłem)...

[toc] | [prev] | [next] | [standalone]

#30707

W dniu czwartek, 28 września 2017 18:08:03 UTC+2 użytkownik wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU napisał:
> gdańsk... morskie powietrze dobrze wpływa na tamtejsze dziewczyny, 
> niestety nie miałem okazji sprawdzić, bo mnie tam nie przyjęli (wiadomo, 
> nie zasłużyłem)...

może nie aplikowałeś?

[toc] | [prev] | [next] | [standalone]

#30708

> może nie aplikowałeś?

aplikowałem czy nie aplikowałem,
ważne, że mnie nie przyjeli...

[toc] | [prev] | [next] | [standalone]

#30709

W dniu czwartek, 28 września 2017 19:22:33 UTC+2 użytkownik godek....@gmail.com napisał:
> W dniu czwartek, 28 września 2017 18:08:03 UTC+2 użytkownik wół, wół roboczy, wół dojno roboczo obronny 'POPIS/EU napisał:
> > gdańsk... morskie powietrze dobrze wpływa na tamtejsze dziewczyny, 
> > niestety nie miałem okazji sprawdzić, bo mnie tam nie przyjęli (wiadomo, 
> > nie zasłużyłem)...
> 
> może nie aplikowałeś?

dobre

[toc] | [prev] | [next] | [standalone]

#30712

W dniu czwartek, 21 września 2017 12:10:49 UTC+2 użytkownik godek....@gmail.com napisał:
> 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
> 
spoko ale mysle ze stety czy nieststy tutaj malo osob jest zainteresowanych jezykami funkcyjnymi, (co nie znaczy ze nie mozna o nich pisac)

[toc] | [prev] | [next] | [standalone]

#30713

W dniu sobota, 30 września 2017 13:57:06 UTC+2 użytkownik fir napisał:
> W dniu czwartek, 21 września 2017 12:10:49 UTC+2 użytkownik godek....@gmail.com napisał:
> > 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
> > 
> spoko ale mysle ze stety czy nieststy tutaj malo osob jest zainteresowanych jezykami funkcyjnymi, (co nie znaczy ze nie mozna o nich pisac)

Grupa jest o programowaniu. W moim odczuciu programowanie
funkcyjne jest jedną z podstawowych technik, jakie każdy
profesjonalny programista powinien opanować -- nie dlatego,
żeby stosować ją do wszystkiego, ale dlatego, żeby znać jej
możliwości i ograniczenia.

Czasem pojawia się też na tej grupie ożywione zainteresowanie
takimi zagadnieniami, jak kompilacja czy asemblery. Są to tematy,
które zostały poruszone w pracy. (Warto zwrócić uwagę, że kompilator
w istocie rzeczy jest programem czysto funkcyjnym, nawet jeśli
często nie jest w taki sposób implementowany).

[toc] | [prev] | [next] | [standalone]

#30714

ta twoja gadka to ma jakieś zastosowania praktyczne czy służy do 
ustalenia hierarchii do żłoba?

P.S.
ale nie o tym, dlaczego nie mogę znaleźć od dwóch miesięcy w warszawie 
nikogo kto by mi napisał prosty program na stm-a?

[toc] | [prev] | [next] | [standalone]

#30717

W dniu 30.09.2017 o 17:14, wół, wół roboczy, wół dojno roboczo obronny 
'POPIS/EU pisze:
> dlaczego nie mogę znaleźć od dwóch miesięcy w warszawie nikogo kto by mi 
> napisał prosty program na stm-a?

Skoro taki prosty, to czemu sam go nie napiszesz?!?

-- 
http://szyk.jcom.pl/
http://szyk.free.of.pl/
http://szykcech.cba.pl/
http://szyk.000webhostapp.com/
http://www.geocities.ws/szyk/
http://szyk.wex.pl/

[toc] | [prev] | [next] | [standalone]

#30718

> Skoro taki prosty, to czemu sam go nie napiszesz?!?

bo ja jestem niepełnosprawny...
niepełnosprawny intelektualnie...
mam na to dowód - wypis z pw...

[toc] | [prev] | [next] | [standalone]

#30726

> (Warto zwrócić uwagę, że kompilator
> w istocie rzeczy jest programem czysto funkcyjnym,

Nie, nie jest. I w ogóle co to miałoby znaczyć - "czysto funkcyjnym"? Kompilator ma wyprodukować wyjście na podstawie wejścia. Każdy program tak robi - czy każdy program jest "czysto funkcyjny"?

> nawet jeśli
> często nie jest w taki sposób implementowany).

Nie jest w taki sposób implementowany, bo w istocie rzeczy nie jest czysto funkcyjny (cokolwiek to znaczy). Co ogólnie rozszerza moją niedawną tezę, że metody kojarzone z językami funkcjonalnymi są nienaturalne.
(Co nie znaczy, że są nieużyteczne.)

-- 
Maciej Sobczak * http://www.inspirel.com

[toc] | [prev] | [next] | [standalone]

#30727

W dniu poniedziałek, 2 października 2017 14:20:39 UTC+2 użytkownik Maciej Sobczak napisał:
> > (Warto zwrócić uwagę, że kompilator
> > w istocie rzeczy jest programem czysto funkcyjnym,
> 
> Nie, nie jest. I w ogóle co to miałoby znaczyć - "czysto funkcyjnym"? 

Miałoby znaczyć tyle, że dla danego wejścia daje zawsze to samo wyjście.

> Kompilator ma wyprodukować wyjście na podstawie wejścia. Każdy program tak robi - czy każdy program jest "czysto funkcyjny"?

Nie każdy program tak robi. Na przykład system czasu rzeczywistego
ma się odpowiednio zachować w określonych okolicznościach.
Swego czasu opisałem framework do optymalizacji ewolucyjnej, który
zasadniczo nie był funkcyjny.

> > nawet jeśli
> > często nie jest w taki sposób implementowany).
> 
> Nie jest w taki sposób implementowany, bo w istocie rzeczy nie jest czysto funkcyjny (cokolwiek to znaczy).

Jeżeli nie wiesz co to znaczy, to skąd wiesz, że w istocie
rzeczy nie jest czysto funkcyjny?

> Co ogólnie rozszerza moją niedawną tezę, że metody kojarzone z językami funkcjonalnymi są nienaturalne.
> (Co nie znaczy, że są nieużyteczne.)

Jakie metody?

[toc] | [prev] | [next] | [standalone]

#30728

On Mon, 2 Oct 2017 11:00:16 -0700 (PDT), godek.maciek@gmail.com wrote:

>> Nie, nie jest. I w ogóle co to miałoby znaczyć - "czysto funkcyjnym"? 
> 
> Miałoby znaczyć tyle, że dla danego wejścia daje zawsze to samo wyjście.
> 
>> Kompilator ma wyprodukować wyjście na podstawie wejścia. Każdy program tak robi - czy każdy program jest "czysto funkcyjny"?
> 
> Nie każdy program tak robi. Na przykład system czasu rzeczywistego
> ma się odpowiednio zachować w określonych okolicznościach.
> Swego czasu opisałem framework do optymalizacji ewolucyjnej, który
> zasadniczo nie był funkcyjny.

Kompilator też daje różne wyniki w zależności od okoliczności (flag
kompilacji). 
 

-- 
pozdrawiam
Roman Tyczka

[toc] | [prev] | [next] | [standalone]

#30730

W dniu wtorek, 3 października 2017 11:35:40 UTC+2 użytkownik Roman Tyczka napisał:

> > Nie każdy program tak robi. Na przykład system czasu rzeczywistego
> > ma się odpowiednio zachować w określonych okolicznościach.
> > Swego czasu opisałem framework do optymalizacji ewolucyjnej, który
> > zasadniczo nie był funkcyjny.
> 
> Kompilator też daje różne wyniki w zależności od okoliczności (flag
> kompilacji). 

Czyli wejść

[toc] | [prev] | [next] | [standalone]

#30729

> > Nie, nie jest. I w ogóle co to miałoby znaczyć - "czysto funkcyjnym"? 
> 
> Miałoby znaczyć tyle, że dla danego wejścia daje zawsze to samo wyjście.

Biorąc pod uwagę deterministyczny sposób działania układów cyfrowych, każdy program wykonany na takich układach tak działa. W każdym języku.
Ale to oznacza też, że określenie "czysto funkcyjny" jest niepraktyczne, bo niczego nie rozstrzyga - bo skoro każdy program jest "czysto funkcyjny", to szkoda literek na określanie wszystkiego w ten sposób.

> Nie każdy program tak robi. Na przykład system czasu rzeczywistego
> ma się odpowiednio zachować w określonych okolicznościach.

Te okoliczności to też wejście (bo niby skąd program ma wiedzieć o tych okolicznościach? informacja o otoczeniu musi jakoś wpłynąć do programu a to jest właśnie wejście). Podobnie jak interwały upływającego czasu - to też jest wejście.

> > Nie jest w taki sposób implementowany, bo w istocie rzeczy nie jest czysto funkcyjny (cokolwiek to znaczy).
> 
> Jeżeli nie wiesz co to znaczy, to skąd wiesz, że w istocie
> rzeczy nie jest czysto funkcyjny?

Bo określenie "czysto coś" ma zawsze wadę bycia niedookreślonym. I zwykle tak czy siak nie jest prawdą.
Poza tym, obowiązuje zasada "nie wiem o co chodzi, ale chętnie się wypowiem".

> > Co ogólnie rozszerza moją niedawną tezę, że metody kojarzone z językami funkcjonalnymi są nienaturalne.
> > (Co nie znaczy, że są nieużyteczne.)
> 
> Jakie metody?

Te czyste. :-)

-- 
Maciej Sobczak * http://www.inspirel.com

[toc] | [prev] | [next] | [standalone]

#30731

W dniu wtorek, 3 października 2017 18:56:43 UTC+2 użytkownik Maciej Sobczak napisał:
> > > Nie, nie jest. I w ogóle co to miałoby znaczyć - "czysto funkcyjnym"? 
> > 
> > Miałoby znaczyć tyle, że dla danego wejścia daje zawsze to samo wyjście.
> 
> Biorąc pod uwagę deterministyczny sposób działania układów cyfrowych, każdy program wykonany na takich układach tak działa. W każdym języku.
> Ale to oznacza też, że określenie "czysto funkcyjny" jest niepraktyczne, bo niczego nie rozstrzyga - bo skoro każdy program jest "czysto funkcyjny", to szkoda literek na określanie wszystkiego w ten sposób.

Nie. Na przykład unixowe polecenia takie jak mkdir czy rm nie są czysto
funkcyjne, bo ich istotą jest wykonanie pewnego skutku ubocznego -- zmiana
pewnego stanu.

Podobnie wspomniany przeze mnie system do algorytmów genetycznych
(można sobie o nim poczytać w rozdziale drugim książki
https://github.com/panicz/pamphlet/) -- bazuje na operacji niedeterministycznej,
ponieważ losuje pewien obiekt. Zatem nie jest ze swojej istoty czysto
funkcyjny.

Określenie "czysto funkcyjny" jest bardzo praktyczne, ponieważ
wyznacza środki analizy potrzebne do tego, żeby analizować dany
system. Systemy czysto funkcyjne można analizować w terminach
podstawień wartości wyrażeń za wyrażenia.

> > Nie każdy program tak robi. Na przykład system czasu rzeczywistego
> > ma się odpowiednio zachować w określonych okolicznościach.
> 
> Te okoliczności to też wejście (bo niby skąd program ma wiedzieć o tych okolicznościach? informacja o otoczeniu musi jakoś wpłynąć do programu a to jest właśnie wejście). Podobnie jak interwały upływającego czasu - to też jest wejście.
> 
> > > Nie jest w taki sposób implementowany, bo w istocie rzeczy nie jest czysto funkcyjny (cokolwiek to znaczy).
> > 
> > Jeżeli nie wiesz co to znaczy, to skąd wiesz, że w istocie
> > rzeczy nie jest czysto funkcyjny?
> 
> Bo określenie "czysto coś" ma zawsze wadę bycia niedookreślonym. I zwykle tak czy siak nie jest prawdą.

Jest całkowicie dookreślone. W jakimś sensie, w każdym razie.
Bo rzeczywiście, wiele kompilatorów działa tak, że wykonuje pewien
efekt uboczny, np. sprawia, że na dysku pojawiają się jakieś pliki
(i czasem też znikają). Ale to nie należy do jego istoty, tylko
jest szczegółem implementacyjnym (w mojej pracy kompilatory nie robią
takich obrzydliwych rzeczy).

> Poza tym, obowiązuje zasada "nie wiem o co chodzi, ale chętnie się wypowiem".

A, to przepraszam :)

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | pl.comp.programming

csiph-web