How to achieve implicit state without using classes and objects

Learning
, ,
1

Hi everyone,

I am new to OCaml and I am trying to write my own parser library just for fun.

The easiest way to start of course is explicitly passing the updated parser state around. For example:

let my_parser (st: TokenParser.state): TokenParser.state * string =
  let (st, keyword) = TokenParser.token_ () st in
  let (st, ident)   = TokenParser.token_ () st in
  (st, "Result = " ^ keyword.text ^ ":" ^ ident.text)

But I want to hide this explicit state-passing without resorting to monadic interface, so I can write something like this:

let my_parser (): string =
  let keyword = TokenParser.token_ () in
  let ident   = TokenParser.token_ () in
  (st, "Result = " ^ keyword.text ^ ":" ^ ident.text)

I had a look around and the Parseff library does this by making use of Domain Local Storage. But it seems that the general recommendation is not to make use of DLS for newer libraries.

My next hunch was to resort to objects to keep the parser state internal. But I want to know if there is an alternative to going the object route while still keeping things simple?

2

My parser functions usually take the form type 'a parser = state -> 'a where state is mutable, such that I don’t need to thread its output and I don’t allocate unnecessarily, and use exceptions for backtracking. Example of a combinator:

type state = { text : string; mutable pos : int }

let rec skip_many parse_elem state =
    let start = state.pos in
    match parse_elem state with
    | _ -> skip_many parse_elem state
    | exception Syntax_error when state.pos = start ->
        (* parse_elem didn't consume any input *)
        ()
3

Thanks amongonz,

That at least gets me halfway there:

let my_parser (st: TokenParser.state): TokenParser.state * string =
  let keyword = TokenParser.token_ () st in
  let ident   = TokenParser.token_ () st in
  (st, "Result = " ^ keyword.text ^ ":" ^ ident.text)

:slight_smile:

This is a good compromise if I don’t get any better suggestions on using maybe first class modules or other OCaml non-OOP features.

When I googled around, I also read something about algebraic effects but it looked a bit complicated and I am not sure if they would be the right tool for this job.

4

If you want to have mutable states, you don’t need to keep the functional return type:

type source = { text: string; mutable pos: int }
let my_parser source =
   let keyword = token source in
   let ident = token source in
   String.concat "" ["Result = "; keyword; ":"; ident ]
5

Ah of course, sorry I missed that:

let my_parser (st: TokenParser.state): string =
  let keyword = TokenParser.token_ () st in
  let ident   = TokenParser.token_ () st in
  "Result = " ^ keyword.text ^ ":" ^ ident.text
6

If you want some state available within an entire module without passing it around, but want it encapsulated, generative functors are a nice way to get that. Here’s a sketch from the top level:

# module M () = struct
    type state = 
       { mutable value: int
       ; mutable trace: int list
       }
  
    let s : state = { value = 0; trace = [] }
  
    let incr () = 
       s.trace <- (s.value :: s.trace);
       s.value <- s.value + 1
  
    let trace () = s.trace
  end
  ;;
module M :
  () ->
    sig
      type state = { mutable value : int; mutable trace : int list; }
      val s : state
      val incr : unit -> unit
      val trace : unit -> int list
    end

# module A = M ()
  module B = M ();;
module A :
  sig
    type state = { mutable value : int; mutable trace : int list; }
    val s : state
    val incr : unit -> unit
    val trace : unit -> int list
  end
module B :
  sig
    type state = { mutable value : int; mutable trace : int list; }
    val s : state
    val incr : unit -> unit
    val trace : unit -> int list
  end
# A.incr (); A.incr (); A.incr (); A.trace ();;
- : int list = [2; 1; 0]
# B.incr (); B.trace ();;
- : int list = [0]