Fórum Root.cz

Hlavní témata => Vývoj => Téma založeno: fortran1986 07. 05. 2019, 22:27:10

Název: Jak funguje Call/CC?
Přispěvatel: fortran1986 07. 05. 2019, 22:27:10
Prosím Vás môžete pre obyčajného laika vysvetliť ako funguje Call/CC? (Call with Current Continuation) pozrel som si pár príkladov, ale nejako sa v tom začínam strácať...

Moj mozog sa pri snahe pochopiť to zacyklí.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Idris 08. 05. 2019, 01:34:09
ako funguje Call/CC? (Call with Current Continuation)
Začal bych s tím, co je kontinuace a jak se řetězí. CC je pak jen speciální případ. Kontinuace je jednoduše funkce (například λ-výraz) vyššího řádu, která dostane funkci a předá jí zapouzdřenou hodnotu.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 08. 05. 2019, 11:34:10
V Ruby muzete Call/CC ignorovat. Je to prekonany koncept.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 08. 05. 2019, 11:54:25
ako funguje Call/CC? (Call with Current Continuation)
Začal bych s tím, co je kontinuace a jak se řetězí. CC je pak jen speciální případ. Kontinuace je jednoduše funkce (například λ-výraz) vyššího řádu, která dostane funkci a předá jí zapouzdřenou hodnotu.

kontinuace neni funkce. Kontinuace je stav programu. Mozna jsi myslel call/cc, ale i potom je tve vysvetleni nic nerikajici. Nenapsal jsi, co ta funkce dela.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Idris 08. 05. 2019, 13:40:41
ako funguje Call/CC? (Call with Current Continuation)
Začal bych s tím, co je kontinuace a jak se řetězí. CC je pak jen speciální případ. Kontinuace je jednoduše funkce (například λ-výraz) vyššího řádu, která dostane funkci a předá jí zapouzdřenou hodnotu.

kontinuace neni funkce. Kontinuace je stav programu. Mozna jsi myslel call/cc, ale i potom je tve vysvetleni nic nerikajici. Nenapsal jsi, co ta funkce dela.
Přečti si definici, třeba na Wikipedii.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 08. 05. 2019, 14:22:55
ako funguje Call/CC? (Call with Current Continuation)
Začal bych s tím, co je kontinuace a jak se řetězí. CC je pak jen speciální případ. Kontinuace je jednoduše funkce (například λ-výraz) vyššího řádu, která dostane funkci a předá jí zapouzdřenou hodnotu.

kontinuace neni funkce. Kontinuace je stav programu. Mozna jsi myslel call/cc, ale i potom je tve vysvetleni nic nerikajici. Nenapsal jsi, co ta funkce dela.
Přečti si definici, třeba na Wikipedii.

a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution

https://en.wikipedia.org/wiki/Continuation

kontinuace je objekt reprezentujici navesti skoku vcetne stavu programu v dobe sveho vythoreni.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Idris 08. 05. 2019, 14:25:39
ako funguje Call/CC? (Call with Current Continuation)
Začal bych s tím, co je kontinuace a jak se řetězí. CC je pak jen speciální případ. Kontinuace je jednoduše funkce (například λ-výraz) vyššího řádu, která dostane funkci a předá jí zapouzdřenou hodnotu.

kontinuace neni funkce. Kontinuace je stav programu. Mozna jsi myslel call/cc, ale i potom je tve vysvetleni nic nerikajici. Nenapsal jsi, co ta funkce dela.
Přečti si definici, třeba na Wikipedii.

a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution

https://en.wikipedia.org/wiki/Continuation
To je implementace, ne definice. Ale třeba to tazateli taky pomůže.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 08. 05. 2019, 14:29:13
To je implementace, ne definice. Ale třeba to tazateli taky pomůže.

