Skip to content

TM010 case matching

Joe Politz edited this page Jul 13, 2013 · 3 revisions

Motivation

Pyret should eventually support full-blown pattern-matching, but this is a significant undertaking. As a partial solution, we can implement a feature similar to type-case from PLAI and PLAI-typed. We'll use the syntax of cases as the keyword.

Proposal

The grammar will be:

cases(expr) expr:
  | identifier [(binding, ...)] => block
  ...
  [ | else => block ]
end

The semantics is entirely defined through desugaring; there is no core component to cases. A cases expression desugars as, by example:

cases(list.List) [1,2,3]:
  | link(x, y) => x + y.length()
  | empty => 0
end

Desugars to

type.case_matcher([1,2,3], [
    { key: "link", action: fun(x, y): x + y.length() end },
    { key: "empty", action: fun: 0 end }
  ],
  fun: raise(error.case-miss("No cases matched", <source-location>)) end)

If an else branch is present, that is thunked as the third argument instead:

cases(list.List) [1,2,3:
  | link(x, y) => x + y.length()
  | else => 0
end

Desugars to

type.case_matcher(val, [
    { key: "link", action: fun(x, y): x + y.length() end }
  ],
  fun: 0 end)

Each data declaration now has a case_matcher compiled for it that finds the first match in the list and returns calling its action, and calls the else thunk otherwise. It maps strings passed as keys to the predicates of the data type (e.g. "link" maps to is-link), and also to helper functions that call the matching action with the right arity and fields. List's matcher looks like:

fun list_matcher(val, cases, else-block):
  preds = { "link": is-link, "empty": is-empty }
  helpers = { "link": fun(f): f(val.first, val.rest) end, "empty": fun(f): f() end }
  matched = for filter(case in cases):
    if not builtins.hasfield(preds, case.key):
       raise(invalid-case("Case " + case.key + " does not exist.", <source location>))
    else:
       preds.[case.key](val)
    end
  end
  if is-empty(matched): else-block()
  else: helpers.[matched.first.key](matchers.first.action)
end

There are more efficient implementations of this to explore, but this is a straightforward specification of the desired behavior.