Relaxing the mutual recursion syntax?

Hey there!

First I would like to thank the ReScript team for building such a pleasant language for the web.

Since ReScript aims at being more familiar to JS devs than Reason was, are there ideological / technical (type inference?) reasons why OCaml’s “let rec … and … and” syntax
is used instead of allowing mutual recursion freely?

Relaxing the syntax would be particularly useful for mutually recursive modules split into different files and would certainly make the transition from JS/TS easier.

Thanks for your time and keep up the good work :slight_smile:

1 Like

I believe this is very unlikely for a variety of reasons. (I’m not an expert on how the compiler works, so anyone feel free to correct me or clarify this.) There are technical as well as theoretical reasons for why recursion is opt-in. The use case you mention specifically, using mutual recursion across file-level modules, is impossible AFAIK. Mutually recursive modules are already one of the most complicated parts of the compiler, which is why they are almost always discouraged.

If you’re porting mutually recursive JS functions from different files, it would be much easier to just put the ReScript versions together in one module. Another general-purpose way to cut a recursive knot is to use callback arguments, so one function can send itself as a callback to another function, and vice-versa.

As far as value-level mutual recursion (let rec ... and), I don’t think it would work as opt-out instead of opt-in. If everything was mutually recursive by default, then you would lose core features like shadowing, and type inference would be worse.

One way to understand ReScript code is that every let-binding creates a new scope. Just like a manual { } local scope, any expression is able to “see” the values in the scopes outside of its own, but can’t “see” into its inner scopes. In code like this:

let x = 1
let x = x + 1

both x values coexist in their own scopes. The first x can’t see the second x, but the second can see the first. (And each x can’t see itself, either.)

When you use let rec ... and you’re telling the compiler “don’t create a new scope after this binding.” So then the values will all share the same scope, and thus be able to see each other. This has tradeoffs, though. Our previous example can’t compile if it’s recursive (due to shadowing). let rec x = 1 and x = x + 1 raises a compile error.

I’m sure someone else can explain the technical aspects better than I can, but I hope that somewhat explains why recursion works the way that it does.

And this part is just my opinion, but I believe that it’s better to think of this as a feature rather than a limitation. One core selling point of FP languages is that they encourage simple, elegant solutions. They make it easier to write “good” code and harder to write “bad” code (as subjective as that may be). Mutual recursion has its place, but it makes your code more complex and harder to maintain. Even when I’m writing JS, I don’t want to spread mutually-recursive functions across different files. If you only enable it when it’s necessary, you’ll help keep your code a lot cleaner and more readable (for both humans and the compiler).

9 Likes

Thanks for your comprehensive explanation :slightly_smiling_face:

I agree that mutually recursive definitions should be kept together for readability even more if it simplifies the type inferencer significantly.

For the few cases where mutual recursion is necessary, notably when traversing mutually recursive types. I can see three different ways of solving the dependencies:

  1. Use mutually recursive modules directly (this requires typing the modules)
module type display = {
  type t
  let show: t => string
}

module rec Stmt: display = {
  type t = ExprStmt(Expr.t) | LetStmt(string, Expr.t)

  let show = (s: Stmt.t): string =>
    switch s {
    | ExprStmt(expr) => Expr.show(expr)
    | LetStmt(x, rhs) => `let ${x} = ` ++ Expr.show(rhs)
    }
}

and Expr: display = {
  type rec t =
    | IntConst(int)
    | BlockExpr(array<Stmt.t>, option<t>)

  let rec show = (e: t): string =>
    switch e {
    | IntConst(n) => Int.toString(n)
    | BlockExpr(stmts, retExpr) =>
      stmts->Array.joinWith(";\n", stmt => Stmt.show(stmt)) ++
        retExpr->Option.mapWithDefault("", show)
    }
}
  1. Explicitly pass dependencies as arguments as you have mentioned
type rec expr =
  | IntConst(int)
  | BlockExpr(array<stmt>, option<expr>)
and stmt = ExprStmt(expr) | LetStmt(string, expr)

module Stmt = {
  type t = stmt

  let show = (s: stmt, showExpr: expr => string): string =>
    switch s {
    | ExprStmt(expr) => showExpr(expr)
    | LetStmt(x, rhs) => `let ${x} = ` ++ showExpr(rhs)
    }
}

module Expr = {
  type t = expr

  let rec show = (e: expr): string =>
    switch e {
    | IntConst(n) => Int.toString(n)
    | BlockExpr(stmts, retExpr) =>
      stmts->Array.joinWith(";\n", stmt => Stmt.show(stmt, show)) ++
        retExpr->Option.mapWithDefault("", show)
    }
}
  1. “Linearize” or flatten mutually recursive functions into one module
module Ast = {
  type rec expr =
    | IntConst(int)
    | BlockExpr(array<stmt>, option<expr>)
  and stmt = ExprStmt(expr) | LetStmt(string, expr)

  let rec showExpr = (e: expr): string =>
    switch e {
    | IntConst(n) => Int.toString(n)
    | BlockExpr(stmts, retExpr) =>
      stmts->Array.joinWith(";\n", showStmt) ++ retExpr->Option.mapWithDefault("", showExpr)
    }

  and showStmt = (s: stmt): string =>
    switch s {
    | ExprStmt(expr) => showExpr(expr)
    | LetStmt(x, rhs) => `let ${x} = ` ++ showExpr(rhs)
    }
}

// create aliases
module Expr = {
  type t = Ast.expr
  let show = Ast.showExpr
}

module Stmt = {
  type t = Ast.stmt
  let show = Ast.showStmt
}

Which approach do you think would be easiest to maintain / is the most readable / is the most idiomatic?

I prefer the third style by far. Not only is it easier to read & understand, but it will also be easier to maintain.

I believe recursive modules should always be a last resort, and arguably never used at all. The fact that the language itself makes them difficult to use is a signal that they should be avoided.

3 Likes

Right, this is the approach I have been using so far but I wasn’t sure it was recommended.

Thanks again for your feedback!