to je definice.
Název: Re:Jak funguje Call/CC?
Přispěvatel: fortran1986 09. 05. 2019, 09:23:44
Včera som som si to testoval, prečítal som o tom pár článkov a skúšal som si príklady. A potom som si týmto spôsobom sám vyskúšal naimplementovať funkcie map a filter aby sa mi to trochu dostalo do krvi:

https://pastebin.com/XWvc8ZgC

Teórii stále úplne na 100% nechápem (je to náročné na predstavivosť, kúpim si dáku knihu o funkcionálnom programovaní), ale už som viac v obraze... viem ako sa to zapisuje a tiež som pochopil aké to prináša výhody. A načo to využijem

Napríklad skladanie stromu pri rekurzívnom prechádzaní listu to značne uľahčuje.

Takže teraz už tomu rozumiem natoľko že to použil v jednom parseri s kontinuáciami pri rekurzii sa jedho kód veľmi zjednodušil.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 09. 05. 2019, 10:25:20
Včera som som si to testoval, prečítal som o tom pár článkov a skúšal som si príklady. A potom som si týmto spôsobom sám vyskúšal naimplementovať funkcie map a filter aby sa mi to trochu dostalo do krvi:

https://pastebin.com/XWvc8ZgC

Teórii stále úplne na 100% nechápem (je to náročné na predstavivosť, kúpim si dáku knihu o funkcionálnom programovaní), ale už som viac v obraze... viem ako sa to zapisuje a tiež som pochopil aké to prináša výhody. A načo to využijem

Napríklad skladanie stromu pri rekurzívnom prechádzaní listu to značne uľahčuje.

Takže teraz už tomu rozumiem natoľko že to použil v jednom parseri s kontinuáciami pri rekurzii sa jedho kód veľmi zjednodušil.

a kde tam pouzivate call/cc? Vy jen definujete modul, ktery se tak jmenuje.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Idris 09. 05. 2019, 13:58:29
Včera som som si to testoval, prečítal som o tom pár článkov a skúšal som si príklady. A potom som si týmto spôsobom sám vyskúšal naimplementovať funkcie map a filter aby sa mi to trochu dostalo do krvi:

https://pastebin.com/XWvc8ZgC

Teórii stále úplne na 100% nechápem (je to náročné na predstavivosť, kúpim si dáku knihu o funkcionálnom programovaní), ale už som viac v obraze... viem ako sa to zapisuje a tiež som pochopil aké to prináša výhody. A načo to využijem

Napríklad skladanie stromu pri rekurzívnom prechádzaní listu to značne uľahčuje.

Takže teraz už tomu rozumiem natoľko že to použil v jednom parseri s kontinuáciami pri rekurzii sa jedho kód veľmi zjednodušil.
Fakt bych začal s kontinuacemi bez toho “current”. Je to podrobně vysvětlené v textech o Haskellu. Kontinuace je prostě funkce typu (A->R)->R, která “vrací” hodnotu zavoláním funkce. Toto je klasická funkcionální definice (pozor, gill píše blbosti). Nejjednodušší případ je převod konstanty na kontinuaci: λx.λf.f(x) - této operaci, která zapouzdří hodnotu do kontinuace, se někdy říká unit. Protože kontinuace je funkce, zapouzdřená hodnota se z ní získá funkční aplikací, kdy se jí předá funkce typu A->R. Výhodou kontinuací je, že se dají skládat, dvě obecně různé kontinuace jsou sice funkce, ale s nekompatibilními typy, takže nejde přímo zavolat jedna na výsledek druhé, ale jdou spojit do jedné funkce tak, aby taky byla kontinuací.

