New Tagged/discriminated enums and new match operator for pattern matching

[khalyomede]

Hi, just learned about Lobster on Youtube. Big fan of the simplicity and syntax, congratulations!

The proposal below assumes you answer yes to the question "Can you/do you want to implement it". Feel free to totally ditch it if it's not the case!

Tagged enum - typed constructor

We could define enums cases to accept constructors:

import steam

enum Result:
  ok: fn (string)
  error: fn (string)

def get_file_content(path: string) -> Result:
  content = steam_read_file(path)

  if content is nil:
    return error("Could not open file")

  return ok(content)

content = match file_get_content("does-not-exist.yml")
  ok (value: string): value
  error (message: string): message

print(content) # "Could not open file"

content = match file_get_content("README")
  ok (value: string): value
  error (message: string): message

print(content) # "# Hello world"

Tagged enum - with generic parameter

import steam

enum Result<T, E>:
  ok: fn (T)
  error: fn (E)

struct Exception:
  message: string
  stack = []

def get_file_content(path: string) -> Result<string, Exception>:
  content = steam_read_file(path)

  if content is nil:
    return error( Exception { message: "Could not open file" } )

  return ok(content)

content = match file_get_content("does-not-exist.yml")
  ok (value: string): value
  error (exception: Exception): exception.message

print(content) # "Could not open file"

content = match file_get_content("README")
  ok (value): value
  error (exception: Exception): exception.message

print(content) # "# Hello world"

Why

