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.
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
263
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     1
19 May 2009
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     2
---------------------------------------------------------------------------
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     3
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     4
Unify OMeta with pattern matching. Support extensible pattern matching.
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     5
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     6
Input stream can't hold semantic-values without extra stack
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     7
discipline, because inputs and semantic-values are not of the same
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     8
type.
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
     9
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    10
The wildcard operator, _, is of type token -> semantic-value
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    11
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    12
Running example: parenthesised n-ary addition (into binary addition)
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    13
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    14
  e()		--> e0():a '+' e0():b ^(a + b) / e0()
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    15
  paren(p)	--> '(' p():a ')' ^a
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    16
  e0()		--> paren(e) / num()
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    17
  num()		--> '1' ^1 / '2' ^2 / '3' ^3 / ...
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    18
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    19
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    20
define :e() -> { a=:e0() '+' b=:e0() -> a + b;
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    21
                 a=:e0() -> a };
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    22
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    23
define :paren(p) -> { '(' a=p() ')' -> a }
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    24
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    25
define :e0() -> { a=:paren(:e) -> a;
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    26
                  a=:num() -> a }
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    27
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    28
define :num() -> { '1' -> 1; '2' -> 2; '3' -> 3; ... }
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    29
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    30
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    31
8 July 2009
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    32
---------------------------------------------------------------------------
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    33
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    34
I should have written something about where the cutpoints in the
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    35
backtracking should go. The issue is to do with autocurrying: if too
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    36
many or too few arguments are supplied, how are the pattern-matching
3cba309393c7 Half-way through experimentation with oo:fp:parsing language in etng-r2
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents:
diff changeset
    37
continuations wired up?
277
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    38
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    39
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    40
7 August 2009
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    41
---------------------------------------------------------------------------
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    42
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    43
Input streams have two manifestations: from the POV of the lookup
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    44
driver, streams *can* be empty, but from the POV of a *parser*, they
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    45
*cannot* be empty: this is the essence of autocurrying. So when the
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    46
lookup driver starts running, it examines its input stream. If the
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    47
stream is empty, it returns the parser without further effort. [TODO:
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    48
figure out what happens to the "receiver" (as distinct from "via") in
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    49
this case!] If the stream is nonempty, it *wraps* it in an *infinite
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    50
stream* guise, and if the wrapped stream ever internally runs out of
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    51
input, a curried function is returned to the caller with a parameter
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    52
(dynamic variable) used to speculatively extend the input stream as
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    53
subsequent input comes available.
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    54
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    55
The curried-function representation needs to be a bit special: a
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    56
partial match. This may address the TODO about what happens to the
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    57
receiver.
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    58
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    59
Re: cutpoints -- a commit is a cutpoint, and they happen on the arrows
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    60
in functions: { .a .b -> .c } has a cutpoint after the .b has been
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    61
matched. Essentially any transition from a LHS to an RHS is a
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    62
cutpoint. This is involved in what happens to "receiver" vs "via" in
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    63
lookup, too.
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    64
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    65
Here are some notes from a couple of weeks ago that I made in my graph
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    66
pad:
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    67
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    68
 - functions are implicit 'or's of 'seq's by default.
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    69
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    70
 - stream * kt * kf -> ()
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    71
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    72
 - currying:: model stream as CPS pair. Then when input runs out,
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    73
   nonlocal exit to code that conses an intermediate lambda and waits
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    74
   for more input? Problematic because during parsing it's often the
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    75
   next unexpected token that causes the parser to switch to a more
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    76
   appropriate clause -- and here we lack the means to terminate
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    77
   pattern matching!
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    78
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    79
 - therefore omit currying?? no. Alternative: treat every object as
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    80
   "actor"? Messages stream into the actor
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    81
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    82
 - matcher: stream kt kf ---- stream is always infinite! Will never
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    83
   report "empty" to the parser and may suspend the parser pending
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    84
   further messages
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    85
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    86
 - Every object is therefore a parser.
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    87
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    88
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    89
Thoughts on the TODO from above about "receiver" vs "via": Because
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    90
sequences used to be seen as actually sugar for real curried
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    91
procedures, and the interstitial procedures would be
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    92
non-self-capturing, we can ignore supplied receivers to intermediate
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    93
curried procedures!
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    94
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    95
That means that the "receiver" supplied at the first, original
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    96
"lookup" needs to be preserved through all intermediate curryings, for
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    97
use at the time the "apply" is done. Any "receiver"s supplied after
24ee1ca92b9a Notes on this new pattern-matching/parsing technique.
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 263
diff changeset
    98