Call/cc je jen zvláštní případ, kdy ona aplikace na “návratovou” hodnotu způsobí návrat výpočtu za volání call/cc, klidně i vícekrát, čímž se dosahuje nedeterminismu. Například operátor amb se takto často vnitřně implementuje.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 09. 05. 2019, 14:52:07
Muzes nam Idrisi ukazat priklad pouziti, kdy je to k necemu uzitecne?
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 09. 05. 2019, 14:54:33
V Ruby muzete Call/CC ignorovat. Je to prekonany koncept.
Ruby muzete ignorovat. Je to prekonany koncept.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 09. 05. 2019, 15:20:43
V Ruby muzete Call/CC ignorovat. Je to prekonany koncept.
Ruby muzete ignorovat. Je to prekonany koncept.

to je mozne, ale i v prekonanem (podle koho?) Ruby lze pouziti call/cc nahradit modernejsimi konstrukty.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 09. 05. 2019, 15:44:31
V cem dnes programuji hipsteri?
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 09. 05. 2019, 15:48:47
Kontinuace je prostě funkce typu (A->R)->R, která “vrací” hodnotu zavoláním funkce.
Nejsem si úplně jistej, jestli je na tomhle významu všeobecná shoda (nebo jinak: jestli tohle není příliš úzký význam, někdo by mohl asi říct i "implementace").

Třeba tady http://erlang.org/doc/man/mnesia.html#select-4 se slovo "continuation" používá prostě pro nějakou (neznámou) strukturu (ne nutně funkci), která umožňuje pokračovat v činnosti kdykoli jindy - v tomhle případě pokračovat v paginaci záznamů z DB.

Důkaz, že to skutečně není funkce:
Kód: [Vybrat]
$ iex
Erlang/OTP 21 [erts-10.0] [source] [64-bit] [smp:4:4] [ds:4:4:10] [async-threads:1] [hipe]

