Is there a way to achieve a mutually recursive ADT in Kotlin?

Question

I am currently trying to learn about language grammar and parsers, and trying to implement stuff in Kotlin as I go. I have a small description here in Backus–Naur form for the definition of type:

<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' 

Now this SEEMS to me that its some sort of ADT where the definitions are mutually recursive, and you can like, 'spread' the definitions in the sense that if

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

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

Then the definition of <a> would 'spread' within the definition of <b>, and <b> would be able to take on values of red green or blue.

I tried to represent this in Kotlin using the sealed classes, like so:

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()
    }
}

But I could not figure out how to emulate that 'spread' functionality. The best I could come up with is to have wrapper classes around the different possibilities that can be spread.

That would be fine if this was the scope of the entire BNF ruleset, but what if there are many, many, many more such definitions that require this 'spread' functionality, and so a whole bunch of these definitions are interlinked like that. That would a lot of wrapper classes.

Is there a better way to represent such definitions as Kotlin data types?

Answer 1

Thanks to the comment by Sweeper, I was able to figure it out. What code did I want to write that I could not, with my current implementation? Well, I couldn't write statements such as the following:

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

Which is fundamentally the problem. The BNF description, if somehow implemented, would imply I COULD in fact make such statements. So I decided to look at the BNF and draw a diagram to represent all the "is a" and "has a" relationships described, which I got the following:

The dashed lines are "has a", and the solid lines are "is a". And after analysing it for a bit, I realised that some types have multiple outgoing "is-a" arrows. This means that they are doing multiple inheritance. Thus I decided to model this using sealed interfaces (instead of classes) since this is the only way to do multiple inheritance in Kotlin.

The resulting code I have is as follows:

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 {
        data object Pair: PairElementType
    }
}

Now, with that, I now CAN make statements such as

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

Hopefully, as I scale up and continue implementing the BNF spec, this approach won't run into any dead ends.

Answer 2

I found a gist with this cool answer:

sealed interface Z
sealed interface S<T>

sealed interface SStackLang<T>{
    object SBegin:SStackLang<Z>
    data class SPush<T>(val intVal:Int,val old:SStackLang<T>):SStackLang<S<T>>
    data class SAdd<T>(val old:SStackLang<S<S<T>>>):SStackLang<S<T>>
}

infix fun<T> SStackLang<T>.push(intVal: Int):SStackLang<S<T>> = SStackLang.SPush(intVal,this)

operator fun<T> SStackLang<S<S<T>>>.unaryPlus():SStackLang<S<T>> = SStackLang.SAdd(this)


fun main(){
    val init = SStackLang.SBegin
    val addOne = init push 2
    val addTwo = addOne push 2
    val addThree = addTwo push 3
    val popThenAdd = +addThree
    println(popThenAdd)
    val popThenAddAgain = +popThenAdd
    // error
    // val triggerErr = +popThenAddAgain
}

It goes beyond the initial question with even cross types, sums, products and even operators, please give it a check.

The orginal gist can be found at https://gist.github.com/ruxiliang/b7bf70e3508785e6499af09e8d4e98f4

Thank you ruxiliang for your help