Declare a type as a subtype of another one

Learning
1

I am trying to figure out is it possible to declare a type as a subtype of another one.

Here is a snippet

type binop = 
  | Plus
  | Minus
  | Times
  | Div

type 'a sized =
  { size : 'a
  ; data : 'a
  }

type addr =
  {  base : sexp
   ; offset : sexp
  }

and exp =
  | Void
  | Const of Int64.t
  | Binop of
      { lhs : sexp
      ; op : binop
      ; rhs : sexp
      }
  | Addr of addr

and sexp = exp sized

type mem = addr sized

Consider that exp type can have Addr variant and when it is sized, it becomes sexp type. Following same procedure, we can generate type mem. It seems that mem should be a subtype of sexp. However, the compiler treat them as different types with no relationship. Is there anyway I can decalre mem as a subtype of sexp?

This provides convenience when we pass parameters. For example, if a function expect a sexp parameter, I can pass var m of mem type and then explicit cast it to sexp through m:>sexp.

There is a similar question, but my case is that sized type has wraped both exp and addr, so I have no idea how to process.

2

Caml, generally speaking, doesn’t have the notion of behavioral sub-typing or casting at all. If you want behavioral subtyping, you need to use OCaml’s classes.

The way to do the same thing which is more idiomatic to OCaml would be to define a functor for the shared functionality of all sized types you wish to reason about, where the input module defines a few basic operations that differ between the two.

This essentially gives you the same kind of code reuse as behavioral subtyping without the need for a type hierarchy. Benefits are that polymorphism is ad-hoc, the code path is more explicit and obvious, and binding is always static. Drawbacks are that it tends to involve a little more boilerplate code than behavioral subtyping.

If that doesn’t float your boat, use classes.

Also, depending what you want to do, it may simply be enough to define functions which work with 'a sized without bothering with functors, but it looks like a functor will probably be the most appropriate thing in this case, so you can define a little wrapper code and add an Addr constructor to your raw addr when you parameterize your functor an never again.

1 Like
3

Yes, but you need to switch to polymorphic variants (which support structural subtyping):

(* polymorphic variants cannot be used with inline records *)
type binop_exp =
  {
    lhs: sexp;
    op: binop;
    rhs: sexp;
  }

and exp =
  [ `Void
  | `Const of int64
  | `Binop of binop_exp
  | `Addr of addr ]

and sexp = exp sized

and mem = [ `Addr of addr ] sized

However, note that generally speaking the convenience afforded by the structural subtyping is not worth the extra complexity that comes with polymorphic variants, so I wouldn’t necessarily suggest to actually go in this direction :slight_smile:

Cheers,
Nicolas

2 Likes
4

Thank you for your solution! This is what I want.

Just curious, what would you suggest to achieve this without polymorphic variants?

5

Thank you for your idea, but I am not sure about the input to the functor. Do I need to define a struct for both exp and addr, and then feed them to a functor sized? If so, how are these two structs related and inferred that addr is a subtype of exp?

1 Like
6

Nothing really: simply use two different types and write an explicit “casting” function to map the subtype to the supertype.

Cheers,
Nicolas

1 Like
7

addr is never a subtype of exp. OCaml just doesn’t work like that. Concrete types (outside of objects) in OCaml have no hierarchy.

In your example Addr of addr represents a subset of the values of exp, but it doesn’t work without the Addr tag. It’s more like Addr of addr is a member of the union exp than a subtype of it.

Using a functor in this context is probably overkill because you are only dealing with two types. In this case, it probably is easier to simply write this and use it at the call-site where necessary:

let mem_to_sexp {size; data} = {size; data = Addr data}

note that I assume size is of type int for simplicity, and because I assume this was a typo on your part. Please forgive me if I’m mistaken.

As for how to use a functor in this context:

(* this is the *module type* which will act as a shim between types you want 
 * to treat as `sexp`. It includes the "casting function" nojb mentions.
 *)
module type SexpWrapper = sig
  type t
  val wrap : t -> sexp
end

(* here are the operations wanted for both sexp and mem *)
module SexpOps(M : SexpWrapper) = struct
  type t = M.t

  let get_exp t = (M.wrap t).data
  let eval t =
    let sexp = M.wrap t in
    failwith "still need to implement eval"
end

module Mem = SexpOps(struct
    type t = mem
    let wrap {size; data} = {size; data = Addr data}
  end)

module Sexp = SexpOps(struct
    type t = sexp
    let wrap = Fun.id
  end)

It’s a lot of code for one operation.

2 Likes
8

Thank you so much for your clear explanation! It is a little bit overkill, but it definitely provides a good example for me in this case. Many thanks!

2 Likes