etng-r2/pattern-matching-ftw.txt
author Tony Garnock-Jones <tonygarnockjones@gmail.com>
Wed, 16 Jan 2019 17:15:58 +0000
changeset 438 1fe179d53161
parent 282 36ad47fbeb8d
permissions -rw-r--r--
Add missing primitive implementation for the plain interpreter.
19 May 2009
---------------------------------------------------------------------------

Unify OMeta with pattern matching. Support extensible pattern matching.

Input stream can't hold semantic-values without extra stack
discipline, because inputs and semantic-values are not of the same
type.

The wildcard operator, _, is of type token -> semantic-value

Running example: parenthesised n-ary addition (into binary addition)

  e()		--> e0():a '+' e0():b ^(a + b) / e0()
  paren(p)	--> '(' p():a ')' ^a
  e0()		--> paren(e) / num()
  num()		--> '1' ^1 / '2' ^2 / '3' ^3 / ...


define :e() -> { a=:e0() '+' b=:e0() -> a + b;
                 a=:e0() -> a };

define :paren(p) -> { '(' a=p() ')' -> a }

define :e0() -> { a=:paren(:e) -> a;
                  a=:num() -> a }

define :num() -> { '1' -> 1; '2' -> 2; '3' -> 3; ... }


8 July 2009
---------------------------------------------------------------------------

I should have written something about where the cutpoints in the
backtracking should go. The issue is to do with autocurrying: if too
many or too few arguments are supplied, how are the pattern-matching
continuations wired up?


7 August 2009
---------------------------------------------------------------------------

Input streams have two manifestations: from the POV of the lookup
driver, streams *can* be empty, but from the POV of a *parser*, they
*cannot* be empty: this is the essence of autocurrying. So when the
lookup driver starts running, it examines its input stream. If the
stream is empty, it returns the parser without further effort. [TODO:
figure out what happens to the "receiver" (as distinct from "via") in
this case!] If the stream is nonempty, it *wraps* it in an *infinite
stream* guise, and if the wrapped stream ever internally runs out of
input, a curried function is returned to the caller with a parameter
(dynamic variable) used to speculatively extend the input stream as
subsequent input comes available.

The curried-function representation needs to be a bit special: a
partial match. This may address the TODO about what happens to the
receiver.

Re: cutpoints -- a commit is a cutpoint, and they happen on the arrows
in functions: { .a .b -> .c } has a cutpoint after the .b has been
matched. Essentially any transition from a LHS to an RHS is a
cutpoint. This is involved in what happens to "receiver" vs "via" in
lookup, too.

Here are some notes from a couple of weeks ago that I made in my graph
pad:

 - functions are implicit 'or's of 'seq's by default.

 - stream * kt * kf -> ()

 - currying:: model stream as CPS pair. Then when input runs out,
   nonlocal exit to code that conses an intermediate lambda and waits
   for more input? Problematic because during parsing it's often the
   next unexpected token that causes the parser to switch to a more
   appropriate clause -- and here we lack the means to terminate
   pattern matching!

 - therefore omit currying?? no. Alternative: treat every object as
   "actor"? Messages stream into the actor

 - matcher: stream kt kf ---- stream is always infinite! Will never
   report "empty" to the parser and may suspend the parser pending
   further messages

 - Every object is therefore a parser.


Thoughts on the TODO from above about "receiver" vs "via": Because
sequences used to be seen as actually sugar for real curried
procedures, and the interstitial procedures would be
non-self-capturing, we can ignore supplied receivers to intermediate
curried procedures!

That means that the "receiver" supplied at the first, original
"lookup" needs to be preserved through all intermediate curryings, for
use at the time the "apply" is done. Any "receiver"s supplied after
that first one are to be ignored.


10 August 2009
---------------------------------------------------------------------------

Lining up OMeta and eTNG:

  or :: implicit; clauses in a function
  seq :: implicit; part of currying
  exactly :: (lit)
  anything :: (discard)
  bind :: (bind), but eTNG doesn't do nested patterns here yet
  sequence :: could be a function? a bit like tuple-matching?
  nest :: needs to be provided?
  not :: -
  follow :: -
  many :: -
  many1 :: -


14 August 2009
---------------------------------------------------------------------------

Objects need to present alternately as *interpreter* and
*interpretee*. Interpreters are in the pattern-match role;
interpretees are data (ADTs etc). Data and co-data?

So presenting as an interpreter is straightforward. Presenting as data
is trickier. Ordinary expressions combine objects, interpreter in head
position and syntax in non-head positions. On the pattern-matching
side, the matching logic embodies the interpreter. The matching logic
examines the offered data either *reflectively* or *interactively*.

(Ha - where COLA has a recursive lookup that is ground-out on the
primitive lookup object, we here have a recursive streaming-of-data
that needs to be ground-out on primitive data streams! (as in,
messages should be able to be Real Streams With Behaviour, but in
order to be well-founded, some fake/primitive implementation needs to
be available.)

Reflective examination actually feels pretty interactive, just on the
object's metaobject. Is representation (i.e. normal meta stuff) the
same as data/interpretee in this sense? After all, a pattern-matcher
may wish to examine an object's structure either at a physical level
or a logical level. Normal meta stuff is the physical, representative,
stuff; this interpretee idea is the logical level.

Objects should be able to control how they are presented as data. One
possibility is a two-stage menu/inject, where the interpreter offers a
menu of contexts and the datum injects a context into the menu,
backing off and trying an alternative context on DNU. The symmetric
case works just as well, though, where the datum presents a menu and
the interpreter injects into it. This is effectively multiple dispatch
:-(

    -- an interpreter menu
    -- context     representation-pattern
    { .stream -> { .pair head tail -> ...;
                   .nil            -> ... };
      .tuple  -> { length          -> ... } }

This is also really similar to HTTP content negotiation.

Actually on second thoughts perhaps it's better for the interpreter to
inject a preferred interpretation into the datum, and have it answer
either a representation under that interpretation, or DNU.

    -- data menu for cons
    { .stream k -> k .pair head tail;
      .tuple  k -> k 2 head tail }

    -- data menu for nil
    { .stream k -> k .nil;
      .tuple  k -> k 0 }

Is using DNU appropriate here, or is an explicit failure-k better?

    { .stream kt kf -> kt .pair head tail;
      .tuple kt kf -> kt 2 head tail;
      _ kt kf -> kf () }