D 2015-07-11T17:54:11.612
L First-Class\sLabels
N text/x-markdown
U neilmadden
W 3476
# First-Class Labels
Part of me wants to make SiCL statically typed, or at least informed by typing discipline so that that door is open in the future. One very interesting approach is that of [first-class labels](http://research.microsoft.com/pubs/64501/fclabels.pdf) described in the linked paper.
We can think of the fields in a record and the tags in an algebraic data type (variant) as individual objects in their own right. These can be polymorphic in the type of value that can be associated with them. For example, we might have two different record types in our program with a "name" field - one takes a simple string, while the other takes a complex Name object (with first-name, last-name, title, etc fields). The "name" field would be shared between them, with a type like (in ML-style postfix type notation):
val name : a Label
i.e., name is a label that can take any type of value. We can then define operations over labels to construct records etc. For example, the '=' infix operator extends a record with a new field value:
{ _ = _, ... } : ∀r,l,a. (r\\l) => a -> r... -> a Label -> {l : a, r...}
This (in slightly odd syntax) says that to assign a value to some field in a record that may contain other fields, then firstly r must "lack" (r\\l) an "l" field already, and then given a value of type "a", a record r, a label of type "a Label" (i.e., matching the type of value), then we return a record with the new label l of type a, and the remaining record r (using row typing).
This looks complicated, but it's a really nice and simple idea. In particular, it provides a typing discipline (and reasonably efficient compilation strategy) for having first-class symbols in the language with a lot of flexibility on how they are used - for records and objects, for first-class messages, for algebraic datatypes, etc. You can even assign labels to variables, pass them as arguments to functions (and return them), store them in data structures, etc.
I therefore propose adding a first-class label concept to SiCL, either dynamically typed or statically so (static typing would require row typing, which is nice but by no means simple).
Label constants are created using either an initial upper-case letter (Foo, Bar, etc) or by a macro postfix colon operator that converts the preceding identifier or string into a label - thus foo: and "foo": are labels (the same label in this case). This ensures a natural syntax for both variants and record fields.
Variant types can then be formed as a sum of labels:
type MyType = A | B(x,y) | C
Such a type is closed by default. We could also allow open variant types where additional labels can be passed:
type MyType = A | B(x,y) | C | ...
(The "\| ..." is the actual syntax here). This indicates that functions taking a value of this type can expect any of the given variants or any other variant label at all (and must include default cases in matching etc).
Likewise for records:
type MyRecord = { x: Int, y: Text }
is a fixed type record, while
type MyRecord = { x: Int, y: Text, ... }
allows additional fields to be present.
A label is itself a function that takes a value of the appropriate type and returns a Field of that type:
type a Label = a -> a Field
Thus, the expression x: is a label while (x: 12) is an integer field (Int Field). (x: Int) is a Type Field (or Label field, given that Int must be a label?).
Z e0d69804c0346d663d4a5ff9532a1eec