Scheme snadno a rychle - 3. Vyhodnocovani

14.3.2007 23:43 | Přečteno: 1579× | Programování | poslední úprava: 14.3.2007 23:44

potom co jsme poresili gramatiky a takove ty veci a mame hezky derivacni strom. muzeme prejit k vyhodnocovani, resp. k samotnemu vypoctu. takze vsechno doted byly jenom takove pomocne plky a ted si drzte klobouky, protoze jedeme z kopce

3.1. vyhodnoceni symbolu

jak jsem psal v predchozi kapitole, po rozparsovani mame jenom nejaky seznam, ktery obsahuje symboly po pripade nejake dalsi seznamy symbolu. proste nic uzasneho. k jednotlivym symbolum musime priradit nejake skutecne hodnoty. to se ve schemu deje pomoci tzv. prostredi (nekde jsem videl oznaceni ramce), coz jsou zkratka a dobre asociativni pole, kde jako klic slouzi symbol a jako hodnota realne prirazena hodnota. prostredi maji jeste jednu vlastnost -- jsou hierarchicky usporadany. pokud se hledany symbol v danem prostredi nenachazi prohleda se nadrazene a pokud ani tam neni, je bud vyhodnocen na svou prirozenou vazbu (napriklad cislo se vyhodnoti na cislo) a pokud takovou vazbu nema, je vracena chyba.

v praxi se osvedcilo mit dva typy prostredi, jeden typ schopny pojmout velke pocty symbolu (radove desitky, stovky, tisice) a druhy zase male (radove jednotky). ty velke jsou urceny pro pocatecni prostredi a ty mensi pro prostredi jednotlivych funkci. v praxi se pak pro prostredi s velkym poctem symbolu pouzivaji hash-tabulky a pro male bud spojove seznamy nebo pole. (zajimavych vysledku jde dosahnout v obou pripadech i pomoci binarnich stromu, s tim ze pro velka prostredi je potreba je nejakym zpusobem, nejlepe narazove vyvazovat)

z r5rs plyne, ze az na pocatecni prostredi, maji jednotliva prostredi konstantni velikost. ale rada implementaci to umi prehlizet.

3.2. vyhodnoceni seznamu vychodilovym modelem

otazka zni: jak vyhodnotit treba? (+ 1 (+ 2 3))

mohl bych zde uvest trivialni model na bazi stromove rekurze, kdy se overi, jestli je na vstupu seznam, tak se vyhodnoti prvni prvek a kdyz je to funkce tak se vyhodnoti i ostatni casti seznamu, ktere se funkci predaji jako parametry a vraci se vysledek. ale to sebou nese neprijemne dusledky typu, jak resit call/cc nebo koncova volani.

existuje rada sofistikovanych vyhodnocovacich modelu, at uz na bazi registrovych ci zasobnikovych procesoru. ja jsem prevzal model doc. vychodila, ktery tento model prednasi prvakum na katedre informatiky univerzity palackeho v olomouci a mirne jej modifikoval. (ty odkazy jsou proto, ze jsem slibil, nejake "kredity" pro katedru ;-]) jedna se o zasobnikovy model, pravda neni z nejrychlejsich, ale ma nektere prijemne rysy, napr. snadne rozsireni na implicitne paralelni vyhodnocovani, ale o tom az nekdy jindy, kdyby vas to zajimalo.

takze predstavme si vyhodnocovani jako virtualni procesor, ktery ma dva zasobniky -- jeden na zpracovani ukolu (exct) a druhy na ukladani mezivysledku (rslt). na zasobnik s ukoly (execution stack) se budou ukladat jednotlive instrukce, vcetne argumentu a prostredi, ve kterem ma byt dana instrukce vyhodnocena. v momente kdy zasobnik s ukoly je prazdny. mel by byt na zasobniku s mezivysledky prave jeden prvek. ktery je vysledkem.

pro zacatek zavedeme nasledujici instrukce:

3.2.1 vyhodnoceni vyrazu

3.2.1.1. instrukce eval

[eval arg env (tail-priznak)] -- po jejim odebrani z vrcholu zasobniku se vyhodnoti argument arg v danem prostredi. tzn. pokud je argument symbol. vyhodnoti se na vazbu v danem prostredi a hodnota se zapise na zasobnik s vysledky. (tail-priznak slouzi k vyhodnoceni vyrazu v tail-pozici, coz zatim nebudeme resit a budeme jej s naprostym klidem ignorovat) pokud je argument arg seznam, nachysta se vyhodnoceni prvniho prvku a dalsi casti seznamu cakaji na zpracovani pomoci instrukce "inspect".

