Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Suggestion: Sum Types and Tagged Unions without Reflection #9241

Closed
drudru opened this issue Jun 18, 2016 · 6 comments
Closed

Suggestion: Sum Types and Tagged Unions without Reflection #9241

drudru opened this issue Jun 18, 2016 · 6 comments
Labels
Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. Suggestion An idea for TypeScript

Comments

@drudru
Copy link

drudru commented Jun 18, 2016

I’m very happy to see #186 close with pull request: #9163. This is a big step forward.

I read both of those and read Wes Wigham's recent work. I openned this as a new issue to avoid cluttering the closed issue.

Tagged Union without Reflection

I still think there is room to add some tagged-unions in the style of an FP language to TypeScript. The benefits are widely understood and documented. The key attribute of this suggestion is the removal of visibility into the tag of the union. This is how every other statically-typed FP language implements them since they also erase types at run-time.

Hopefully this can become part of the language at some point in the future. Considering the recent code landing in 2.0, the urgency is greatly reduced, but still worth discussing.

A quick list of benefits:

  1. The structure should be hidden for safety
  2. The syntax and semantics are much more 1 to 1 with other languages
  3. A new type gets created so we can support recursive definitions
  4. It would provide a clean syntax for class destructuring in the future (with pattern matching after that)
  5. The definitions are defined in one place and are not allowed to be extended. Any conditionals would be exhaustive and easy to see.

Proposed implementation:

  1. Use the 'class system', with nominal typing by default
  2. Add a new keyword to define these new types
  3. It should work now with 'switch' statements
data Shape =
    | Square(size:number)
    | Rectangle(width:number, height:number)
    | Circle(radius: number)
    | Shapes(shapes:Shape[])
    ;

Or an enum like type without associated values.

data StatusRegister =
    | Sign
    | Zero
    | F5
    | HalfCarry
    | F3
    | ParityOverflow
    | Subtract
    | Carry
    ;

If ‘data’ is controversial as a keyword, then ‘datatype’ could be used.
I chose 'data' since the keyword 'type' is a type-synonym declaration in both Haskell and TypeScript.
Since Haskell uses 'data' to define new data types, I thought it best to keep that similarity.

Once these declarations are done, they are closed. So you see the entirety of the definition in a single place.

In terms of implementation, the Shape declaration would create a new type or class called Shape. Square, Circle, and Rectangle would be the subclasses. This is a common strategy for supporting the feature in OO languages. It was most notably used in Scala.

The Shape type above could be equivalent to.

interface Shape {};
class Square implements Shape {
    constructor(private size:number);
}
class Rectangle implements Shape {
    constructor(private width:number, private height:number);
}
class Circle implements Shape {
    constructor(private radius:number);
}
class Shapes implements Shape {
    constructor(private shapes:Shapes[]);
}

... or they could be defined as functions that construct that type.

The type guards would switch purely on the value vs. the ‘kind’.
No run-time reflection should be used.

function area(s: Shape) {
    switch (s) {
        case Square: return s.size * s.size;
        case Rectangle: return s.width * s.height;
        case Circle: return Math.PI * s.radius * s.radius;
        case Shapes: return union_rect(s.shapes);
    }
}
// Handling serialization and deserialization say from some Protobuf/Thrift type system
// Notice ordering may not correspond 

