Kotlin中有没有办法实现相互递归的ADT？

Question

我目前正在尝试学习语言语法和解析器，并尝试在 Kotlin 中实现一些东西。我这里有一个关于类型定义的巴科斯-诺尔形式的小描述：

<type>           ::= <base-type>
                   | <array-type>
                   | <pair-type>

<base-type>      ::= 'int'
                   | 'bool'
                   | 'char'
                   | 'string'

<array-type>     ::= <type> '[' ']'

<pair-type>      ::= 'pair' '(' <pair-elem-type> ',' <pair-elem-type> ')'

<pair-elem-type> ::= <base-type>
                   | <array-type>
                   | 'pair' 

现在在我看来，它是某种 ADT，其中定义是相互递归的，并且您可以喜欢“传播”定义，因为如果

<a> ::= 'red'
      | 'green'

<b> ::= <a>
      | 'blue'

然后

<a>

的定义将在

<b>

的定义内“传播”，并且

<b>

将能够采用

red

green

或

blue

的值。

我尝试在 Kotlin 中使用密封类来表示这一点，如下所示：

sealed class Type {
    sealed class BaseType: Type() {
        data object Int: BaseType()
        data object Bool: BaseType()
        data object Char: BaseType()
        data object Str: BaseType()
    }
    class ArrayType(type: Type): Type()
    class PairType(fst: PairElementType, snd: PairElementType): Type()
    sealed class PairElementType {
        data object Pair: PairElementType()
        class BaseTypeElement(type: BaseType): PairElementType()
        class ArrayTypeElement(type: ArrayType): PairElementType()
    }
}

但我不知道如何模拟“传播”功能。我能想到的最好的办法就是围绕可以传播的不同可能性提供包装类。

如果这是整个 BNF 规则集的范围，那就没问题了，但是如果有很多很多这样的定义需要这种“传播”功能，那么一大堆这些定义就这样相互关联呢？那将有很多包装类。

是否有更好的方法来表示 Kotlin 数据类型等定义？

Answer 1

感谢Sweeper的评论，我终于弄清楚了。哪些代码是我想编写但在当前的实现中无法编写的？好吧，我无法写出如下的语句：

val a: Type.PairElementType = Type.BaseType.Int

这就是根本问题。 BNF，如果以某种方式实现，将意味着我实际上可以做出这样的声明。所以我决定看看 BNF 并画一个图来表示所有描述的“是一个”和“有一个”关系，我得到了以下结果：

虚线是“has a”，实线是“is a”。经过一番分析后，我意识到某些类型有多个传出的“is-a”箭头。这意味着他们正在进行多重继承。因此，我决定使用密封接口（而不是类）对此进行建模，因为这是在 Kotlin 中进行多重继承的唯一方法。

我得到的结果代码如下：

sealed interface Type {
    sealed interface BaseType: Type, PairElementType {
        data object Int: BaseType
        data object Bool: BaseType
        data object Char: BaseType
        data object Str: BaseType
    }
    class ArrayType(type: Type): Type, PairElementType
    class PairType(fst: PairElementType, snd: PairElementType): Type
    sealed interface PairElementType: AST {
        data object Pair: PairElementType
    }
}

现在，我现在可以做出如下声明：

val a: Type.PairElementType = Type.BaseType.Int

希望，当我扩大规模并继续实施 BNF 规范时，这种方法不会遇到任何死胡同。