abclinuxu.cz AbcLinuxu.cz itbiz.cz ITBiz.cz HDmag.cz HDmag.cz abcprace.cz AbcPráce.cz
AbcLinuxu hledá autory!
Inzerujte na AbcPráce.cz od 950 Kč
Rozšířené hledání
×
eParkomat, startup z ČR, postoupil mezi finalisty evropského akcelerátoru ChallengeUp!
Robot na pivo mu otevřel dveře k opravdovému byznysu
Internet věcí: Propojený svět? Už se to blíží...
včera 16:24 | Nová verze

Byla vydána Mageia 5.1. Jedná se o první opravné vydání verze 5, jež vyšla v červnu loňského roku (zprávička). Uživatelům verze 5 nepřináší opravné vydání nic nového, samozřejmě pokud pravidelně aktualizují. Vydání obsahuje všechny aktualizace za posledního téměř půldruhého roku. Mageia 5.1 obsahuje LibreOffice 4.4.7, Linux 4.4.32, KDE4 4.14.5 nebo GNOME 3.14.3.

Ladislav Hagara | Komentářů: 4
včera 13:42 | Pozvánky

V Praze probíhá konference Internet a Technologie 16.2, volné pokračování jarní konference sdružení CZ.NIC. Konferenci lze sledovat online na YouTube. K dispozici je také archiv předchozích konferencí.

Ladislav Hagara | Komentářů: 0
2.12. 22:44 | Komunita

Joinup informuje, že Mnichov používá open source groupware Kolab. V srpnu byl dokončen dvouletý přechod na toto řešení. V provozu je asi 60 000 poštovních schránek. Nejenom Kolabu se věnoval Georg Greve ve své přednášce Open Source: the future for the European institutions (SlideShare) na konferenci DIGITEC 2016, jež proběhla v úterý 29. listopadu v Bruselu. Videozáznam přednášek z hlavního sálu je ke zhlédnutí na Livestreamu.

Ladislav Hagara | Komentářů: 22
2.12. 15:30 | Zajímavý projekt

Společnost Jolla oznámila v příspěvku Case study: Sailfish Watch na svém blogu, že naportovala Sailfish OS na chytré hodinky. Využila a inspirovala se otevřeným operačním systémem pro chytré hodinky AsteroidOS. Použita je knihovna libhybris. Ukázka ovládání hodinek na YouTube.

Ladislav Hagara | Komentářů: 8
2.12. 14:15 | Nová verze

Byla vydána verze 7.1.0 skriptovacího jazyka PHP používaného zejména k vývoji dynamických webových stránek. Jedná se o první stabilní verzi nejnovější větvě 7.1. Přehled novinek v dokumentaci. Podrobnosti v ChangeLogu. K dispozici je také příručka pro přechod z PHP 7.0.x na PHP 7.1.x.

Ladislav Hagara | Komentářů: 3
2.12. 12:55 | Nová verze

Google Chrome 55 byl prohlášen za stabilní. Nejnovější stabilní verze 55.0.2883.75 tohoto webového prohlížeče přináší řadu oprav a vylepšení (YouTube). Opraveno bylo také 36 bezpečnostních chyb. Mariusz Mlynski si například vydělal 22 500 dolarů za 3 nahlášené chyby (Universal XSS in Blink).

Ladislav Hagara | Komentářů: 4
2.12. 11:55 | Pozvánky

Máte rádi svobodný software a hardware nebo se o nich chcete něco dozvědět? Přijďte na 135. sraz spolku OpenAlt, který se bude konat ve čtvrtek 8. prosince od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Sraz bude tentokrát tématický. Bude retro! K vidění budou přístroje jako Psion 5mx nebo Palm Z22. Ze svobodného hardwaru pak Openmoko nebo čtečka WikiReader. Přijďte se i vy pochlubit svými legendami, nebo alespoň na pivo. Moderní hardware má vstup samozřejmě také povolen.

xkucf03 | Komentářů: 1
2.12. 00:10 | Nová verze

