[RFC FS-1039 Discussion] Struct representation for active patterns

[gsomix]

Discussion for https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1039-struct-representation-for-active-patterns.md

[gsomix]

@dsyme When you have free time could you please give me an advice? I'm going to start implementation of the feature, where should I start? Thanks!

[dsyme]

@gsomix I did take a look at this once before. I tried something like this

1. add a StructOption type to FSharp.Core
2. Identify the places in TypeChecker.fs where we either assume or check that a partial active pattern has option return type. If I remember rightly, this is a bit painful and the code is messy, but let me know if you have trouble
3. At these places, the ideal would be to adjust the logic to say "if we can already see it's a StructOption then don't do the assertion". However, that might not work if the assumption of a non-struct option is made before processing of type annotations. If that's the case then the thing will be harder
4. There may be corresponding cases signature file (.fsi) processing
5. Pattern matching now supports structs so you may be ok for the rest, with very few changes needed

[amongonz]

The .NET standard libraries already use the prefix Value for value-type alternatives of existing types (ValueTuple and ValueTask), so I'd expect it to be called ValueOption, instead of StructOption. Same for Choice.

Also, in my own code I'm using a 'T valoption alias, and I recommend adding a similar alias to FSharp.Core. It makes it look more like 'T option, and refactoring becomes easier too.

[dsyme]

@mistiara @gsomix I'd like to discuss naming for StructOption.

I understand the desire to use ValueOption and we should consider it.

One thing that speaks against it is that the name Value has somewhat different connotations in F#, e.g. val in signatures and member val in class declarations. I wonder if that weighs more heavily than conforming to more .NET general standards for what is definitely an F# specific type.

In my own code I've been using this:

    [<Struct>]
    type StructOption<'T> =
        | UNone
        | USome of 'T
    and 'T uoption = StructOption<'T>

where I suppose U stands for Unboxed. Alternatives would be:

    [<Struct>]
    type ValueOption<'T> =
        | VNone
        | VSome of 'T
    and 'T voption = ValueOption<'T>

    [<Struct>]
    type StructOption<'T> =
        | SNone
        | SSome of 'T
    and 'T soption = StructOption<'T>

    [<Struct>]
    type StructOption<'T> =
        | StructNone
        | StructSome of 'T
    and 'T uoption = StructOption<'T>

and so one. Also there is the more cumbersome alternative of using RequireQualifiedAccess which I'm not in favour of.

Of these I still tend to favour the first of UNone, USome and uoption for some reason - perhaps it is just familiarity.

There is a related question of how we might eventually add (or have the a separate library provide) versions of List.try* functions which transact struct options, e.g. what would these be called?

