Re: compiling pattern matching to point-free combinators sequence
Jon Purdy <[email protected]> Wed, 30 Apr 2014 11:20:09 -0700
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAE3FWBtrr-JHEcAj-jFYePNq4yxJZNUfnqUbKuVsvscjE--FhA@mail.gmail.com> |
--Fl9pRkyihvuChgAs8IEbJ91CsEgvz7SGKW4-Thu
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
> Rewriting system is powerful and can compute symbolic expression as well =
but the explosion of rewriting steps can lead to slow execution time.
I think it is possible to produce a fast implementation of a
concatenative system based on pure rewriting. I was working on such a
thing a few years ago. My approach (as I remember it) was to collect
all rewrite rules, sort them in order of specificity, and group those
by the head word if there was one; the result was an O(1) hash table
lookup plus an O(log n) search for the most specific pattern, each
rewriting step. Seemed fast enough, though I never benchmarked it. I
will see if I can dig up the code or rewrite it for fun.
> My first problem is to find a way of rewriting a rule with named paramete=
rs into a point-free word (in a forth or factor meaning).
That=E2=80=99s called an =E2=80=9Cabstraction algorithm=E2=80=9D=E2=80=94co=
nverting lambdas into
combinators. The Brent Kirby article that William Tanksley linked is a
good start, but it would require a good deal of optimisation to be
suitable.
You can also think of a concatenative expression with local variables
as a data flow graph=E2=80=94directed and acyclic, hopefully=E2=80=94and tr=
y to reduce
the graph as much as possible. But that breaks down with higher-order
functions, which seem to be the best way to make concatenative
expressions succinct, legible, and efficient.
--Fl9pRkyihvuChgAs8IEbJ91CsEgvz7SGKW4-Thu
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/htm=
l4/strict.dtd">
<html>
<head>
</head>
=20
<body style=3D"background-color: #fff;">
<span style=3D"display:none"> </span>
<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id=3D"ygrp-mlmsg" style=3D"position:relative;">
<div id=3D"ygrp-msg" style=3D"z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->
<div id=3D"ygrp-text" >
=20=20=20=20=20=20
=20=20=20=20=20=20
<p>> Rewriting system is powerful and can compute symbolic express=
ion as well but the explosion of rewriting steps can lead to slow execution=
time.<br>
<br>
I think it is possible to produce a fast implementation of a<br>
concatenative system based on pure rewriting. I was working on such a<br>
thing a few years ago. My approach (as I remember it) was to collect<br>
all rewrite rules, sort them in order of specificity, and group those<br>
by the head word if there was one; the result was an O(1) hash table<br>
lookup plus an O(log n) search for the most specific pattern, each<br>
rewriting step. Seemed fast enough, though I never benchmarked it. I<br>
will see if I can dig up the code or rewrite it for fun.<br>
<br>
> My first problem is to find a way of rewriting a rule with named param=
eters into a point-free word (in a forth or factor meaning).<br>
<br>
That=E2=80=99s called an =E2=80=9Cabstraction algorithm=E2=80=9D=E2=80=94co=
nverting lambdas into<br>
combinators. The Brent Kirby article that William Tanksley linked is a<br>
good start, but it would require a good deal of optimisation to be<br>
suitable.<br>
<br>
You can also think of a concatenative expression with local variables<br>
as a data flow graph=E2=80=94directed and acyclic, hopefully=E2=80=94and tr=
y to reduce<br>
the graph as much as possible. But that breaks down with higher-order<br>
functions, which seem to be the best way to make concatenative<br>
expressions succinct, legible, and efficient.<br>
</p>
</div>
=20=20=20=20=20
<!--~-|**|PrettyHtmlStart|**|-~-->
<div style=3D"color: #fff; height: 0;">__._,_.___</div>
=20=20=20=20=20=20=20=20=20=20
=20=20
=20
=20=20=20=20
<div style=3D"clear:both"> </div>
<table cellspacing=3D4px style=3D"margin-top: 20px; margin-bottom: 10px=
; color: #2D50FD;">
<tbody>
<tr>
<td style=3D"font-size: 12px; font-family: arial; font-weight: bo=
ld; padding: 7px 5px 5px;" >
<a style=3D"text-decoration: none; color: #2D50FD=
" href=3D"https://groups.yahoo.com/neo/groups/concatenative/conversations/m=
essages/4981;_ylc=3DX3oDMTJwdTQ2aWtpBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3J=
wc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5ODEEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzk4OD=
gyMDEw?act=3Dreply&messageNum=3D4981">Reply via web post</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"mailto:[email protected]?subject=3DRe%3A%20%=
5Bstack%5D%20compiling%20pattern%20matching%20to%20point-free%20combinators=
%20sequence" style=3D"text-decoration: none; color: #2D50FD;">
Reply to sender </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;">
<a href=3D"mailto:[email protected]?subject=3DRe%3A=
%20%5Bstack%5D%20compiling%20pattern%20matching%20to%20point-free%20combina=
tors%20sequence" style=3D"text-decoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"https://groups.yahoo.com/neo/groups/concatenative/co=
nversations/newtopic;_ylc=3DX3oDMTJlMDVsOG1jBF9TAzk3MzU5NzE0BGdycElkAzE4Mzk=
yNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM5ODg4MjAxMA=
--" style=3D"text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;color: #2D50FD;" >
<a href=3D"https://groups.yahoo.com/neo/groups/=
concatenative/conversations/topics/4976;_ylc=3DX3oDMTM0NjNic2s3BF9TAzk3MzU5=
NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5ODEEc2VjA2Z0cgR=
zbGsDdnRwYwRzdGltZQMxMzk4ODgyMDEwBHRwY0lkAzQ5NzY-" style=3D"text-decoration=
: none; color: #2D50FD;">Messages in this topic</a>
(3)
</td>
</tr>
</tbody>
</table>
=20=20=20=20=20=20=20=20
<div id=3D"megaphoneModule">
=20=20=20=20=20
<hr style=3D"height:2px ; border-width:0; color:#E3E3E3; background-col=
or:#E3E3E3;">
</div>
<!------- Start Nav Bar ------>
=20
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-vital" style=3D"background-color: #f2f2f2; font-family: Ver=
dana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-transf=
orm: uppercase; "><a href=3D"https://groups.yahoo.com/neo/groups/concatenat=
ive/info;_ylc=3DX3oDMTJlbHFvcmgwBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3B=
JZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM5ODg4MjAxMA--" style=3D=
"text-decoration: none;">Visit Your Group</a></span>
<ul style=3D"list-style-type: none; margin: 0; padding: 0; display: in=
line;">
</ul>
</div>
<div id=3D"ft" style=3D"font-family: Arial; font-size: 11px; margin-top: 5p=
x; padding: 0 2px 0 0; clear: both;">
<a href=3D"https://groups.yahoo.com/neo;_ylc=3DX3oDMTJkMzc4dWpiBF9TAzk3Mz=
U5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzd=
GltZQMxMzk4ODgyMDEw" style=3D"float: left;"><img src=3D"http://l.yimg.com/r=
u/static/images/yg/img/email/new_logo/logo-groups-137x15.png" height=3D"15"=
width=3D"137" alt=3D"Yahoo! Groups" style=3D"border: 0;"/></a>
<div style=3D"color: #747575; float: right;"> • <a href=3D"https://i=
nfo.yahoo.com/privacy/us/yahoo/groups/details.html" style=3D"text-decoratio=
n: none;">Privacy</a> • <a href=3D"mailto:concatenative-unsubscribe@ya=
hoogroups.com?subject=3DUnsubscribe" style=3D"text-decoration: none;">Unsub=
scribe</a> • <a href=3D"https://info.yahoo.com/legal/us/yahoo/utos/ter=
ms/" style=3D"text-decoration: none;">Terms of Use</a> </div>
</div>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
=20
<!-- Sponsor -->
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-sponsor" style=3D"width:160px; float:right; clear:none; m=
argin:0 0 25px 0; background: #fff;">
<!-- Start Recommendations -->
<div id=3D"ygrp-reco">
</div>
<!-- End Recommendations -->
</div> <!-- |**|end egp html banner|**| -->
<div style=3D"clear:both; color: #FFF; font-size:1px;">.</div>
</div>
<img src=3D"http://geo.yahoo.com/serv?s=3D97359714/grpId=3D1839274/grpspI=
d=3D1705006764/msgId=3D4981/stime=3D1398882010" width=3D"1" height=3D"1"> <=
br>
<img src=3D"http://y.analytics.yahoo.com/fpc.pl?ywarid=3D515FB27823A7407E&a=
=3D10001310322279&js=3Dno&resp=3Dimg" width=3D"1" height=3D"1">=20
<div style=3D"color: #fff; height: 0;">__,_._,___</div>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</body>
<!--~-|**|PrettyHtmlStart|**|-~-->
<head>
<style type=3D"text/css">
<!--
#ygrp-mkp {
border: 1px solid #d8d8d8;
font-family: Arial;
margin: 10px 0;
padding: 0 10px;
}
#ygrp-mkp hr {
border: 1px solid #d8d8d8;
}
#ygrp-mkp #hd {
color: #628c2a;
font-size: 85%;
font-weight: 700;
line-height: 122%;
margin: 10px 0;
}
#ygrp-mkp #ads {
margin-bottom: 10px;
}
#ygrp-mkp .ad {
padding: 0 0;
}
#ygrp-mkp .ad p {
margin: 0;
}
#ygrp-mkp .ad a {
color: #0000ff;
text-decoration: none;
}
#ygrp-sponsor #ygrp-lc {
font-family: Arial;
}
#ygrp-sponsor #ygrp-lc #hd {
margin: 10px 0px;
font-weight: 700;
font-size: 78%;
line-height: 122%;
}
#ygrp-sponsor #ygrp-lc .ad {
margin-bottom: 10px;
padding: 0 0;
}
#actions {
font-family: Verdana;
font-size: 11px;
padding: 10px 0;
}
#activity {
background-color: #e0ecee;
float: left;
font-family: Verdana;
font-size: 10px;
padding: 10px;
}
#activity span {
font-weight: 700;
}
#activity span:first-child {
text-transform: uppercase;
}
#activity span a {
color: #5085b6;
text-decoration: none;
}
#activity span span {
color: #ff7900;
}
#activity span .underline {
text-decoration: underline;
}
.attach {
clear: both;
display: table;
font-family: Arial;
font-size: 12px;
padding: 10px 0;
width: 400px;
}
.attach div a {
text-decoration: none;
}
.attach img {
border: none;
padding-right: 5px;
}
.attach label {
display: block;
margin-bottom: 5px;
}
.attach label a {
text-decoration: none;
}
=20=20
blockquote {
margin: 0 0 0 4px;
}
.bold {
font-family: Arial;
font-size: 13px;
font-weight: 700;
}
.bold a {
text-decoration: none;
}
dd.last p a {
font-family: Verdana;
font-weight: 700;
}
dd.last p span {
margin-right: 10px;
font-family: Verdana;
font-weight: 700;
}
dd.last p span.yshortcuts {
margin-right: 0;
}
div.attach-table div div a {
text-decoration: none;
}
div.attach-table {
width: 400px;
}
div.file-title a, div.file-title a:active, div.file-title a:hover, div.fi=
le-title a:visited {
text-decoration: none;
}
div.photo-title a, div.photo-title a:active, div.photo-title a:hover, div=
.photo-title a:visited {
text-decoration: none;
}
div#ygrp-mlmsg #ygrp-msg p a span.yshortcuts {
font-family: Verdana;
font-size: 10px;
font-weight: normal;
}
.green {
color: #628c2a;
}
.MsoNormal {
margin: 0 0 0 0;
}
o {
font-size: 0;
}
#photos div {
float: left;
width: 72px;
}
#photos div div {
border: 1px solid #666666;
height: 62px;
overflow: hidden;
width: 62px;
}
#photos div label {
color: #666666;
font-size: 10px;
overflow: hidden;
text-align: center;
white-space: nowrap;
width: 64px;
}
#reco-category {
font-size: 77%;
}
#reco-desc {
font-size: 77%;
}
.replbq {
margin: 4px;
}
#ygrp-actbar div a:first-child {
/* border-right: 0px solid #000;*/
margin-right: 2px;
padding-right: 5px;
}
#ygrp-mlmsg {
font-size: 13px;
font-family: Arial, helvetica,clean, sans-serif;
*font-size: small;
*font: x-small;
}
#ygrp-mlmsg table {
font-size: inherit;
font: 100%;
}
#ygrp-mlmsg select, input, textarea {
font: 99% Arial, Helvetica, clean, sans-serif;
}
#ygrp-mlmsg pre, code {
font:115% monospace;
*font-size:100%;
}
#ygrp-mlmsg * {
line-height: 1.22em;
}
#ygrp-mlmsg #logo {
padding-bottom: 10px;
}
#ygrp-msg p a {
font-family: Verdana;
}
#ygrp-msg p#attach-count span {
color: #1E66AE;
font-weight: 700;
}
#ygrp-reco #reco-head {
color: #ff7900;
font-weight: 700;
}
#ygrp-reco {
margin-bottom: 20px;
padding: 0px;
}
#ygrp-sponsor #ov li a {
font-size: 130%;
text-decoration: none;
}
#ygrp-sponsor #ov li {
font-size: 77%;
list-style-type: square;
padding: 6px 0;
}=20
#ygrp-sponsor #ov ul {
margin: 0;
padding: 0 0 0 8px;
}
#ygrp-text {
font-family: Georgia;
}
#ygrp-text p {
margin: 0 0 1em 0;
}
#ygrp-text tt {
font-size: 120%;
}
#ygrp-vital ul li:last-child {
border-right: none !important;=20
}=20
-->
</style>
</head>
<!--~-|**|PrettyHtmlEnd|**|-~-->
</html>
<!-- end group email -->
--Fl9pRkyihvuChgAs8IEbJ91CsEgvz7SGKW4-Thu--