Simple expression is reportedly recursive in parser combinators

Question

Guess what is the result of this compilation?

import scala.util.parsing.combinator._

object ExprParser extends JavaTokenParsers {
    lazy val literal = int  
    lazy val int = rep("0")
}

Compiler says that int is recursive and asks for the type of it. My experiment says that the core of the recursion is hidden in the declaration of the literal! Remove it and you will see that recursion is gone!

Answer 1

It is relevant here that JavaTokenParsers defines something called literal.

And rep("0") is actually rep(literal("0")) (literal is an implicit conversion from String to Parser[String]).

But the literal in JavaTokenParsers takes an argument, and yours doesn't. So you might expect that yours would simply overload, and not override, and there would be no conflict — and no mutual recursion between int and literal.

And in fact, if you supply explicit types:

object ExprParser extends JavaTokenParsers {
  lazy val literal: Parser[List[String]] = int 
  lazy val int: Parser[List[String]] = rep("0")
}

This flies by the compiler just fine.

So why is the explicit-return-type rule for recursion being triggered when the return types are omitted?

This is a rather subtle question, I think. I'm not confident I know exactly what's going on here. I cannot find specific language in the Scala Language Specification that covers it.

My best guess is that at the time the explicit-return-type rule is triggered, the compiler is still at a relatively early phase where it hasn't yet resolved exactly what or isn't an overload or an override. Not having the return types yet, it has to proceed based on partial information about the types involved.

But it does know that your definition of literal involves the name int, and your definition of int involves the name literal, and so it considers that recursive and gives up.