List.choose??: ('T -> 'U uoption) -> 'T list -> 'U list
List.tryFind??: ('T -> bool) -> 'T list -> 'T uoption
List.tryPick??: ('T -> 'U uoption) -> 'T list -> 'U uoption

Systematic options might be:

List.uchoose??: ('T -> 'U uoption) -> 'T list -> 'U list
List.utryFind??: ('T -> bool) -> 'T list -> 'T uoption
List.utryPick??: ('T -> 'U uoption) -> 'T list -> 'U uoption

or

List.vchoose??: ('T -> 'U uoption) -> 'T list -> 'U list
List.vtryFind??: ('T -> bool) -> 'T list -> 'T uoption
List.vtryPick??: ('T -> 'U uoption) -> 'T list -> 'U uoption

or

List.choosev??: ('T -> 'U voption) -> 'T list -> 'U list
List.tryvFind??: ('T -> bool) -> 'T list -> 'T voption
List.tryvPick??: ('T -> 'U voption) -> 'T list -> 'U voption

I'm not saying these should go into FSharp.Core straightaway, but we should consider them as part of naming.

Please give feedback asap as I'd like to get this type into FSharp.Core so we can start to assume its existence for later language work.

[dsyme]

Please thumbs-up this comment if you would be happy with StructOption/UNone/USome/uoption
and thumbs down if you would be very unhappy with it.

[dsyme]

Please thumbs-up this comment if you would be happy with ValueOption/VNone/VSome/voption and thumbs down if you would be very unhappy with it.

[isaacabraham]

I'm assuming that there won't be any support for struct option in record definitions etc. e.g.

type Foo =
    { x : struct (int * string) // struct tuple
      y : string (struct option) // would this be valid? I guess not
      z : string uoption } // this would be the way to do it I guess (works already)

For consistency if nothing else, I wonder whether sticking with Struct prefixing might help rather than having Struct Tuples but Value Options. What naming do we already use for [<Struct>] DUs anyway - if we're calling them Struct DUs, we should call this a struct option as well IMHO (and then it's just a choice of u, s or struct as a prefix).

[dsyme]

@isaacabraham It's plausible we could do new syntax like that, but I think we wouldn't do it. For tuples, we kind of have to, since they are a form of structural type, or atl east we have the special syntax for them. For other nominal types like struct options and struct choices it is less compelling.

[ForNeVeR]

Please, guys, don't forget about new F# users. I think they could be confused by the U-naming: why is it StructOption but USome? Won't that create a pedagogical problem?

[amongonz]

@dsyme I proposed ValueOption because I originally expected developers would become familiar with ValueTask (and possibly ValueTuple) over time. But I agree the decision should be taken with F# conventions in mind.

I would personally make it:

[<Struct>]
type ValueOption<'T> =
    | UNone
    | USome of 'T
and 'T uoption = ValueOption<'T>

but StructOption is just as fine. Also, it doesn't really matter which one we choose because most developers will use the uoption shorthand anyway.

I'm more worried about the naming of struct-option versions of functions. Since we would already be using the u- prefix, naming them as them List.uchoose seems like the most intuitive option.

But what would we do with struct-option specific functions? I do not want a StructOption module, as that would hurt the ergonomics just as much as StructSome/StructNone. Maybe adding prefixed versions to the existing Option module?

[matthid]

Can someone please clarify why you are all so familiar with u-prefix? Do we already have other apis with this? Personally I find it confusing to mix "unbox" with "struct" naming and we have ulong for unsigned already. I don't like the u prefix at all if there is no other compelling reason (like existing APIs).

Therefore I'd prefer:

    [<Struct>]
    type StructOption<'T> =
        | SNone
        | SSome of 'T
    and 'T soption = StructOption<'T>

Which is consistent in using s and "struct". Also we could add struct option as alias in the future.

[vasily-kirichenko]

@matthid SSome is hard to read.

[dsyme]

I would personally make it ValueOption/UNone/USome/uoption

Yes, that's possible though it seems odd to use both V and U as well as Struct. BTW I think one reason I don't mind u is that the letter occurs in Struct, there is a very slight increase in affinity because of that.

But what would we do with struct-option specific functions? I do not want a StructOption module, as that would hurt the ergonomics just as much as StructSome/StructNone. Maybe adding prefixed versions to the existing Option module?

Yes, that is a possibility

Do we already have other apis with this?

No we don't. I think it's just from my personal code.

Personally I find it confusing to mix "unbox" with "struct" naming and we have ulong for unsigned already. I don't like the u prefix at all if there is no other compelling reason (like existing APIs).

Good points

I'd prefer... StructOption/SNone/SSome/soption

There's something about that I don't like. Is it that s is used for pluralization? Or that SS is not a nice thing to see in my code for historical reasons? Or that soption reads like you say it sop-tion? I don't know. Maybe it's just me. Somehow I'd prefer v or u (though I understand what you have against u)

[dsyme]

Please, guys, don't forget about new F# users. I think they could be confused by the U-naming: why is it StructOption but USome? Won't that create a pedagogical problem?

Is that arguing in favour of StructOption/SNone/SSome/soption or ValueOption/VNone/VSome/voption? thanks

[vasily-kirichenko]

Is it possible to make it so that adding a single open ValueOptions module/namespace/fake module would make all option and all active patterns be struct options and struct active patterns? I just think that everyone would like to use struct options/APs in all new code instead of old ref siblings. So I'd like to have an ability to "switch" struct-mode for a scope (or, better, have structs by default).

[dsyme]

@gsomix I agree we should do that optimization but it can be tricky to get right

• In general you'd like the optimization to apply to arbitrarily large numbers of pattern discriminant. But this means an arbitrarily large active pattern or discrimination function. The inliner/optimizer normally trims off information for large functions. We'd probably need to collect information for things specifically recognised as discrimination functions

• The decision about whether to inline + slice-and-dice the continuations is a bit tricky because additional logic can sit in between the generator and consumer of information. In active patterns used in pattern matching it's probably tractable to put the pieces together

• The decision to inline still has to be made carefully - there really has to be a known consuming continuation for each generated result.

[dsyme]

@gsomix I would love someone to attempt this optimization.

[gerardtoconnor]

@dsyme ... did you mean to @ me not @gsomix?

[gerardtoconnor]

In case those messages were meant for me, I appreciate there is a few considerations, but the wins are big if we can do it, I am happy to start investigating and attempt this optimisation, if I run into any blocks can I query here?

[dsyme]

@gerardtoconnor Yes I meant you :) I agree with you about the direction this should take, subject to my comment above

[gerardtoconnor]

@dsyme thanks for confirming, all points above noted, will investigate this weekend 👍

[amongonz]

Right now active patterns can also be used as functions returning Option/Choice. Would this add a new kind of active pattern that took continuations as arguments? Or would this be just an optimization, not introducing any new kind of pattern?

[gerardtoconnor]

@mistiara this is primarily an optimization so the usage would not change. Ideally this would remove the need to have any function that returns Option/Choice, making AP match the AP function but I need to investigate and test all the edge cases as there a many tricky considerations. Can you given me an example of where you are using an AP as a function to return Option/Choice to see if this can be optimised also? Likely case is that the default will remain the same and we try lift in optimization stage if conditions met.

[amongonz]

@gerardtoconnor I don't do it that often, actually. I was just wondering if you planned on adding a different representation like struct APs would have done.

But after thinking for a while, I also wonder if such an optimization can't apply more generically. We already have inline active patterns, the problem is we can't elide their allocation.

But the proposed optimization already has to figure out how to merge calls to the AP cases with the branches of the consuming match, so I wonder if we can elide the allocation for union types in general, instead of just APs, and let inline APs benefit from it.

So for this example

type Temperature =
    | Celsius of int
    | Farenheit of int

let inline temperature (input:string) =
    let n = Int32.Parse(input.Substring(0, input.Length-2)) // e.g. 24°C, 75°F
    if input.EndsWith("°C") then Celsius n else Farenheit n

let app (argv:string[]) =
    match temperature argv.[0] with
    | Celsius n -> printfn "%d °C" n
    | Farenheit n -> printfn "%d °F" n

the compiler would elide the allocation of temperature's return value in app. And inline active patterns would do so too by virtue of returning Option/Choice like they already do.

[gerardtoconnor]

I have already thought about this optimization generally, why I proposed it here, in an ideal world, with exception of persisted state DUs, we should in theory be able to lift and replace matches with direct calls, it's just easier to implement first with AP as the function bind is in place without value captures etc to worry about, as well as functions usually being small, not blowing up on inlines.

[amongonz]

@gerardtoconnor Sure, that's reasonable! I just wanted to write that down; I love F# but I spend more time than usual removing unintended allocations, so I stay tuned to issues like this one.

[abelbraaksma]

@dsyme, since ValueOption has now been implemented, this can be closed? And status "needs implementation" changed to "implemented"? ;)

Also, that it's implemented is not yet clear from the rfc: https://github.com/fsharp/fslang-design/blob/master/RFCs/FS-1039-struct-representation-for-active-patterns.md

(I don't know about the status of Choice and struct AP though, but if work hasn't started, perhaps they should get their own space?)

[cartermp]

The ValueOption section has its own set of RFCs, e.g. https://github.com/fsharp/fslang-design/blob/master/FSharp.Core-4.5.0.0/FS-1057-valueoption.md

I'll clear out the section in the RFC for this issue, which does remain unimplemented.

[abelbraaksma]

Makes sense, and the new title certainly helps. I wasn't aware of the other RFC, tx.

[cartermp]

No worries! Thanks for pinging. Hard to keep track of these sorts of things over time 🙂