Zásobník nadivoko

12.4.2007 22:15 | Přečteno: 1495× | Dev/Tech/Gnu |

Minule jsem tu psal o Pypy, implementaci Pythonu v jazyce samém, a o neuvěřitelné flexibilitě, kterou tato hračka nabízí.

Též jsem psal, že Pypy umí variaci na Stackless Python, tedy oprostění se od limitů systémového zásobníku. Rekurze omezená jen velikostí paměti je jen začátek. Program může explicitně manipulovat se svým zásobníkem. Je možné rozličným způsobem přepínat zásobníkové rámce funkcí atd. Následující kód mi hlava dost dlouho nebrala :

from pypy.rlib.rstack import yield_current_frame_to_caller

def g():
    print 2
    frametop_before_5 = yield_current_frame_to_caller()
    print 4
    frametop_before_7 = frametop_before_5.switch()
    print 6
    return frametop_before_7

def f():
    print 1
    frametop_before_4 = g()
    print 3
    frametop_before_6 = frametop_before_4.switch()
    print 5
    frametop_after_return = frametop_before_6.switch()
    print 7
    assert frametop_after_return is None


def entry_point(argv):
	print "ahoj"
	f()
	return 0
 
def target(*args):
	return entry_point, None

Tento program vypíše "ahoj" a pak čísla od 1 do 7 (uspořádaně). Jen je potřeba to přeložit Pypáckým translátorem do C. Ty výsledné divočiny se zásobníkym se provádějí až v céčku. Jenže v C byste si to asi netroufli naprogramovat, v Pythonu je to bezpečné .

$ python translate.py --stackless --batch targetstack.py
...
[translation] Done.
$ ./targetstack-c
ahoj
1
2
3
4
5
6
7

Přepínáním rámců to nekončí, je například možné vzít zásobník s běžícím výpočtem, zabalit a poslat dopočítat na jiný stroj - taková serializace říznutá kontinuací.        

Komentáře

[outsider]

Jsem jedinej, kdo netusi, k cemu by to mohlo byt dobry? Umi to aspon uvarit kafe?

[paskma]

No ty korutiny a zelená vlákna se hodí, když si chceš naprogramovat MMORPG (čti: statisíce vláken, které je potřeba migrovat mezi stroji).

[Hynek (Pichi) Vychodil]

Hmm a co takhle na to použít erlang a máš to odladěné bezmála 20 lety v průmyslovém nasazení.

[paskma]

Jo, erlang je sice robustní a masivní paralelismus zvládající, ale Python má tu výhodu, že je to obyčejný imperativní jazyk.

[Hynek (Pichi) Vychodil]

... ale Python má tu výhodu, že je to obyčejný imperativní jazyk.

A je to skutečně výhoda? V tom vidím jedinou výhodu, umí v tom kódit každej jouda.

[paskma]

V podstatě jo . Znám spousty chytrých lidí, co nemají s Pythonem problém, ale o Erlangu v životě neslyšeli. Ne že by se chytří lidi nedovedli Erlang naučit, ale zkus si podat inzerát, že hledáš makáče na Erlang...

[Ladicek]

No a pak existujou lidi jako valeon )

[podlesh]

Ty děláš něco s MMORPG v takovém měřítku?

[paskma]

Nop. Já se snažím vyrobit model-checker

[Ladicek]

Nad tímhle kódem začínám chápat, proč někteří lidé považují texty markýze de Sade za umění…

[paskma]

Tak to si ještě počkej. Příště napíšu o fork() na úrovni Pythoňáckých korutin. S tím pak jde dělat takový nechutný backtracking, že si člověk připadá jako v Prologu.

[Messa]

No a odkaz na vygenerovaný Céčkový zdroják?

[paskma]

Céčkový zdroják nic moc, je to stavový automat vygenerovaný z grafové reprezentace...