Byla vydána verze 3.2 svobodného systému pro detekci a prevenci průniků a monitorování bezpečnosti počítačových sítí Suricata. Z novinek lze zmínit například podporu protokolů DNP3 a CIP/ENIP, vylepšenou podporu TLS a samozřejmě také aktualizovanou dokumentaci.

Ladislav Hagara | Komentářů: 0
1.12. 21:00 | Nová verze

Byla vydána beta verze Linux Mintu 18.1 s kódovým jménem Serena. Na blogu Linux Mintu jsou hned dvě oznámení. První o vydání Linux Mintu s prostředím MATE a druhé o vydání Linux Mintu s prostředím Cinnamon. Stejným způsobem jsou rozděleny také poznámky k vydání (MATE, Cinnamon) a přehled novinek s náhledy (MATE, Cinnamon). Linux Mint 18.1 bude podporován až do roku 2021.

Ladislav Hagara | Komentářů: 0
1.12. 16:42 | Nová verze

Byl vydán Devuan Jessie 1.0 Beta 2. Jedná se o druhou beta verzi forku Debianu bez systemd představeného v listopadu 2014 (zprávička). První beta verze byla vydána v dubnu letošního roku (zprávička). Jedna z posledních přednášek věnovaných Devuanu proběhla v listopadu na konferenci FSCONS 2016 (YouTube, pdf).

Ladislav Hagara | Komentářů: 2
Kolik máte dat ve svém domovském adresáři na svém primárním osobním počítači?
 (32%)
 (24%)
 (29%)
 (7%)
 (5%)
 (3%)
Celkem 770 hlasů
 Komentářů: 50, poslední 29.11. 15:50
Rozcestník
Reklama

Dotaz: Teorie programovani a "derivace funkce"

5.2.2013 15:16 JS
Teorie programovani a "derivace funkce"
Přečteno: 1119×
Ahoj,

ucim se ted trochu Haskell, protoze me napadla urcita teoreticka idea/koncepce v programovani, a rad bych se dozvedel, jestli uz neco takoveho neexistuje (a pod jakym nazvem to hledat). Rikam si, ze prave komunita lidi kolem Haskellu a funkcionalniho programovani by mohla znat odpoved, protoze jsou to vetsinou velice zdatni teoretici. Proto se ptam tady, protoze vim, ze se tady hodne takovych lidi pohybuje.

Ve funkcionalnim programovani (a la Haskell) mame jen ciste funkce. Tedy realny program (na realnem pocitaci) lze chapat jako jeden velky stavovy automat, nad kterym je jedna cista funkce, ktera vstup a vnitrni stav prevadi do vystupu a noveho vnitrniho stavu.

V praxi to tak ovsem nedelame, protoze by to bylo neefektivni. V praxi je totiz casta situace, ze ten vnitrni stav se tou operaci zmeni jen pomerne malo, nebo jen jeho cast; a provadeni vypoctu timto zpusobem by znamenalo, ze se pro vystup prepocitavaji i veci, ktere uz jsme vypocitali v minulem stavovem prechodu. V praxi se to resi imperativnim programovanim, ktere uklada ruzne mezivysledky.

Zajimalo me tedy, jestli existuje nejaky systematictejsi postup, jak by bylo mozne z onoho popisu "cista funkce nad globalnim stavem" odvodit, ktere veci uz neni potreba prepocitavat. Tim by bylo mozne definovat program vyse uvedenym zpusobem (jako funkci pro stavovy automat), coz je velmi elegantni, a pozdeji ho prevest na "imperativni" model, a neprijit tak o tu efektivitu. V podstate, velice neformalne, to znamena tu funkci "zderivovat", tedy najit funkci, ktera mi pro zmenu vstupu vrati zmenu na vystupu.

