Literal-based singleton types

[George Leontiev]

Hello guys,

I'd like to talk about literal-based singleton types, things like 42.type.

We (Eugene and I) have got them [mostly] working in scala (using the work done by Paul Phillips several years ago), and would really like to have some input from you. If this feature would be useful in your project, could you please share some use-cases/scenarios where it might help?

Your input will help a lot in formalizing and testing the feature, providing some interaction examples and (hopefully) eventually writing down the official SIP.

Here[1] is some information on what is done, what needs to be done, etc.

Here[2] is the branch where this feature is implemented. If you want to build and play with it, please note that several (four) tests currently don't pass (there's a reasoning in [1] for that).

Thank you!

[1] https://docs.google.com/document/d/12hRcjnCqsnQOE-TECU5g99oZoxVgIhrI0bqqgq6ToQk/edit?usp=sharing

[2] https://github.com/folone/scala/tree/topic/42.type

--

QED.

[Erik Osheim]

On Thu, Feb 13, 2014 at 08:26:28PM +0100, George Leontiev wrote:
> We (Eugene and I) have got them [mostly] working in scala (using the work
> done by Paul Phillips several years ago), and would really like to have
> some input from you. If this feature would be useful in your project, could
> you please share some use-cases/scenarios where it might help?

So, here are some big uses I would have for this technology.

It would be really nice be able to define a type like Residue[13.type]
(Z/13Z, the group of integers modulo 13). We could then mandate that
residues can be added only when they are parameterized on the same
number. Possibly something like:

case class Residue[N <: Int](x: Long) { lhs =>
def +(rhs: Residue[N]): Residue[N] =
Residue((lhs.n + rhs.n) % N.value)
}

I'm not sure how (or if) I could get the value corresponding to a
singleton type (used for N.value). Maybe I would need to do something
like this instead?

case class Residue[N <: Int](x: Int, n: N)

Another use is to help with property based testing. In Spire, I have a
Ranged type that makes it easy to ask for numbers in a particular
range in ScalaCheck:

forAll { x: Ranged[Int, _1, _100] =>
val n: Int = x.value // guaranteed to be 1 to 100
}

Currently Spire just builds some of the most common number literals
and uses boilerplate to define the end points of Ranged. (I know we
should be using Shapeless, sorry Miles!) But this is another place
where I think singleton types could really help make things clear.

Of course, I can imagine all kinds of length/dimension checking and
other standard cases, but in terms of concrete things I've already
been working on, these are two examples where this technology would
help a lot.

Thanks,

-- Erik

[Sébastien Doeraene]

Hi all,

There is an important use case for literal-based singleton types, as you call them, in Scala.js. In particular for Strings. Sparing you the Scala.js details, I want to be able to declare several overloads of a method that differ only in the actual strings in parameters, for example:

trait HTMLCanvasElement extends HTMLElement {

  def getContext(contextId: String): Any

  def getContext(contextId: "2d".type): CanvasRenderingContext2D

}

so that at call-site:

val anyContext = canvas.getContext("webgl")

val context2D = canvas.getConttext("2d")

anyContext is an Any but context2D is statically known to be a CanvasRenderingContext2D.

Note: I know the two methods will erase to the same signature at erasure and hence will clash. I don't care. I can use dummy default parameters to disambiguate. Or more likely I'll just have a compiler plugin phase do some magic between typer and erasure. I just want the typer to be happy with it (up to pickler at least).

Cheers,
Sébastien

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.

For more options, visit https://groups.google.com/groups/opt_out.

[Simon Ochsenreither]

trait HTMLCanvasElement extends HTMLElement {

  def getContext(contextId: String): Any

  def getContext(contextId: "2d".type): CanvasRenderingContext2D

}

This looks pretty similar to what TypeScript does!

Coincidence or intention?

[Haoyi Li]

Convergent evolution: they're both targeting the same crappy platform with stupid libraries, but if we want to handle it will then we have no choice but to do our best dealing with them!

--

[Sébastien Doeraene]

@Simon: inspiration, I would say ;-)

Sébastien

[martin odersky]

On Fri, Feb 14, 2014 at 12:41 AM, Sébastien Doeraene <sjrdo...@gmail.com> wrote:

@Simon: inspiration, I would say ;-)

We are currently deliberating about dropping the ".type" suffix for literals. Without it, it would read:

  def getContext(contextId: "2d"): CanvasRenderingContext2D