that first one are to be ignored.
280
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
    99
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   100
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   101
10 August 2009
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   102
---------------------------------------------------------------------------
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   103
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   104
Lining up OMeta and eTNG:
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   105
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   106
  or :: implicit; clauses in a function
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   107
  seq :: implicit; part of currying
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   108
  exactly :: (lit)
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   109
  anything :: (discard)
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   110
  bind :: (bind), but eTNG doesn't do nested patterns here yet
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   111
  sequence :: could be a function? a bit like tuple-matching?
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   112
  nest :: needs to be provided?
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   113
  not :: -
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   114
  follow :: -
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   115
  many :: -
f0535598e4af Notes on AST for OMeta and eTNG pattern language
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 277
diff changeset
   116
  many1 :: -
282
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   117
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   118
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   119
14 August 2009
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   120
---------------------------------------------------------------------------
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   121
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   122
Objects need to present alternately as *interpreter* and
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   123
*interpretee*. Interpreters are in the pattern-match role;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   124
interpretees are data (ADTs etc). Data and co-data?
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   125
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   126
So presenting as an interpreter is straightforward. Presenting as data
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   127
is trickier. Ordinary expressions combine objects, interpreter in head
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   128
position and syntax in non-head positions. On the pattern-matching
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   129
side, the matching logic embodies the interpreter. The matching logic
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   130
examines the offered data either *reflectively* or *interactively*.
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   131
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   132
(Ha - where COLA has a recursive lookup that is ground-out on the
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   133
primitive lookup object, we here have a recursive streaming-of-data
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   134
that needs to be ground-out on primitive data streams! (as in,
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   135
messages should be able to be Real Streams With Behaviour, but in
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   136
order to be well-founded, some fake/primitive implementation needs to
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   137
be available.)
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   138
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   139
Reflective examination actually feels pretty interactive, just on the
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   140
object's metaobject. Is representation (i.e. normal meta stuff) the
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   141
same as data/interpretee in this sense? After all, a pattern-matcher
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   142
may wish to examine an object's structure either at a physical level
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   143
or a logical level. Normal meta stuff is the physical, representative,
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   144
stuff; this interpretee idea is the logical level.
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   145
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   146
Objects should be able to control how they are presented as data. One
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   147
possibility is a two-stage menu/inject, where the interpreter offers a
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   148
menu of contexts and the datum injects a context into the menu,
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   149
backing off and trying an alternative context on DNU. The symmetric
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   150
case works just as well, though, where the datum presents a menu and
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   151
the interpreter injects into it. This is effectively multiple dispatch
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   152
:-(
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   153
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   154
    -- an interpreter menu
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   155
    -- context     representation-pattern
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   156
    { .stream -> { .pair head tail -> ...;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   157
                   .nil            -> ... };
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   158
      .tuple  -> { length          -> ... } }
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   159
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   160
This is also really similar to HTTP content negotiation.
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   161
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   162
Actually on second thoughts perhaps it's better for the interpreter to
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   163
inject a preferred interpretation into the datum, and have it answer
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   164
either a representation under that interpretation, or DNU.
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   165
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   166
    -- data menu for cons
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   167
    { .stream k -> k .pair head tail;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   168
      .tuple  k -> k 2 head tail }
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   169
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   170
    -- data menu for nil
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   171
    { .stream k -> k .nil;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   172
      .tuple  k -> k 0 }
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   173
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   174
Is using DNU appropriate here, or is an explicit failure-k better?
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   175
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   176
    { .stream kt kf -> kt .pair head tail;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   177
      .tuple kt kf -> kt 2 head tail;
36ad47fbeb8d Notes on data/codata interpretee/interpreter menu/inject
Tony Garnock-Jones <tonyg@kcbbs.gen.nz>
parents: 280
diff changeset
   178
      _ kt kf -> kf () }