Názory k článku
Mercury: Abstrakce nad algoritmy

...asi se tak stalo proto, že typový systém Mercury nemá chybu....

Nebo prostě proto, že to nikoho nezaujalo. Tak to občas v životě chodí.

Mam takovy dotaz, sice se primo netyka Mercuryho, ale LISPu, nicmene tyto jazyky maji hodne spolecneho.

Tyka se to tail-recursion, ktera je take v clanku zminena. V temer kazdem clanku o LISPu autori pisou, ze nema cenu pouzivat smycky, vse se ma delat pomoci rekurze a o vlastni tvorbu smycky (pokud je to mozne) se postara tail-recursion.

Problem je, ze se uz nikde nepise, kdy se tail-recursion provede (tj. interpreter kod vlastne optimalizuje) a kdy ne. Take predpokladam, ze ne vsechny LISPy toto umi.

Jak je tomu u Mercuryho, ktere rekurzivni fce dovede "rozmotat" a u kterych selze?

Podle dokumentace je Mercury schopen rozmotat i nejméně dvojice predikátů, které se na konci volají navzájem. A dále má tušim optimalizaci v tom duchu, že predikát zůstává tail-rekurzivní i v případě, že striktně vzato po návratu z rekurzivního volání volá ještě jeden typový konstruktor (vyrobení seznamu z hlavy a ocasu, vyrobení n-tice, apod.).

Mercury má taky jeden option --warn-non-tail-recursive, který při kompilaci způsobí vypsání všech self-rekurzivních predikátů, které se nepodařilo rozmotat.

je to proste - tail recurcursion se provede v pripade, ze je zavolana ta sama funkce, ale s vysledkem tohoto volani se dal nepracuje - uvedu priklad ve Schemu (mam ho radsi) - dialekt LISPu

;; toto je faktorial klasickou rekurzi
(define (fact x)
(if (= x 0) 1 (* x (fact (- x 1)))))

;; koncovou rekurzi je to pak nejak takto
(define (fakt x)
(define (int-fact i result)
(if (> i x) result ;; vraci vysledek
(int-fact (+ i 1) (* result i))))) ;; koncova rekurze
(int-fact 1 1))

doufam, ze jde videt ze v tom druhem pripade int-fact nikde nepracuje se svym vysledkem a uklada si ho do parametru result

Ve Scheme se provede tail-call pri volani kazde funkce, pokud je dane volani v tail-pozici - nemusi se jednat o rekurzivni volani te same funkce.

tail-recursion je pak specialni pripad pouziti tail-call pro rekurzi :-)

tail-pozice je definovana jednoduse - posledni vyraz v tele funkce je v tail pozici, then a else vetev ifu je ta tail-pozice, pokud cely if je v tail-pozici a podobne, detaily viz R5RS. V podstate jde o to, ze vysledek volani funkce se nepouzije dale jako argument pri volani dalsi funkce, ale vrati se.

no vicemene se shodujem - s vysledkem se proste dal nepracuje - popsal jsem to opravdu trochu zjednodusene

Mezi Scheme a Common Lispem je jeden dramaticky rozdil - standardni Lisp negarantuje optimalizaci tail-rekurze NIKDE. Bezne implementace Lispu ve vetsi ci mensi mire TCO podporuji, ale spolehnout se na to neda. Zapomente na rekurzi, pouzijte smycku.

Tvrzení, že v Lispu se nemají používat cykly, protože vše jde dělat rekurzí, je blábol. Tvrzení, že v Common Lispu se mají místo rekurze používat cykly, protože standard jazyka nepožaduje TRO, je blábol stejně tak.

V první řadě: Jeden z podstatných rozdílů mezi Mercury a Lispem je, že Mercury definuje určitý programovací styl, zatímco Lisp nechává v otázce stylu programátorovi naprostou volnost. Takže zatímco v Mercury je rekurze zcela přirozenou technikou, v Lispu použijete cyklus nebo rekurzi v závislosti na charakteru toho, co chcete vyjádřit. Někdy je lepší použít cyklus, někdy zase rekurzi a někdy záleží čistě na vkusu.

Co se týče TRO v Lispu, každý solidní překladač ji umí, takže není nejmenší důvod ji nepoužívat. Nemluvě o tom, že v mnoha případech se rekurze používá bez ohledu na to je-li tail či netail, prostě proto, že nad zpracovávanými daty není moc hluboká.

Kdyz uz tu je zminena ukazka v perlu, doplnim, ze do pythonu se taky dostaly kousky funkcionalniho programovani, soucet ctvercu by se dal udelat takto

import operator
seznam = [1,2,3]
ctverce = map(lambda x: x*x, seznam)
soucet_ctvercu = reduce(operator.add, ctverce)

v modulu operator jsou definovany funkcionalni verze beznych operatoru, lambda by pozornym ctenarum clanku mela byt jasna, map take, reduce je obdoba foldu.

