Kontynuacje

2

Pytanie zasadnicze:
Proszę o rozpiskę działania callCC tak na chłopski rozum.

A teraz w formie żali:
Najpierw może zapodam mój brudnopis z rozpiskami:

{-
class Monad m where
    (>>=)  :: m a -> (a -> m b) -> m b
    return :: a -> m a
-}

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }

instance Monad (Cont r) where
  return n = Cont (\k -> k n)
  m >>= f  = Cont (\k -> runCont m (\a -> runCont (f a) k))

class (Monad m) => MonadCont m where 
    callCC :: ((a -> m b) -> m a) -> m a 

instance MonadCont (Cont r) where 
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

{-
bar :: Cont r Int
bar = callCC $ \k -> do
  let n = 5
  k n
  return 25
-}

bar :: Cont r Int
bar = callCC $ \k ->
  k 5 >>= \_ ->
  Cont (\k -> k 25)

{-
baz :: (Integer -> Cont r a) -> Cont r Integer
baz = \k ->
  k 5 >>= \_ ->
  Cont (\k -> k 25)
-}

baz :: (Integer -> Cont r a) -> Cont r Integer
--baz = \k -> Cont (\l -> runCont (k 5) (\a -> runCont ((\_ -> Cont (\k -> k 25)) a) l))
--baz = \k -> Cont (\l -> runCont (k 5) (\_ -> runCont (Cont (\k -> k 25)) l))
--baz = \k -> Cont (\l -> runCont (k 5) (\_ -> (\k -> k 25) l))
baz = \k -> Cont (\l -> runCont (k 5) (\_ -> l 25))

foo :: (Integer -> (a -> r) -> r) -> (Integer -> r) -> r
foo = \k l -> k 5 (\_ -> l 25)

boo :: (Integer -> r) -> r
--boo = callCC (\k -> Cont (\l -> runCont (k 5) (\_ -> l 25)))
--boo = \m -> ((\k l -> k 5 (\_ -> l 25)) (\a -> (\_ -> m a))) m
--boo = \m -> ((\k -> k 5 (\_ -> m 25)) (\a -> (\_ -> m a)))
--boo = \m -> ((\a -> (\_ -> m a)) 5 (\_ -> m 25))
--boo = \m -> ((\a _ -> m a) 5 (\_ -> m 25))
--boo = \m -> ((\a -> m a) 5)
boo = \m -> m 5

{-
-}

add x y = x + y
square x = x * x

add_cont :: Int -> Int -> Cont r Int
add_cont x y = return (add x y)

square_cont :: Int -> Cont r Int
square_cont x = return (square x)

{-
pythagoras_cont :: Int -> Int -> Cont r Int
pythagoras_cont x y =
    do x_squared <- square_cont x
       y_squared <- square_cont y
       sum_of_squares <- add_cont x_squared y_squared
       return sum_of_squares
-}

--m >>= f  = Cont (\k -> runCont m (\a -> runCont (f a) k))

