Review feasability of First-Class Patterns

[mlhaufe]

Problem 1

Given the following definition and associated expression:

const Expr = Data({ Num: ['value'], Var: ['name'], Mul: ['left', 'right'] })

const e = Mul(Var('x'), Num(1))

How can e be simplified to Var('x')?

Currently here is the idiomatic approach:

// isNum and isVar ellided, but usually defined as well for completeness
const isNum = Trait(Expr, {
    [all]: () => false,
    Num: () => true
})

const simplify = Trait(Expr, {
    [all]: (self) => self,
    Mul: (self) => {
        const {left, right} = self
        if(isNum(left) && left.value == 1)
            return simplify(right)
        else if(isNum(right) && right.value == 1)
            return simplify(left)
        else if(isNum(left) && left.value == 0)
            return Num(0)
        else if(isNum(right) && right.value == 0)
            return Num(0)
        else
            return self
    }
})

const e2 = simplify(e)

With pattern matching (hypothetical syntax) the following may be possible:

const simplify = Trait(Expr, {
    [all]: (self) => self,
    Mul: [
        [ {left:  Num(1)}, ({right}) => right],
        [ {right: Num(1)}, ({left})  => left ],
        [ {left:  Num(0)}, ({left})  => left ],
        [ {right: Num(0)}, ({right}) => right]
    ]
})

Problem 2

For the Fibonacci function, here is the current approach:

const fib = Trait(undefined, {
  [all]: (n) => n == 0 ? 0 :
                n == 1 ? 1 :
                fib(n-1) + fib(n-2)
})

If literals are allowed for Trait and all was replaced by _:

const fib = Trait(Number, {
  0: () => 0,
  1: () => 1,
  _: (n) => fib(n-1) + fib(n-2)
})

References

• First Class Patterns - Mark Tullsen
• Enhancing Type Systems With First-Class Patterns - Lutz Hamel, et al.
• Patterns as Objects in Newspeak - Gilad Bracha
• F Sharp Programming/Active Patterns
• Pattern Matching for an Object-Oriented Dynamically Typed Programming Language - Felix Geller, et al.

Work items:

• #34
• #35
• #38

[mlhaufe]

1. What if multiple patterns match?
2. How do patterns impact Data? Does this open the possibility of predicate/tag checking?
   1. I can't help but think about Unification and Logic/Relational programming
3. Want an otherwise pattern. Can _ be used?
4. Pattern matching arrays?
5. Probably no nested patterns in this first phase. Just === against the members

[mlhaufe]

Pattern syntax

const traitName = Trait(DataDecl, {
  VariantName: (self, ...args) => {...},
  VariantName: [
    [[pattern1, pattern2, ...patternN], (self, v2, ...vN) => {...}]
  ]
})

Pattern types

// Literals
1
false
'foo'

// wildcard
_

//  variant instances
Nil
Cons(1, Nil)
Cons(pattern1, pattern2)
Cons(1, Cons(pattern, Nil)

// structural 
{left: 3, right: Nil }
{left: pattern1, right: pattern2 }