continuation style de passage vs monades
Quelles sont les différences entre le style de passage de continuation (cps) et les monades.
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.
Vous voudrez peut-être jeter un oeil à ceci http://blog.sigfpe.com/2008/12/mother-of-all-monads.html
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.)
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.