How to avoid recursive type-checking problem in a tree-walking generator?

Support
1

I want to create a tree-walker based on the following types:

abstract class Node(val kind: String)

class Leaf(kind: String, val payload: Any?) : Node(kind)

class Unary(kind: String, val operand: Node) : Node(kind)

class Binary(kind: String, val left: Node, val right: Node) : Node(kind)

I tried with this code:

fun nodeWalker(start: Node) = sequence<Any?> {
    fun visit(node: Node) = sequence<Any?> {
        if (node is Leaf) {
            yield(node.payload)
        }
        else if (node is Unary) {
            for (uit in visit(node.operand)) {
                yield(uit)
            }
        }
        else if (node is Binary) {
            for (lit in visit(node.left)) {
                yield(lit)
            }
            for (rit in visit(node.right)) {
                yield(rit)
            }
        }
    }

    visit(start).forEach {
        yield(it)
    }
}

However, this fails to compile, giving the error:

Error:(15, 24) Type checking has run into a recursive problem. Easiest workaround: specify types of your declarations explicitly

That’s the visit call in the for (uit in visit(node.operand)) { line. How can I avoid this error? Which declarations is the error message referring to? Adding a type like so: uit: Any? didn’t make any difference.

The code is at

2

As it says, just specify the type:

fun visit(node: Node): Sequence<Any?>

1 Like
3

Ah - OK, thanks. I see now.

4

What is the fixed version of this code?

fun visit(node: Node): Sequence<Any?> also produces errors.

5

You need to use fun visit(node: Node): Sequence<Any?> = sequence { instead.
The problem is that you call visit within the sequence block. Apparently the kotlin compiler is not smart enough the resolve the return type of visit before checking the sequence block. This is probably something that can be improved in the future.

1 Like
6

That’s great thank you for clarification.

How would the TreeWalker walk if there were a node with N children? Eg:

class Multi(kind: String, val operands: List) : Node(kind)

I suppose this would not be in the spirit of a “tree” structure but anyway, a practical possibility.