Python nedovoluje v lambda funkci prirazeni.
pokus
map(lambda x: s += x**2, [1,2,3])
vyvola vyjimku
SyntaxError: invalid syntax
a tento pokus
map(lambda x: s = s + x**2, [1,2,3])
vyvola primo
SyntaxError: lambda cannot contain assignment

K map a reduce patri jeste filter, co dela je asi jasne:
filter(lambda x: x>3, [1,3,4,56,5,4,3,34])
vrati seznam
[4, 56, 5, 4, 34]

lambda vyrazy budou asi hodne popularni (taky se neni duvod divit) - nove by je mel mit i C# 2.0 (jako anonymni delegaty)

Co chcete demonstrovat nesmyslným použitím mapu? Map v Perlu je seznamový operátor, který má svůj smysl pouze v seznamovém a skalárním kontextu, tedy pokud vrací nějakou hodnotu. Stejně nesmyslně jste mohl použít grep.

Map jsem nejdříve užil "správně", ze seznamu seznam. Ani mne nenapadlo, že jsem tím následným nesprávným použitím ("pro čuňátka") vlastně na ten kontroverzní bod Perlu přímo ukázal: spoustu jazykových konstruktů můžete "zneužívat". Výhoda je jasná, máte větši prostor pro volbu, jak co napíšete. Nevýhoda je ale také jasná, můžete si navyknout psát programy špinavě, takže je nepřečtete ani sám. I v Perlu se dá samozřejmě programovat jasně a s čistou strukturou. Perl to však (díky své bohatosti a dovoleným vedlejším efektům) nepodněcuje. (Chápejte mne správně, Perl zbožňuji a píšu v něm stejně často jako v Mercury, vybírám si podle situace. Teprve díky Mercury však získávám větší cit pro to, co je "čuňárna", a co je "správné" použití nějakého jazykového prostředku. V Perlu ani dokumentaci tahle distinkce připomínána není, řekl bych spíše naopak.)

A novice asked the Master: ``Here is a programmer that never designs, documents or tests his programs. Yet all who know him consider him one of the best programmers in the world. Why is this?''

The Master replies: ``That programmer has mastered the Tao. He has gone beyond the need for design; he does not become angry when the system crashes, but accepts the universe without concern. He has gone beyond the need for documentation; he no longer cares if anyone else sees his code. He has gone beyond the need for testing; each of his programs are perfect within themselves, serene and elegant, their purpose self-evident. Truly, he has entered the mystery of Tao.''

Plánuje se taky, že to bude umět řešit halting problém?

Na tom intenzivně pracuju já osobně. Už jsem implementoval parsery zdrojáků všech podstatných programovacích jazyků a reprezentaci Turingova stroje. Teď už mi zbývá jen ten poslední krok, rozvinout výpočet stroje do stromu a podívat se, jestli je ten strom konečný. Myslím, že to už bude hračka. ;-)

V assembleru se dá taky for cyklus nahradit rekurzí - voláním: Mějme for cyklus, který přičítá jedno pole k druhému. V edi je adresa pole ke kterému se přičítá, v esi adresa které se přičítá, v ecx počet (ecx nesmí být 0):

aa: mov eax,[edi]
add eax,[esi]
mov [edi],eax
add edi,4
add esi,4
dec exc
jnz aa

Tak ten se přepíše na rekurzivní volání takhle
mov ecx,4
push ecx
aa: pop eax
mov eax,[edi]
add eax,[esi]
mov [edi],eax
add edi,4
add esi,4
dec ecx
jz bb
call aa
bb:

Na assembleru Z80 dokonce na to byla speciálni instrukce call nz :) Takže tam by se to dalo napsat (BC-počet, HL-adresa zdroje, DE-adres cíle)
push bc
aa: pop ix
ld a,[de]
add a,[hl]
ld [de],a
inc de
inc hl
dec bc (doufám že tahle instrukce ovlivňuje ten správnej flag - nechce se mi teď hrabat v datasheetu od Z80 ;-) )
call nz, aa

> dec bc (doufám že tahle instrukce ovlivňuje ten správnej flag - nechce se mi teď hrabat v datasheetu od Z80 ;-)

Ne, nutno pouzit klasicky trik
ld a,b
or c

(To je samozrejme totalne offtopic, jenom me zrovna tohle i po tech cca 8mi letech od meho posledniho kodu pro Z80 vytanulo na mysli, nektere postupy se holt zadrou pod kuzi hluboko... ;-))

Currying neni pojmenovan po matematikovi jmenem Howard Curry, ale po matematikovi jmenem Haskell Curry. Viz http://www.fact-index.com/h/ha/haskell_curry.html

Krom toho lambda kalkulus zavedli Alonzo Church and Stephen Kleene, nikoliv Haskell Curry. Viz http://www.fact-index.com/l/la/lambda_calculus.html

Slovni spojeni Howard Curry nejspise vzniklo omylem inspirovano Curry-Howardovym izomorfismem - viz http://www.fact-index.com/c/cu/curry_howard_isomorphism.html