This post is about implementing open recursion with OCaml modules as opposed to classes. It’s a complete hack and a terrible idea—but it’s fun!

1 What’s open recursion?

Open recursion, in the context of object-oriented programming (OOP), refers to the ability of a method on an object to call another method on the same object (“self”), with the implementation of the second method not being fixed. So, for example: 

class Greeter:
    def greet(self):
        return 'Hello, ' + self.addressee()

    def addressee(self):
        return 'World'

g = Greeter()
print(g.greet())

Hello, World

Now, if we derive a subclass from Greeter and override one of its methods: 

class Greeter:
    def greet(self):
        return 'Hello, ' + self.addressee()

    def addressee(self):
        return 'World'

class NameGreeter(Greeter):
    def __init__(self, name):
        self.name = name

    def addressee(self):
        return self.name

g = NameGreeter('Bob')
print(g.greet())

Hello, Bob

So, overriding the addressee method changed the behavior of the greet method. In other words, the greet method from the parent class called the addressee method of the subclass, even though that method doesn’t even “know” that the NameGreeter class exists.

2 Use cases

One salient use case for open recursion is in Abstract Syntax Tree (AST) transformers. This arises in the land of OCaml preprocessors, where syntax extensions are implemented by defining a class whose methods correspond to the mapping functions over different kinds of OCaml AST nodes.

The object system supports open recursion, which allows a transformer to be defined by inheriting from a default base class, whose methods are no-ops (they return the input AST node). Overriding just the method for the type of AST node the syntax extension is interested in works correctly because the inherited methods will call the new implementations instead.

You can read more about how open recursion facilitates writing AST transformers, and more generally about writing ppx’s: see whitequark’s excellent blog post.

3 Translating to OCaml

Here’s the above Python code translated into OCaml: 

class greeter = object (self)
  method greet = "Hello, " ^ self#addressee
  method addressee = "World"
end

class name_greeter name = object (self)
  inherit greeter as super
  method! addressee = name
end

let g = new name_greeter "Bob"
let () = print_endline g#greet

Hello, Bob

Note the use of method! instead of method in the subclass. Akin to the @Override annotation in Java, it asks the compiler to check that you are overriding an existing method. If not, the compiler will issue a warning, in case you have misspelled the method name, for example.

4 Module time

4.1 It doesn’t work!

Now, there’s a common feeling in the OCaml community that the OOP part of the language is largely subsumed by the module system, which is a powerful and versatile abstraction tool. One of the main claims that OOP still has over modules is that open recursion is not possible with modules. For example, the analogous code written using modules does not have the desired behavior: 

 1: module Greeter = struct
 2:   type t = unit
 3: 
 4:   let create () = ()
 5:   let addressee _t = "World"
 6:   let greet _t = "Hello, " ^ addressee _t
 7: end
 8: 
 9: module Name_greeter = struct
10:   type t = { name : string }
11:   include (Greeter : module type of Greeter with type t := Greeter.t)
12:   let create ~name = { name }
13:   let addressee t = t.name
14: end
15: 
16: let g = Name_greeter.create ~name:"Bob"
17: let () = print_endline (Name_greeter.greet g)

Hello, World

Because the definition of greet refers to the lexical binding of addressee in force at the location of the definition, i.e., line 5. That means that overriding the definition of addressee has no effect except on the behavior of calling addressee itself.

4.2 Recursive module shenanigans

It turns out we can accomplish open recursion using the module system, but we need to structure our types a bit differently than using the straightforward classes-to-modules translation.

First, we define a Greeter signature for the overall signature of the class. Then, add the base “class” Greeter as a recursive functor that takes a module of its own output type as input. That is to say, 

module type Greeter = sig
  type t
  type ctor

  val create : ctor -> t
  val addressee : t -> string
  val greet : t -> string
end

module Greeter (Self : Greeter) :
  Greeter with type t = Self.t and type ctor = Self.ctor = struct
  type t = Self.t
  type ctor = Self.ctor

  let create = Self.create
  let addressee _t = "World"
  let greet t = "Hello, " ^ Self.addressee t
end

And now we can define the Greeter “class” as the Greeter functor instantiated on itself: 

module rec G : (Greeter with type t = unit and type ctor = unit) = Greeter (struct
    type t = unit
    type ctor = unit

    include (G : Greeter with type t := unit and type ctor := unit)

    let create () = ()
  end)

let () =
  let g = G.create () in
  print_endline (G.greet g)
;;

Hello, World

And now, we define the “subclass” Name_greeter: 

type 'super name_greeter =
  { super : 'super
  ; name : string
  }

module Name_greeter (Self : Greeter) :
  Greeter with type t = Self.t and type ctor = Self.ctor = struct
  type t = Self.t
  type ctor = Self.ctor

  module rec Super : (Greeter with type t := t and type ctor := ctor) = Greeter (Self)

  let create = Self.create
  let addressee = Self.addressee
  let greet (t : t) = Super.greet t
end

module rec NG : (Greeter with type t = unit name_greeter and type ctor = unit * string) =
  Name_greeter (struct
    include NG

    let create (super, name) = { super; name }
    let addressee t = t.name
  end)

let g = NG.create ((), "Bob")
let () = print_endline (NG.greet g)

Which prints: 

Hello, Bob

Success! But at what cost…