Path-dependent types: accessing outer class

Question
1

Following graph/node example from official docs, I want to access the graph given a node. Example without using path-dependent types:

object NoPDT {
  class Graph {
    def useNode(node: Graph.Node) = ???
  }
  object Graph {
    class Node(val graph: Graph)
  }

  // access graph given a node
  def useNode(node: Graph.Node) = node.graph.useNode(node)
}

Attempts to use path-dependent types:

object PDT {
  class Graph {
    class Node {
      def graph = Graph.this
    }
    def useNode(node: Node) = ???
  }

  // Attempt 1: does not work
  def useNode(node: Graph#Node) = node.graph.useNode(node) 


  // Attempt 2: works but needs cast
  def useNode(node: Graph#Node) = node.graph.useNode(node.asInstanceOf) 


  // Attempt 3: kind of works but needs extra parameter, see below
  def useNode[G <: Graph](graph: G, node: graph.Node) = graph.useNode(node) 

  val graph = Graph()
  val node = graph.Node()

  // works but defies the point of accessing outer class from inner
  useNode(graph, node)
  // does not work
  useNode(node.graph, node)
}

Based on these experiments, my conclusion is that there is no way to access outer class without a cast. Is that correct, or am I missing something?

2

The point of path dependant types is that there is a new Node type for each and every instance of Graph
Thus, it is impossible to talk about the Node type without a Graph value.

Thus, may I ask, what were you trying to solve here?

3

This is where the compiler starts losing track of what belongs to what.

For path-dependent types it’s very important that the path be stable. So, for example, you can’t use a var in a path-dependent type because the compiler isn’t confident when the var might change. Most of path-dependency is built around vals and the equivalent (like function arguments).

So you need some type annotations in order to help it understand that, yes, this specific instance is the one you mean. Unfortunately, in my hands, it doesn’t seem to treat the Graph this type as a stable value even though it obviously has to be–you can’t switch your own this instance out from under yourself!

It’s possible to work around this by introducing a (seemingly superfluous) val self: this.type = this in the Graph that stabilizes the paths, even though it is just the graph’s this and is typed as such. And then the inner class needs a method that witnesses that it is in fact an inner class its own outer class. There’s a compilable example here: Scastie - An interactive playground for Scala.

You probably want to change the names to something more meaningful.

Anyway, yes, the problem of “why can’t I explain to the compiler that if I have an inner class that I also have a stable instance of its outer class” is something I’ve hit also.

2 Likes
4

I am not trying to talk about the Node type without a Graph value. I am trying to retrieve a Graph value given a Node value, without the compiler losing track that the Node is from the same Graph. See the NoPDT example - I am trying to achieve the same behavior with the added safety of PDT.

5

This indeed works, thank you! Here is a cleaned up snippet for posterity:

object PDT {
  class Graph {
    val thisGraph: this.type = this
    class Node {
      val thisNode: thisGraph.Node = this

      val graph: thisGraph.type = thisGraph
    }
    def useNode(node: thisGraph.Node) = ???
  }

  def useNode(node: Graph#Node) = node.graph.useNode(node.thisNode)
}

Yeah, instability of this seems to be the crux of a problem here. It definitely makes PDTs less appealing.

6

Ah okay, I though that the problem was that useNode needed too parameters.
Because this works: Scastie - An interactive playground for Scala.

1 Like
7

Oh nice, so this makes my attempt #3 work using useNode(node.graph, node). Thank you!

But yeah this still does not provide a way to go from Graph#Node to corresponding outer Graph, so it does not eliminate the need for redundant second parameter.

8

So, AFAIK, Graph#Node should not even exist anymore. I am a bit lost on the details, because I do know the syntax was re-added for cases where it is safe, but I never understood when it is safe. This is what I meant before when I said: " Thus, it is impossible to talk about the Node type without a Graph value". As far as my limited understanding of all this goes, this doesn’t make sense.

I tried to make this in order to be able to talk of any GenNode but still it doesn’t work: Scastie - An interactive playground for Scala.

I haven’t been able to find a way to say that the Node.Graph type should be a GenGraph whose Node type is the same type of the GenNode.
Mainly because there is no way in Scala to refer to the type of the class of this; only to this.type

1 Like
9

I just realized, there is not really a need to encode that at the GenNode level, rather just at the generic useNode level: Scastie - An interactive playground for Scala.

I think you can achieve something similar with the # syntax. But, TBH, I just prefer to stay away from that.

1 Like
10

Yeah, I made that conclusion as well given all these hoops needed to make it work.

11

There is an intersection of weird things here:

  1. defs with singleton types are not stable (vals are):
class Graph {
  class Node {
    val graph = Graph.this // val (without singleton type)
  }
  def useNode(node: Node) = ???
}

def useNode(node: Graph#Node) = node.graph.useNode(node)
// [...] Required: node.graph.Node

class Graph {
  class Node {
    def graph: Graph.this.type = Graph.this // def with singleton type
  }
  def useNode(node: Node) = ???
}

def useNode(node: Graph#Node) = node.graph.useNode(node)
// [...] Required: [unknown type].Node
  1. node is not seen as a node.graph.Node, even when the paths are stable:
class Graph {
  class Node {
    val graph = Graph.this
  }
}

def test(node: Graph#Node) = node: node.graph.Node
// Found:    (node : Playground.Graph#Node)
// Required: node.graph.Node

I believe 2. is the crux of the issue, and is not related to which paths are stable
(Since the compiler is fine with node.graph.Node)
You’ll note however that this is a weird thing for the compiler to think about, since node should conform to type node.something which seems very circular
All proposed solutions in one way or another avoid this circularity, node.thisNode most straightforwardly

Both 1. and 2. seem to straddle the bug-feature boundary: they are surprising, but probably implied by the spec, but fixing them would not break anything (?)

1 Like
12

This is also the feeling I have, it is however safe in this case (in Scala 3 an error would be reported otherwise)

This is because all types here are class-like (class, trait, …):
https://docs.scala-lang.org/scala3/reference/dropped-features/type-projection.html
I think this article should be worded much differently, to avoid both of our impressions

13

Here is my attempt at it:

2 Likes
14
1 Like