pythagoras_cont :: Int -> Int -> Cont r Int
--pythagoras_cont x y = square_cont x >>= (\x_squared -> square_cont y >>= (\y_squared -> add_cont x_squared y_squared >>= (\sum_of_squares -> Cont (\k -> k sum_of_squares))))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> square_cont y >>= (\y_squared -> (add_cont x_squared y_squared >>= (\sum_of_squares -> Cont (\k -> k sum_of_squares)))))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> square_cont y >>= (\y_squared -> Cont (\l -> runCont (add_cont x_squared y_squared) (\a -> runCont ((\sum_of_squares -> Cont (\k -> k sum_of_squares)) a) l))))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> square_cont y >>= (\y_squared -> Cont (\l -> runCont (add_cont x_squared y_squared) (\a -> runCont (Cont(\k -> k a)) l))))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> square_cont y >>= (\y_squared -> Cont (\l -> runCont (add_cont x_squared y_squared) (\a -> l a))))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> Cont (\k -> runCont (square_cont y) (\b -> runCont ((\y_squared -> Cont (\l -> runCont (add_cont x_squared y_squared) (\a -> l a))) b) k)))
--pythagoras_cont x y = square_cont x >>= (\x_squared -> Cont (\k -> runCont (square_cont y) (\b -> runCont (Cont (\l -> runCont (add_cont x_squared b) (\a -> l a))) k)))
--pythagoras_cont x y = Cont (\n -> runCont (square_cont x) (\c -> runCont ((\x_squared -> Cont (\k -> runCont (square_cont y) (\b -> runCont (Cont (\l -> runCont (add_cont x_squared b) (\a -> l a))) k))) c) n))
--pythagoras_cont x y = Cont (\n -> runCont (square_cont x) (\c -> runCont (Cont (\k -> runCont (square_cont y) (\b -> runCont (Cont (\l -> runCont (add_cont c b) (\a -> l a))) k))) n))
--pythagoras_cont x y = Cont (\n -> runCont (square_cont x) (\c -> runCont (Cont (\k -> runCont (square_cont y) (\b -> runCont (add_cont c b) (\a -> k a)))) n))
pythagoras_cont x y = Cont (\k -> runCont (square_cont x) (\c -> runCont (square_cont y) (\b -> runCont (add_cont c b) (\a -> k a))))

Sprawa jest taka. Rozumiem mniej więcej na czym polegają kontynuacje i jak działa monada do składania kontynuacji, natomiast za cholerę nie jestem w stanie zrozumieć jak działa funkcja callCC. Moja rozpiska metody bar potwierdza, że jak wywołam aktualną kontynuację w bloku do to następne funkcje nie zostaną wykonane. Tyle, że dalej nie potrafię sobie opracować jakichś analogii mniej abstrakcyjnych niż znaczki.

0

Tego nie da się nie rozumieć, szczególnie po http://en.wikibooks.org/wiki/Haskell/Continuation_passing_style

Każda funkcja zwracająca Kontynuację pobiera jeszcze jeden parametr, funkcję, która będzie naszą kontynuacją.
CallCC jest generalizacją return. Parametr z return od razu idzie do funkcji, którą kontynuacja ma pobrać, natomiast callCC pozwala zmodyfikować sterowanie(swoją drogą bardzo przypomina monadycznego binda(>>=), porównaj nagłówki typów). Weźmy przykład z tutka

add :: Int -> Int -> Cont r Int
add x y = return (x + y)

square :: Int -> Cont r Int
square x = return (x * x)

-- pythagoras z returnem
pythagoras :: Int -> Int -> Cont r Int
pythagoras x y = do
  x_s <- square x
  y_s <- square y
  sos <- add x_s y_s
  return sos
-- sposób użycia     => wynik
-- runCont (pythagoras 4 3) print     => 25

-- pythagoras z callCC mogący zakończyć się niespodzianką
pythagoras' :: Int -> Int -> Cont r Int
pythagoras' x y = do
  x_s <- square x
  y_s <- square y
  sos <- add x_s y_s
-- (callCC $ \k -> k sos) jest tożsame return sos
  callCC $ \k -> if sos < 20 then error("That's wrong!") else k sos