Jenze, co to vlastne znamena, "zmena" nejake veliciny, v tomto pripade? Obecne to zavisi od situace. Ale muzeme zkusit jednoduche pripady, a podivat se, jak bychom to tam asi chteli mit. Vezmeme si napriklad klasickou trojici funkci map/filter/reduce, ktere operuji nad posloupnostmi a ktere lze povazovat za urcite stavebni prvky, z kterych lze poskladat tu velkou prechodovou funkci, kterou chceme timto zpusobem optimalizovat.

Vsechny tri map/filter/reduce pracuji s argumentem posloupnosti. "Zmenou" v tomto pripade tedy muze byt pridani/ubrani/zmena jednoho prvku. U map i filter je derivace pomerne primocara - prepocita se jeden prvek. U reduce je zajimave, pokud je redukcni operace grupova, pak staci prepocitat take v podstate jen jeden prvek.

No a tohle me na tom zaujalo, a proto se tady na to ptam. Nikdy predtim jsem si neuvedomil, ze by optimalizace mohly zaviset na tom, jestli je neco grupa nebo ne (napriklad cloveka okamzite napada otazka - bylo by mozne to priohnout tak, aby funkce v reduce grupova byla?). Zni to zajimave, takze, chtel jsem se zeptat, rozviji uz nekdo takovou teorii? A souvisi to cele nejak s linym vyhodnocovanim?

Odpovědi

5.2.2013 16:28 l4m4
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Ve funkcionalnim programovani (a la Haskell) mame jen ciste funkce. Tedy realny program (na realnem pocitaci) lze chapat jako jeden velky stavovy automat, nad kterym je jedna cista funkce, ktera vstup a vnitrni stav prevadi do vystupu a noveho vnitrniho stavu.
Tady jsem se ztratil.

I když fyzicky nakonec program v Haskellu provádí CPU, na který se lze dívat jako na stavový automat, tak ten program není formulován jako nějaký převod jednoho stavu do jiného, ale jako výpočet (představitelný prostě jako dosazování vzorců do jiných vzorců).
5.2.2013 17:31 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Aha, asi jsem se blbe vyjadril. Ono totiz plati tak nejak oboji. Dejme tomu, ze bych chtel v Haskellu napsat treba hru (nerikam, ze chci, je to hypoteticke). Pak v te hre je nejaky stav sveta, a ten se meni na zaklade nejake funkce (ktera popisuje chovani toho sveta, reakci na vstup a jeho zobrazeni). Takze jedna zmena toho stavu, jedna reakce na vstup hrace, a vykresleni vystupu, je pak vypoctem te funkce.

Jenze problem je, ze ja nechci udelat jeden vypocet, ale serii vypoctu. Takze otazka je, jestli nejak nemohu vyuzit vlastnosti te funkce, abych z nich odvodil funkci, ktera provede jen dilci vypocet na zaklade znalosti predchoziho stavu.
5.2.2013 16:49 VM
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Ano, pokud mám v počítači v paměti a na disku dohromady n bitů, tak program můžu chápat jako funkci z 2^n stavů do 2^n stavů. V praxi se některé jednoduché úlohy opravdu řeší tabulkami, kde mám výstupní hodnoty pro všechny možné vstupní hodnoty. Údajně si takhle pomáhají třeba matematické koprocesory pro výpočet goniometrických funkcí. Pro většinu reálných výpočtů je ale těch 2^n stavů moc, a to i když je omezím na nějaké malé n vstupních bitů, takže se to počítá klasicky.
5.2.2013 17:38 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
O to mi nejde, to je jasne. Me prave jde o to brat to jako klasicky vypocet po celou dobu, akorat si myslim, ze je jednodussi ho reprezentovat jako jednu velkou operaci nad jednim velkym stavem, a taky nad tim tak uvazovat, nez spousta mensich operaci nad mensimi stavy.
6.2.2013 09:08 pc
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
nevim jestli spravne chapu vas dotaz, nejsem ani teroretik programovani, ale pro "derivaci" resp. uchovani urciteho stavu vypoctu pro optimalizaci opakovaneho volani se provadi technika tzv. memoization (nevim jak prelozit).v jazycich ktere podporuji uzavery (closures) se to da implicitne resit kompozici functoru.

