continuation style de passage vs monades

Quelles sont les différences entre le style de passage de continuation (cps) et les monades.

23
demandé sur hammar 2010-12-24 13:58:47

4 réponses

Tel Que mentionné dans L'essence de la programmation fonctionnelle:

La programmation avec des monades rappelle fortement le style de continuation-passing (CPS), et cet article explore la relation entre les deux. En un sens, ils sont équivalents: CPS apparaît comme un cas particulier d'une monade, et toute monade peut être intégrée dans CPS en changeant le type de réponse. Mais l'approche monadique fournit un aperçu supplémentaire et permet un degré de contrôle plus fin.

Ce papier est assez rigoureux, et en fait, il ne s'étend pas tout à fait sur la relation entre CPS et monades. Ici, je tente de donner un exemple informel, mais illustratif:

(Note: ci-dessous est une compréhension de Monad d'un débutant (moi-même), bien qu'après l'avoir écrit, il semble ressembler à une réponse de ces utilisateurs de haut niveau. Prenez-le avec une tonne de sel)

Considérez la monade classique Maybe

-- I don't use the do notation to make it 
-- look similar to foo below

bar :: Maybe Int
bar =
    Just 5 >>= \x ->
    Just 4 >>= \y ->
    return $ x + y

bar' :: Maybe Int
bar' =
    Just 5 >>= \x ->
    Nothing >>= \_ ->
    return $ x

GHCi> bar
Just 9
GHCi> bar'
Nothing

Donc le calcul s'arrête dès que Nothing est rencontré, rien nouveau ici. Essayons d'imiter un tel comportement monadique en utilisant CPS:

Voici notre fonction vanilla add utilisant CPS. Nous utilisons tous les Int ici au lieu du type de données algébriques pour le rendre plus facile:

add :: Int -> Int -> (Int -> Int) -> Int
add x y k = k (x+y)

GHCi> add 3 4 id
7

Remarquez à quel point il est similaire à une monade

foo :: Int
foo =
    add 1 2 $ \x -> -- 3
    add x 4 $ \y -> -- 7
    add y 5 $ \z -> -- 12
    z

GHCi> foo
12

OK. Supposons que nous voulons que le calcul soit plafonné à 10. Autrement dit, quel que soit le calcul doit s'arrêter lorsque l'étape suivante aboutirait à une valeur supérieure à 10. C'est un peu comme dire "un calcul peut-être doit s'arrêter et retourner Nothing dès que toute valeur dans la chaîne est Nothing). Voyons comment nous pouvons le faire en écrivant un "transformateur CPS"

cap10 :: (Int -> Int) -> (Int -> Int)
cap10 k = \x ->
    if x <= 10 
    then 
        let x' = k x in 
        if x' <= 10 then x' else x
    else x

foo' :: Int
foo' =
    add 1 2 $ cap10 $ \x -> -- 3
    add x 4 $ cap10 $ \y -> -- 7
    add y 5 $ cap10 $ \z -> -- 12
    undefined

GHCi> foo'
7

Notez que la valeur de retour finale peut être undefined, mais c'est bien, car l'évaluation s'arrête à la 3ème étape (z).

Nous pouvons voir que cap10 "enveloppe" la suite normale avec une logique supplémentaire. Et c'est très proche de ce que monad doit -- coller des calculs avec une logique supplémentaire.

Faisons un pas en outre:

(>>==) :: ((Int -> Int) -> Int) -> (Int -> Int) -> Int
m >>== k = m $ cap10 k

foo'' :: Int
foo'' =
    add 1 2 >>== \x -> -- 3
    add x 4 >>== \y -> -- 7
    add y 5 >>== \z -> -- 12
    undefined

GCHi> foo''
7

Wouah! Peut-être que nous venons d'inventer la monade Cap10!

Maintenant, si nous regardons la le code source de la Suite, nous voyons que Cont est

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

Le type de runCont est

Cont r a -> (a -> r) -> r
((a -> r) -> r) -> (a -> r) -> r

, Qui s'aligne parfaitement avec le type de notre >>==

Maintenant pour répondre à la question

Maintenant, après avoir tapé tout cela, j'ai relu la question originale. Le PO a demandé la "différence": P

Je suppose que la différence est CPS donne à l'appelant plus de contrôle, où comme d'habitude le >>= dans une monade est entièrement contrôlé par l'auteur de la monade.

22
répondu kizzx2 2011-08-07 16:58:06

Vous voudrez peut-être jeter un oeil à ceci http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

7
répondu Peter Jankuliak 2011-03-12 17:45:24

Un article intéressant qui explore la question Est "Imperative functional programming" , par Peyton Jones et Wadler.

C'est le document qui a introduit IO monadique, et il a des comparaisons avec des approches alternatives, y compris CPS.

Les auteurs concluent:

Donc les monades sont plus puissantes que les continuations, mais seulement à cause des types! Il n'est pas clair s'il s'agit seulement d'un artefact du système de type Hindley-Milner, ou si les types sont révéler une différence d'importance fondamentale (notre propre intuition c'est la dernière-mais ce n'est qu'une intuition.)

4
répondu Federico Squartini 2011-08-08 08:44:33

Il n'y a pas de relation, donc la question a autant de sens que de poser des questions sur la différence entre la couleur bleue et Pluton.

-9
répondu Jörg W Mittag 2010-12-24 16:59:48