compiling pattern matching to point-free combinators sequence
Cyrille Duret <[email protected]> Wed, 30 Apr 2014 09:04:36 +0200
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CALk5yVdmzsvpMLUH7f3ng+tbLDBLUPoCsdBv3R=scyGk9ZUs9Q@mail.gmail.com> |
--f46d04428a6c4f768c04f83d290e
Content-Type: text/plain; charset=UTF-8
hello,
I have good interest in postfix concatenative languages for some years now,
I discover the postfix notation with forth and saw the beauty of joy and
now I try to experiment the benefit of a concatenative language for
distributed application, user interface ( I am thinking of a visual touch
based programming environment a bit like hopscotch
https://www.gethopscotch.com/) , etc..
My language of prototyping is javascript and my language of choice for
implementation is ATS2 (http://www.ats-lang.org/)
I have already done a conventional implementation of a very basic language
here https://github.com/cduret/stk.js , but I want to go further.
At the time I read this paper (
http://mitarbeiter.hs-heilbronn.de/~herzberg/Publications/ICSOFT.2009.pdf),
I saw the power and simplicity of a concatenative language based on a
rewriting system.
So I began my implementation of a basic rewrite system :
The words can be defined with pattern matching as follow :
x dup => x x.
x y swap => y x.
[x_] call => x_.
...
Rewriting system is powerful and can compute symbolic expression as well
but the explosion of rewriting steps can lead to slow execution time.
That's why I try to think about a compiler that would transform the
rule-based program into a stack oriented bytecode.
My first problem is to find a way of rewriting a rule with named parameters
into a point-free word (in a forth or factor meaning).
How I could compile the rule :
a b toto => a a * 3 b * +.
into
toto => 3 * swap dup * +.
I am looking for such an algorithm if you have some advices..
thank you very much ;-)
--f46d04428a6c4f768c04f83d290e
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><div dir=3D"ltr">hello,<div>I have good interest in postfix concat=
enative languages for some years now, I discover the postfix notation with =
forth and saw the beauty of joy and now I try to experiment the benefit of =
a concatenative language for distributed application, user interface ( I am=
thinking of a visual touch based programming environment a bit like hopsco=
tch <a href=3D"https://www.gethopscotch.com/">https://www.gethopscotch.com/=
</a>) , etc..</div>
<div><br></div><div>My language of prototyping is javascript and my languag=
e of choice for implementation is ATS2 (<a href=3D"http://www.ats-lang.org/=
">http://www.ats-lang.org/</a>)</div><div><br></div><div>I have already don=
e a conventional implementation of a very basic language here=C2=A0<a href=
=3D"https://github.com/cduret/stk.js">https://github.com/cduret/stk.js</a> =
, but I want to go further.</div>
<div>At the time I read this paper (<a href=3D"http://mitarbeiter.hs-heilbr=
onn.de/~herzberg/Publications/ICSOFT.2009.pdf">http://mitarbeiter.hs-heilbr=
onn.de/~herzberg/Publications/ICSOFT.2009.pdf</a>), I saw the power and sim=
plicity of a concatenative language based on a rewriting system.</div>
<div><br></div><div>So I began my implementation of a basic rewrite system =
:</div><div>The words can be defined with pattern matching as follow :</div=
><div><br></div><div><div style=3D"margin:0px;padding:0px;vertical-align:ba=
seline;font-family:Arial,Helvetica,sans-serif;font-size:13px;">
<div style=3D"margin:0px;padding:0px;vertical-align:baseline;">x dup =3D>=
; x x.</div></div><div style=3D"margin:0px;padding:0px;vertical-align:basel=
ine;font-family:Arial,Helvetica,sans-serif;font-size:13px;">
x y swap =3D> y x.<br></div><div style=3D"margin:0px;padding:0px;vertica=
l-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px;">[x=
_] call =3D> x_.</div></div><div style=3D"margin:0px;padding:0px;vertica=
l-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px;">
...</div><div style=3D"margin:0px;padding:0px;vertical-align:baseline;font-=
family:Arial,Helvetica,sans-serif;font-size:13px;"><br></div><div style=3D"=
margin:0px;padding:0px;vertical-align:baseline;font-family:Arial,Helvetica,=
sans-serif;font-size:13px;">
Rewriting system is powerful and can compute symbolic expression as well bu=
t the explosion of rewriting steps can lead to slow execution time.</div><d=
iv style=3D"margin:0px;padding:0px;vertical-align:baseline;font-family:Aria=
l,Helvetica,sans-serif;font-size:13px;">
That's why I try to think about a compiler that would transform the rul=
e-based program into a stack oriented bytecode.</div><div style=3D"margin:0=
px;padding:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-ser=
if;font-size:13px;">
<br></div><div style=3D"margin:0px;padding:0px;vertical-align:baseline;font=
-family:Arial,Helvetica,sans-serif;font-size:13px;">My first problem is to =
find a way of rewriting a rule with named parameters into a point-free word=
(in a forth or factor meaning).</div>
<div style=3D"margin:0px;padding:0px;vertical-align:baseline;font-family:Ar=
ial,Helvetica,sans-serif;font-size:13px;"><br></div><div style=3D"margin:0p=
x;padding:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-seri=
f;font-size:13px;">
How I could compile the rule :</div><div style=3D"margin:0px;padding:0px;ve=
rtical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px=
;"><br></div><div style=3D"margin:0px;padding:0px;vertical-align:baseline;f=
ont-family:Arial,Helvetica,sans-serif;font-size:13px;">
a b toto =3D> a a * 3 b * +.=C2=A0<br></div><div style=3D"margin:0px;pad=
ding:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;fon=
t-size:13px;"><br></div><div style=3D"margin:0px;padding:0px;vertical-align=
:baseline;font-family:Arial,Helvetica,sans-serif;font-size:13px;">
into=C2=A0</div><div style=3D"margin:0px;padding:0px;vertical-align:baselin=
e;font-family:Arial,Helvetica,sans-serif;font-size:13px;"><br></div><div st=
yle=3D"margin:0px;padding:0px;vertical-align:baseline;font-family:Arial,Hel=
vetica,sans-serif;font-size:13px;">
toto =3D> 3 * swap dup * +.<br></div><div style=3D"margin:0px;padding:0p=
x;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-size:=
13px;"><br></div><div style=3D"margin:0px;padding:0px;vertical-align:baseli=
ne;font-family:Arial,Helvetica,sans-serif;font-size:13px;">
<br></div><div style=3D"margin:0px;padding:0px;vertical-align:baseline;font=
-family:Arial,Helvetica,sans-serif;font-size:13px;">I am looking for such a=
n algorithm if you have some advices..</div><div style=3D"margin:0px;paddin=
g:0px;vertical-align:baseline;font-family:Arial,Helvetica,sans-serif;font-s=
ize:13px;">
<br></div><div style=3D"margin:0px;padding:0px;vertical-align:baseline;font=
-family:Arial,Helvetica,sans-serif;font-size:13px;">thank you very much ;-)=
</div></div>
</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/4976;_ylc=3DX3oDMTJwNnBiM3AyBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3J=
wc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5NzYEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzk4OD=
QxNDc4?act=3Dreply&messageNum=3D4976">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%20compiling%=
20pattern%20matching%20to%20point-free%20combinators%20sequence" style=3D"t=
ext-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=
%20compiling%20pattern%20matching%20to%20point-free%20combinators%20sequenc=
e" 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=3DX3oDMTJlZHFwaG9iBF9TAzk3MzU5NzE0BGdycElkAzE4Mzk=
yNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM5ODg0MTQ3OA=
--" 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=3DX3oDMTM0MHA2Y2dvBF9TAzk3MzU5=
NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5NzYEc2VjA2Z0cgR=
zbGsDdnRwYwRzdGltZQMxMzk4ODQxNDc4BHRwY0lkAzQ5NzY-" style=3D"text-decoration=
: none; color: #2D50FD;">Messages in this topic</a>
(1)
</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=3DX3oDMTJlNnQwbGJ0BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3B=
JZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM5ODg0MTQ3Nw--" 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=3DX3oDMTJkbmI0YW5mBF9TAzk3ND=
c2NTkwBGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzd=
GltZQMxMzk4ODQxNDc4" 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=3D4976/stime=3D1398841478" 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 -->
--f46d04428a6c4f768c04f83d290e--