What are some compelling use cases for dependent method types?

by

More or less any use of member (ie. nested) types can give rise to a need for dependent method types. In particular, I maintain that without dependent method types the classic cake pattern is closer to being an anti-pattern.

So what’s the problem? Nested types in Scala are dependent on their enclosing instance. Consequently, in the absence of dependent method types, attempts to use them outside of that instance can be frustratingly difficult. This can turn designs which initially seem elegant and appealing into monstrosities which are nightmarishly rigid and difficult to refactor.

I’ll illustrate that with an exercise I give during my Advanced Scala training course,

trait ResourceManager {
  type Resource <: BasicResource
  trait BasicResource {
    def hash : String
    def duplicates(r : Resource) : Boolean
  }
  def create : Resource

  // Test methods: exercise is to move them outside ResourceManager
  def testHash(r : Resource) = assert(r.hash == "9e47088d")  
  def testDuplicates(r : Resource) = assert(r.duplicates(r))
}

trait FileManager extends ResourceManager {
  type Resource <: File
  trait File extends BasicResource {
    def local : Boolean
  }
  override def create : Resource
}

class NetworkFileManager extends FileManager {
  type Resource = RemoteFile
  class RemoteFile extends File {
    def local = false
    def hash = "9e47088d"
    def duplicates(r : Resource) = (local == r.local) && (hash == r.hash)
  }
  override def create : Resource = new RemoteFile
}

It’s an example of the classic cake pattern: we have a family of abstractions which are gradually refined through a heirarchy (ResourceManager/Resource are refined by FileManager/File which are in turn refined by NetworkFileManager/RemoteFile). It’s a toy example, but the pattern is real: it’s used throughout the Scala compiler and was used extensively in the Scala Eclipse plugin.

Here’s an example of the abstraction in use,

val nfm = new NetworkFileManager
val rf : nfm.Resource = nfm.create
nfm.testHash(rf)
nfm.testDuplicates(rf)

Note that the path dependency means that the compiler will guarantee that the testHash and testDuplicates methods on NetworkFileManager can only be called with arguments which correspond to it, ie. it’s own RemoteFiles, and nothing else.

That’s undeniably a desirable property, but suppose we wanted to move this test code to a different source file? With dependent method types it’s trivially easy to redefine those methods outside the ResourceManager hierarchy,

def testHash4(rm : ResourceManager)(r : rm.Resource) = 
  assert(r.hash == "9e47088d")

def testDuplicates4(rm : ResourceManager)(r : rm.Resource) = 
  assert(r.duplicates(r))

Note the uses of dependent method types here: the type of the second argument (rm.Resource) depends on the value of the first argument (rm).

It is possible to do this without dependent method types, but it’s extremely awkward and the mechanism is quite unintuitive: I’ve been teaching this course for nearly two years now, and in that time, noone has come up with a working solution unprompted.

Try it for yourself …

// Reimplement the testHash and testDuplicates methods outside
// the ResourceManager hierarchy without using dependent method types
def testHash        // TODO ... 
def testDuplicates  // TODO ...

testHash(rf)
testDuplicates(rf)

After a short while struggling with it you’ll probably discover why I (or maybe it was David MacIver, we can’t remember which of us coined the term) call this the Bakery of Doom.

Edit: consensus is that Bakery of Doom was David MacIver’s coinage …

For the bonus: Scala’s form of dependent types in general (and dependent method types as a part of it) was inspired by the programming language Beta … they arise naturally from Beta’s consistent nesting semantics. I don’t know of any other even faintly mainstream programming language which has dependent types in this form. Languages like Coq, Cayenne, Epigram and Agda have a different form of dependent typing which is in some ways more general, but which differs significantly by being part of type systems which, unlike Scala, don’t have subtyping.

More Related Contents:

  1. What does the `#` operator mean in Scala?
  2. What is meant by Scala’s path-dependent types?
  3. What is the difference between def foo = {} and def foo() = {} in Scala?
  4. Scala: How to define “generic” function parameters?
  5. How to pattern match into an uppercase variable?
  6. Turning A => M[B] into M[A => B]
  7. Unable to map on HList
  8. forall in Scala
  9. Multiple parameter closure argument type not inferred
  10. Why does one select Scala type members with a hash instead of a dot?
  11. What is the eta expansion in Scala?
  12. How to define schema for custom type in Spark SQL?
  13. How to split a dataframe into dataframes with same column values?
  14. How to use regex to include/exclude some input files in sc.textFile?
  15. Cartesian product of two lists
  16. I want to get the type of a variable at runtime
  17. Two ways of currying in Scala; what’s the use-case for each?
  18. How to get ID of a map task in Spark?
  19. Scala underscore minimal function
  20. Debugging Scala code with simple-build-tool (sbt) and IntelliJ
  21. Use functional combinators on Scala Tuples?
  22. scala tuple unpacking
  23. Using varargs from Scala
  24. Can’t prove that singleton types are singleton types while generating type class instance
  25. Clarification needed about futures and promises in Scala
  26. Difference between MutableList and ListBuffer
  27. Creating a method definition tree from a method symbol and a body
  28. Is there an equivalent to SuppressWarnings in Scala?
  29. Why isn’t Validation a Monad?
  30. Is it possible to have tuple assignment to variables in Scala? [duplicate]

Leave a Comment