pokud je jazyk jako haskell referencne transparentni (u vsech funkci krome IO), tj. je zajisteno ze hodnota funkce je pro jedny parametry vzdy stejna, muzou se takove optimalizace provadet i na urovni prekladace, ale nevim jestli to nejake konkretni implementace provadi.

btw. jestli chcete fundovanou odpoved, tak polozte otazku na stackoverflow.com. tam je daleko vetsi sance, ze ji dostanete.

6.2.2013 11:06 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Jasne, memoization je znama technika. Ale ja vidim sanci jit trochu dal - memoization se neda (prakticky) delat na slozitejsich datovych strukturach. Dalo by se to castecne povazovat za specialni pripad toho, o cem mluvim - vy vite, ze se predchozi hodnota nezmenila, a tak automaticky znate vysledek volane funkce. To co chci ja je efektivne prepocitat "nenulovou" zmenu.

No, ja nevim, jestli je to vhodna otazka pro Stackoverflow, a vlastne je to spis takovy neformalni pruzkum. Prave jsem trochu doufal, ze se tady najde par lidi, kteri budou vedet, na co me odkazat.
6.2.2013 14:42 pc
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
asi mam maly obzor, ale nedokazu si predstavit jak jinak nez "ukladanim" mezivysledku a jeho naslednym pouzitim pri opakovanem volani by slo toto dosahnout. rozdil bude asi jen v tom, jak komplikovane/skryte se tohle resi v tom kterem jazyce. v haskellu a zrejme i dalsich funkcionalnich jazycich to jde o poznani snadneji. pokud se zapise funkce bez volnych promennych, tj. ve vyrazu se vyskytuji jen parametry predane nejblizsi vnejsi lambde (tzv. konstantni aplikativni forma), tak vypocet takove funkce probehne jen jednou i pri opakovanem volani a dosahne se tak "automaticke" memoizace. a je jedno o jake datove struktury se bude jednat, jestli o proste numericke typy nebo treba binarni stromy.

nektere numericke algoritmy by treba (bez memoizace) dokazaly odvodit napr. vyraz pro vypocet n-teho clenu fibonacciho posloupnosti s O(1), ale u obecne funkce si takovou redukci nedokazu predstavit.

6.2.2013 15:41 karel_iv | skóre: 1
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
vyraz pro vypocet n-teho clenu fibonacciho posloupnosti s O(1), ale u obecne funkce si takovou redukci nedokazu predstavit.
To jde? Sám to umím v O(log n) pomocí mocnění matic (viz anglická wiki).

PS nerýpu, jen se ptám.

6.2.2013 17:03 pc
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
binetova veta ? ale samozrejme s urcitou mirou presnosti.
F(n) = (1-φ)n / √5
6.2.2013 17:07 Michal Kubeček | skóre: 71 | Luštěnice
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"

Na to si nepotřebujete hrát s maticemi, na to stačí ten vzoreček pro F_{m+n}, který odvodíte buď indukcí nebo z toho, že F_n je počet způsobů, jak poskládat úsečku délky n z úseček délek 1 a 2.

Konstantní složitost má v jistém smyslu ten explicitní vzoreček, který máte v odkazovaném článku také, ale to předpokládá, že s konstantní složitostí umocníte reálné číslo s dostatečnou přesností, což v praktické implementaci nedokážete.

8.2.2013 12:51 l4m4
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
V praktické implementaci bude explicitní vzoreček mít asymptotickou složitost O(n log(n)2) (tj. násobení pomocí FFT). Hraní si s maticemi v optimální variantě asi O(n log(n)3), ale muselo by se to odvodit...
6.2.2013 17:20 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
To co chci je neco jineho nez memoizace. Vezmi si jako priklad funkci ktera pro zadanou posloupnost prvku vrati jejich soucet. Kdyz se zmeni jeden prvek posloupnosti, je potreba znovu secist celou tu posloupnost. Memoizace nepomuze, protoze ta by si pamatovala ruzne soucty ruznych posloupnosti. Ale pokud vim, ze scitani je grupova operace, mohu odvodit funkci, ktera na zaklade toho, ze se zmenil jeden prvek a jak, a na zaklade znalosti predchoziho vysledku, dokaze odvodit vysledek novy. Tato nova funkce je "necim podobnym derivaci" od te puvodni funkce. Pouzit tuto novou funkci je efektivnejsi nez prepocitavat znova celou posloupnost.

