Výpočetní složitost v deklarativním programování

[desprit]

Mohl by mi někdo vysvětlit tohle? "Functional programming is declarative, which means that the form of a function doesn't entail its time complexity. For example, the school-taught formula for Fibonacci numbers can be evaluated by a functional interpreter in linear time. This is what's appealing about functional programming, for even monadic computations can be optimised to some extent. Likewise, theories in logic programming can be written simply as borders(alaska, yukon), borders(X,Y) :- borders(Y,X) and an inference engine will correctly account for the symmetry of the borders predicate. We needn't care about time complexity all that much."

Moc mi není jasné, jak ta optimalizace nastane sama od sebe.

[Reklama]

[desprit]

Nikdo? To je to tak složité?

[v]

možná zkuste dotaz trochu rozvést...

autor měl asi na mysli, že v čistém funkcionálním jazyce má překladač mnohem větší možnosti optimalizace, protože toho o sémantice programu ví víc (referential transparency etc.) a optimalizace nenastane sama od sebe, ale někdo ji musí v překladači implementovat
IMHO je to trochu mýtus ("sufficiently smart compiler")

[JS]

Ano, ta optimalizace samozrejme sama nenastane, nekdo to musi implementovat. Jde spis o to, ze jelikoz je algoritmus zapsan na "vyssi urovni", prekladac muze mit v nekterych vecech vetsi prostor se rozhodnout, jak to prelozit.

Napriklad v tom odkazu na Fibonacciho posloupnost, standardne rekurzivne pocitat podle vzorce x(n) = x(n-1) + x(n-2) je nesmysl, ale prekladac muze teoreticky implementovat memoizaci (tedy zapamatovani si predchozich vypocitanych hodnot funkce), a to tento vypocet dost urychli.

[BoneFlute]

Ano, ta optimalizace samozrejme sama nenastane, nekdo to musi implementovat.

Tak teoreticky stačí vytvořit fitness fci, a naimplementuje se sama (jedinej případ, kdy evoluce cca funguje). A samozřejmě na takovou funkci je třeba právě dobře definovaný stavový prostor. A ten se deklarativně definuje lépe, než imperativně.

[Reklama]

[gll]

Ano, ta optimalizace samozrejme sama nenastane, nekdo to musi implementovat. Jde spis o to, ze jelikoz je algoritmus zapsan na "vyssi urovni", prekladac muze mit v nekterych vecech vetsi prostor se rozhodnout, jak to prelozit.

Napriklad v tom odkazu na Fibonacciho posloupnost, standardne rekurzivne pocitat podle vzorce x(n) = x(n-1) + x(n-2) je nesmysl, ale prekladac muze teoreticky implementovat memoizaci (tedy zapamatovani si predchozich vypocitanych hodnot funkce), a to tento vypocet dost urychli.

zadny prekladac v tomhle pripade neimplementuje memoizaci sám od sebe.

[dsafasdfasdf]

ctenicko

http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf

[gll]

ctenicko

http://courses.csail.mit.edu/6.01/spring07/lectures/lecture4.pdf

dělají memoizaci explicitně. Nevyvrací to, co jsem napsal. Žádný překladač sám neuhádne, kterou funci se vyplatí memoizovat.

[Aoidhghean]

Tyto jazyky používají fixpoint calculus, jenž umožňuje zbavit se rekurze, načež je snazší provést automatickou optimalizaci. Akorát to pak chce typové proměnné, které v plné šíři má jen Haskell.

[Mirek Prýmek]

Možná by to stálo za to říct i úplně polopaticky: deklarativní programování (aspoň teoreticky nebo v ideálním případě) nepopisuje postup výpočtu, ale známá fakta a požadovaný výsledek. Takže skutečný postup výpočtu může být různý => různá komplexita.

V praxi to tak ale moc není - postup výpočtu bývá známý a někdy s ním programátor i chce počítat, chce ho {zne|vy}užít (viz Prolog a jeho znásilnění k imperativnímu programování).