-- runCont (pythagoras' 4 3) print    => 25
-- runCont (pythagoras' 1 1) print    => *** Exception: That's wrong!


-- kontynuacją dla funkcji wew. bloku do będą następne wyrażenia z tego bloku
-- modyfikacja square
foo :: Int -> Cont r Int
foo x = callCC $ \k -> if x < 5 then error("Blah") else k (x*x)

-- po zamienieniu square z foo 
pythagoras'' :: Int -> Int -> Cont r Int
pythagoras'' x y = do
  x_s <- foo x
  y_s <- foo y
  sos <- add x_s y_s
  return sos

-- runCont (pythagoras'' 5 5) print   => 50
-- runCont (pythagoras'' 1 1) print   => *** Exception: Blah

pythagoras''' :: Int -> Int -> Cont r Int
pythagoras''' x y = do
  x_s <- square x
  -- jak powyżej, kontynuacją dla funkcji wew. bloku do będą następne wyrażenia z tego bloku
  y_s <- callCC $ \k -> if x_s > 25 then error("Ja sie tak nie bawie") else k (y * y)
  sos <- add x_s y_s
  return sos

-- runCont (pythagoras''' 1 1) print  => 2
-- runCont (pythagoras''' 6 1) print  => *** Exception: Ja sie tak nie bawie
--   ^           ^               ^          
--   |           |               |
--   |           |             To jest naszą funkcją k z argumentu callCC wewnątrz pythagoras y, 
--   |           |             jej przekazujemy wynik z monady
--   |      To produkuje kontynuację, czyli może przyjąć funkcje do której przekaże wynik
--  To wpina print, parametr k z callCC w miejscu returna to właśnie ten print.

Zagnieżdżenia callCC analogicznie.

Jeżeli dalej nie rozumiesz to nie przejmuj się. Z kontynuacjami jest jak z rekurencją, nie wszyscy zostali stworzeni do jej zrozumienia.

1

No dobra, to odpowiem sobie sam w skrócie.

Najpierw trzeba powiedzieć, że Cont r b to nie kontynuacja. Kontynuacja to funkcja typu: a -> Cont r b.

Załóżmy, że mamy takie definicje:

instance Monad (Cont r) where
  return n = Cont (\afterReturn -> afterReturn n)
  m >>= f  = Cont (\afterBind -> runCont m (\a -> runCont (f a) afterBind))

instance MonadCont (Cont r) where 
    callCC f = Cont $ \afterCall -> runCont (f (\a -> Cont $ \_ -> afterCall a)) afterCall

>>= wymawia się jako bind.

Zamieniłem wszędzie k na afterXXX, gdyż Cont-ów używa się generalnie w ciągach (czy to notacja do czy explicite bindowanie).

Jak widać bind tworzy kontynuację, która najpierw wykonuje Cont-a m, który to potem przekaże sterowanie wraz z wynikiem do funkcji:

(\a -> runCont (f a) afterBind)

A więc wywoła funkcję f z wynikiem Cont-a m, co wygeneruje Cont-a, który coś zrobi i przekaże wynik i sterowanie do afterBind.

W sumie bez sensu objaśniam, bo to oczywiste. Za to nieoczywiste jest co się dzieje w callCC.

Otóz callCC przyjmuje funkcję f. Funkcja f przyjmuje funkcję, która przyjmuje coś typu a, a następnie zwraca Cont-a. callCC po zaaplikowaniu f ostatecznie zwraca Cont-a, a więc jest zwykle elementem w ciągu kontynuacji np w notacji do.

callCC używa się np tak:

resultCont = callCC $ \exit -> do
  v1 <- c1
  when (cond) (exit ve)
  v2 <- c2
  return (v1 + v2)

Tutaj:

\exit -> do 
  v1 <- c1
  when (cond) (exit ve)
  v2 <- c2
  return (v1 + v2)

jest funkcją f z definicji callCC. Parametr exit jest funkcją, która przyjmuje coś i zwraca Cont-a. Dokładniej jest on podawany w funkcji callCC. Inaczej mówiąc:

exit = (\a -> Cont $ \_ -> afterCall a)
lub inaczej
exit a = Cont $ \_ -> afterCall a

Jak widzimy, jeżeli wywołamy funkcję exit z parametrem to otrzymamy Cont-a, który po włożeniu w niego kontynuacji zignoruje ją i przekaże sterowanie do kontynuacji podanej dla całej callCC.

Jeżeli natomiast nie wywołamy w bloku do funkcji exit to cały blok do zwróci zwykłego Cont-a. Parametr exit, a więc i jego definicja podana w definicji callCC będzie zignorowany i nie wykonywany. Inaczej mówiąc, jeśli:

cont = do 
  v1 <- c1
  when (cond) (exit ve)
  v2 <- c2
  return (v1 + v2)

f = \exit ->
  cont

To następują przekształcenia. callCC f przyjmuje następujące postacie:

Cont $ \afterCall -> runCont (f (\a -> Cont $ \_ -> afterCall a)) afterCall
--aplikujemy
Cont $ \afterCall -> runCont ((\exit -> cont) (\a -> Cont $ \_ -> afterCall a)) afterCall
--tu widzimy, że parametr exit nie jest używany, więc możemy go zignorować
Cont $ \afterCall -> runCont ((\_ -> cont) (\a -> Cont $ \_ -> afterCall a)) afterCall
--teraz aplikujemy
Cont $ \afterCall -> runCont (cont) afterCall

Jak widać, jeśli w ciele do nie skorzystamy z parametru exit, to callCC zredukuje się w zasadzie do zera.

Co trzeba sobie uzmysłowić, żeby zrozumieć callCC (wg mnie):
W Cont-cie parametr afterXXX jest kontynuacją, czyli krokami, które nastąpią po tym Cont-cie.
callCC przyjmuje funkcję f, która przyjmuje parametr, nazwijmy go exit, typu takiego jak kontynuacja.
Jeżeli w bloku do nie użyjemy parametru exit, to nie zostanie on nawet obliczony.
Natomiast jeśli go użyjemy to on stworzy nam Cont-a, który nie zachowuje się jak normalny Cont, tzn normalny Cont przekazuje sterowanie do funkcji po nim, która jest do niego zbindowana, natomiast parametr exit tworzy Cont-a który przekazuje sterowanie do kontynuacji afterCall. Inaczej: Cont-y które normalnie byłyby w ciągu wywołań wypadają z tego ciągu, bo Cont wyprodukowany przez exit nie przekazuje do nich sterowania.

0

@Wibowit: Po 10 latach przydała ci się ta wiedza? Bo jak ja patrzę na kontunuacje to to dla mnie dalej jest przerost formy nad treścią. Jeszcze nie znalazłem przykładu gdzie to można użyć. Trochę taki funkcyjny odpowiednik DDD:

  • DDD -> OOP zrobione właściwie (powiedzą kapłani DDD, a ja danej nie rozumiem gdzie zysk)
  • Kontynuacje -> FP zrobione właściwie (Nie wiem czy powiedzą tak kapłani kontynuacji, bo jeszcze żadnego nie spotkałem, ale zysku nie widzę. No bo czemu nie mogę zrobić zwykłego ifa tylko kontynuacji używamć mam?)
0

Po 10 latach przydała ci się ta wiedza?

ogólnie nie :) nawet zapomniałem już jak działa to callCC itd.

nawet jeśli continuation passing style się przydaje raz na ruski rok (mi się generalnie nie przydał) to i tak w typowym programowaniu w scali jest stosowany tak rzadko, że programiście scali nie opłaca się utrwalać sobie mechanizmu działania kontynuacji. inaczej mówiąc, zwrot z inwestycji jest moim zdaniem raczej kiepski. ale do potrenowania umysłu można sobie to callCC rozpykać :)

0
Wibowit napisał(a):

nawet jeśli continuation passing style się przydaje raz na ruski rok (mi się generalnie nie przydał) to i tak w typowym programowaniu w scali jest stosowany tak rzadko, że programiście scali nie opłaca się utrwalać sobie mechanizmu działania kontynuacji.

Jeśli nie w Scali to jestem ciekaw gdzie. Bo chyba nie w Haskellu:

Before using the Continuation monad, be sure that you have a firm understanding of continuation-passing style and that continuations represent the best solution to your particular design problem. Many algorithms which require continuations in other languages do not require them in Haskell, due to Haskell's lazy semantics. Abuse of the Continuation monad can produce code that is impossible to understand and maintain.

Źródło: Dokumentacja MTL

Może w jakimś nie leniwym Haskellu jak Idris czy Kind?

Wibowit napisał(a):

ale do potrenowania umysłu można sobie to callCC rozpykać :)

Leży na liście rzeczy do zrobienia, ale jak mówiłem nie widzę case'a pod callCC w moim projekcie hobbystycznym :(

1 użytkowników online, w tym zalogowanych: 0, gości: 1