-
Notifications
You must be signed in to change notification settings - Fork 7
/
concept.html
343 lines (280 loc) · 15 KB
/
concept.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
<!DOCTYPE html>
<html lang="en">
<head>
<!--# include file="/templates/header.html" -->
<style>
.version {
padding-top: 10px;
color: #888;
}
.version2 {
padding-top: 0px;
color: #888;
}
.CodeMirror {
margin-top: 0px;
}
</style>
<title>Egison - Concept of Egison Pattern Matching</title>
</head>
<body data-spy="scroll" data-target=".bs-sidebar" data-offset="0">
<!--# include file="/templates/navbar.html" -->
<div class="container manual">
<div class="row">
<div class="col-md-12" id="top" role="complementary">
<h1>The Concept of Egison Pattern Matching</h1>
</div>
</div>
<div class="row">
<div class="col-md-12" role="main">
<hr/>
<p>
The aim of this document is to explain the concept of Egison as quickly as possible.<br/>
We use pseudocode of Haskell to make it easy to understand for those who don't used to parenthesized syntax.<br/>
</p>
<hr/>
<h2>Introduction</h2>
<p>
Pattern-matching is an important feature of programming languages.<br/>
Pattern-matching enables us to express data decomposition and conditional branches <!-- that make programs messy --> in a simple pattern-matching expression.
</p>
<p>
However, the existing pattern-matching expressions have a problem that they are only capable against the limited range of data types.<br/>
For example, they are good at pattern-matching against lists, but not good at pattern-matching against multisets and sets that ignore the order of the elements.<br/>
Therefore, there still exist data operations that we cannot express directly.
</p>
<p>
Egison is a programming language designed to solve this problem.<br/>
</p>
<p>
In the following sample code, we are enumerating the elements that appear multiple times in a collection.<br/>
If we write it in the existing languages in a naive way without using library functions, we need to write nested loops and a conditional branch.<br/>
If we write it in Egison, we can write it in a single pattern-matching expression.
</p>
<div class="row">
<div class="col-md-6" role="main">
<div class="version">Ruby version</div>
<textarea class="ruby-code">xs = [1,2,3,2,4]
pairs = []
(1..xs.length).each do |i|
(i+1..xs.length).each do |j|
if xs[i] == xs[j]
pairs.push(xs[i])
end
end
end
p(pairs)#=>[2]</textarea>
</div>
<div class="col-md-6" role="main">
<div class="version">Egison version</div>
<textarea class="code">(match-all {1 2 3 2 4} (list integer)
[<join _ <cons $x <join _ <cons ,x _>>>>
x]);=>{2}</textarea>
</div>
</div>
<p>
In the following sections, we will explain what is the novelty of Egison with specific examples.
</p>
<h2>Syntax of Pattern-Matching</h2>
<p>
Let us introduce the syntax of the <code>match-all</code> expression.<br/>
We can explain the concept of Egison with only this expression.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all
{1 2 3} ; Target
(list integer) ; Matcher
[<cons $x $xs> [x xs]] ; Match-Clause: [Pattern Body]
)
;=>{[1 {2 3}]} ; Result</textarea>
<p>
The characteristic of our <code>match-all</code> expression is it takes a <i>matcher</i>.
Our interpreter matches the target with the pattern in the way specified with the matcher.<br/>
A matcher specifies the way of pattern-matching.
</p>
<p>
If we wrote the same meaning code in Haskell, it will be as follow. (<b>The following code does not run because Haskell does not support such kind of syntax for now.</b>)
</p>
<div class="version">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll
[1, 2, 3] as -- Target ('as' is a reserved word for pattern-matching)
(List Integer) with -- Matcher ('with' is a reserved word for pattern-matching)
x:xs -> (x, xs) -- Match-Clause: Pattern -> Body
-- =>[(1,[2,3])] -- Result</textarea>
<h2>Modularization of the Way of Pattern-Matching</h2>
<p>
We can define the way of pattern-matching for each data type.<br/>
In the following example, we do pattern-matching against a collection as a list, multiset and set respectively.<br/>
The pattern constructor <code>cons</code> divides a collection into an element and the rest.<br/>
The meaning of <code>cons</code> varies for each matcher and is defined in Egison libraries for each matcher.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all {1 2 3} (list integer) [<cons $x $xs> [x xs]])
;=>{[1 {2 3}]}
(match-all {1 2 3} (multiset integer) [<cons $x $xs> [x xs]])
;=>{[1 {2 3}] [2 {1 3}] [3 {1 2}]} ; The order of elements is ignored
(match-all {1 2 3} (set integer) [<cons $x $xs> [x xs]])
;=>{[1 {1 2 3}] [2 {1 2 3}] [3 {1 2 3}]} ; The order and duplication of elements are ignored</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll [1, 2, 3] as (List Integer) with x:xs -> (x, xs)
-- =>[(1,[2,3])]
matchAll [1, 2, 3] as (Multiset Integer) with x:xs -> (x, xs)
-- =>[(1,[2,3]),(2,[1,3]),(3,[1,2])] ; The order of elements is ignored
matchAll [1, 2, 3] as (Set Integer) with x:xs -> (x, xs)
-- =>[(1,[1,2,3]),(2,[1,2,3]),(3,[1,2,3])] ; The order and duplication of elements are ignored</textarea>
<p>
Please note that we are handling pattern-matching with <b>multiple results</b>.<br/>
This feature is necessary to pattern-matching against data types whose data have no standard form such as multisets and sets.<br/>
This is because they have multiple ways of destruction.
</p>
<p>
We can extract two elements from a collection with the nested <code>cons</code> pattern.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all {1 2 3} (list integer) [<cons $x <cons $y _>> [x y]])
;=>{[1 2]}
(match-all {1 2 3} (multiset integer) [<cons $x <cons $y _>> [x y]])
;=>{[1 2] [1 3] [2 1] [2 3] [3 1] [3 2]}
(match-all {1 2 3} (set integer) [<cons $x <cons $y _>> [x y]])
;=>{[1 1] [1 2] [2 1] [1 3] [2 2] [3 1] [2 3] [3 2] [3 3]}</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll [1, 2, 3] as (List Integer) with x:y:_ -> (x, y)
-- =>[(1,[2,3])]
matchAll [1, 2, 3] as (Multiset Integer) with x:y:_ -> (x, y)
-- =>[(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)]
matchAll [1, 2, 3] as (Set Integer) with x:y:_ -> (x, y)
-- =>[(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),(2,3),(3,2),(3,3)]</textarea>
<p>
We have the <code>join</code> pattern constructor, which divides a collection into two collections.<br/>
The meaning of <code>join</code> also varies for each matcher and is defined in Egison libraries for each matcher.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all {1 2 3} (list integer) [<join $xs $ys> [xs ys]])
;=>{[{} {1 2 3}] [{1} {2 3}] [{1 2} {3}] [{1 2 3} {}]}
(match-all {1 2 3} (multiset integer) [<join $xs $ys> [xs ys]])
;=>{[{} {1 2 3}] [{1} {2 3}] [{2} {1 3}] [{3} {1 2}] [{1 2} {3}] [{1 3} {2}] [{2 3} {1}] [{1 2 3} {}]}</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll [1, 2, 3] as (List Integer) with
xs ++ ys -> (xs, ys)
-- =>[([],[1,2,3]),([1],[2,3]),([1,2],[3]),([1,2,3],[])]
matchAll [1, 2, 3] as (Multiset Integer) with
xs ++ ys -> (xs, ys)
-- =>[([],[1,2,3]),([1],[2,3]),([2],[1,3]),([3],[1,2]),([1,2],[3]),([1,3],[2]),([2,3],[1]),([1,2,3],[])]</textarea>
<p>
Let us emphasize that <b>we can define matchers such as <code>list</code>, <code>multiset</code> and <code>set</code> and pattern-constructors such as <code>cons</code> and <code>join</code> by ourselves</b>.
</p>
<h2>Non-Linear Patterns</h2>
<p>
We can handle multiple occurrence of same variables in a pattern.<br/>
Patterns that have <code>,</code> ahead are called <i>value-patterns</i>.<br/>
In many cases, it is natural to check equality by a value-pattern.<br/>
We can define how to handle value-patterns for each data type in the matcher.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all {1 2 3 3 2 4} (multiset integer) [<cons $x <cons ,x _>> x])
;=>{2 3 3 2}</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll [1, 2, 3, 3, 2, 4] as (Multiset Integer) with x:x:_ -> x
-- =>[2,3,3,2]</textarea>
<p>
Egison is purely functional programming language.
We can directly handle pattern-matching against <b>infinite collections</b> as Haskell.<br/>
Please also note that, we can write an any expression in a value pattern.
</p>
<div class="version">Egison version</div>
<textarea class="code">(take 10 (match-all primes (list integer)
[<join _ <cons $p <cons ,(+ p 2) _>>> ; patterns for twin primes
[p (+ p 2)]]))
;=>{[3 5] [5 7] [11 13] [17 19] [29 31] [41 43] [59 61] [71 73] [101 103] [107 109]}</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">take 10 (matchAll primes as (List Integer) with (_ ++ (p : p+2 : _))) -> (p, p+2))
-- =>[(3,5),(5,7),(11,13),(17,19),(29,31),(41,43),(59,61),(71,73),(101,103),(107,109)]</textarea>
<p>
Non-linear patterns extend the expressive power of pattern-matching so much.<br/>
It eliminates deeply nested loops and conditional branches.<br/>
Please check our <a href="https://www.egison.org/demonstrations/poker-hands.html">Poker Hands Demonstration</a>.
</p>
<p>
We can do pattern-matching also against nested data types such as lists of sets and sets and sets.
The following code enumerates common elements among collections inside a collection that contains three collections.
</p>
<div class="version">Egison version</div>
<textarea class="code">(match-all {{1 2 3 4 5} {4 5 1} {6 1 7 4}} (list (multiset integer))
[<cons <cons $n _> <cons <cons ,n _> <cons <cons ,n _> <nil>>>> n])
;=>{1 4}</textarea>
<div class="version2">Haskell version (pseudocode)</div>
<textarea class="haskell-code">matchAll [[1, 2, 3, 4, 5], [4, 5, 1] [6, 1, 7, 4]] as List (Multiset Integer) with
(n:_):(n:_):(n:_):[] -> n
-- =>[1,4]</textarea>
<h2>Lexical Scoping of Patterns</h2>
<p>
We can modularize useful patterns with <i>pattern-functions</i>, functions that receive patterns and return a pattern.<br/>
Since a pattern-function has lexical scoping, useful patterns can be reused in many places in a program without worry of name clash.
</p>
<div class="version">Egison version</div>
<textarea class="code">(define $twin
(pattern-function [$pat1 $pat2]
<cons (& $pat pat1)
<cons ,pat
pat2>>))
(take 1 (match-all {1 2 1 3 2} (multiset integer)
[(twin $m (twin $n _)) [m n]]))
;=>{[1 2]}</textarea>
<p>
This feature enables us to write complex patterns very simply.<br/>
Please check our <a href="https://www.egison.org/demonstrations/mahjong.html">Mahjong Demonstration</a>.
</p>
<h2>Conclusion</h2>
<p>
The combination of <strong>all of the following features</strong> realizes intuitive powerful pattern-matching.
</p>
<dl style="margin-top:14px;">
<dt>Modularization of the way of pattern-matching</dt>
<dd>
We can define the way of pattern-matching for each data types.<br/>
For example, we can define how to pattern-match against lists, multiset, and sets respectively.<br/>
</dd>
<dt>Multiple pattern-matching results</dt>
<dd>
We can handle pattern-matching that has multiple results with backtracking.<br/>
This feature is necessary to pattern-matching against data types whose data have no standard form.<br/>
</dd>
<dt>Non-linear patterns</dt>
<dd>
We can handle multiple occurrence of same variables in a pattern.
</dd>
<dt>Lexical scoping of patterns</dt>
<dd>
We can modularize useful patterns with <i>pattern-functions</i>, functions that receive patterns and return a pattern.<br/>
Since a pattern-function has lexical scoping, bindings for pattern-variables in the argument patterns and the body of pattern-functions don't conflict.<br/>
Useful patterns can be reused in many places in a program without worry of name clash.<br/>
</dd>
</dl>
<h2 id="see-also">See Also ...</h2>
<p>
We have written a lot of documentations about Egison pattern-matching.
Please refer the following articles, too.
</p>
<ul>
<li><a href="/manual/pattern-matching.html">Egison Manual - Pattern Matching</a></li>
<li><a href="/blog/moments.html">The 3 Exciting Moments Developing Egison</a></li>
</ul>
<p>
We also recommend you to read the chapter <a href="/manual/mechanism.html">Pattern-Matching Mechanism</a>, if you are interested in the mechanism pattern-matching inside Egison.
</p>
<h2 id="next">What to do next...</h2>
<p>
<a class="btn btn-lg btn-github" href="https://arxiv.org/pdf/1808.10603.pdf" role="button" target="_blank">Egison Paper on arXiv.org »</a>
<a class="btn btn-lg btn-primary" href="https://www.egison.org/demonstrations/poker-hands.html" role="button">View More Demonstrations »</a>
<a class="btn btn-lg btn-primary" href="/" role="button">Back to Home</a>
</p>
</div>
</div><!--/row-->
<hr class="divider">
<div class="row">
<!--# include file="/templates/disqus-main.html" -->
</div><!--/row-->
</div><!-- /.container -->
<!--# include file="/templates/footer.html" -->
</body>
</html>