function fromJSON(json:any):Shape {
    If (json.hasOwnProperty(‘kind’) === false) throw “Error”;

    switch (json.kind) {
        case 1: return Square(json.size);
        case 2: return Circle(json.radius);
        case 3: return Rectangle(json.width, json.height);
        case 4: return Shapes(json.shapes.map(el => fromJSON(el));
    }
}
function SRfromJSON(json:any):StatusRegister {
    If (json.hasOwnProperty(‘obType’) === false) throw “Error”;

    switch (json.obType) {
        case 1: return ParityOverflow;
        case 2: return Carry;
        case 3: return Zero;
        case 4: return HalfCarry;
        default: throw "Invalid json";
    }
}

Although destructuring is part of ES6, and it can work on a class instance, it uses structural typing.
If two objects have the same shape, the developer may want the guarantee of nominal matching for destructuring. This proposal would make that simple.

// Contrived example of same shape destructing with
// a contrived 'match' expression

data Vector2D =
| Vec2D(x: number, y:number)
| PosVec2D(x: number, y:number)  // Position Vector
;

function vecop_jj(v: Vector2D) {
    let res = match (v) {
        | PosVec2D: throw “Error - cannot mix position vectors with this operation”;
        | Vec2D(x, y): x - y;
    }
}


That is what I have so far. It might be interesting to consider pretty-printing or serialization, but I think the overall object system may determine the preferred implementation.

As a side note, I was thinking very hard about #186 2 weeks ago. I wanted to have a proposal for something this Monday. However, I was trying to unify all the possible cases (enums, string types, classes, and a new variant type). I couldn't come up with a clean solution.

When the recent code landed from Anders on Monday, it was great news. Wwe going to have something we can use very soon in 2.0. It also simplified the problem this suggestion was originally addressing.

@drudru drudru changed the title Suggestion: More on Sum Types and Tagged Unions Suggestion: Sum Types and Tagged Unions without Reflection Jun 18, 2016
@DanielRosenwasser DanielRosenwasser added Suggestion An idea for TypeScript Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. labels Jun 18, 2016
@ghost
Copy link

ghost commented Jun 22, 2016

I really like the type safety of this proposal. Much safer and better than switching on strings.

@drudru
Copy link
Author

drudru commented Jun 23, 2016

Just as an update, I have been reflecting on this problem some more.

It turns out that there are some problems with this technique that give me some pause.

The problem is that this can introduce a lot of 'boilerplate'

For example, lets say we used the above as the Node/AST for TypeScript. In order to traverse these trees, we would need to write code. Ditto for serialization and deserialization.

This is already happening in the TypeScript compiler with: ts.forEachChild. The function is 371 lines long.

In the Haskell,OCaml, and Scala communities, the discussion about 'Boilerplate' has been going on for quite some time and continues to this day. This may be a really complicated problem!

@dead-claudia
Copy link

Few remarks:

  1. No to case Type: .... That visually conflicts with existing switch statements, and the semantics would depend on the types in a very opaque way. (Currently, I know of no statement type whose semantics depend on the type of any part of it.)
  2. I like the idea of a special match statement, and think that should take the place of what you initially considered with the switch.
  3. Nominal typing of that kind of thing may depend on Support some non-structural (nominal) type matching #202.

@dead-claudia
Copy link

dead-claudia commented Aug 24, 2016

@drudru Oh, and although I'm neutral, expect some resistance from others.

@drudru
Copy link
Author

drudru commented Sep 1, 2016

Hi - one more update.

Some interesting things have happened since I opened this issue.

  1. C# 7.0 has shipped with pattern matching.
  2. TypeScript 2.0 RC has shipped with Tagged Unions.

Given the above, I think compatibility will be important. Also, I think the larger community will gain experience and some new solutions will be proposed.

I think it makes sense at this point to close this issue. Thanks for reading.

@drudru drudru closed this as completed Sep 1, 2016
@dead-claudia
Copy link

I'll also mention that a limited form of pattern matching also exists with destructuring. It's not exactly conditional like true pattern matching, but it's a step in that direction.

(And tagged unions in 2.0 RC do technically check for completeness with the unreachable code path analysis, building on the 1.8 type narrowing. Things like this would result in a compiler warning:)

// Switch statement
function getValue(ref: One | Two | Three): number {
  switch (ref.type) {
  case "one": return 1
  case "two": return ref.number
  case "three": return 3
  default: return 4 // unreachable
  }
}

// If-else
function doSomething(ref: One | Two | Three) {
  if (ref.type === "three") {
    blah()
  } else {
    if (ref.type !== "two") return
    baz()
    if (ref.type === "one") {
      doSomethingElse() // unreachable
    }
  }
}

interface One { type: "one" }
interface Two { type: "two"; value: number }
interface Three { type: "three" }

@microsoft microsoft locked and limited conversation to collaborators Jun 19, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Needs Proposal This issue needs a plan that clarifies the finer details of how it could be implemented. Suggestion An idea for TypeScript
Projects
None yet
Development

No branches or pull requests

3 participants