PPX Deriving and polymorphic variants

Community
1

I’ve recently come across a nice trick for encoding FSMs (Finite State Machines) in OCaml.

The idea is to use a polymorphic variant to represent the states of the machine. When the machine is described as an explicit list of transitions – as opposed to function as in the above-cited example --, this makes the definition slightly more readable.

For example, instead of writing (using here strings as state identifiers)

type fsm = {
  ...
  trans: (string * string) list;
  ...
  }

and then define, for example

# let f1 = { ...; trans=["S1","S2"]; ... }
> val f1 : fsm = {...; trans = [("S1", "S2")]; ... }

one writes

type 'state fsm = { 
  ...
  trans: ('state * 'state) list;
  ...
  }

and

# let f1 = { ...; trans=[`S1,`S2]; ... }
> val u1 : [> `S1 | `S2 ] fsm = { ...; trans = [(`S1,`S2)]; ...}

which is – arguably – a bit easier to write and read.

The problem, with the second approach, is how do we print (as a string for example) a textual representation of the machine ?
If the constructors encoding the states had been defined using a “regular” variant, by writing

type state = S1 | S2

for example, one could have used a [@@deriving show] PPX annotation for that purpose.
But I don’t see how to apply this technique with the approach above – esp. because the type representing the distinct states in not named here.
In fact, I suspect this is just not possible, because this type is here viewed as a polymorphic type parameter.

Am i right or am i missing sth ?

Jocelyn

2

Can you provide a complete example of an FSM? I don’t see why @@deriving shouldn’t be able to do this trick. Maybe with a little (ahem) help, but still …

ETA: Do you mean something like this? (tested with pa_ppx.deriving_plugins.show, so should work with pa_deriving.show)

type 'a fsm = { trans: ('a * 'a) list } [@@deriving show];;

let f1 = { trans=[`S1,`S2]; } ;;

let _ =
  print_string ([%show: [ `S1 | `S2] fsm] f1)
3

Thanks for the answer, but the proposed solution requires the user to explicit give the type of the FSM when printing.

What i was seeking for was sth more general, like:

module fsm = struct
  type 'state t = { ...; trans: ('state * 'state) list; ... }
  ...
  let string_of_trans (src,dst) = string_of_state src ^ "->" ^ string_of_state dst
  ...
end

let f1 = { Fsm.trans = [`S1,`S2] } 
let _ = Printf.printf "First transition is : %s\n" (List.hd f1.trans)

But i now realize that, PPX or not, there’s no way to define the string_of_state function in this context because the type parameter 'state can be bound to any type when defining a value of type Fsm.t. In fact, this the reason who drove me to write a functorized interface to the FSM module in the Lascar library. I was not familiar with polymorphic variants and PPX rewriters at this time. The trick evoked at the beginning of this post made me think that maybe there was a functor-less formulation…

2 Likes
4

Hmm … the thing is, there’s -no- way to get what you want, without explicitly writing down a type. Using generative variants doesn’t change this. Using strings doesn’t change this. Regardless, you have to write down the type that will be the actual for the formal 'state sometime, so that @@deriving can generate code against it. You might not write it down right at the definition of “fsm”, but you’re going to write it down somewhere: that’s inescapable.

5

It believe it’s possible to get close to what you want using PPX and no functors – whether it’s worth doing it that way is a different question :wink: The idea is as follows:

  • Define your FSM implementations inside a module T.
  • Define a preprocessor that imports the inferred types as OCaml AST values, then collects all state types from the AST and generates a to_string function for them.

As a little proof-of-concept, we can use ppx_import as a type-importer and ppxlib.metaquot to convert imported module type ASTs to Parsetree values:

(* --- Fsm.ml ---------------------------------- *)

module T = struct
  type 'a t = { trans : ('a * 'a) list }

  let linear = { trans = [ (`A, `B); (`B, `C) ] }
  let cyclic = { trans = [ (`A, `D); (`D, `A) ] }
end

module type S = module type of T

(* --- Test.ml --------------------------------- *)

open Ppxlib

let () =
  let loc = Location.none in
  [%str module type A = [%import: (module Fsm.S)]]
  |> Format.printf "PPX is magic:\n\n%a\n%!" Ppxlib.Pprintast.structure

Then we can get the following output:

ᐅ dune exec ./test.exe
PPX is magic:

module type A  =
  sig
    type 'a t = {
      trans: ('a * 'a) list }
    val linear : [ `A  | `B  | `C ] t
    val cyclic : [ `A  | `D ] t
  end

which demonstrates that we have the state types at our fingertips (but doesn’t actually convert that AST to a corresponding to_string function). Demonstration available here.

For the record, I don’t recommend this kind of approach, but it’s interesting to know that it’s possible :slightly_smiling_face:

1 Like
6

Oh, hm. I had forgotten about module type of. And heck, about interrogating .cmi files. So … now that you’ve opened that can of worms, one could imagine something like

type t = [%import: (type of Fsm.T.linear)]

and maybe (going a little further)

type st = [%import 'st with type 'st Fsm.T.t = (type of Fsm.T.linear)]

(implying structural unification of the type-expressions). Of course the “type of” operator is not part of Ocaml, but in the context of %import, it could be grin.

7

Thanks for ideas ! Having just started to experiment with PPX, i simply could not imagine that such clever use of the mechanism was possible !
OTOH – and as suggested above – the question is now whether injecting this complex machinery just for avoiding denoting states with strings is worth doing :wink:
I’m currently implementing a small EDSL for injecting FSMs in a larger programming framework written in OCaml. These ideas may be prove useful in this context.
Thanks again for your feedback.