Interactive Elixir (1.6.6) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> :mnesia.create_schema([Node.self])
:ok
iex(2)> :mnesia.start()
:ok
iex(3)> :mnesia.create_table(:test,[])
{:atomic, :ok}
iex(4)> :mnesia.dirty_write({:test, :a, 1})
:ok
iex(5)> :mnesia.dirty_write({:test, :b, 2})
:ok
iex(6)> :mnesia.dirty_match_object({:test, :_, :_})
[{:test, :b, 2}, {:test, :a, 1}]
iex(7)> :mnesia.transaction(fn ->
...(7)>   {rec, cont} = :mnesia.select(:test, [{:_,[],[:'$_']}], 1, :read)
...(7)>   IO.puts("rec1 = #{inspect rec}")
...(7)>   IO.puts("cont1 = #{inspect cont}")
...(7)>   {rec, cont} = :mnesia.select(cont)
...(7)>   IO.puts("rec2 = #{inspect rec}")
...(7)>   IO.puts("cont2 = #{inspect cont}")
...(7)> end)
rec1 = [{:test, :a, 1}]
cont1 = {:mnesia_select, :test, {:tid, 4, #PID<0.100.0>}, :nonode@nohost, :ram_copies, {#Reference<0.3882805345.2162294785.166659>, 161, 1, #Reference<0.3882805345.2162294785.166789>, [], 0}, [], :undefined, :undefined, [{:_, [], [:"$_"]}]}
rec2 = [{:test, :b, 2}]
cont2 = {:mnesia_select, :test, {:tid, 4, #PID<0.100.0>}, :nonode@nohost, :ram_copies, {#Reference<0.3882805345.2162294785.166659>, 162, 1, #Reference<0.3882805345.2162294785.166789>, [], 0}, [], :undefined, :undefined, [{:_, [], [:"$_"]}]}
{:atomic, :ok}
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 09. 05. 2019, 15:58:50
...a ještě ilustrace toho, že kontinuace umožňuje se do jí reifikovaného stavu vrátit:
Kód: [Vybrat]
iex(28)> :mnesia.transaction(fn ->
...(28)>   {rec, cont1} = :mnesia.select(:test, [{:_,[],[:'$_']}], 1, :read)
...(28)>   IO.puts("rec1 = #{inspect rec}")
...(28)>   IO.puts("cont1 = #{inspect cont1}")
...(28)>   {rec, cont2} = :mnesia.select(cont1)
...(28)>   IO.puts("rec2 = #{inspect rec}")
...(28)>   IO.puts("cont2 = #{inspect cont2}")
...(28)>   {rec, cont3} = :mnesia.select(cont1)
...(28)>   IO.puts("rec3 = #{inspect rec}")
...(28)>   IO.puts("cont3 = #{inspect cont3}")
...(28)>   IO.puts("cont2 == cont3 = #{cont2 == cont3}")
...(28)> end)
rec1 = [{:test, :a, 1}]
cont1 = {:mnesia_select, :test, {:tid, 7, #PID<0.100.0>}, :nonode@nohost, :ram_copies, {#Reference<0.3882805345.2162294785.166659>, 161, 1, #Reference<0.3882805345.2162294787.167694>, [], 0}, [], :undefined, :undefined, [{:_, [], [:"$_"]}]}
rec2 = [{:test, :b, 2}]
cont2 = {:mnesia_select, :test, {:tid, 7, #PID<0.100.0>}, :nonode@nohost, :ram_copies, {#Reference<0.3882805345.2162294785.166659>, 162, 1, #Reference<0.3882805345.2162294787.167694>, [], 0}, [], :undefined, :undefined, [{:_, [], [:"$_"]}]}
rec3 = [{:test, :b, 2}]
cont3 = {:mnesia_select, :test, {:tid, 7, #PID<0.100.0>}, :nonode@nohost, :ram_copies, {#Reference<0.3882805345.2162294785.166659>, 162, 1, #Reference<0.3882805345.2162294787.167694>, [], 0}, [], :undefined, :undefined, [{:_, [], [:"$_"]}]}
cont2 == cont3 = true
Navíc protože je to procházení databáze deterministické, platí to cont2 == cont3. Pokud by to byl třeba generátor náhodných čísel v ne-pure jazyce, nemuselo by to nutně platit.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 10. 05. 2019, 14:58:24
Třeba tady http://erlang.org/doc/man/mnesia.html#select-4 se slovo "continuation" používá prostě pro nějakou (neznámou) strukturu (ne nutně funkci), která umožňuje pokračovat v činnosti kdykoli jindy - v tomhle případě pokračovat v paginaci záznamů z DB.

to nema s kontinuaci, o ktere tu diskutujeme, nic spolecneho.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 10. 05. 2019, 15:03:39
to nema s kontinuaci, o ktere tu diskutujeme, nic spolecneho.
Je to přesně to, co jsi citoval z té Wikipedie:

a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution

https://en.wikipedia.org/wiki/Continuation
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 10. 05. 2019, 15:11:02
to nema s kontinuaci, o ktere tu diskutujeme, nic spolecneho.
Je to přesně to, co jsi citoval z té Wikipedie:

a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution

https://en.wikipedia.org/wiki/Continuation

to neni, nepamatuje si stav programu a neumoznuje se vratit zpet na misto sveho vytvoreni. Cemu ty rikas kontinuace, je databazovy kurzor.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 10. 05. 2019, 15:12:09
to neni, nepamatuje si stav programu a neumoznuje se vratit zpet na misto sveho vytvoreni.
Jak myslíš, nemám potřebu se hádat.

Cemu ty rikas kontinuace, je databazovy kurzor.
Neříkám tomu tak já, ale autoři Erlangu.
Název: Re:Jak funguje Call/CC?
Přispěvatel: gill 11. 05. 2019, 11:54:36
Cemu ty rikas kontinuace, je databazovy kurzor.
Neříkám tomu tak já, ale autoři Erlangu.

je to homonymum. S tématem diskuze nemá nic společného. Erlang call/cc neumí.
Název: Re:Jak funguje Call/CC?
Přispěvatel: Mirek Prýmek 11. 05. 2019, 11:56:11
Erlang call/cc neumí.
To jsem ani netvrdil.