Abusing exceptions

I was trying to implement Ken Shan, et al's fair backtracking monad (ICFP 2005) yesterday for the InforML typechecker. However, no matter how I tried implementing it, I would become stuck trying to give them a type because SML doesn't have existential data types. It kept gnawing at me and this morning it came to me that by abusing local exception definitions I could work around this. It wouldn't work if, like OCaml, SML only allowed top level exception definitions. It might also be possible to use SML/NJ's callcc, but I had an easier time wrapping my head around this.

  1.  
  2. type env
  3.  
  4. (* Takes an environment, a success "continuation",
  5. and a failure "continuation", and pretends that it
  6. will give you an exception back *)
  7.  
  8. type 'a monad = env -> (env * 'a -> exn) -> exn -> exn
  9.  
  10. infix 5 >>=
  11. infix 5 >>
  12. infix 5 ||
  13.  
  14. (* Unit *)
  15. fun return x =
  16. (fn s => fn sk => fn fk => raise (sk (s, x)))
  17.  
  18. (* Bind *)
  19. fun (m : 'a monad) >>= (f : 'a -> 'b monad) =
  20. let
  21. exception SuccCont of env * 'a
  22. in
  23. (fn s => fn sk => fn fk =>
  24. (m s SuccCont fk)
  25. handle SuccCont (s', x) => ((f x) s sk fk))
  26. end
  27.  
  28. (* Sequence *)
  29. fun (m1 : 'a monad) >> (m2 : 'b monad) =
  30. [| x | _ <~ m1, x <~ m2 |]
  31.  
  32. (* Choice *)
  33. fun (m1 : 'a monad) || (m2 : 'a monad) =
  34. let
  35. exception FailCont
  36. in
  37. (fn s => fn sk => fn fk =>
  38. (m1 s sk FailCont)
  39. handle FailCont => (m2 s sk fk))
  40. end
  41.  
  42. (* Zero, disjunctive unit *)
  43. val zero = (fn s => fn sk => fn fk => raise fk)
  44.  

Leave a Comment