What's Typescripts syntax for this?

Cheers

 - Martin

--

Martin Odersky
EPFL

[Denys Shabalin]

Assuming that constant types will be represented with ConstantTypeTree(Literal(Constant(value))) .type-less notation will break liftable api in quasiquotes:

// StdLiftables.scala
implicit val liftInt: Liftable[Int] = { i => Literal(Constant(i)) }

// user code

val x = 42

q"$x" // Literal(Constant(42))
tq"$x" // Literal(Constant(42)) but it's not correct tree here

The problem won't arise in .type notation.

[martin odersky]

On Fri, Feb 14, 2014 at 11:46 AM, Denys Shabalin <denys.s...@typesafe.com> wrote:

Assuming that constant types will be represented with ConstantTypeTree(Literal(Constant(value))) .type-less notation will break liftable api in quasiquotes:

// StdLiftables.scala
implicit val liftInt: Liftable[Int] = { i => Literal(Constant(i)) }

// user code

val x = 42

q"$x" // Literal(Constant(42))
tq"$x" // Literal(Constant(42)) but it's not correct tree here

I think that's part of a larger problem with the interaction of quasi-quotes and trees. Trees make use of the fact that the compiler always knows whether something is supposed to be a term or a type. Consequently, the same tree form is used for terms and for types, but might mean something different in each case. It would be best if we found a way that quasi-quotes could implement the same behavior. Different implicit lifting functions for term trees and type trees maybe?

Cheers

 - Martin

[Denys Shabalin]

The problem here is that if we want to support lifting to types we might also support lifting to patterns and the api quickly becomes convoluted and really hard to understand: 3 types of Liftable, 3 types of Unliftable, 5 interpolators.......

With .type notation this would work just fine in this case and could get away with just a single kind of Liftable api. At the moment you can do something similar with idents (albeit non-hygienically):

scala> object O
scala> implicit val liftO = Liftable[O.type] { _ => q"`O`" }
scala> q"$O"; pq"$O"; tq"O.type"
res16: reflect.runtime.universe.Tree = `O`
res17: reflect.runtime.universe.Tree = `O`
res18: reflect.runtime.universe.SingletonTypeTree = `O`.type

Due to .type being different from plain idents we can use the same Liftable in all major contexts without trouble. It would be great if similar thing was true for constants.

[Vojin Jovanovic]

Hi all, 

I think that the most practical use case are the named/labeled records for embedded query languages for SQL and noSQL engines and reactive programming frameworks.

As an example I will take Scalding [1] which is a widely used big-data framework designed by Twitter. Scalding contains the "Fields API" that drops typesafety in order overcome the issues with large tuples. It is very inconvenient when one needs to access data with non-intuitive `t._<n>`. Here is one examples of Scalding code:

       