long pypy_g_slp_entry_point(struct pypy_list0 *l_argv_0) {
        bool_t l_v12; bool_t l_v16; bool_t l_v6; long l_v17; long l_v18;
        long l_v4; struct pypy_object0 *l_v3;
        struct pypy_object_vtable0 *l_v15; struct pypy_object_vtable0 *l_v2;
        struct pypy_object_vtable0 *l_v5;

    block0:
        l_v4 = pypy_g_entry_point(l_argv_0);
        l_v5 = (&pypy_g_ExcData)->ed_exc_type;
        l_v6 = (l_v5 == NULL);
        if (!l_v6) {
                goto block3;
        }
        goto block1;

    block1:
        /* kept alive: l_argv_0 */ ;
        l_v18 = l_v4;
        goto block2;

    block2:
        RPY_DEBUG_RETURN();
        return l_v18;

    block3:
        l_v3 = (&pypy_g_ExcData)->ed_exc_value;
        l_v2 = (&pypy_g_ExcData)->ed_exc_type;
        (&pypy_g_ExcData)->ed_exc_value = ((struct pypy_object0 *) NULL);
        (&pypy_g_ExcData)->ed_exc_type = ((struct pypy_object_vtable0 *) NULL);
        /* kept alive: l_v3 */ ;
        /* kept alive: l_argv_0 */ ;

[paskma]

BTW: Jediný důvod, proč je v Adě goto je ten, že by ho mohli ocenit generátory kódu

[Tom.š Ze.le.in]

Výborně, je to jistě krok správným směrem. I když mi přijde zbytečné mluvit pořád o tom zásobníku. Pokud to má být konsistentní, tak by to mělo fungovat i když se f i g inlinují (i když nevím, jestli to v Pythonu jde) a žádný zásobník ve hře není (a, popravdě řečeno, bych od "sufficiently advanced" kompilátoru očekával, že to vystreamlinuje do print 1...print 7 během kompilace). Nebo to je opravdu implementačně závislé na manipulace se zásobníkem v C a s "pravými" kontinuacemi to nepracuje?

[Kyosuke]

Hmm, a co aspoň takhle ocenit, že si aspoň někdo po všech těch letech (kromě smalltalkerů a lisperů, samozřejmě ) všiml, že není třeba se omezovat na lineární zásobník?

(Mimochodem, to mi připomíná...prosím Tě, jak že to děláš s Lispem ve Vimu? Pořád nějak nemůžu přijít na to, jak lidsky hackovat závorky v tom modálním zázraku. )

[Tom.š Ze.le.in]

Vždyť jsem to v první větě ocenil. A v seznamu chybí forthisti - ti se omezují na dva zásobníky :)

Asi nadešel čas na coming out. Pro psaní v lispu jsem přešel na emacs... po tuctu let s vimem. Pořád to ještě bolí, a ostatní věci dělám ve vimu, ale je to schizofrenní. Slime je slime. Zkoušel jsem kde co - konfiguraci vimu, propojení clispu a vimu přes readline mapování kláves, různé doplňky (vim+ecl a slim-vim), viper, ale prostě to není ono.

[Kyosuke]

Ksakru, a já se těšil, že mě konečně naučiš, jak že to efektivně děláš s Lispem ve Vimu a ono takhle. Možná by to chtělo, až bude použitelný Climacs, v něm reimplementovat Vim - ale celý, ne jen nějakou náhražku. Já se přiznávám, že jsem taky schizofrenní. Nu což, co se dá dělat.

[deda.jabko]

huh, pekna prasarna... ale dokazu ocenit ty kouzla... i kdyz fakt se s tim lip pracuje, kdyz je to prirozeny konstrukt jazyka, nez kdyz se explicitne hrabe na zasobnik.... btw. v jave 7 se uvazuje o implementaci kontinuaci... takze takoveto pokusy na realnych jazycich nejsou vubec od cesty....

[Hynek (Pichi) Vychodil]

Teda, když to srovnám s tímhle v erlangu:

-module(switch).
-export([start/0]).
-define(print(X), io:format("~p~n", [X])).
-define(switch(X), X ! switch, receive switch -> ok end).

g() ->
	?print(2),
	F = receive PID when is_pid(PID) -> PID end,
	?switch(F),
	?print(4),
	?switch(F),
	?print(6),
	?switch(F).

f() ->
	?print(1),
	G = spawn(fun g/0), G ! self(),
	receive switch -> ok end,
	?print(3),
	?switch(G),
	?print(5),
	?switch(G),
	?print(7),
	G ! switch,
	ok.

start() ->
	io:format("ahoj~n"),
	f().

Tak je to celkem nic moc ten python a to se to ještě musí přeložit a spustit jinak než obvykle, rozuměj taky zkompilovat. Přičemž zkompilovat v erlangu znamená:

> c(switch).
{ok,switch}
> switch:start().
ahoj
1
2
3
4
5
6
7
ok
>

[paskma]

Hm, pěkné. Ale já jsem neříkal, že Python přináší něco unikárního. Kontinuace jsou ve funkcionálních jazycích normálka. Akorád že tohle je skoro-mainstreamový Python a navíc to jde přeložit do céčka.

[Hynek (Pichi) Vychodil]

... Kontinuace jsou ve funkcionálních jazycích normálka. ...

Na tom je vtipné, že v erlnagu kontinuace nejsou. Krom toho, kdykoliv narazím na problém s kontinuací, vždy bych se zamyslel, jestli to není chyba designu a nakonec je tu vždy možnost řešit to jako v erlangu thready, ale to musí být aspoň tak tenké jako v erlangu. V podstatě je to takový syntaktický cukr, akorát, že zatraceně sladký a i výkonostně jsou kontinuace trochu jinde než thready byť erlangovsky výkonné.

[Ondrej 'SanTiago' Zajicek]

No a pomoci call-with-current-continuation se da docilit toho sameho a navic mnohem elegantnejsim zpusobem.