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

Erased type-tagged anonymous union types #538

Open
alfonsogarciacaro opened this issue Feb 14, 2017 · 23 comments
Open

Erased type-tagged anonymous union types #538

alfonsogarciacaro opened this issue Feb 14, 2017 · 23 comments

Comments

@alfonsogarciacaro
Copy link

@alfonsogarciacaro alfonsogarciacaro commented Feb 14, 2017

Modified Proposal (by @dsyme)

This is a suggestion to add adhoc structural type-tagged union types where

  • type syntax (A|B) or Typed(A|B) or Typed<A,B>
  • each type of (A|B|C|...) is distinct and non-overlapping w.r.t. runtime type tests
  • such types are erased to object
  • introducing such a union value would need to be either explicit (e.g. using some new operator like Typed) or type-directed or both

See #538 for original proposal. e.g. this would allow some or all of these:

let generateValue1 () : Typed(int | string)) = if Monday then 2 else "4"

let generateValue2 () = if Monday then Typed 2 else Typed "4"

let eliminateValue (x : Typed(int | string)) = ...
    match x with 
    | :? int as i ->  ...
    | :? string as s -> ...

let eliminateValue2 x = ...
    match x with 
    | Typed(i : int) ->  ...
    | Typed(s; string) -> ...

type Allowed =  Typed(int | string)

There are plenty of questions about such a design (e.g. can you eliminate "some but not all" of the cases in a match? Is column-polymorphism supported?). However putting those aside, such a construct already has utility in the context of Fable, since it corresponds pretty closely to Typescript unions and how JS treats values. It also has lots of applications in F# programming, especially if the use of Typed can be inferred in many cases.

Now, this construct automatically gives a structural union message type , e.g.

type MsgA = MsgA of int * int
let update1 () = Typed (MsgA (3,4))

type MsgB = MsgB of int * int
let update2 () = Typed (MsgB (3,4))

val update1 : unit -> Typed MsgA  // actually : unit -> Typed (MsgA | ..), i.e. column-generic on use
val update2 : unit -> Typed MsgB // actually : unit -> Typed (MsgB | ..), i.e. column-generic on use

and a combination of update1 and update2 would give

let update = combine update1 update2 

val update : unit -> Typed (MsgA | MsgB)

As noted in the comments, some notion of column-generics would likely be needed, at least introduced implicitly at use-sites.

Original Proposal (@alfonsogarciacaro)

I propose we add erased union types as an F# first citizen. The erased union types already exist in Fable to emulate Typescript (non-labeled) union types:

http://fable.io/docs/interacting.html#Erase-attribute

Note that Fable allows you to define your custom erased union types, but this is because it's painful to type a generic one like U2.Case1. If the compiler omits the need to prefix the argument, this wouldn't be necessary and using a generic type can be the easiest solution.

The F# compiler could convert the following code:

// The name ErasedUnion is tentative
// The compiler should check the generic args are different
let foo(arg: ErasedUnion<string, int>) =
    match arg with
    | ErasedUnion.Case1 s -> s.Length
    | ErasedUnion.Case2 i -> i

// No need to instantiate ErasedUnion, but the compiler checks the type
foo "hola"
foo 5
// This doesn't compile
foo 5.

Into something like:

let foo(arg: obj) =
   match arg with
   | :? string as s -> s.Length
   | :? int as i -> i
   | _ -> invalidArg "arg" "Unexpected type"
  • Pros: It will make the Fable bindings generated from Typescript declaration files much more pleasant to work with.

  • Cons: It's a feature that seems to be exclusively dedicated to interact with a dynamic language like JS.

  • Estimated cost (XS, S, M, L, XL, XXL): S

Alternatives

For Fable it's been suggested to generate overloads in the type bindings instead of using erased union types:

interface IFoo {
    foo(arg: string | number): void;
}
type IFoo =
    abstract foo: arg: string -> unit
    abstract foo: arg: number -> unit

However these has some problems:

  • It can quickly explode when you have several erased union arguments
  • Due to type inference the F# compiler many times doesn't know which overload to use
  • Cannot be used in properties
  • Doesn't let you use erased unions yourself.

Affadavit

Please tick this by placing a cross in the box:

  • This is not a question (e.g. like one you might ask on stackoverflow) and I have searched stackoverflow for discussions of this issue
  • I have searched both open and closed suggestions on this site and believe this is not a duplicate
  • This is not something which has obviously "already been decided" in previous versions of F#. If you're questioning a fundamental design decision that has obviously already been taken (e.g. "Make F# untyped") then please don't submit it.

Please tick all that apply:

  • This is not a breaking change to the F# language design
  • I would be willing to help implement and/or test this
  • I or my company would be willing to help crowdfund F# Software Foundation members to work on this
@AviAvni

This comment has been minimized.

Copy link

@AviAvni AviAvni commented Feb 14, 2017

This is sound like it need to be implemented with CompilationRepresentationAttribute
Like the way the option.None represents as null so you can defined your erased union

@Horusiath

This comment has been minimized.

Copy link

@Horusiath Horusiath commented Feb 15, 2017

