StackOverflow dans le prolongement monade

Utilisation de la monade de continuation suivante:StackOverflow dans le prolongement monade

type ContinuationMonad() = 
    member this.Bind (m, f) = fun c -> m (fun a -> f a c) 
    member this.Return x = fun k -> k x 

let cont = ContinuationMonad()

Je ne vois pas pourquoi ce qui suit me donne un débordement de pile:

let map f xs = 
    let rec map xs = 
     cont { 
      match xs with 
      | [] -> return [] 
      | x :: xs -> 
       let! xs = map xs 
       return f x :: xs 
     } 
    map xs id;; 

let q = [1..100000] |> map ((+) 1)

Bien que ce qui suit ne pas:

let map f xs = 
    let rec map xs = 
     cont { 
      match xs with 
      | [] -> return [] 
      | x :: xs -> 
       let! v = fun g -> g(f x) 
       let! xs = map xs 
       return v :: xs 
     } 
    map xs id;; 

let q = [1..100000] |> map ((+) 1)

Source

2012-06-25 David Grenier

Notez que je suis sur VS 2012 RC, si quelqu'un pouvait le tester a le même comportement sur la version actuelle de VS2010. –

Oui, et il a aussi le même comportement dans OCaml. Voir ma réponse ci-dessous. – t0yv0

FWIW, ce comportement peut encore être observé avec VS2015, F # 4.0, mise à jour 3 (bien que les réponses indiquent qu'il ne peut pas être attribué au compilateur). – Abel

Pour fixer votre exemple, ajoutez cette méthode à votre définition de la monade:

member this.Delay(mk) = fun c -> mk() c

Apparemment, la partie qui déborde est la destruction de la grande liste d'entrée dans l'appel récursif de map. Retarder cela résout le problème.

Notez que votre deuxième version met l'appel récursif à map derrière un autre let! qui desugars à Bind et un lambda supplémentaire, en effet retarder l'appel récursif à map.

Je devais poursuivre quelques fausses pistes avant d'arriver à cette conclusion. Ce qui a aidé à observer que StackOverflow est également lancé par OCaml (bien qu'à un N plus élevé) à moins que l'appel récursif soit retardé. Alors que F# TCO a quelques bizarreries, OCaml est plus éprouvée, donc cela m'a convaincu que le problème est en effet avec le code et non le compilateur:

let cReturn x = fun k -> k x 
let cBind m f = fun c -> m (fun a -> f a c) 

let map f xs = 
    (* inner map loop overflows trying to pattern-match long lists *) 
    let rec map xs = 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> 
     cBind (map xs) (fun xs -> cReturn (f x :: xs)) in 
    map xs (fun x -> x) 

let map_fixed f xs = 
    (* works without overflowing by delaying the recursive call *) 
    let rec map xs = 
    match xs with 
     | [] -> cReturn [] 
     | x :: xs -> 
     cBind (fun c -> map xs c) (fun xs -> cReturn (f x :: xs)) in 
    map xs (fun x -> x) 

let map_fused f xs = 
    (* manually fused version avoids the problem by tail-calling `map` *) 
    let rec map xs k = 
    match xs with 
     | [] -> k [] 
     | x :: xs -> 
     map xs (fun xs -> k (f x :: xs)) in 
    map xs (fun x -> x)

Source

2012-06-25 14:47:57 t0yv0

Vous pouvez résoudre ce problème sans ajouter le membre Delay - voir mon commentaire sur la réponse de John Palmer. –

@JackP., Je suis d'accord que l'ajout du membre Delay n'est pas le seul correctif. Cependant, vous devez retarder l'appariement de la liste d'entrée pour qu'elle ne se produise pas entièrement sur la pile.Si vous ne faites pas cela, le code débordera (si ce n'est pas à 'N = 100000' alors à un plus haut' N'. – t0yv0

Le compilateur F # n'est parfois pas très intelligent - dans le premier cas, il calcule map xs puis f x puis les joint, donc map xs n'est pas en position de queue. Dans le second cas, il peut réorganiser le map xs pour être en position de queue facilement.

Source

2012-06-25 12:18:33

Je ne vois pas comment '(f x)' peut être calculé n'importe où mais dans la continuation générée par le workflow. –

@DavidGrenier - John a raison. '(f x)' est calculé à l'intérieur de la continuation générée par le workflow, mais il n'est pas calculé à l'intérieur de son propre * continuation *. C'est-à-dire que le workflow crée seulement une continuation qui enveloppe '(f x) :: xs' - donc quand cette continuation est appelée, elle ne peut pas faire un appel de queue à' f'. Quand cette continuation est exécutée, elle doit pousser une trame de pile chaque fois qu'elle appelle 'f', et puisqu'elle le fait récursivement, vous obtenez le' StackOverflowException'. Dans votre deuxième exemple, le compilateur F # est capable de générer des appels de queue pour tout. –

@JackP Je ne suis pas d'accord avec le commentaire et votre réponse. 'map' renvoie immédiatement, l'appel de la queue' map' n'est pas pertinent. 'f' n'est pas récursif, l'appel de queue' f' n'est pas non plus pertinent. En outre, la faute n'est pas avec le compilateur F #, OCaml fait de même ici, basé sur mes tests. – t0yv0

StackOverflow dans le prolongement monade

Répondre

Questions connexes