val trainingData = job.project('startDate, 'awardedTime, 'salary)

  .filter('start_date) { sd: String => sd < periodEndDate }

Here, `filter` contains an additional argument ('startDate) that projects what is used in the closure. Then, the closure argument type can not be inferred and we need to annotate it with "String". This approach is very verbose and unsafe but people still use it in order to avoid large tuples.

Other possible use-cases are Spark [2], and Scala RX [3] where users often build large pipelines for data processing. 

[1] - https://github.com/twitter/scalding/

[2] - https://spark.incubator.apache.org/

[3] - http://rxscala.github.io/

Best regards, 

-- 

Vojin

[David Hall]

On Thu, Feb 13, 2014 at 12:29 PM, Erik Osheim <er...@plastic-idolatry.com> wrote:

On Thu, Feb 13, 2014 at 08:26:28PM +0100, George Leontiev wrote:
> We (Eugene and I) have got them [mostly] working in scala (using the work
> done by Paul Phillips several years ago), and would really like to have
> some input from you. If this feature would be useful in your project, could
> you please share some use-cases/scenarios where it might help?

So, here are some big uses I would have for this technology.

+1, I would also like these for Breeze.  Use cases would look like Erik's and Sebastien's.  For example, emulating Matlab's frobenius norm syntax, which is written norm(mat, 'fro').

-- David

[Sébastien Doeraene]

def getContext(contextId: "2d"): CanvasRenderingContext2D
What's Typescripts syntax for this?

Exactly that: just the string as the type.

interface HTMLCanvasElement extends HTMLElement {
    width: number;
    height: number;
    toDataURL(type?: string, ...args: any[]): string;
    getContext(contextId: string, ...args: any[]): any;
    getContext(contextId: "2d"): CanvasRenderingContext2D;
}

Sébastien

[George Leontiev]

Wow, thanks a lot for all the feedback!

I'll post once we have something document-like ready to show.

Thanks again!

[martin odersky]

On Fri, Feb 14, 2014 at 9:56 PM, Sébastien Doeraene <sjrdo...@gmail.com> wrote:

def getContext(contextId: "2d"): CanvasRenderingContext2D
What's Typescripts syntax for this?

Exactly that: just the string as the type.

Sounds good then to try the same thing! 

 - Martin

 

interface HTMLCanvasElement extends HTMLElement {
    width: number;
    height: number;
    toDataURL(type?: string, ...args: any[]): string;
    getContext(contextId: string, ...args: any[]): any;
    getContext(contextId: "2d"): CanvasRenderingContext2D;
}

Sébastien

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

--

Martin Odersky
EPFL

[Eugene Burmako]

How are quasiquotes then going to support this syntax? Maybe we could still consider "42".type?

[martin odersky]

On Sun, Feb 16, 2014 at 1:23 PM, Eugene Burmako <xen...@gmail.com> wrote:

How are quasiquotes then going to support this syntax? Maybe we could still consider "42".type?

No, the quasi-quote problem is a more general one. Scala syntax trees systematically re-use the same tree for terms and types. I am sure there's an equally systematic way in quasi-quotes to adapt to this, in particular since for quasi-quotes, just as for parsing, it is always known whether something is a term or a type.

Cheers

 - Martin 

--

Martin Odersky
EPFL

[Simon Ochsenreither]

How are quasiquotes then going to support this syntax? Maybe we could still consider "42".type?

I kind of agree with that. "42" feels a lot too close to default arguments, especially for people coming from other languages where the x: "42" syntax is used for default arguments.
Imho, the .type serves as a useful reminder here that we are working with types, not terms.

[John Nilsson]

I'm wonderig. Isn't the conflict here that we're trying to use method overloading to derive types in the first place.

For values scala allready have parttern matching. Maybe a better approach here would be a type level match expression?

type Ret[T] = T match {

case "foo" => Foo

case _ => Any

}

BR

John

--

[Haoyi Li]

While we're throwing out alternatives, another approach would be using some kind of whitebox macro. In the Javascript case, although overloading works great for canvas.getContext("2d") and maybe $("div"), it fails for more complex cases like $("div > span.my-class") whereas a whitebox macro $ could be intelligent enough to parse the CSS selector (if possible) and pick a type signature the best it can.

[Denys Shabalin]

Me and Eugene have been discussing a future where trees were safe by construction (i.e. all fields have the most specific type that describes its contents) and it turns out that in this world current Liftable would not be sharp enough:

   case class X(...)

   implicit val liftX: Liftable[X] = ...  // equiv to a X => Tree function

  
   q"f($x)" // won't compile as function argument has to be a TermTree, not just a Tree

So indeed we might have to have separate Liftables for different contexts with more precise signatures if trees were to become safe by construction...

[Alois Cochard]

Hi George, Eugene and all,

I'm very happy to learn about this initiative, I was dreaming for something like that :-)

I would use it mainly in DSL, which make we wonder, what about a complete literal support like:

Foo[1, "bar"] instead of Foo[1.type, "bar".type] ?

In there some technical reason to avoid such syntax? logically I don't see any ambiguity, as long as the trait is defined like 'trait Foo[Nat, Sing]' the compiler should be able to workout automatically.

It's basically the approach took by GHC.TypeLits

[Alois Cochard]

Sorry I didn't read the full thread before posting, looks like you guys agreed on such syntax already :-)

Awesome stuff

[Léonard Schneider]

I'm coming late to the party but I've been so busy these months... I wonder how I could miss this post.

Anyway, the biggest use I see is getting the possibility to play with type safe sized collections. This enable a lot of algebra very naturally. To me this is awesome. I think this is very important to be able to combine these literal types, with literals computed through macros to unleash their whole power. So I have speculated some kind of type macros (but very different from previous ones) and possibility to materialize a literal type to the literal value it represents. See below example for more details.

type Nat[n <: Int.literal] = if(n >= 0) n else Nothing // maybe another keyword than 'type' would be better suited as we want 'n <: Nat' to apply this function

type Nat*[n <: Nat] = if(n > 0) n else Nothing

type If[c <: Boolean.literal, m, n] = if(c) n else m

type NArray[T, n <: Nat] = if(n > 0) Array[NArray[T, n - 1]] else T

class Vector[T: Numeric, n <: Nat*](arr: Array[T] = Array.fill(n - 1)) { a =>

  def apply[m <: Nat*]: If[m <= n, T, Nothing] = a.arr(m - 1) // materialization of literal type

  def ++[m <: Nat*](b: Vector[T, m]) = Vector[T, n + m](a.arr + b.arr) 

  def head: If[n > 0, T, Nothing] = arr.head

  def +[m <: Nat*](b: Vector[T, n]) = {

    val c = new Vector[T, n]

    for(i <- 0 until n) c.arr(i) = a.arr(i) + b.arr(i) // materialization of literal type

    c

  }

  // etc.

}

class Matrix[T: Numeric, n <: Nat*, m <: Nat*](arr: Array[Array[T]] = Array.fill(n, m)) { a =>

  def apply[i <: Nat*, j <: Nat*]: If[i <= n && j <= m, T, Nothing] = a.arr(i)(j) // materialization of literal type

  def *[p <: Nat*](b: Matrix[T, m, p]) = {

    val c = new Matrix[n, p]

    for(i <- 0 until n; j <- 0 until p; r <- 0 until m) c.arr(i)(j) += a.arr(i)(r) + b.arr(r)(j) // materialization of literal type

    c

  }

  // etc.

}

[Miles Sabin]

I'm really not particularly enthused by this proposal. I don't think
it'll do any harm, but I also don't think it adds much value.

In practice, I never want to have to write 23.type or "foo".type. What
I actually want to be able to do is use 23 or "foo" as value arguments
somewhere and have the singleton types Int(23) and String("foo")
inferred for me in a way which can then be used to drive type class
instance selection. This is precisely what I've hacked together for
HList/Tuple/record indexing/selection in shapeless, using an implicit
macro which narrows a literal value argument to its singleton type,

scala> import shapeless._, syntax.std.tuple._
import shapeless._
import syntax.std.tuple._

scala> (23, "foo", true)(0)
res0: Int = 23

scala> (23, "foo", true)(1)
res1: String = foo

scala> (23, "foo", true)(2)
res2: Boolean = true

I don't see that being able to write,

(23, "foo", true)[0.type]

would improve on this in any way, in fact quite the contrary.

Note also that for String literals we have always been able to do this
(although for some reason this fact has been under-appreciated for a
very long time): a trivial example here,

https://gist.github.com/milessabin/aae285025a32fac0f5c1

Combining this with selectDynamic has some important practical
applications in shapeless lenses and records.

What I would really like to have is the ability to signal to the
compiler that we would like a Singleton type to be inferred for a
literal value, without the macro-hackery that I currently need.
Specifically I would like to be able to write,

def foo[T <: Singleton](t: T): Option[T] = Some(t)

And have foo(23) yield Option[Int(23)]. This would be a genuinely
useful, conservative extension of current Scala, which could even be
regarded as a bugfix: It has a long standing open ticket at least for
the String literal case,

https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/lenses.scala#L501

Cheers,


Miles

> --
> You received this message because you are subscribed to the Google Groups
> "scala-language" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to scala-languag...@googlegroups.com.

> For more options, visit https://groups.google.com/d/optout.



--
Miles Sabin
tel: +44 7813 944 528
skype: milessabin
gtalk: mi...@milessabin.com
g+: http://www.milessabin.com
http://twitter.com/milessabin

[Miles Sabin]

On Sun, May 11, 2014 at 2:55 PM, Miles Sabin <mi...@milessabin.com> wrote:
> And have foo(23) yield Option[Int(23)]. This would be a genuinely
> useful, conservative extension of current Scala, which could even be
> regarded as a bugfix: It has a long standing open ticket at least for
> the String literal case,

Whoops ... wrong link. It should have been,

https://issues.scala-lang.org/browse/SI-5103

Cheers,


Miles

[martin odersky]

On Mon, May 12, 2014 at 10:25 AM, Jesper Nordenberg <jesper.n...@gmail.com> wrote:

On Sunday, 11 May 2014 14:55:25 UTC+2, Miles Sabin wrote:

What I would really like to have is the ability to signal to the
compiler that we would like a Singleton type to be inferred for a
literal value, without the macro-hackery that I currently need.
Specifically I would like to be able to write,

  def foo[T <: Singleton](t: T): Option[T] = Some(t)

And have foo(23) yield Option[Int(23)]. This would be a genuinely
useful, conservative extension of current Scala, which could even be
regarded as a bugfix: It has a long standing open ticket at least for
the String literal case,

I also think it would be a safe and very useful addition. In terms of syntax, I prefer writing just 23 or "id" instead of 23.type or "id".type.

Cheers

 - Martin 

 

 

Yes, this would be a nice extension to the Scala type inference. However to be really useful it also has to work for expressions like 'foo(1 + 2)' (with type inferred to 'foo[3.type](3) : Option[3.type]').

 

 

 

/Jesper Nordenberg

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Martin Odersky
EPFL

--

JOIN US. REGISTER TODAY!

Scala

Days

June 16th-18th,

Berlin

[Alois Cochard]

Agreed,

But I'm pretty sure it could be useful as well directly as type parameter without any run-time representation like I describe in my original message:

def foo[T <: Nat]: Bar[T, String] = ...

foo[24]

I see use cases for both approach.

 (23, "foo", true)[0] and (23, "foo", true)(0)

--
You received this message because you are subscribed to a topic in the Google Groups "scala-language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scala-language/9VEnFZImyJI/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scala-languag...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Alois Cochard

http://aloiscochard.blogspot.com

http://twitter.com/aloiscochard

http://github.com/aloiscochard

[Naftoli Gugenheim]

Isn't that more of a "special case"? If you write .type it's analogous to other singleton types.

[Miles Sabin]

On Mon, May 12, 2014 at 10:25 AM, Jesper Nordenberg
<jesper.n...@gmail.com> wrote:
> Yes, this would be a nice extension to the Scala type inference. However to
> be really useful it also has to work for expressions like 'foo(1 + 2)' (with
> type inferred to 'foo[3.type](3) : Option[3.type]').

At the moment this drops out of constant folding automatically,

scala> def sameType(s1: String)(s2: s1.type) = (s1, s2)
sameType: (s1: String)(s2: s1.type)(String, String)

scala> sameType("foo")("foo")
res0: (String, String) = (foo,foo)

scala> sameType("foo")("fo"+"o")
res1: (String, String) = (foo,foo)

scala> sameType("foo")("bar")
<console>:9: error: type mismatch;
found : String("bar")
required: String("foo")
sameType("foo")("bar")
^

I'm not actually convinced this is a good thing ... it means that
constant folding isn't type preserving.

Cheers,


Miles

[Miles Sabin]

On Tue, May 13, 2014 at 9:57 AM, Miles Sabin <mi...@milessabin.com> wrote:
> At the moment this drops out of constant folding automatically,

Confirmed for Ints with a build from retronym/ticket/5103 ...

scala> def foo[T <: Singleton](t: T): Option[T] = Some(t)
foo: [T <: Singleton](t: T)Option[T]

scala> foo(1+2)
res1: Option[Int(3)] = Some(3)

Constant folding gets to this before the typer ...

[Lukas Rytz]

On Tue, May 13, 2014 at 9:57 AM, Miles Sabin <mi...@milessabin.com> wrote:

On Mon, May 12, 2014 at 10:25 AM, Jesper Nordenberg
<jesper.n...@gmail.com> wrote:

> Yes, this would be a nice extension to the Scala type inference. However to
> be really useful it also has to work for expressions like 'foo(1 + 2)' (with
> type inferred to 'foo[3.type](3) : Option[3.type]').

At the moment this drops out of constant folding automatically,

scala> def sameType(s1: String)(s2: s1.type) = (s1, s2)
sameType: (s1: String)(s2: s1.type)(String, String)

scala> sameType("foo")("foo")
res0: (String, String) = (foo,foo)

scala> sameType("foo")("fo"+"o")
res1: (String, String) = (foo,foo)

scala> sameType("foo")("bar")
<console>:9: error: type mismatch;
 found   : String("bar")
 required: String("foo")
              sameType("foo")("bar")
                              ^

I'm not actually convinced this is a good thing ... it means that
constant folding isn't type preserving.

What do you mean by that? I think it's valid to say that the expression

("fo"+"o") has type "foo".type already before constant folding.