I think lobster did an an amazing job at implementing type safety in a simple manner. I always wondered through different statically analyzed languages (F#, Haskell, V, Zig, ...) and every time I tried to put my head in those, I always stumble upon a "what the freck" moment about either the syntax, or the poor tagged union capability/support (to be completely fair, F# was the closest to my definition of a good and simple language).

I think lobster can definitely differenciate itself by implement true tagged union and pattern matching ability. Languages have always wanted to draw a line between FP and OOP, and Lobster can join them both like a good old Lord of the Ring movie.

More seriously, in my opinion having Tagged union and pattern matching would increase the robustness of the language because this way of describing a program is way much safer since the programmer that use your module not only handle the "happy path" but also all the possible "exception".

End note

This proposal will have no sense if you tell me the compiler is able to statically warn if a code that could throw is not properly try-catched.

The big show stopper about languages implementing throw mecanism is mostly the inability to be able to detect unhandled possible exceptions thrown by a function. If Lobster is able to detect this, then this proposal would have a lower interest for me.

[aardappel]

Yes, I have thoughts about adding tagged unions at some point. Though note:

• Pattern matching is an orthogonal concern from tagged unions, and can equally well be performed on objects. See for example here about adding pattern matching to objects: Add Pattern Matching #113
  • People sometimes like tagged unions because dispatching code for them can be kept next to eachother, as opposed to spread over classes. Lobster can already do that with non-inline methods declared right next to eachother.
• Tagged unions are in some cases all about performance (in Rust, not most FPLs), since they can be in-line allocated rather than dynamically allocated. If max performance is not your concern, then existing objects are largely equivalent.
  • This performance hinges on all cases of the union having very similar amounts of fields. For example if you make a Rust enum where one case has 1 field and the other has 5 fields, and the 1 field case is most frequently used, this is wildly inefficient.
• Tagged unions can have different semantics because they are by value rather than by reference, allowing you to guarantee instances are never shared. If that is not a concern for you, or you actually may want sharing, objects again work just as well.
• People generally like them a lot in Rust because Rust (and FPLs) don't have any good traditional inheritance mechanisms, but Lobster does.

That is to say, people tend to have a lot of excitement for tagged unions but are not actually aware why they want them (over object with inheritance). Personally, my biggest interest from the above would be in performance, I am guessing for you it is pattern matching? What if Lobster had pattern matching on objects, would you still want them?

Anyway, if I'd add them to Lobster, they'd likely piggy-back on struct rather than trying to overload enum with new meaning.

struct Result
struct Ok : Result
struct Error : Result
    err:string

Or maybe we could invent a more convenient syntax to all declare that in 1, but that is immaterial to the concept.

Then, an instance of Result would be the union of sizes of its "subclasses", and have a hidden type field, all passed by value like current structs already are.

If you look in TODO.TXT in the repo, you'd find these notes on tagged unions (which I call ADTs, from the FPL world):

- NOTE: now that we have inline structs, ADTs should be based on them, since being same-sized
  and being inline go so wonderfully together!
  - This would make types like Maybe/Optional etc super cheap.
  - don't even need to invent some separate enum/adt feature and use pattern matching for this,
    structs that participate in an inheritance hierarchy can simply have a typeinfo prefixed,
    ONLY when they are in a context of the superclass! That is even more efficient than enums
    in Rust, which presumably always carry their tag. In fact it is more similar to "fat" trait
    pointers in Rust, except without the pointers. A tagged struct can even shrink to not need
    the padding to bring all these structs to the same size.. and all this is easy because they're
    always copied.
- Rust's same-size ADTs with value semantics allow interesting copy-over use cases that are not
  possible in even C++, where there is no need to update pointers to an object.
  Maybe we can have a declaration in Lobster that forces a certain set of derived classes to be
  padded to the same size, with a special overwrite operator. The type of the variable would need
  to be of the superclass, and the superclass itself should maybe not be instantiable, or also be
  the same size.
  Basically you'd declare the superclass as everything below here is same size.
  What are examples of algorithms that could be simpler this way?
  - game objects changing state
  - AST node being changed
  - Type variables! This one is hard to do without.
  - Values in an interpreter
  Though most of these are easy to do with existing code.. it is more to avoid allocation and
  allow these values to be inline? Without inline values, you first have to construct on the heap
  before overwrite. Still useful to be possible for cases like type variables.
- Features to make it easier to use structs ADT style as opposed to inheritance
  - ADT is similar to a base class with no members and a fixed set of sub-classes.
    - So make that use case into a simpler declaration syntax.
  - extend switch to do pattern matching.
    - failing that, a switch that can use types as case labels would be a good start,
      and simple to do given that we have type indices!

[khalyomede]

Thank you for giving your honest point of view about it. If Lobster had pattern matching over object this would be sufficient enough for my use case (and as you suggested I would represent my ADTs using structs). In fact, I mentioned generic tagged unions, but personally this would not be of a big interest for me to be honest. Again structs would be fine for me!

As long as Lobster correct me when I forget to check an error branch in my code, and I do not have errors at runtime, I'm happy and open to anything. End goal: to sleep at night 😂

Happy to know this was already on your todo list and you considered them by design. I really like your honesty thank you again!

[aardappel]

Oh and as for your note on exceptions: Lobster does not have language-native exceptions. It does however have them implemented in terms of non-local returns in exceptions.lobster, and if you do a throw thats not inside a try you will indeed get an error.

[khalyomede]

Very cool, then since there is some kind of safety on this area, I guess my need for tagged enums/pattern matching is less important. While this could be a good idea to implement it, it has the drawback of overloading/complexifying the language. Maybe other folks will find other useful use-cases but for me that will do it.

Thank you for your instructive and insightful view on this subject. I learned on the princess and I felt heard. That means a lot to me. Hope the community sticks to this way of behaving, keep up the good work!

[aardappel]

For now, we have exhaustive switch on types, which goes pretty far towards this functionality, is simple and fast!

Example:

lobster/tests/typeswitch.lobster

Lines 6 to 77 in b74f00c

	abstract class A:
	a = 0
	class B : A
	b = 1
	abstract class C : A
	c = 2
	class D : C
	d = 3
	class E : C
	e = 4
	class F : E
	f = 5
	// 6 classes, but 2 are abstract, so this switch will demand that exactly 4 cases
	// must always be covered!
	/*
	(A)
	|\
	B (C)
	|\
	D E
	|
	F
	*/
	let tests = [ B {}, D {}, E {}, F {} ]
	// Exactly 1 case per class.
	let results1 = map(tests) t:
	switch t:
	case B: t.b
	case D: t.d
	case E: t.e
	case F: t.f
	// No default needed / allowed!
	assert equal(results1, [ 1, 3, 4, 5 ])
	// Subclasses can be done by superclasses.
	let results2 = map(tests) t:
	switch t:
	case B: t.b
	case D: t.d
	case E: t.e
	// No default needed / allowed!
	assert equal(results2, [ 1, 3, 4, 4 ])
	// Abstract base class may implement for all subclasses.
	let results3 = map(tests) t:
	switch t:
	case B: t.b
	case C: t.c
	// No default needed / allowed!
	assert equal(results3, [ 1, 2, 2, 2 ])
	// Probably bad practice, but defaults are still allowed.
	let results4 = map(tests) t:
	switch t:
	default: t.a // Can't access anything else!
	case F: t.f
	assert equal(results4, [ 0, 0, 0, 5 ])

Docs:

lobster/docs/source/language_reference.md

Lines 727 to 750 in b74f00c

	You can also "dynamic dispatch" with `switch` ! You can use class names as
	switch cases:
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	switch x:
	case A: print x.field_in_a
	case B: print x.field_in_b
	~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
	As you can see, the type of variable switched on will be "upgraded" to the type
	matched, so you can access its fields.
	switches on types are "exhaustive", meaning if you don't use a `default` case
	(and its a good habit to not use those) you will get a compile-time error if
	a type is not covered by a switch (all possible subclasses of the type of the
	switched on value).
	Superclass cases can apply to subclass cases, and if both are present, the
	most specific case will always be used. It is a good idea to make superclasses
	`abstract` for use with `switch`, that way you may omit a case for them,
	causing all their subclasses to need their own case.
	The actual implementation use vtables much like the above dynamic dispatch,
	so is similar in speed too.