Ad-hoc phantom typing / refinement types

137 views
Skip to first unread message

Julian Michael

unread,
Aug 19, 2016, 4:31:38 AM8/19/16
to scala-user
Hi all,

I might be exploring a well-worn field, but I'll share my whole journey below anyway and list some questions at the end. Here's a snippet I found myself writing today when I got upset at having to lowercase strings everywhere:

package object util {
  
  trait LowerCaseStringCapsule {                                             type LowerCaseString <: String
    def lowerCase(s: String): LowerCaseString
  }

  val LowerCaseStrings: LowerCaseStringCapsule = new LowerCaseStringCapsule {
    override type LowerCaseString = String
    override def lowerCase(s: String): LowerCaseString = s.toLowerCase
  }

  // ...
}

It seems to me that you can use abstract types to do opaque sealing to make a type alias that represents a subtype corresponding to an property—say, being in the range of _.toLowerCase. Hopefully it's clear where this is going: with minimal changes of your code (you just have to call your more specific method instead of the old one—you could provide a value class wrapper to make it easier) you could gain the benefits of some increased granularity without needing any boilerplate.

However, with the above code those benefits might be quite small. As soon as I want to do anything else with this string I'll lose the property—any operations that preserve the property, I'll have to put in the capsule, and when working with the subtype I'll have to be sure to use the special methods. It'd be nicer if I could make this happen with the methods already on strings—so, for example,
  (a: LowerCaseString + b: LowerCaseString): LowerCaseString.
I tried to generalize this pattern to allow that sort of thing. It was a painful experience. (Skip to the last code snippet if you're not interested in my journey.) One try:

trait LowerCaseStringCapsule {
  type LowerCaseString <: String
  def lowerCase(s: String): LowerCaseString
  def +(s1: LowerCaseString, s2: LowerCaseString): LowerCaseString
}
val LowerCaseStrings: LowerCaseStringCapsule = new LowerCaseStringCapsule {
  override type LowerCaseString = String
  override def lowerCase(s: String): LowerCaseString = s.toLowerCase
  override def +(s1: LowerCaseString, s2: LowerCaseString): LowerCaseString = s1 + s2
}
import LowerCaseStrings.LowerCaseString
implicit class LowerCaseStringWrapper(val lcs: LowerCaseString) extends AnyVal {
  def +(other: LowerCaseString): LowerCaseString = LowerCaseStrings.+(lcs, other)
}

This did not work: after importing everything, the + method being called in, for example, lowerCase("H") + lowerCase("I") was the one on String. I also tried other approaches, like using an implicit conversion instead of an upper bound:

trait LowerCaseStringCapsule {
  type LowerCaseString
  def lowerCase(s: String): LowerCaseString
  def +(s1: LowerCaseString, s2: LowerCaseString): LowerCaseString
  implicit def shedLowerCaseReq(lcs: LowerCaseString): String
}
val LowerCaseStrings: LowerCaseStringCapsule = new LowerCaseStringCapsule {
  override type LowerCaseString = String
  override def lowerCase(s: String): LowerCaseString = s.toLowerCase
  override def +(s1: LowerCaseString, s2: LowerCaseString): LowerCaseString = s1 + s2
  override implicit def shedLowerCaseReq(lcs: LowerCaseString): String = lcs
}
implicit class LowerCaseStringWrapper(val lcs: LowerCaseString) extends AnyVal {
  def +(other: LowerCaseString): LowerCaseString = LowerCaseStrings.+(lcs, other)
}

This almost worked—but the implicit resolution on + is ambiguous. Here was yet another try:

trait LowerCaseStringCapsule {
  type LowerCaseString <: {
    def +(other: LowerCaseString): LowerCaseString
  }
  def lowerCase(s: String): LowerCaseString
  override implicit def shedLowerCaseReq(lcs: LowerCaseString): String
}
val LowerCaseStrings: LowerCaseStringCapsule = new LowerCaseStringCapsule {
  override type LowerCaseString = String
  override def lowerCase(s: String): LowerCaseString = s.toLowerCase
  override implicit def shedLowerCaseReq(lcs: LowerCaseString): String = lcs
}

This didn't work because LowerCaseString appeared as a parameter type in its own refinement. Finally, I wrote something with the desired functionality:

trait LowerCaseStringCapsule0 {
  type LowerCaseString
  def lowerCase(s: String): LowerCaseString
  def +(s1: LowerCaseString, s2: LowerCaseString): LowerCaseString
  implicit def shedLowerCaseReq(lcs: LowerCaseString): String
}
trait LowerCaseStringCapsule extends LowerCaseStringCapsule0 {
  implicit def wrap(lcs: LowerCaseString): LowerCaseStringWrapper
}
val LowerCaseStrings: LowerCaseStringCapsule = new LowerCaseStringCapsule {
  override type LowerCaseString = String
  override def lowerCase(s: String): LowerCaseString = s.toLowerCase
  def +(s1: LowerCaseString, s2: LowerCaseString) = s1 + s2
  override implicit def shedLowerCaseReq(lcs: LowerCaseString): String = lcs
  override implicit def wrap(lcs: LowerCaseString) = new LowerCaseStringWrapper(lcs.asInstanceOf[LowerCaseStrings.LowerCaseString])
}
import LowerCaseStrings.LowerCaseString
class LowerCaseStringWrapper(val lcs: LowerCaseString) extends AnyVal {
  def +(other: LowerCaseString): LowerCaseString = LowerCaseStrings.+(lcs, other)
}

A truly satisfying (horrifying?) confluence of Scala features. The cast is "safe"—it's just a bit of information I couldn't manage to get into the type system using generalized type constraints or type refinements, apparently because it had to refer to LowerCaseStrings inside its own definition. It seems to me that the value class should not get instantiated, so both implicit conversions should be the identity function. I'm hopeful about this pattern being very useful. Here are my questions for you:

1. That's a lot of boilerplate! Is there a better way?
2. Will the Scala compiler optimize out the implicit conversions, since they're more-or-less obviously the identity?
3. If no to either of the above, would this sort of thing be worth providing more language support for?
4. Unless this is A Bad Idea and I'm not realizing it—any nice examples of this pattern being used in the wild? Good ideas for particular use cases? Is this a well-known thing that I missed the memo about?

Finally, I'll give my pie in the sky. In the ideal case, I would like to attach the property (like "lower case") to the result of a method on something someone else wrote, i.e., I want to make "WHOA".toLowerCase return my new LowerCaseString. This way I could define my own small, relevant set of properties by how they interact with methods on certain types, and then get new guarantees from the type system "for free" just by importing my properties. AFAIK you can't do anything crazy with implicits to replace existing methods... I imagine that for just about all other use cases, it's a horrible idea. Maybe it still is. But is this effect possible somehow?

Thanks all!
Julian
Reply all
Reply to author
Forward
0 new messages