Recursive types and values

[AttilaMihaly]

We ran into an interesting issue today. We were trying to keep track of type and value dependencies using a directed acyclic graph and realized that recursive types and values need special handling. The problem is that a DAG as the name suggests cannot have cycles. This makes sense for dependencies in general because circular dependencies usually signal an issue except for recursive types and values where the cycle is intentional.

The Morphir IR currently does allow recursive types and values and while most business models don't rely on those heavily the IR itself does and I can imagine valid business use cases that would rely on at least recursive types. So not supporting recursion could introduce significant limitations.

Assuming that we don't want to completely eliminate recursion we can still limit it to a bounded scope where it's more manageable and compatible with our desire to avoid circular dependencies in general. Elm does this by only allowing recursion within a module. We should do the same but that still leaves the complexity of dealing with recursive vs non-recursive definitions to the tooling. Making it more explicit would make tool developer's life much easier.

We already did something similar with recursive let bindings:
https://github.com/finos/morphir-elm/blob/2d8a4b444606b4f260875a23c071ca3641b162e3/src/Morphir/IR/Value.elm#L210-L211

Here, we differentiate recursive bindings from regular non-recursive bindings which are topologically ordered for easier processing.

Should we apply the same approach on a module level for types and values so that we have RecursiveTypeDefinition and RecursiveValueDefinition?

[AttilaMihaly]

The next question that arises is whether to allow mutual (or indirect) recursion? Direct recursion is slightly simpler to represent because there's a single entry point. With mutual recursion there's multiple entry points so you cannot refer to the whole structure with a single name so it's more challenging to represent. In a dictionary for example you will have duplicate values.

I think we should not allow mutual recursion or at least limit it to a single entry point.

[DamianReeves]

Do you mind adding an example of mutual recursion?

[AttilaMihaly]

You mean made up example or a valid one that makes sense?

Here's a made up one for recursive values:

foo a =
  bar a

bar a =
  foo a

Mutually recursive types:

type Foo = Foo Bar

type Bar = Bar Foo

Of course, neither of these actually make sense and they are infinite.

[DamianReeves]

I asked for examples because I could never actually think of a good meaningful example. I wonder if that is telling about the need for this 🤔 .

[AttilaMihaly]

One realistic example would be if you had a recursive structure with two or more types of nodes mixed together that you want to traverse but in certain cases still want to differentiate. Say data and logic:

type Data 
    = IntData Int 
    | ListData (List Value)

type Logic
    = Var String
    | IfThenElse Value Value Value

type Value 
    = Data Data
    | Logic Logic

When processing this data structure you will end up with mutually recursive functions as well.

So there are valid use-cases, the difficult question is how relevant are they?

To be honest, structuring the Morphir IR like the above would make a lot of sense :)