Help with existential type example from Cake Solutions

[Josh Hagins]

In their blog post on the subject, Cake Solutions presents the following snipped as an example of existential types in action:

trait VirtualMachine[A] {
  def compile: A
  def run: A => Unit
}


case class SimpleVirtualMachine[A](compile: A, run: A => Unit)
  extends VirtualMachine[A]


def helloWorldVM(s: String) = SimpleVirtualMachine(s, println)
def intVM(i: Int) = SimpleVirtualMachine(i, println)


def compileAndRun(vm: VirtualMachine[A] forSome {type A}) {
  vm.run(vm.compile)
}

However, upon entering the `compileAndRun` method into the REPL, I got the following error:

<console>:12: error: type mismatch;
 found   : (some other)A(in value vm)
 required: A(in value vm)
         vm.run(vm.compile)
                   ^

What's going wrong here? My interpretation of the error message is that the return type of `A` of `vm.compile` is not necessarily the same type `A` that is required by `vm.run`. How is this possible?

[Josh Hagins]

To add, I get the same kind of error when using the more common wildcard type syntax in place of `forSome`.

[Stephen Compall]

On June 29, 2015 3:42:05 PM EDT, Josh Hagins <hagin...@gmail.com> wrote:
>def compileAndRun(vm: VirtualMachine[A] forSome {type A}) {
> vm.run(vm.compile)
>}
>
>However, upon entering the `compileAndRun` method into the REPL, I got
>the
>following error:
>
><console>:12: error: type mismatch;
> found : (some other)A(in value vm)
> required: A(in value vm)
> vm.run(vm.compile)
> ^
>
>What's going wrong here? My interpretation of the error message is that
>the
>return type of `A` of `vm.compile` is not necessarily the same type `A`
>
>that is required by `vm.run`. How is this possible?

You can add a type parameter to compileAndRun and it will be equally invokable. See section "Existentials are much better" of http://typelevel.org/blog/2015/02/26/rawtypes.html for a few examples.

--
Stephen Compall
If anyone in the MSA is online, you should watch this flythrough.

[Josh Hagins]

Right, it works if compileAndRun also has a type parameter, but the linked blog post claims that this is bad design, since compileAndRun shouldn't know or care about VirtualMachine's reified type. Not sure that I agree with this claim, but are they wrong? Would this snippet compile with an older version of Scala (I'm running 2.11.7)? 

[Stephen Compall]

On June 29, 2015 5:00:39 PM EDT, Josh Hagins <hagin...@gmail.com> wrote:
>Right, it works if compileAndRun also has a type parameter, but the
>linked
>blog post claims that this is bad design, since compileAndRun shouldn't
>
>know or care about VirtualMachine's reified type. Not sure that I agree
>
>with this claim, but are they wrong?

Yes, they're wrong. Their premise is faulty: adding the type parameter [A] to compileAndRun doesn't give the body the power to find out what A is. Even in the GADT case, you can no more *or less* deduce the value of the type parameter in the existential than in the parameterized version.

[Josh Hagins]

Gotcha. So I get that nothing is lost in providing compileAndRun with a type parameter, but why is it necessary? In what scenario would the return type of vm.compile not match the required type of vm.run in the original snippet, assuming it compiled?

[Adriaan Moors]

This is a nice opportunity to explore the relationship between universal and existential quantification -- two sides of the same coin, really.

I claim these definitions are equivalent:

scala> def compileAndRun(vm: VirtualMachine[A] forSome {type A}): Unit = vm match { case vm: VirtualMachine[e] => vm.run(vm.compile) }

compileAndRun: (vm: VirtualMachine[_])Unit

scala> def compileAndRun[A](vm: VirtualMachine[A]): Unit = vm.run(vm.compile)

compileAndRun: [A](vm: VirtualMachine[A])Unit

The first one says, "if you pass me a VirtualMachine[A], for some hidden type A, I can produce a Unit".

The second definition: "for all types A, if you give me a VirtualMachine[A], I can produce a Unit". Since A is not further constrained in any way, compileAndRun can never learn what A is, so it is effectively hidden from its implementation.

The compiler unfortunately isn't good at inferring types when existential types are involved, which requires us to "look inside" the existential package in the first variation.

The pattern match gives the hidden type a name and a scope (without revealing what it is), giving the compiler a handle on how vm.run and vm.compile's types relate.

If you're designing a class where you expect existentials to be used for one of its type parameters, use a type member instead:

scala> trait VirtualMachine {

     |   type A

     |   def compile: A

     |   def run: A => Unit

     | }

defined trait VirtualMachine

scala> def compileAndRun(vm: VirtualMachine): Unit = vm.run(vm.compile)

compileAndRun: (vm: VirtualMachine)Unit

(now our existential type `e` from above is called `vm.A`)

cheers

adriaan

PS: Another way to look at the potential differences between both definitions, is using :javap.

Both signatures erase to (LVirtualMachine;)V. Their bytecode differs only to the extent that the pattern matcher doesn't optimize the null check away (and a sub-optimal check that indeed an (erased) Unit was produced...).

scala> class Compare {

     |          def compileAndRunX(vm: VirtualMachine[A] forSome {type A}): Unit = vm match { case vm: VirtualMachine[e] => vm.run(vm.compile) }

     |          def compileAndRunPoly[A](vm: VirtualMachine[A]): Unit = vm.run(vm.compile)

     | }

defined class Compare

scala> :javap -vc Compare

<...>

  public void compileAndRunX(VirtualMachine<?>);

    descriptor: (LVirtualMachine;)V

    flags: ACC_PUBLIC

    Code:

      stack=3, locals=2, args_size=2

         0: aload_1

         1: ifnull        26

         4: aload_1

         5: invokeinterface #13,  1           // InterfaceMethod VirtualMachine.run:()Lscala/Function1;

        10: aload_1

        11: invokeinterface #17,  1           // InterfaceMethod VirtualMachine.compile:()Ljava/lang/Object;

        16: invokeinterface #23,  2           // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;

        21: checkcast     #25                 // class scala/runtime/BoxedUnit

        24: pop

        25: return

        26: new           #27                 // class scala/MatchError

        29: dup

        30: aload_1

        31: invokespecial #31                 // Method scala/MatchError."<init>":(Ljava/lang/Object;)V

        34: athrow

<...>

  public <A extends java.lang.Object> void compileAndRunPoly(VirtualMachine<A>);

    descriptor: (LVirtualMachine;)V

    flags: ACC_PUBLIC

    Code:

      stack=2, locals=2, args_size=2

         0: aload_1

         1: invokeinterface #13,  1           // InterfaceMethod VirtualMachine.run:()Lscala/Function1;

         6: aload_1

         7: invokeinterface #17,  1           // InterfaceMethod VirtualMachine.compile:()Ljava/lang/Object;

        12: invokeinterface #23,  2           // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;

        17: pop

        18: return

      LocalVariableTable:

        Start  Length  Slot  Name   Signature

            0      19     0  this   LCompare;

            0      19     1    vm   LVirtualMachine;

      LineNumberTable:

        line 13: 0

    Signature: #61                          // <A:Ljava/lang/Object;>(LVirtualMachine<TA;>;)V

--
You received this message because you are subscribed to the Google Groups "scala-user" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-user+...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.