Motoko compiler bug # polymorphic recursion

[infu]

TL;DR Polymorphic recursion occurs when you try to do something like

type Something<A> = { 
map: <B>( (A) -> B ) -> Something<B> 
}

and is not currently supported. However there is a workaround for what I was trying to do Motoko compiler bug # polymorphic recursion - #13 by infu

---

OOPS! You’ve triggered a compiler bug.

Works:

  public class Something<A>() {
        public func map<B>() : Something<B> {
            Something<B>()
          };
      };

Works:

  public class Something<A>() {
      public func map<B>( f : (A) -> B ) : () {
      };
  };

Combining these two gives error:

  public class Something<A>() {
      public func map<B>(f: (A) -> B) : Something<B> {
        Something<B>()
      };
  };

If it’s a bug, any ideas on how to go around it before it gets fixed ?

Tried with two different motoko versions

Motoko 0.7.0 (source gkg65w0i-1jxsxgpi-jyzd1iws-ci2znrp1)

Fatal error: exception Stack overflow
Raised by primitive operation at Mo_types__Type.rel_typ in file "mo_types/type.ml", line 741, characters 6-81
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
Called from Mo_types__Type.rel_list in file "mo_types/type.ml", line 669, characters 6-38
Called from Mo_types__Type.rel_typ in file "mo_types/type.ml", line 741, characters 6-81
Called from Mo_types__Type.rel_fields in file "mo_types/type.ml", line 761, characters 6-36
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
Called from Mo_types__Type.rel_list in file "mo_types/type.ml", line 669, characters 6-38
Called from Mo_types__Type.rel_fields in file "mo_types/type.ml", line 761, characters 6-36
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
Called from Mo_types__Type.rel_list in file "mo_types/type.ml", line 669, characters 6-38
Called from Mo_types__Type.rel_fields in file "mo_types/type.ml", line 761, characters 6-36
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
Called from Mo_types__Type.rel_list in file "mo_types/type.ml", line 669, characters 6-38
Called from Mo_types__Type.rel_fields in file "mo_types/type.ml", line 761, characters 6-36
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
...

Motoko 0.6.20 (source 640crzw6-q5fr2cc2-j0arj8l2-rfv2v0jh)
Fatal error: exception Stack overflow
Raised by primitive operation at Mo_types__Type.rel_typ in file "mo_types/type.ml", line 725, characters 6-81
Called from Stdlib__list.for_all2 in file "list.ml", line 173, characters 24-31
Called from Mo_types__Type.rel_list in file "mo_types/type.ml", line 653, characters 6-38
Called from Mo_types__Type.rel_typ in file "mo_types/type.ml", line 725, characters 6-81
Called from Mo_types__Type.rel_fields in file "mo_types/type.ml", line 745, characters 6-36
...

@claudio

[ggreif]

This smells like a known bug, Segmentation fault: 11 when trying to define a method which returns a new “instance” of a class · Issue #3057 · dfinity/motoko · GitHub. There is a duplicate too: Stack overflow in type checking · Issue #3135 · dfinity/motoko · GitHub.

[infu]

I see. I want to make a library which can be chained like Somelib(…).map(x => x +2).concat(x => …).another(…)
I guess I have to give up on the idea, or this can be fixed soon?

[icme]

Have you tried using something like the functor pattern? - I used it in motoko-color

As long as all of those map/concat methods are in your object it should work.

[infu]

Thanks for the tip! Icme saves the day

[infu]

Unfortunately, it’s a suboptimal solution.
I could use something like this, but that <A> isn’t working there

I tried replacing it with <Any> and returning the proper type later

Then trying to use it like this:

Gives error Pattern of type Nat cannot consume expected type Any

So the working solution is to type <FromType, ToType> in every function.

…

This could work, let’s see how it plays out when I add more code

Trying to create local types inside a function…

Also gives error references type parameter X__10 from an outer scope

After adding some more code and stumbling on things like expression of type B__13 cannot produce expected type B__14 I am giving up. I think it’s not possible to replace the original class pattern with object with functions. Not to mention the module code looks less clean. You will probably end up passing bogus transforming functions all around like

Just to keep the type checking happy. This is where I realized I will also need to add transformations everywhere. So this is the new code (not working and missing probably 10 more lines of code doing weird stuff.

vs the original

But hey, it was a good waste of time

[infu]

If you have been wondering what I am trying to do → Reactive programming (Observables/ ReactiveX/ RxJS like library)

So this code can work:

[claudio]

Yep, this is related to Segmentation fault: 11 when trying to define a method which returns a new “instance” of a class · Issue #3057 · dfinity/motoko · GitHub

We don’t know how to support polymorphic recursion/non-regular types in Motoko’s type system but don’t have a decent check to rule it out yet either.

If you can, I’d try to separate the operations that require different instantiations of the recursive type from the definition of that recursive type itself. I.e. try to make map a static function that takes an observable rather than including it as a member of the observable type.

[paulyoung]

@infu

I am trying to do → Reactive programming (Observables/ ReactiveX/ RxJS like library)

I wrote this a while back in case it’s of any interest.

(Git committer/author info lost during open sourcing)

[infu]

That’s helpful! Learned a few things. No operators tho, they are causing the polymorphic recursion.

When I try to put them outside, usage will look like this. Loses readability and that’s a deal breaker for the intended purposes (having something easy to use like the “jQuery for smart contracts”)

There is probably still a workaround, just don’t know it yet.

Also tried this

And it also produced the same stack overflow error.

My reasoning - If ReactiveX is the best way of handling async problems and IC smart contract features are mainly async problems, then maybe it will be the perfect tool for the job.

[ggreif]

You are unnecessarily eta-expanding:

func(x) = Nat16.fromInt x

is equivalent to Nat16.fromInt.

(just commenting)

[infu]

Thanks for noting. I will be happy to know if you see anything that can be done better in my code. Usually, I find these tricks in someone else’s code.

I got it to work this way. All the types are known in advance and placed as variants.

But it kind of loses the benefits of the type-checking system, which is awesome. (I can put whatever #variant I want and the compiler won’t mind. Maybe it’s because I didn’t fully wire it all.

This shorter version looks neat

[infu]

I got to this, which is actually looking pretty simple/good and is the closest to chaining interface I could get.

Working code:

let ob = Observable<Nat>( func (subscriber) {
    subscriber.next(3);
    subscriber.next(5);
    subscriber.next(12);
});

pipe3(
    ob,
    map( func (val : Nat) : Nat16 {
         Nat16.fromNat(val + 10)
    }),
    map( func (val : Nat16) : Nat {
         Nat16.toNat(val + 30)
    })
).subscribe( {
    next = func (v) {
    Debug.print("next " # debug_show(v));
    }
});

Output:
next 43
next 45
next 52

Module here Attempt to implement ReactiveX in Motoko with "chaining" · GitHub

Pipe function is outside of the class and you need to change its name whenever you add more parameters pipe2, pipe3, pipe4, etc.