Takze, memoizace je OK, ale jakmile zacnes predavat jako parametry slozitejsi datove struktury, narazi to. A to je prave problem, ktery se snazim resit. Mozna naivne a neumele - a proto se na to ptam, jestli uz nekdo uvazoval timto smerem.
6.2.2013 20:14 pc
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
dik za doplneni, ale myslim ze jsem to pochopil uz pred tim.

to co hledas by ale imho vyzadovalo specialni typovou tridu, ktera by pro prekladac indikovala ze to zobrazeni je grupova operace a podle toho by s ni taky zachazel. tohle ale standardni typovy system haskellu afaik neobsahuje, nevim jak je to jinde. lze urcite definovat vlastni datove typy a operace nad nimi, ktere by vyhovovaly podminkam pro grupovou algebru, ale tady se asi bavime o obecne metode, ktera by z libovolne funkce vytvorila funkci vyssiho radu, ktera by optimalizovala vypocet vyuzitim grupove algebry. v implementaci by ale stejne pak musela byt nejaka forma memoizingu, protoze tu "konecnou" mnozinu hodnot proste musi vypocitat, i kdyz muze vyuzit vyhody lineho vyhodnocovani. na mnozinach typu cela cisla by to imho ani jinak neslo.

pokud bych se vratil k map, filter, reduce (foldl, foldr v haskellu), tak je podstatne co presne si predstavujes tim doplnenim prvku. pokud se pridanim zachova indukce vypoctu, tak ten puvodni pozadavek lze trivialne splnit uzaverou nebo pro narocnejsi pozadavky nekterou ze stavovych monad. v opacnem pripade plati to co je v predchozim odstavci - bud se definuje cely vlastni typovy system pro grupove operace a bude to fungovat na explicitne resene omezene mnozine nebo pokud by to melo fungovat genericky tak se uz presouvame na uzemi umele inteligence :-) rad se necham vyvest z omylu, pokud tohle uz nejaky jazyk zvlada.

Goheeca avatar 6.2.2013 21:54 Goheeca | skóre: 7
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Tak nějak to taky vidím, že v obecném případě to bude chtít v základu minimálně nějaký ATP, mě nejblíže je ACL2 (a stejně s ním v podstatě neumím).
7.2.2013 08:03 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Aha, diky za odpoved. Ja ani nejak necekam, ze bude existovat obecne reseni - to je asi algoritmicky neresitelny problem, ale spis neco, co pokryje velkou cast pripadu.
6.2.2013 22:06 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
bylo by mozne to priohnout tak, aby funkce v reduce grupova byla?
Typový systém Haskellu je příliš slabý na to, aby tuto vlastnost vyjádřil. Existují programovací jazyky, kde to možné je. Mj. v Haskellu lze využít invarianty funkcí (např. map f . map g == map (f . g)) v přepisovacích pravidlech pro optimalizaci.
7.2.2013 08:03 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Muzes byt konkretnejsi?
7.2.2013 12:21 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Typový systém Haskellu je příliš slabý na to, aby tuto vlastnost vyjádřil.
Předpokládejme, že máme reduce : (a -> a -> a) -> List a -> a a chceme zajistit asociativitu prvního parametru (například, aby reduce mohl počítat paralelně). Jednou z možností, jak to udělat, je přidat funkci reduce další parametr, který bude sloužit jako konstruktivní důkaz oné asociativity.