napr. ("|" znaci dno zasobniku)

exct: [eval #<symbol 158> #env] |
rslt: |
=>
exct: |
rslt: #<int 158>

nebo

exct: [eval (+ 1 2) #env] |
rslt: |
=>
exct: [eval #<symbol +> #env] [inspect (1 2) #env] |
rslt: |

3.2.1.2. instrukce inspect

pokud je na vrcholu zasobniku s mezivysledky (rslt) funkce, provede se vyhodnoceni jednotlivych argumentu a aplikace jako argument dane funkce. (specialni formy se vyhodnocuji trochu jinak, ale o tom az v pristi kapitole)

napr.

exct: [eval #<symbol +> #env] [inspect (1 2) #env] |
rslt: |
=>
exct: [inspect (1 2) #env] |
rslt: #<func +> |
=>
exct: [eval #<symbol 1> #env] [eval #<symbol 2> #env] [run 2 #env] |
rslt: #<func +> |
=>....=>
exct: [run 2 #env] |
rslt: #<int 2> #<int 1> #<func +> |

3.2.1.3. instrukce run

odebere z vrcholu zasobniku dany pocet prvku a aplikuje je na funkci na vrcholu, kterou taky odebere. vysledek volani pak umisti opet na zasobnik.

napr.

exct: [run 2 #env] |
rslt: #<int 2> #<int 1> #<func +> |
=>
exct: |
rslt: #<int 3> |

3.2.2. implementacni poznamky

no, v predchozi casti, operuju s hodnotou typu func, kterou jsem zatim nikde nedefinoval. jedna se o ukazatel na funkci, ktera prijima pocet parametru a po le parametru a vysledek operace vraci. zavedeme tedy typ scm_func jako ukazatel na funkci.

typedef struct scm_value * (*scm_func)(int cnt, struct scm_value **);

a union v scm_value rozsirime o tento typ. jako argument by sel pouzit i jeden seznam -- na druhou stranu jsem si rikal, ze pristup k poli bude rychlejsi, navic aserce na pocet vstupu muze byt dost casta, tak se oplati mit predem spocitany pocet argumentu pred volanim funkce.

dalsi veci, ktera vyrazne zrychli beh, je agresivni inlinovani vetsiny funkci. operace se zasobnikem (fyzickeho procesoru) jsou sice rychle, ale kdyz se vo laji mooooockrat jde to poznat.

samozrejme kompilace s -O3 udela taky hodne.

3.3. specialni formy

u beznych funkci se predpoklada, ze argumnety budou vyhodnocovany naraz v libovolnem poradi i kdyz r5rs rika, ze by to melo byt v jednom nebo druhem smeru a poporade. u specialnich forem uz to poradi specifikovane je a treba v pripade kosntrukce (define foo bar) by vyhodnoceni hodnoty foo vedlo k chybe.

3.3.1. ukazka vyhodnoceni nekterych spec. forem.

3.3.1.1. spec. forma if

exct: [eval (if condition result1 result2) #env] |
rslt: |
=>
exct: [inspect (condition result1 result2) #env] |
rslt: #<specform if> |
=>
exct: [eval condition #env] [if #env] |
rslt: result1 result2 |
=>
exct: [if #env] |
rslt: #<bool #t> result1 result2 |
=>
exct: [eval result1 #env] |
rslt: |

3.3.1.2. spec. forma define

exct: [eval (define foo bar) #env] |
rslt: |
=>
exct: [inspect (foo bar) #env] |
rslt: #<specform define> |
=>
exct: [eval bar #env] [define #env] |
rstl: #<symbol foo> |
=>
exct: [define #env] |
rslt: bar #<symbol foo> |
=>
exct: |
rslt: bar

3.3.2. a dalsi

dalsi specialni formy se daji definovat obdobne, ale to je mimo rozsah tohoto textu. asi nikomu neuniklo, ze sice umime vyhodnocovat spoustu vyrazu, ale diky chybejici abstrakci ne vsechny, ale o dalsich hezkych konstruktech jako lambda nebo call/cc bude rec v dalsi kapitole.

zaverem, doufam ze to bylo aspon trochu srozumitelne a nekdo to docetl az na konec.        

Komentáře

[Tom.š Ze.le.in]

Hezký, ale bez těch kontinuací to prostě není ono.

Asi bych neprovokoval kdybych před měsícem nečetl zhruba totéž (a možná lépe) v PAIP :)

[deda.jabko]

diky, ale myslim, ze nez bych presel ke kontinuacim, tak by bylo lepsi vysvetlit jeste implementaci alespon lambda vyrazu ;-]

nicmene ta knizka vypada fakt dobre a uderne (tj. nechtel bych s ni byt uderen) a nepochybuju, ze tam to bude vysvetlene lip... prece jen je to knizka, kterou autor pripravoval delsi dobu a to co tady prezentuju je vybor z mojich poznamek k diplomce.

[Tom.š Ze.le.in]

Prostředí jsou hierarchicky uspořádány - pokud použiju pro lexikální proměnné něco jako alist a povolím opakování klíče, tak mi stačí jedno takové prostředí, ne? Případný overhead vyhledávání lexikální proměnné podle symbolu se při kompilaci stejně ztratí.

"pokud ani tam neni, je bud vyhodnocen na svou prirozenou vazbu (napriklad cislo se vyhodnoti na cislo)" - to jako že ve Scheme můžu převázat i čísla? Myslil jsem, že se vyhledávají jen symboly...

Jinak ta kniha se mi docela líbila, je psaná v lehce archaickém CL, ale ve dvou kapitolách se právě implementuje Scheme (jednou jako interpreter, podruhé jako kompilátor). Ta implementace v CL je asi snazší než v C, aspoň parsování moc místa věnováno nebylo :)

[deda.jabko]

s tim alistem (pokud tim myslite "asociativni seznam") nevim, nevim... v pripade dynamickeho rozsahu platnosti promenych by to asi slo pouzit, ale v pripade lexikalniho by to asi zlobilo zejmena s uzavery, protoze kazdy lambda vyraz musi mit odkaz na prostredi sveho vzniku.

u tech cisel jsem to formuloval trochu nestastne, aby to bylo koser, melo by tam byt "symbol cisla se vyhodnoti na prislusne cislo", jinak pokud se zarazite nad obratem (define 0 1) - nektere interpretry to umi (je v tom proste ta elegance, ze nic neni absolutni), ale je fakt, ze vetsina interpretru tento konstrukt zavrhuje, protoze to ma sve konsekvence na vykon aplikace... nicmene podivam se jeste do r5rs jak to ma byt doopravdy.

s tou knihou jste me docela navnadil... zacinam zvazovat, ze bych po 5 letech zjistil, kde je knihovna...

[Tom.š Ze.le.in]

Proč by to nefungovalo lexikálně? Když interpretuji třeba let, tak pro výrazy uvnitř vazby přidám do prostředí na začátek nové proměnné - a ty jsou pak soukromé pro daný lexikální rozsah, vnější prostředí je nevidí (vzhledem k tomu že má odkaz na původní seznam, tedy pouze nějaký konec nového).

[deda.jabko]

a co v pripade?

(define (make-closure x)
        (lambda () (set! x (+ x 1)) x))
(define closure1 (make-closure 10))
(define closure2 (make-closure 20))

nedokazu si to nejak moc dobre pomoci toho listu predstavit. minimalne by to mel byt strom...

[deda.jabko]

kdyz nad tim tak premyslim, tak by to v tomto pripade mel byt dokonce obecny orientovany graf

[Tom.š Ze.le.in]

Pořád mi přijde, že v tom nevidím problém:

(eval '(make-closure 10) env) =>
  (eval '(lambda () (set! x (+ x 1)) x)) (cons '(x . 10) env))
(eval '(make-closure 20) env) =>
  (eval '(lambda () (set! x (+ x 1)) x)) (cons '(x . 20) env))

Každá closure má svoji vlastní verzi x.

Tedy pro interpreter, pro kompilátor by bylo potřeba mít v alistu ne hodnotu, ale nějaký odkaz na skutečné místo kde ta data budou.

Co přehlížím?

[deda.jabko]

spis by me zajimalo, jak ten seznam bude vypadat po zavolani

(define closure1 (make-closure 10))
(define closure2 (make-closure 20))

diky lexikalnimu rozsahu musi byt prostredi z (make-closure) zachovane... a nemuzu prijit na to, jak by v tom seznamu byly usporadane, aby fungovalo vyhledavani... nicmene toto by fungovalo moc dobre pri dynamickem rozsahu...

[Tom.š Ze.le.in]

Po zavolání obou define bude prostředí stejné jako před ním (pokud tedy předpokládám, že obě define vážou do globálních proměnných, které jsou mimo).

Při vyhodnocování lambdy se musí samozřejmě uložit do výsledného uzávěru i stav prostředí v místě, kde se lambda nachází - tedy nakonec bude prostředí env stejné jako předtím, avšak v každém uzávěru bude odkaz na (cons '(x 10/20) env).

No, vlastně je výsledné prostředí, nazíráno globálně, opravdu strom. :) Ale v každém určitém místě je z něj vidět jen seznam.

[deda.jabko]

vyborne, takze vlastne oba dva myslime totez, ale trosku jinak to popisujeme a implementujeme. hierarchicke usporadani prostredi je opravdu ten seznam symbolu o kterem tady delsi dobu diskutujeme ;-] (je to spravne, dukaz z obou stran overen ;])

presto bych se dal radsi drzel terminu prostredi a jako takovy jej samostatne implementoval... kod bude citelnejsi... a ted nevim do jake miry se bude snaz implementovat samotne volani, uzavery a podobne veci... tak me napada jedna vec... pokud budou vsechna prostredi jeden velky seznam, nedovoli to ukladat symboly do ruznych datovych struktur... a co jsem si tak hral s optimalizacemi, tak pokud pocatecni prostredi (cca 30 polozek) je implementovane jako spojovy seznam misto hash tabulky ma to docela vyznamne dusledky na vykon.

[Tom.š Ze.le.in]

Dobře :) Rozdíl jsem viděl v tom, že při evaluaci prohledávám pouze dvě prostředí - jedno lexikální (které je při diskutované implementaci z pohledu evaluátoru vždy seznam), a jedno počáteční (hash nebo cokoliv jiného), a nějakou jinou hierarchičností se v evaluátoru nezabývám.

Jinak počáteční prostředí jako seznam opravdu není vhodné - těch položek tam bude skoro v každém rozumném případě mnohem více než třicet (funkce...). Ale pro lexikální proměnné to obyčejně není tak zlé (a pokud je, tak je možná stejně načase kompilovat).

Snad se konečně přibližuju terminologií - českou jakožto správný amatér neznám, a i tu anglickou spíš od CL než od scheme.

[deda.jabko]

dival jsem se jeste na ty promenne a r5rs moc jasne o oddeleni semantiky a syntaxe cisel nemluvi (konkretne vubec). pro zajimavost jsem si zkusil presunout interpretaci cisel uz do parseru a zlepseni bylo jenom 10%. tech 10% stoji za to ozelet svet, kde se snadno kazda nula muze stat jednickou ;-]

[Tom.š Ze.le.in]

A #f můžu taky převázat?

Jinak u těch čísel bude asi rozdíl ve výkonnosti tím větší, čím je efektivnější implementace - pokud budu mít kompilátor, který pozná číslo a rovnou ho jako číslo uloží, tak by to měl být větší rozdíl než u interpreteru. Pokud bude umět kompilátor constant folding, tak to zvedne rozdíl. Pokud kompilátor bude umět nahradit (= 0 ...) specifickou instrukcí. Pokud bude umět provádět loop unrolling (dobře, ve scheme nějakou rekurzivní variantu). Pokud bude provádět partial evaluation. Atp. U prostého evaluátoru se ten rozdíl ztratí, ale u "průmyslového" překladače bych to viděl jako zásadní. (I když to je možná rozdíl v důrazu mezi Scheme a CL - elegance a obecnost vs. efektivita. Portable program v CL třeba nesmí předefinovat ani standardní fuknce, a implementace mají právo na to spoléhat)

[deda.jabko]

proc ne? zijeme ve svobedne zemi! ;-] a ten rozdil mezi interpretrem scheme a kompilatorem cl je fakt znacny. kompilator cl jde pouzit i na skutecne nasazeni (kdyz clovek zkousne, ze vypada jak exot) interpretr schemu je zase genialni na hrani si s novymi prvky jazyka nebo vyhodnocovani, protoze se fakt vleze na par stovek radku.

[deda.jabko]

jeste jsem si uvedomil, ze moznost prevazani #f a #t vlastne odpovida i pojeti logiky, kdy se jedna o pouhe symboly (syntakticke struktury), ktere je nutne ohodnotit.... v praxi to zadne pouziti moc nema... ale nekdo mozna je schopen ocenit, ze se jazyk podoba vic teorii nez realnemu poznani.... ;-]

[Tom.š Ze.le.in]

Jinak pro úplnost asi klasická kniha ohledně implementace Scheme je Lisp in Small Pieces , ale tu jsem bohužel nečetl (i když jsem ji tu v Londýně v knihkupectví ještě viděl)