How do I avoid infinite recursion in a parser combinator

The answer came from Frerich on the elixir slack.

I’d gotten too far into think about the parsing aspect of the problem and didn’t see the purely functional aspect - eager vs lazy evaluation.

The solution in the end is simple, introduce an intermediate parser that sits between value() and list()

My first use of a macro in Elixir:

defmacro lazy(parser) do
    quote do
      Parser.new(
        :lazy,
        fn ctx -> Parser.invoke(unquote(parser), ctx) end
      )
    end
  end

Now I can write:

def value() do
  choice([
    number_value(),
    boolean_value(),
    string_value(),
    lazy(list_value())
  ])
)

And the recursion is broken.

Congradulations on writing your first macro!

Indeed, this is one of the places where lazy evaluation makes an algorithm simpler.
Situations like this, where infinite recursion happens while building an intermediate structure for things that ‘may’ exist to an unknown (but finite) depth, come up from time to time.

The problem definitely is related to left-recursion. One could see it as left-recursion happening already before starting the parsing process itself.

In this particular example, you might be able to get away with a definition of lazy as a function (rather than a macro) like this:

def lazy(parser_producing_fun) do
  Parser.new(:lazy, fn cx -> Parser.invoke(parser_producing_fun.(), ctx) end
end

However, you’d need to call it as lazy(&list_value/0 instead of lazy(list_value()) so it alters the way it has to be used a little. Your choice

I recently finally took the time to watch that video myself.

I am wondering if I’m confusing stuff when I’m thinking that Saśa Jurić touches on the topic in the video already - starting at around 49:57min he talks about the problem of a subquery being its own select_statement() parser function.

He ends up evaluating the term lazily, just like you ended up doing, so I think it is the same situation you were dealing with?

I came here to say exactly this The relevant part of the talk starts here. In the talk I opted for the function version (basically what @Qqwy suggests in the earlier response).

Ah, it is a while since I watched the video and I forgot that Saša covered the problem in it. Thanks anyway! Would have saved me a lot of bother if I had remembered that!

I did think about the function approach as an alternative but (esp in a case where the deferred parser may take arguments) I thought the macro was likely to be cleaner at a cost of being slightly less clear that something unusual is going on.

Perhaps I might change the name to LAZY or lazy! to make it clearer there’s something to take note of.

Yes, it’s kind of a left-recursion at the Elixir level. In my Ergo docs I’m calling this “Eager recursion” to distinguish from left-recursion in the grammar itself.