Scheme snadno a rychle - 3. Vyhodnocovani (diskuse)

[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)