Re: compiling pattern matching to point-free combinators sequence
Cyrille Duret <[email protected]> Thu, 1 May 2014 10:09:38 +0200
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CALk5yVeWWhE9RwnZW8OXU3BXE=8hK2iGgSNfRNDma8pDLJVjZw@mail.gmail.com> |
--001a11c2903cb9399004f8522fc7
Content-Type: text/plain; charset=UTF-8
@william
Thanks for the references, indeed enchilada and SPREAD are the closest to
my implementation and I will look carefully at their code.
For the lambda reduction I will try this simple algorithm first but I think
a lot of optimizations are required after reducing the amazing number of
combinator words produced
if you think simple lambda expression as
A\ B A [C A] is reduced to
[B] dip dup [i] dip [[C] dip i] cons
you can suspect that the generated code will be way too fat to be efficient.
@jon
I would be interested to see ur implementation.
The heart of my implementation is the match and rewrite functions of this
amazing book about term rewriting
http://www.amazon.com/Term-Rewriting-That-Franz-Baader/dp/0521779200
I adapted it to concatenative needs
My ultimate goal would be to have a very simple rewriting core and doing
all with it : type-checking, optimization, compilation/code generation.
I don't know if it is possible but I have the feeling that the combination
of rewriting and concatenative paradigm is so powerful.
@john
thanks for the reference I got the book
http://www.amazon.com/Functional-Programming-Parallel-Rewriting-International/dp/0201416638that
describe the underlying implementation of the Clean (now Pure)
programming language.
I don't know if the high level part is suitable for my case of postfix,
concatenative language, but the VM bytecode generation and the type check
system and the IO implementation is amazing ;-)
--001a11c2903cb9399004f8522fc7
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">@william<div>Thanks for the references, indeed en=
chilada and SPREAD are the closest to my implementation and I will look car=
efully at their code.</div><div><br></div><div>For the lambda reduction I w=
ill try this simple algorithm first but I think a lot of optimizations are =
required after reducing the amazing number of combinator words produced</di=
v>
<div><br></div><div>if you think simple lambda expression as=C2=A0<a name=
=3D"algorithm" style=3D"color:rgb(0,0,0);font-family:'Times New Roman';font=
-size:medium;"><pre> A\ B A [C A] is reduced to </pre>
</a><a name=3D"algorithm" style=3D"color:rgb(0,0,0);font-family:'Times New =
Roman';font-size:medium;"><pre>[B] dip dup [i] dip [[C] dip i] cons</pre></=
a></div><div><a name=3D"algorithm" style=3D"color:rgb(0,0,0);font-family:'T=
imes New Roman';font-size:medium;"><pre>
you can suspect that the generated code will be way too fat to be efficient=
.</pre></a></div><div><a name=3D"algorithm" style=3D"color:rgb(0,0,0);font-=
family:'Times New Roman';font-size:medium;"><pre>
<br></pre></a></div><div>@jon</div><div><br></div><div>I would be intereste=
d to see ur implementation.</div><div>The heart of my implementation is the=
match and rewrite functions of this amazing book about term rewriting</div=
>
<div><a href=3D"http://www.amazon.com/Term-Rewriting-That-Franz-Baader/dp/0=
521779200">http://www.amazon.com/Term-Rewriting-That-Franz-Baader/dp/052177=
9200</a><br></div><div>I adapted it to concatenative needs</div><div><br>
</div><div>My ultimate goal would be to have a very simple rewriting core a=
nd doing all with it : type-checking, optimization, compilation/code genera=
tion.</div><div>I don't know if it is possible but I have the feeling t=
hat the combination of rewriting and concatenative paradigm is so powerful.=
</div>
<div><br></div><div>@john</div><div><br></div><div>thanks for the reference=
I got the book=C2=A0<a href=3D"http://www.amazon.com/Functional-Programmin=
g-Parallel-Rewriting-International/dp/0201416638">http://www.amazon.com/Fun=
ctional-Programming-Parallel-Rewriting-International/dp/0201416638</a> that=
describe the underlying implementation of the Clean (now Pure) programming=
language.</div>
<div>I don't know if the high level part is suitable for my case of pos=
tfix, concatenative language, but the VM bytecode generation and the type c=
heck system and the IO implementation is amazing ;-)</div><div><br></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/4987;_ylc=3DX3oDMTJwbDlxaGk0BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3J=
wc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5ODcEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzk4OT=
MxNzc5?act=3Dreply&messageNum=3D4987">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%5=
D%20compiling%20pattern%20matching%20to%20point-free%20combinators%20sequen=
ce" 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=3DX3oDMTJlNGw2djQ2BF9TAzk3MzU5NzE0BGdycElkAzE4Mzk=
yNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM5ODkzMTc3OQ=
--" 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=3DX3oDMTM0dW1nZHI5BF9TAzk3MzU5=
NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5ODcEc2VjA2Z0cgR=
zbGsDdnRwYwRzdGltZQMxMzk4OTMxNzc5BHRwY0lkAzQ5NzY-" style=3D"text-decoration=
: none; color: #2D50FD;">Messages in this topic</a>
(6)
</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=3DX3oDMTJlcDh2cGsyBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3B=
JZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTM5ODkzMTc3OQ--" 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=3DX3oDMTJkbWRjamc3BF9TAzk3ND=
c2NTkwBGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzd=
GltZQMxMzk4OTMxNzc5" 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=3D4987/stime=3D1398931779" 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 -->
--001a11c2903cb9399004f8522fc7--