Jak funguje Call/CC?

Jak funguje Call/CC?
« kdy: 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í.
« Poslední změna: 07. 05. 2019, 22:48:52 od Petr Krčmář »


Idris

  • *****
  • 2 061
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #1 kdy: 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.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #2 kdy: 08. 05. 2019, 11:34:10 »
V Ruby muzete Call/CC ignorovat. Je to prekonany koncept.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #3 kdy: 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.

Idris

  • *****
  • 2 061
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #4 kdy: 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.


gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #5 kdy: 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.
« Poslední změna: 08. 05. 2019, 14:27:54 od gill »

Idris

  • *****
  • 2 061
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #6 kdy: 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.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #7 kdy: 08. 05. 2019, 14:29:13 »
To je implementace, ne definice. Ale třeba to tazateli taky pomůže.

to je definice.

Re:Jak funguje Call/CC?
« Odpověď #8 kdy: 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.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #9 kdy: 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.

Idris

  • *****
  • 2 061
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #10 kdy: 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.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #11 kdy: 09. 05. 2019, 14:52:07 »
Muzes nam Idrisi ukazat priklad pouziti, kdy je to k necemu uzitecne?

Re:Jak funguje Call/CC?
« Odpověď #12 kdy: 09. 05. 2019, 14:54:33 »
V Ruby muzete Call/CC ignorovat. Je to prekonany koncept.
Ruby muzete ignorovat. Je to prekonany koncept.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #13 kdy: 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.

gill

  • ****
  • 270
    • Zobrazit profil
    • E-mail
Re:Jak funguje Call/CC?
« Odpověď #14 kdy: 09. 05. 2019, 15:44:31 »
V cem dnes programuji hipsteri?