@alfonsogarciacaro erased unions are not only a thing for dynamic lang transpilation. They are also useful in message-based systems i.e. when you want to describe protocols in as a closed set of messages (in case of F# those could be discriminated unions). In that case a behavior that wants to satisfy more than one protocol, must have some way to define union of those, which so far is possible only as a lowest common denominator (usually an obj type).

@dsyme

This comment has been minimized.

Copy link
Collaborator

@dsyme dsyme commented Feb 15, 2017

There are some other interesting reasons for this compiler feature. One is that we frequently hit situations in the F# compiler where a union type incurs an entire extra level in allocations, e.g.

type NameResolutionItem = 
    | Value of ValRef
    | UnionCase of UnionCaseRef
    | Entity of EntityRef
    | ...

The needs for this type are relatively "low perf" (cost of discrimination doesn't really matter - multiple type switches are ok) but the type gets many, many long-lived allocations when the F# compiler is hosted in the IDE. One could make the type a struct wrapping an obj reference manually, but simply adding an annotation to represent this as an erased union type and discriminate by type switching would be a much less intrusive code change. (Note using a struct union would not work well as the struct would still have a dsicrimination tag integer, and would have one field for each union case - struct unions are by no means perfect representations for multi-case types as things stand at the moment)

Estimated cost (XS, S, M, L, XL, XXL): S

:) There's not really any such thing as "S" for language features :) I'd say "M" or "L".

... CompilationRepresentationAttribute ...

yes that would seem natural

@robkuz

This comment has been minimized.

Copy link

@robkuz robkuz commented Feb 15, 2017

Will there be multiple ErasedUnion s under this proposal?
Like ErasedUnion3, ErasedUnion4 etc.?

@AviAvni

This comment has been minimized.

Copy link

@AviAvni AviAvni commented Feb 15, 2017

@robkuz if the implementation will be with CompilationRepresentationAttribute then you can create your own erased union

[<CompilationRepresentationAttribute(CompilationRepresentationFlags.ErasedUnion)>]
type DU<'a, 'b> = A of 'a | B of 'b
@alfonsogarciacaro

This comment has been minimized.

Copy link
Author

@alfonsogarciacaro alfonsogarciacaro commented Feb 15, 2017

@AviAvni @dsyme Please note that if this just enables a CompilationRepresentationFlags.ErasedUnion on customly defined unions and doesn't allow implicit conversions when passing arguments (in the example above writing foo "hola" instead of foo (ErasedUnion.Case1 "hola")), there won't be much benefit for Fable, as this is basically the same situation as we have now.

@ijsgaus

This comment has been minimized.

Copy link

@ijsgaus ijsgaus commented Feb 16, 2017

This is almost same as or on type operator.T1 or T2. In perspective can be realized by special attribute on function. Full erased from compiled code. But how to save metadata?

@dsyme

This comment has been minimized.

Copy link
Collaborator

@dsyme dsyme commented Feb 17, 2017

But how to save metadata?

I think the intent is that the types would be erased (like other F# information). The metadata would only available at compile-time through the extra blob of F#-specific metadata that F# uses

@cartermp

This comment has been minimized.

Copy link
Member

@cartermp cartermp commented Feb 20, 2017

I think that given the reasoning above (both for FABLE and the use case @Horusiath mentioned), this would be a good addition. 👍

@Richiban

This comment has been minimized.

Copy link

@Richiban Richiban commented Mar 14, 2017

Is it very important that the type is erased?

Perhaps it's a slightly separate proposal, but I would love to have ad-hoc type unions in the form:

let print (item : string | int) = 
    match item with
    |  s : string -> printfn "We have a string: %s" s
    |  i : int ->   printfn "We have an int: %i" i

Which would essentially compile down to the same IL as:

let print (item : Choice<string, int>) = 
    match item with
    | Choice1Of2 s -> printfn "We have a string: %s" s
    | Choice2Of2 i -> printfn "We have an int: %i" i

and, more importantly, at the callsite:

print "Hello world"

instead of:

print (Choice1Of2 "Hello world")
@alfonsogarciacaro

This comment has been minimized.

Copy link
Author

@alfonsogarciacaro alfonsogarciacaro commented Jul 23, 2017

In Fable we've finally managed to remove the erased union case name by using the so-called erased/implicit cast operator !^. Check this and this. So now it's possible to do:

let foo(arg: U2<string, int>) =
    match arg with
    | U2.Case1 s -> s.Length
    | U2.Case2 i -> i

// No need to write foo(U2.Case1 "hola")
foo !^"hola"
foo !^5
// The argument is still type checked. This doesn't compile
foo !^5.
@ovatsus

This comment has been minimized.

Copy link
Member

@ovatsus ovatsus commented Dec 3, 2017

TypeScript also supports string literals in these union types, i.e, in addition to type T1 = number | string, it also supports type T1 = number | "string1" | "string2". Would be nice to also support that.

Or alternatively, if string enums were supported like in TypeScript, we could acheive the same effect that way:

    enum Colors { Red = "RED", Green = "GREEN", Blue = "BLUE" }
    type T = number | Colors
@alfonsogarciacaro

This comment has been minimized.

Copy link
Author

@alfonsogarciacaro alfonsogarciacaro commented Dec 4, 2017

@cloudRoutine

This comment has been minimized.

Copy link
Collaborator

@cloudRoutine cloudRoutine commented Dec 20, 2017

@Richiban is this what you're looking for? - Polymorphic Variants

@dsyme dsyme mentioned this issue Feb 21, 2018
5 of 5 tasks complete
@dsyme

This comment has been minimized.

Copy link
Collaborator

@dsyme dsyme commented Mar 2, 2018

@Richiban @alfonsogarciacaro I hijacked this suggestion to convert this to a suggestion for erased ad-hoc type unions of the kind suggested by @Richiban

(Note sure what the callsite would be though @Richiban - perhaps what you say)./

@dsyme dsyme changed the title Erased union types (like Typescript union types) Erased union types Mar 3, 2018
@dsyme dsyme changed the title Erased union types Erased type-tagged anonymous union types Mar 3, 2018
@ijsgaus

This comment has been minimized.

Copy link

@ijsgaus ijsgaus commented Mar 3, 2018

Can we make this types not erased? Why not introduce base implementation on Typed<'t1, 't2, ...> and make this as member of FSharp.Core

@Richiban

This comment has been minimized.

Copy link

@Richiban Richiban commented Mar 3, 2018

@ijsgaus But if it's not erased then it's no difference from Choice<'a,' b>

@wallymathieu

This comment has been minimized.

Copy link

@wallymathieu wallymathieu commented Aug 30, 2018

This seems like a really sweet suggestion! I imagine it could help the performance of a lot of library code.

@voronoipotato

This comment has been minimized.

Copy link

@voronoipotato voronoipotato commented Apr 4, 2019

Would this help this problem?

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose | Cardinal | Mallard
let x  = Goose 7

This code fails. Goose in the Bird DU shadows Goose as a type and turns it into an Atom. This shadowing happens silently and at least to me is surprising.

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose of Goose | Cardinal of Cardinal | Mallard of Mallard
let x  = Goose 7

The type shadowing here still means I can't move forward, because there's no way to make a Goose....

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose' of Goose | Cardinal' of Cardinal | Mallard' of Mallard
let x  = Goose' (Goose 7)

This works. This kind of situation happens where someone created a single case DU, and it gets consumed by someone who can't muck with the original DU for fear of breaking existing code.

@BillHally

This comment has been minimized.

Copy link

@BillHally BillHally commented Apr 6, 2019

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose of Goose | Cardinal of Cardinal | Mallard of Mallard
let x  = Goose 7

The type shadowing here still means I can't move forward, because there's no way to make a Goose....

You can make an instance of the Goose type by specifying the type as well as the case:

let x = Goose.Goose 7 // This works

When wrapped in a module, you can still access everything, but there is weirdness:

module Birds =
    type Goose = Goose of int
    type Cardinal = Cardinal of int
    type Mallard = Mallard of int
    type Bird = Goose of Goose | Cardinal of Cardinal | Mallard of Mallard

open Birds

If you specify Birds.Goose this gives you the Goose case of the type Goose, and
you can't specify it as Birds.Goose.Goose i.e. using the format Module.Type.Case:

let gooseA = Goose.Goose 7 // Type.Case
let gooseB = Birds.Goose 7 // Module.Case
//let gooseC = Birds.Goose.Goose 7 // Module.Type.Case // <-- Doesn't work

Conversely, you must use that form if you wish to fully specify the Goose case of the Bird type i.e.
you must specify it as Birds.Bird.Goose:

let gooseBird1 = Goose gooseA // Case
//let gooseBird2 = Birds.Goose gooseA // Module.Case // <-- Doesn't work
let gooseBird2 = Birds.Bird.Goose gooseA // Module.Type.Case
@realvictorprm

This comment has been minimized.

Copy link
Member

@realvictorprm realvictorprm commented Oct 2, 2019

Would this help this problem?

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose | Cardinal | Mallard
let x  = Goose 7

This code fails. Goose in the Bird DU shadows Goose as a type and turns it into an Atom. This shadowing happens silently and at least to me is surprising.

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose of Goose | Cardinal of Cardinal | Mallard of Mallard
let x  = Goose 7

The type shadowing here still means I can't move forward, because there's no way to make a Goose....

type Goose = Goose of int
type Cardinal = Cardinal of int
type Mallard = Mallard of int
type Bird = Goose' of Goose | Cardinal' of Cardinal | Mallard' of Mallard
let x  = Goose' (Goose 7)

This works. This kind of situation happens where someone created a single case DU, and it gets consumed by someone who can't muck with the original DU for fear of breaking existing code.

This code would be particulary useful for reusing existing cases and avoiding to nest it.

@abelbraaksma

This comment has been minimized.

Copy link

@abelbraaksma abelbraaksma commented Oct 2, 2019

@dsyme,although the discussion has been dormant a bit in this topic, I think this is still a very valuable addition to the language.

Perhaps we could move this forward and mark it approved in principle, so that we can start working it out into an RFC? I'd be willing to put in the effort for that.

@cartermp

This comment has been minimized.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
You can’t perform that action at this time.