8000 Merge pull request #346 from folone/topic/sip-42 · stephenmcd/scala.github.com@27c57fb · GitHub
[go: up one dir, main page]
Skip to content

Commit 27c57fb

Browse files
heathermillerheathermiller
committed
Merge pull request scala#346 from folone/topic/sip-42
Add SIP-23: Literal-based singleton types
2 parents 8540059 + b800dd5 commit 27c57fb

File tree

1 file changed

+306
-0
lines changed

1 file changed

+306
-0
lines changed

‎sips/pending/_posts/2014-06-27-42.type.md

Lines changed: 306 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,306 @@
1+
---
2+
layout: sip
3+
disqus: true
4+
title: SIP-23 - Literal-based singleton types
5+
---
6+
7+
**By: George Leontiev, Eugene Burmako, Jason Zaugg, Adriaan Moors, Paul Phillips**
8+
9+
<span class="label warning">Note: This SIP is considered a "good idea", but is a work-in-process.</span>
10+
<span class="label warning">There is no guarantee that it will not be dropped if at some point it is decided that its foundation is not good enough.</span>
11+
12+
<span class="label success">Champion: Adriaan Moors</span>
13+
14+
<span class="label success">Last update: July 9, 2014</span>
15+
16+
## Motivation
17+
18+
Singleton types bridge the gap between the value level and the type level and hence allow the exploration in Scala of techniques which would typically only be available in languages with support for full-spectrum dependent types.
19+
20+
Scala's type system can model constants (e.g. `42`, `"foo"`, `classOf[String]`). These are inferred in cases like `object O { final val x = 42 }`. They are used to denote and propagate compile time constants (See [6.24 Constant Expressions](http://www.scala-lang.org/files/archive/spec/2.11/06-expressions.html) and discussion of "constant value defintion" in [4.1 Value Declarations and Definitions](http://www.scala-lang.org/files/archive/spec/2.11/04-basic-declarations-and-definitions.html)). However, there is no surface syntax to express such types. This makes people who need them, create macros that would provide workarounds to do just that (e.g. [shapeless](https://github.com/milessabin/shapeless/blob/master/core/src/main/scala/shapeless/singletons.scala)). This can be changed in a relatively simple way, as the whole machinery to enable this is already present in the scala compiler.
21+
22+
Another motivation for adding this functionality is the fact that it is already partially available in scala, but the way it is available makes interaction with this feature a bit inconsistent. Here’s what is possible in the current version of scala:
23+
24+
scala> val t = "test"
25+
t: String = test
26+
27+
scala> val r: t.type = t
28+
r: t.type = test
29+
30+
But:
31+
32+
scala> val r: "test".type = "test"
33+
<console>:1: error: identifier expected but string literal found.
34+
val r: "test".type = "test"
35+
^
36+
37+
And:
38+
39+
scala> val r: 42.type = 42
40+
<console>:1: error: identifier expected but integer literal found.
41+
val r: 42.type = 42
42+
^
43+
44+
Or even:
45+
46+
scala> val t = 42
47+
t: Int = 42
48+
49+
scala> val r: t.type = t
50+
<console>:8: error: type mismatch;
51+
found : t.type (with underlying type Int)
52+
required: AnyRef
53+
val r: t.type = t
54+
^
55+
56+
This looks like an inconsistency, which should be fixed. The proposed change fixes exactly that:
57+
58+
scala> val r: "test".type = "test"
59+
r: "test".type = test
60+
61+
scala> val r: 42.type = 42
62+
r: 42.type = 42
63+
64+
or even:
65+
66+
scala> val r: 42 = 42
67+
r: 42.type = 42
68+
69+
scala> val t = 42
70+
t: Int = 42
71+
72+
scala> val r: t.type = t
73+
r: t.type = 42
74+
75+
To summarize, scala has full support for literal-based singleton types, but language user has very limited possibilities for creating and using them. Two possible ways currently are asking the compiler to infer the singleton type by marking value as `final`, or use `.type` syntax, which is only available for stable identifiers pointing to values that conform to `AnyRef`.
76+
77+
## Prerequisites
78+
79+
### Any vs AnyRef
80+
81+
Currently there is a possibility to use singleton types in some contexts, but only on identifiers which point to a constant that conforms to `AnyRef`. This restriction is due to `Any` not having an `eq` method, which is what’s used for singleton type-equality check and pattern matching [https://github.com/scala/scala/pull/3558](https://github.com/scala/scala/pull/3558). This has been discussed on the mailing list [here](https://groups.google.com/forum/#!msg/scala-internals/12h2TgDFnDM/Sq-EYi7VD7IJ) and [here](https://groups.google.com/forum/#!msg/scala-internals/jsVlJI4H5OQ/BwdZT5hpKtsJ), and there is a consent that this needs to be done.
82+
83+
### Inhabitants of the type
84+
85+
Getting the inhabitant of a singleton type, as described by [Travis Brown](http://meta.plasm.us/posts/2013/06/28/singleton-types-for-literals-in-scala/), can be done with a macro, which is a part of the [proposed implementation](https://github.com/folone/scala/commit/094883efb4d1c50981cea41f049c3930c8efbc3c).
86+
87+
## Use cases
88+
89+
There are quite a few use cases we’ve collected on the [mailing list](https://groups.google.com/forum/#!topic/scala-language/9VEnFZImyJI). Some of them are as follows.
90+
91+
### Spire
92+
93+
Singleton types will be useful for defining 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:
94+
95+
case class Residue[N <: Int : SingleInhabitant](n: Long) { lhs =>
96+
def +(rhs: Residue[N]): Residue[N] =
97+
Residue((lhs.n + rhs.n) % inhabitant[N])
98+
}
99+
100+
Another use is to help with property based testing. In Spire, there is a Ranged type that makes it easy to ask for numbers in a particular range in ScalaCheck:
101+
102+
forAll { x: Ranged[Int, 1, 100] =>
103+
val n: Int = x.value // guaranteed to be 1 to 100
104+
}
105+
106+
Currently Spire just builds some of the most common number literals and uses boilerplate to define the end points of `Ranged`. But this is another place where singleton types could really help make things clear. Here’s what `Ranged` could look like:
107+
108+
class Ranged[From <: Int : SingleInhabitant, To <: Int : SingleInhabitant] {
109+
def value = {
110+
val rnd = new scala.util.Random
111+
val from = inhabitant[From]
112+
val to = inhabitant[To]
113+
(from + rnd.nextInt(to - from + 1))
114+
}
115+
}
116+
117+
There is also all kinds of length/dimension checking and other standard cases where singleton types will help.
118+
119+
### Scala.js
120+
121+
There is an important use case for literal-based singleton types in Scala.js. In particular for Strings: declaring several overloads of a method that differ only in the actual strings in parameters, for example:
122+
123+
trait HTMLCanvasElement extends HTMLElement {
124+
def getContext(contextId: String): Any
125+
def getContext(contextId: "2d".type): CanvasRenderingContext2D
126+
}
127+
128+
so that at call-site:
129+
130+
val anyContext = canvas.getContext("webgl")
131+
val context2D = canvas.getConttext("2d")
132+
133+
`anyContext` is an `Any` but `context2D` is statically known to be a `CanvasRenderingContext2D`.
134+
135+
Note: The way this currently works:
136+
137+
scala> :t canvas.getContext("webgl")
138+
Any
139+
140+
scala> :t canvas.getContext("2d")
141+
Any
142+
143+
But
144+
145+
scala> :t canvas.getContext("2d": "2d".type)
146+
CanvasRenderingContext2D
147+
148+
### Shapeless
149+
150+
The whole approach that shapeless currently uses for managing singleton types (which it calls witnesses) can be rewritten using this feature instead of macros. Specifically, [these invocations](https://github.com/milessabin/shapeless/blob/e3399e35a7bb17b286141f53827619a3dc98efe8/core/src/main/scala/shapeless/singletons.scala#L31-L38) of macros can be rewritten in the following way:
151+
152+
object Witness {
153+
type Aux[T0] = Witness { type T = T0 }
154+
type Lt[Lub] = Witness { type T <: Lub }
155+
156+
implicit def apply[U : SingleInhabitant]: Witness.Aux[U] =
157+
new Witness {
158+
type T = U
159+
val value = inhabitant[T]
160+
}
161+
162+
implicit def apply[U](t: U): Witness.Lt[U] =
163+
new Witness {
164+
type T = t.type
165+
val value: T = t
166+
}
167+
}
168+
169+
This feature is then heavily used to implement [records](https://github.com/milessabin/shapeless/blob/master/examples/src/main/scala/shapeless/examples/records.scala), [labeled generics](https://github.com/milessabin/shapeless/blob/master/examples/src/main/scala/shapeless/examples/labelledgeneric.scala), etc.
170+
171+
**Note:** According to Miles Sabin, this can also be done with an existing fix (by Jason Zaugg) to [SI-5103](https://issues.scala-lang.org/browse/SI-5103).
172+
173+
### Others
174+
175+
Quite a few other projects find this feature relevant for more efficient work on the tasks they are solving: Slick, Spark, Scala RX, Scalding, Breeze.
176+
177+
## Proposal
178+
179+
This document proposes to extend an existing very limited syntax for singleton types to a more general one. That is, possibility to use syntax for singleton types, as well as raw literals, in any type position. Here are several examples (taken from the [tests](https://github.com/folone/scala/blob/topic/42.type/test/files/run/42.type.scala)):
180+
181+
### Simple examples:
182+
183+
type _42 = 42.type
184+
type Unt = ().type
185+
type _ 1 = 1 // .type is optional for literals
186+
final val x = 1
187+
type one = x.type // … but mandatory for identifiers
188+
189+
This is not allowed for the reason that we will have problems bootstrapping this
190+
191+
scala> type _2 = (1+1).type
192+
<console>:1: error: '.' expected but identifier found.
193+
type _2 = (1+1).type
194+
^
195+
196+
### Using it with vars:
197+
198+
scala> var x: 3.type = 3
199+
200+
scala> x = 42
201+
<console>:8: error: type mismatch;
202+
found : 42.type (with underlying type Int)
203+
required: 3.type
204+
x = 42
205+
^
206+
207+
### Pattern-matching
208+
209+
val y: 5 = 5
210+
211+
def g(x: Int) = x match {
212+
case _: y.type => 0
213+
case _: 7.type => 1
214+
case _ => 2
215+
}
216+
217+
### Etc.
218+
219+
trait Succ[T] {
220+
type Out
221+
def apply(x: T): Out
222+
}
223+
224+
implicit object One extends Succ[1.type] {
225+
type Out = 2.type
226+
def apply(x: 1.type) = 2
227+
}
228+
229+
def f[T](x: T)(implicit succ: Succ[T]) = succ(x)
230+
231+
def main(args: Array[String]): Unit = {
232+
println(f(1))
233+
// println(f(5))
234+
println((g(1), g(5), g(7)))
235+
}
236+
237+
## Formalization
238+
239+
The proposed change is essentially as follows (adding on the [language reference](http://iainmcgin.github.io/scala-ref-markdown/ScalaReference.html#scala-syntax-summary)):
240+
241+
SimpleType ::= SimpleType TypeArgs
242+
| SimpleType ‘#’ id
243+
| StableId
244+
| Path ‘.’ ‘type’
245+
| Literal [‘.’ type]
246+
| ‘(’ Types ‘)’
247+
248+
A singleton type is of the form `p.type`, where `p` is a path pointing to a value. Or `literal[.type]` (in this case `.type` is optional, because when using a literal we always know if we are in a type- or term-parsing mode). The type denotes set of values consisting of a single value denoted by path `p`, or a `literal`.
249+
250+
## Implementation
251+
252+
The singleton type part (not including `eq` on `Any`) is implemented on [github](https://github.com/folone/scala/tree/topic/42.type). There are currently several outstanding issues that need to be looked into. Namely, `ConstantType` folding and inlining of functions with singleton type result.
253+
254+
The places where those issues might present themselves are marked with `TODO (folone)`, and can be found like this:
255+
256+
$ ack “TODO \(folone\)” src/
257+
258+
Other places where `ConstantType` is used can be found like this:
259+
260+
$ grep -r --include="*.scala" "ConstantType" src/
261+
262+
## Some details on the optionality of .type
263+
264+
While discussing this document, the agreement was that we should keep the mandatory `.type` for identifiers, to avoid situations described by Adriaan Moors:
265+
266+
type T = Int
267+
final val T = 1
268+
val x: T = 2 // Which T is this: T, or T.type?
269+
270+
but make it optional for literals, e.g. both `42.type` and `42` in type position are valid.
271+
272+
This change is implemented in the branch, and needs a careful update of all the failed check files (partest can do that automatically: `partest --update-check`).
273+
274+
## Dependencies on other SIPs
275+
276+
This project needs an `eq` method on `Any`.
277+
278+
## Related open tickets
279+
280+
* [https://issues.scala-lang.org/browse/SI-8323](https://issues.scala-lang.org/browse/SI-8323)
281+
* [https://issues.scala-lang.org/browse/SI-8564](https://issues.scala-lang.org/browse/SI-8564)
282+
* [https://issues.scala-lang.org/browse/SI-7656](https://issues.scala-lang.org/browse/SI-7656)
283+
* [https://issues.scala-lang.org/browse/SI-5103](https://issues.scala-lang.org/browse/SI-5103)
284+
285+
## Weird behaviour collected so far
286+
287+
### Inlining of functions
288+
289+
scala> def test: 7.type = {
290+
| println("PANDA!")
291+
| 7
292+
| }
293+
test: 7.type
294+
295+
scala> test
296+
res0: 7.type = 7
297+
298+
[Suspected culprit](https://github.com/folone/scala/blob/topic/42.type/src/compiler/scala/tools/nsc/transform/Constructors.scala#L643-L644)
299+
300+
Can hopefully be fixed by verifying that the body is pure (by means of SI-7656) before inlining it.
301+
302+
## Useful links
303+
304+
* Implementation: [https://github.com/folone/scala/tree/topic/42.type](https://github.com/folone/scala/tree/topic/42.type)
305+
* Initial announcement: [https://groups.google.com/forum/#!topic/scala-language/9VEnFZImyJI](https://groups.google.com/forum/#!topic/scala-language/9VEnFZImyJI)
306+
* SIP discussion: [https://groups.google.com/forum/#!topic/scala-sips/YRHd8WW0V40](https://groups.google.com/forum/#!topic/scala-sips/YRHd8WW0V40)

0 commit comments

Comments
 (0)
0