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