[erlang-questions] View patterns

[Thomas Lindgren]

--- ok <ok@REDACTED> wrote:

> Haskell is starting to eat Erlang's lunch, except
> for hot loading.
> Data.ByteString (and especially
> Data.ByteString.Lazy) is an effective
> replacement for Erlang binaries, with support for
> packing and unpacking
> stuff.  There's even talk about an analogue of 'bit
> syntax'.

If this also involved monads, what I've seen of it
looked interesting, but figuring out the details made
my head hurt. 

(I've in recent years seen at least a handful of
distinct non-Erlang efforts on translating between
bits and tree data, actually. PADS and Packettypes are
two examples. Also, "high level views of low level
representations" in ICFP 2005.)

> One of the things which is about to be added to GHC
> is view patterns.
> The idea is that if E is an expression and P is a
> pattern, then
> 	(E -> P)
> is a pattern.  This pattern matches a value V if and
> only if
> P = (E)(V).

So a simple compilation scheme would be:

   case X of
      (E -> P) -> B; 
      Clss
   end

=>

   case (catch E(X)) of
      P -> B;
      _ -> case X of Clss end
   end

Clearly a pattern appearing several times, like
min_list in the example, will need factoring or it
will be dog slow from repeated evaluation. If patterns
can be known to be side-effect free, a compiler could
treat them as common subexpressions and eliminate them
accordingly. (A haskell compiler would probably do
that immediately.) But let's leave such considerations
for later.

A pattern can then be an expression pattern or a
conventional pattern, with conventional or expression
subpatterns, and so on. The best approach to
evaluating these is probably to defer expression
patterns as late as possible. So, replace an
expression pattern with a placeholder, then match the
placeholder later:

{a, (E1->P1), {b, 4711}, (E2->P2)} =>

{a, X1, {b, 4711}, X2} 
  + subsequent expression matching of (E1->P1)(X1) and
(E2->P2)(X2).

We can then probably break mixed patterns up into
bouts of pattern matching and expression evaluation.
Here is a very simple approach (which certainly could
be improved, but it's concise):

match all of (E1->P1)(X1),...,(En->Pn)(Xn) =>

case {E1(X1), ..., En(Xn)} of
  {P1,...,Pn} -> ...;
  ...
end

You can throw in some conventional pattern matches
there too, I'd guess, but it's probably better to do
them before expression matches (avoid evaluating the
expressions E if possible). Given this approach, the
previous pattern above would then be compiled into:

case X of
  {a, T1, {b, 4711}, T2} ->
     case {E1(T1), E2(T2)} of
        {P1, P2} -> Body;
        ...
     end
  ...
end

Where the ellipses "..." indicate where we might run
into code duplication: the 'failure continuation' is
duplicated. Avoiding code duplication is probably a
key issue for a successful compilation scheme. Think
what happens when the duplications start stacking up.

Obviously, this is just a rough sketch, and may well
run into problems when we start looking at corner
cases. (On the other hand, _we_ won't have to worry
about being maximally lazy or not :-). 

But on consideration, implementing expression patterns
as a source-to-source (or core Erlang) transformation
doesn't seem insurmountable. I think there could be
some nice optimizations in there too, e.g.,
eliminating repeated evaluation, avoiding code
duplication, choosing which expression to evaluate
first, ... 

All in all, it seems like, say, a good, publishable
final project for a clever student.

Best,
Thomas



       
____________________________________________________________________________________
Looking for a deal? Find great prices on flights and hotels with Yahoo! FareChase.
http://farechase.yahoo.com/