Simplifying Pattern Matches

[AttilaMihaly]

Problem Statement

The Morphir IR supports patterns at various places in the logic. Patterns are a powerful construct that can be used to test for equality of values, to deconstruct tuples, tagged unions and lists and they can also be nested to create more complex patterns. This makes them a very convenient tool but the flexibility they provide also makes them challenging to transpile into languages that don't support the same form of patterns.

Proposal

What makes mapping patterns especially challenging is that they cover a wide range of different types and for each type of value patterns are used differently. For tagged unions we usually want to branch out based on the tag, for lists we do that based on the number of items in the list and for some built-in types we are looking for exact equality. If we had a specific construct for each of these, the mapping would become much easier because we would limit the number of possibilities in each case significantly.

Implementation Details

Current pattern definition

type Pattern a
    = WildcardPattern a
    | AsPattern a (Pattern a) Name
    | TuplePattern a (List (Pattern a))
    | ConstructorPattern a FQName (List (Pattern a))
    | EmptyListPattern a
    | HeadTailPattern a (Pattern a) (Pattern a)
    | LiteralPattern a Literal
    | UnitPattern a

Matching tagged unions

A tagged union is represented as a set of constructors in Morphir. Each constructor has zero or many arguments. Since a union represents an "or" relationship between the different constructors it naturally maps to control flow where the logic branches out by tag. Here's a simple way to represent that construct:

type Value 
    = -- ...
    | BranchOutByTag Value (Dict Name Value) (Maybe Value)

• The first argument is the value that we are matching against.
• The second argument is a dictionary of names to values where the name represents each constructor name (tag) and the value represents the logic that should be returned if the value being matched was created using that constructor.
• The last argument represents an optional default value that will be returned if the constructor name is not found in the dictionary.
  • The optionality of this default value is directly aligned with the exhaustiveness of the dictionary. There are only two valid configurations:
    • When the default value is not specified the dictionary should contain every constructor defined in the tagged union.
    • When the default value is specified the dictionary should not be exhaustive.
• The value in the second and third arguments should be a lambda or a simple value depending on the number of arguments the constructor has:
  • When the constructor has no arguments the type of the value can be anything.
  • When the constructor has N number of arguments (where N > 0) the value should be a function taking N arguments and the argument types should match up with the constructor's argument types.

Matching lists

When matching lists we want to:

• Branch out based on the size of the list. The size can be specified in multiple ways:
  • expect at least N number of items
  • expect exactly N number of items (expecting an empty list is a special case of this)
• Assign variable names to specific items in the list.

Here's one way to represent such a construct:

type Value 
    = -- ...
    | BranchOutByListItems (List ( ListPattern , Value ))

type ListPattern = AnyListPattern Name | EmptyListPattern | HeadTailPattern Name ListPattern 

Destructuring tuples

Destructuring tuples simply means assigning variable names to its elements. There is no conditional processing or branching involved for this construct.

The simplest way to achieve this is to take a tuple and pass it to a function that has the same number of arguments as many arguments the tuple has. The structure could be as simple as:

type Value 
    = -- ...
    | DestructureTuple Value Value

To make it easier to understand here's how that would look like in Elm:

deconstructTuple ( 1, "foo", True )  
    (\first second third ->
        -- first == 1
        -- second== "foo"
        -- third == True
    )

Branching out on literal values

The only remaining pattern we need to define a construct for is LiteralPattern. We will simply use if/then/else to represent this for now. We might want to get into branching out by ranges for comparable types in the future.

[AttilaMihaly]

Since the use of Tuples is very limited in business models, we should also consider removing support for arbitrary size tuples and only support pairs using and SDK type instead of direct language support.

[mrkmarron]

Hi Attila, I like the overall design but have a couple of thoughts/questions.

Tagged Unions:
The second argument is specified with “The value in the second and third arguments should be a lambda”. Some of the languages we target don’t have direct support for lambdas or the use of lambdas as performance/analysis implications. I think it would be a more general, and nearly as simple design, to have the second argument be a tuple [BoundNames, Value] where BoundNames is a List of (fresh) names that will be bound to the constructor arguments and the Value is an Expression that can refer to these names + any other in scope names. This allows an easy compilation to a lambda but, also for other languages, and easy conversion to multiple assignment followed by a the translated expression.

Destructuring Tuples:
I have a similar comment on the forced use of a lambda here. Would like to see a var list + Value instead of requiring the value is a lambda.

And a +1 to simplifying the Tuples case to just pairs if that is viable for your needs.

[AttilaMihaly]

I think it would be a more general, and nearly as simple design, to have the second argument be a tuple [BoundNames, Value] where BoundNames is a List of (fresh) names that will be bound to the constructor arguments and the Value is an Expression that can refer to these names + any other in scope names. This allows an easy compilation to a lambda but, also for other languages, and easy conversion to multiple assignment followed by a the translated expression.

Makes total sense. It's much easier to work with an explicit structure like that. We'll follow that approach in the implementation.