Předně si první parametr pojmenujeme, abychom se na něj mohli odkazovat v dalších parametrech: reduce : (f:(a -> a -> a)) -> List a -> a.

Nyní se zamyslíme, co je konstruktivním důkazem asociativity f?. Je to funkce, jenž pro každé x : a, y : a, z : a vrátí důkaz, že f x (f y z) = f (f x y) z. To jest nový parametr pro reduce bude funkce x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z.

Takže paralelní reduce může mít typ reduce : (f:(a -> a -> a)) -> (x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z) -> List a -> a.

V Haskellu tento postup nebude fungovat minimálně ze dvou důvodů. Hlavním důvodem je fakt, že Haskell neumí vynutit totální funkce (term undefined = undefined je důkazem čehokoliv, neboť má libovolný typ) a má pouze koinduktivní typy. Druhým důvodem je to, že Haskell zatím nedovoluje mít aplikaci funkce f v typu (typ, jenž závisí na termu f).
Existují programovací jazyky, kde to možné je.
Například jazyky Idris nebo Agda 2. Programovat lze též v důkazových asistentech Isabelle a Coq a kód z nich lze pak extrahovat do nějakého normálního funkcionálního jazyka. Další jazyky, kde to pravděpodobně je možné, jsou v tabulce v článku o závislých typech.
Mj. v Haskellu lze využít invarianty funkcí (např. map f . map g == map (f . g)) v přepisovacích pravidlech pro optimalizaci.
Mám na mysli přepisovací pravidla v GHC. Používá se to v knihovnách Haskellu a hezkou aplikací je článek Stream Fusion. From Lists to Streams to Nothing at All.
7.2.2013 14:27 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Ah, diky za odpoved. Bude mi chvili trvat, nez to vstrebam. ;-)
8.2.2013 10:27 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Tak jsem si to procetl, a pochopil, tedy v ramci toho, co o FP, logice a Haskellu vim (coz neni moc). Diky za odpoved. Coq jsem se chtel naucit, ale zatim jsem na to nesebral odvahu. :-) Hlavne oni zacnou pak mluvit tim logickym jazykem a i normalnim matematikum (a uz nejsem ani to) je to ponekud vzdalenejsi.

Ta prepisovaci pravidla vypadaji zajimave (a i ten zmineny clanek, akorat nejde stahnout), a zda se, ze by to byl zpusob, jak to implementovat.

Jenom moc nechapu, je opravdu nutne nejak deklarovat pro ta prepisovaci pravidla tu asociativitu (a tedy mit typovy system takto silny), nebylo by mozne to proste rict, ze ta konkretni funkce vstupujici do toho reduce je asociativni (treba soucet)? Nedalo by se to prece jen nejak obejit?
8.2.2013 13:38 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Coq jsem se chtel naucit, ale zatim jsem na to nesebral odvahu.
Až se odhodláte, tak doporučuji začít se Software Foundations a poté pokračovat Certified Programming with Dependent Types.
ten zmineny clanek, akorat nejde stahnout
Teď jsem to zkoušel a podařilo se to. Možná to chce jen správné načasování.
Jenom moc nechapu, je opravdu nutne nejak deklarovat pro ta prepisovaci pravidla tu asociativitu (a tedy mit typovy system takto silny)
Na přepisovací pravidla v GHC nejsou kladena žádná velká omezení. Je to čistě vaše věc, jestli pravidla zachovají význam programu nebo jestli přepisování vůbec skončí – nic z toho se nekontroluje.
nebylo by mozne to proste rict, ze ta konkretni funkce vstupujici do toho reduce je asociativni (treba soucet)? Nedalo by se to prece jen nejak obejit?
Pokud vám nevadí, že to nekontroluje kompilátor, tak dalo. Nejjednodušší je udělat dvě funkce reduce a reducePar, přičemž ta první není paralelní a nepotřebuje asociativitu, ta druhá je paralelní a potřebuje asociativitu (ale kompilátor o tom nic neví). Nebo mohu vyžadovat, aby datový typ byl instancí typové třídy, jenž má asociativní operaci a používat výhradně onu operaci:
import Data.Monoid

