Looking around for a monad for dealing with early "return"

Ecosystem
1

As with a lot of things, I think I know how to write this, but I figured I’d ask around, b/c I can’t find it by googling, and perhaps somebody here knows where to look.

I’m translating some Python code to OCaml, and it’s going really well. But I have come across a function that has a complex if-then-else tree, followed by another. And in the first, there are some "return"s. Now I think I know how to write a monad to capture this, and I’m going to go ahead and do that, but I figured I’d ask if anybody here had any suggestions for where to look ?

The type of the monad would be something like:

type ('continue_ty, 'ret_ty) = Continue of 'continue_ty | Return of 'ret_ty

and the idea is that a piece of code that returns Continue x expects the next bit of code to be executed, on x.

Also, I wondered if there was a “bestiary” of OCaml monad implementations … that might be useful to have.

Thanks in advance.

ETA: Ah, I can just use an exception to implement the early-return. I’ll do that!

2

Exceptions will probably make your code most direct-style and easiest to follow, like you pointed out.

I think the closest I know to a pre-existing monad for what you want is the result type, and the Result.bind function, although I’m not sure if it fits your use case since the two cases are Ok and Error, when it seems like Error is a state you don’t want to model (or which isn’t possible) in your example type.

3

You can use local exception:

let exception Exit in
try ...
with Exit ->

Nice and clean.

A bare-bone early exit monad could be:

module Pipeline = struct
  type ('a, 'b) t = Continue of 'a | Terminal of 'b

  let pure v = Continue v
  let exit v = Terminal v

  let bind m f =
    match m with
    | Continue x -> f x
    | Terminal x as value -> value

  module Syntax = struct let ( let* ) = bind end
  module Infix = struct let ( >>= ) = bind end
end

But it’s just a Result monad in disguise…

4

Honestly, I’m surprised at myself that I didn’t just reach for exceptions for nonlocal exit and ref for the updatable variables from the jump, not bothering to post to ask the question. Too much time spent hacking in pure functional OCaml.

5

You don’t even need ref:

let exception Exit of int in
try raise (Exit 42)
with Exit c -> c
6

The most extensive collection of algebraic computational structures in OCaml I’m aware of is @xvw’s preface.

7

haha yes, that’s what I did:


let rec _closure self input (config : AC.t) configs ~currentAltReachedAcceptState
          ~speculative ~treatEofAsEpsilon =
  let exception EarlyReturn of bool in
  let currentAltReachedAcceptState = ref currentAltReachedAcceptState in
  try
      .... raise (EarlyReturn true) ....
  with
    EarlyReturn rv -> rv

The ref is for the one variable that is imperatively modified in the interesting control-flow nest.

8

This also exists in JaneStreet’s base library:

9

I’m reminded of this PR that was submitted to BAP a while back: rewrites knowledge and primus monads by ivg · Pull Request #1361 · BinaryAnalysisPlatform/bap · GitHub

The “double-barreled” CPS style here seems like a nice, general way to accomplish this.

10

Aha, very nice! I am reminded of … John Reppy writing this sort of CPS transformer back in the late 80s as part of SML/NJ. Two continuations, one the normal continuation, one the exception continuation.

11

I thought Andrew Kennedy came up with the double-barrelled CPS idea and terminology in his “Compiling with Continuations, Continued” paper, but it’s interesting that the idea apparently predates that paper by two decades!

I think I probably misremembered the credit from this article, which cites Andrew Kennedy’s paper as an influence for using double-barrelled CPS is OCaml, but that’s only where they got the idea from and not where the idea itself originated.

12

I became a caml-light fan back in 1991 when I realized that SML/NJ was fatally greedy of computer resources, and it really mattered. And I’ve written about how complete was my conversion before. So …

I suspect that every possible CPS-like thingie that we can imagine (other than, well, state-passing) has already been done in the SML/NJ corpus somewhere. B/c it was central to the implementation of that system, eh?

13

I think that must be at What are your feelings about : mlton,mosml,polyml,smlnj - #5 by Chet_Murthy ? I love reading this history :slight_smile:

14

For anyone looking at Base.With_return for reference:

It is only because of a deficiency of ML types that with_return doesn’t have type:

val with_return : 'a. (('a -> ('b. 'b)) -> 'a) -> 'a

OCaml 5.5 is there now, it can type : 'a. (('b. 'a -> 'b) -> 'a) -> 'a which works just as well here.

15

FYI for local exceptions you probably don’t want the overhead of the stack trace, so that’d be raise_notrace …

16

Maybe I’d remembered this tidbiit in some back corner of the cache … but if so it got swapped out to disk and later to tape long ago. Thank you for pulling it back into main memory!

17

I used monad for this kind of logic almost all the time, and personally prefer point-free style[1], so I never pay attention to this, today I learned something new, thanks.

[1]:

let* res = do_foo m >>= do_bar >>= do_baz in
....
(* or using Kleisli composition *)
let pipeline = do_foo >=> do_bar >=> do_baz