-- Funguje i s prazdnym seznamem, protoze monoid ma neutralni prvek.
reduce :: Monoid a => [a] -> a
reduce = mconcat
A do třetice mohu napsat opět dvě varianty reduce – jednu pro obyčejné binární funkce a druhou pro asociativní (ve skutečnosti ta druhá není pro funkce, ale pro prvky typu Assoc a):
{-# LANGUAGE TypeFamilies, FlexibleInstances #-}

import qualified Debug.Trace as D

class Reduction f where
    type El f
    reduce :: f -> [El f] -> El f

instance Reduction (a -> a -> a) where
    type El (a -> a -> a) = a
    reduce = foldl1 . D.trace "normalni"

newtype Assoc a = Assoc { unassoc :: (a -> a -> a) }

instance Reduction (Assoc a) where
    type El (Assoc a) = a
    reduce = foldl1 . unassoc . D.trace "paralelni"
Když pak v GHCi zavolám reduce (+) [1..5], tak dostanu výstup
normalni
15
a když zavolám reduce (Assoc (+)) [1..5], tak dostanu výstup
paralelni
15
Problém všech třech řešení je v tom, že kompilátor asociativitu nekontroluje, neboť ani neví, že daná funkce má být asociativní. Výhodou silnějších typových systémů je, že asociativitu nebo jinou vlastnost může ověřovat kompilátor.
8.2.2013 15:40 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Diky za odkazy a za priklad. Clanek jsem pak nasel jinde.
11.2.2013 09:28 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Tak ctu ted trosku o Curry-Howard izomorfismu a pribuznych tematech na Wikipedii a musim rict, ze jedna vec, ktera me na tom celem pristupu trochu trapi, a to je, ze se tam uplne ignoruje vypocetni narocnost. U matematickeho dukazu mi prece nezalezi na tom, jak dlouho vypocet potrva; a v tom ta analogie fatalne kulha. A to je prave trochu to, co se snazim resit (muj pohled je, ze programy maji byt co nejelegantnejsi, ale jen do te miry, dokud nepoklesne vykon), takze ted opravdu nevim, jestli mi v tom smeru funkcionalni programovani pomuze. Mozna je to jen dojem zacatecnika, kazdopadne si rad poslechnu, jestli k tomu mas nejaky komentar.
11.2.2013 14:18 Radek Miček | skóre: 23 | blog: radekm_blog
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Tak ctu ted trosku o Curry-Howard izomorfismu a pribuznych tematech na Wikipedii a musim rict, ze jedna vec, ktera me na tom celem pristupu trochu trapi, a to je, ze se tam uplne ignoruje vypocetni narocnost. U matematickeho dukazu mi prece nezalezi na tom, jak dlouho vypocet potrva; a v tom ta analogie fatalne kulha.
Myslíte, že to nějak vadí při programování?

Třeba u příkladu s reduce jsem C-H izomorfismus využil jednou, a to když jsem chtěl, aby f byla asociativní. Místo důkazu asociativity jsem požadoval, aby byl typ x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z obydlený – tj. uživatel musel funkci reduce předat term (funkci) proof typu x:a -> y:a -> z:a -> f x (f y z) = f (f x y) z. Při implementaci reduce však není třeba volat funkci proof, tudíž na její časové složitosti nezáleží a kompilátor ji nemusí vůbec překládat.
9.2.2013 09:42 jas | skóre: 13 | blog: blag
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"

Nie som si uplne isty, ze som spravne pochopil otazku, ale ak hej, tak ciastocne riesenie existuje. Kompilator moze hladat dostupne vyrazy a nasledne nahradit vypocet podla vypocitaneho zoznamu za premennu, kde je vypocet ulozeny (v skutocnosti je to trocha zlozitejsie, pre detaily ide o problem AVAIL - hladania dostupnych vyrazov pri analyze toku dat, str. 23, zide sa aj uvod - prvych par stran, po problem LIVE).

Co sa tyka uplneho riesenia, tj. v podstate najdenie optimalnej funkcie voci nejakej cenovej funkcii, tak nic take (aspon pre turing-complete jazyky) neexistuje [jednoducha logika - mat podobne riesenie, tak vsetky ostatne optimalizacie by razom stratili zmysel]. Navyse sa obavam, ze na nieco podobne by sa dal spravit aj dokaz (pre zaciatok by mohlo byt problematicke, ze dany optimalizator by mal skoncit aj pri funkciach, ktore nad nejakym vstupom cyklia a detekovat nieco take - problem zastavenia - nie je rekurzivny problem).

Spravnou cestou je v tom pripade az obmedzovanie moznosti (vyjadrovacej sily) programovacich jazykov. Napr. vo forme konecnych automatov je taka optimalizacia mozna a aj jednoducha (viz minimalizacia konecnych automatov).

11.2.2013 09:23 JS
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"
Ano, ja take predpokladal, ze to bude asi obecne neresitelna uloha, a proto jsem k tomu od zacatku pristupoval tak, ze by bylo zajimave zkusit pokryt nejake bezne pripady. Spis nez omezeni vyjadrovaci sily bych to nazval tvorbou novych abstrakci, ktere umozni kompilatoru aplikovat prislusnou optimalizaci (napr. u tech konecnych automatu - pokud neco oznacim za konecny automat, umozni to kompilatoru s tim tak pracovat, a je to jednodussi nez se pokouset rozpoznat, zda je cast programu adaptovatelna na konecny automat nebo ne).
13.2.2013 15:40 jas | skóre: 13 | blog: blag
Rozbalit Rozbalit vše Re: Teorie programovani a "derivace funkce"

Uz som si precital dokladnejsie otazku a hlavne diskusiu a myslienka pouzitia informacii navyse pre kompilator je zaujimava a v podstate sa pouziva uz celkom dlho (napriklad register alebo inline v gcc) aj ked ide prevazne o velmi jednoduche veci. Rozne obmedzenia (tie nove abstrakcie) z ktorych vyplyvaju lepsie vlastnosti systemov sa studuju uz tiez celkom dlho, horsie je to s ich aplikaciou na realne programovacie jazyky (zvacsa sa pouzivaju skor matematicke modely, ktore su relativne vzdialene od bezneho programovania).

Teoreticky by nemuselo byt zlozite nieco podobne pre haskell spravit. Runtime optimalizacie by asi nemali moc zmysel, kedze rezia spojena s optimalizaciou by pravdepodobne bola vyssia nez to, co poskytne optimalizacia. V case kompilacie by to uz zmysel mohlo mat (tu by sa asi skutocne hodil modifikovany AVAIL problem pre vypocet dostupnych vyrazov, z ktorych sa da vychadzat v danom bode programu). Realizacia by tiez nemusela byt velmi obtiazna (na high-level urovni, programovania to bude chciet urcite dost). Technicky by stacilo pridat do gramatiky pre jazyk pravidlo, ktore by umoznovalo pri definicii funkcie davat priznaky (splna asociativitu, ma nulovy prvok 'm' a pod.) a nasledne vyuzivat tieto informacie pre optimalizacii.

Este som nepocul o projekte, ktory by sa nieco podobne snazil spravit, co samozrejme neznamena, ze taky projekt neexistuje. Kazdopadne ako napad to vyzera zaujimavo.

btw: Na programy (vsetky, nie len funkcionalne) sa casto pozera ako na transformatory stavovej funkcie, takze napojenie len na funkcionalne jazyky a pripadne line vyhodnocovanie by som v tomto pripade ako klucove nevidel.

Založit nové vláknoNahoru

Tiskni Sdílej: Linkuj Jaggni to Vybrali.sme.sk Google Del.icio.us Facebook

ISSN 1214-1267   www.czech-server.cz
© 1999-2015 Nitemedia s. r. o. Všechna práva vyhrazena.