Re: [stack] peg: a lazy, non-deterministic concatenative language
Stephen De Gabrielle <[email protected]> Tue, 17 Apr 2012 16:46:08 +0100
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAGHj7-LPf_=VRjGLQx5ZmcU9hP2pKGTB_8Lch2CaE-f1AVRtUg@mail.gmail.com> |
--8lwVoLq5KNvYN3irnsi1SOh99WLmM5rQiT3j8qp Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On Tue, Apr 17, 2012 at 3:48 PM, William Tanksley, Jr <[email protected]= m > wrote: > ** > > > Don Groves <[email protected]> wrote: > > Of course, any concatentative language doesn't have to use a stack, > > it's just most convenient. > > "Convenient" is kind of vague. A stack is the only parameter-passing > data structure we know of that's computationally complete/Turing > equivalent and doesn't require application. You can also make a > concatenative language using a single integer accumulator, for > example, and it's simple to implement and understand (but it's > ridiculously weak). Since a stack is the only one we know about it's > of course the most convenient one we know about... But what ones don't > we know about? > > Your comment and the \/ branch operator made me wonder about the possibility of a concatenative language that operated on a 'graph-structure= d stack'? (and if such a thing would be useful) > Here's another question: is peg _formally_ concatenative? That is, > given two valid programs, is their concatenation also a valid program? > Are the semantics of the resulting program the composition of the > semantics of the original two? > > I think the answer is "no". A program "a1" and "a2", both of which > deterministically execute something like "False assert" or an > undefined word (which means that they always halt). The concatenation > "a1 a2" will perform (deterministically) the semantics of a2, but > never a1. > > This doesn't make "peg" a bad language... But it does suggest my > "formal" rule for testing concatenativity wants a weaker variant. > Another example of the need for a weakening is words that perform > control flow alteration, like "RETURN" and "call/cc", or Forth's R> > and EXIT. > > For "peg" itself, it's easy to see that concatenativity DOES hold for > programs where the parse "continues" past the beginning of the > program. For Forth, concatenativity holds when certain words in the > dictionary are not used. Rice's theorem will tangle us up for both > languages, but in general it's easy to see when a Forth program is > concatenative. Parsing a peg program MIGHT be possible to explode to > O(2^n), but I think it'll always terminate. > > > don > > -Wm > >=20=20 > --=20 -- Stephen De Gabrielle [email protected] Telephone +44 (0)20 85670911 Mobile +44 (0)79 85189045 http://www.degabrielle.name/stephen ---- Professor: Oh God! I clicked without reading! Cubert: And I slightly modified something I own! Professor: We're monsters! [Non-text portions of this message have been removed] --8lwVoLq5KNvYN3irnsi1SOh99WLmM5rQiT3j8qp Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 7bit <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> </head> <body style="background-color: #fff;"> <span style="display:none"> </span> <!--~-|**|PrettyHtmlStartT|**|-~--> <div id="ygrp-mlmsg" style="position:relative;"> <div id="ygrp-msg" style="z-index: 1;"> <!--~-|**|PrettyHtmlEndT|**|-~--> <div id="ygrp-text" > <p>On Tue, Apr 17, 2012 at 3:48 PM, William Tanksley, Jr <<a href="mailto:wtanksleyjr%40gmail.com">[email protected]</a><br> > wrote:<br> <br> > **<br> ><br> ><br> > Don Groves <<a href="mailto:dgpdx%40comcast.net">[email protected]</a>> wrote:<br> > > Of course, any concatentative language doesn't have to use a stack,<br> > > it's just most convenient.<br> ><br> > "Convenient" is kind of vague. A stack is the only parameter-passing<br> > data structure we know of that's computationally complete/Turing<br> > equivalent and doesn't require application. You can also make a<br> > concatenative language using a single integer accumulator, for<br> > example, and it's simple to implement and understand (but it's<br> > ridiculously weak). Since a stack is the only one we know about it's<br> > of course the most convenient one we know about... But what ones don't<br> > we know about?<br> ><br> > Your comment and the \/ branch operator made me wonder about the<br> possibility of a concatenative language that operated on a 'graph-structured<br> stack'? (and if such a thing would be useful)<br> <br> > Here's another question: is peg _formally_ concatenative? That is,<br> > given two valid programs, is their concatenation also a valid program?<br> > Are the semantics of the resulting program the composition of the<br> > semantics of the original two?<br> ><br> > I think the answer is "no". A program "a1" and "a2", both of which<br> > deterministically execute something like "False assert" or an<br> > undefined word (which means that they always halt). The concatenation<br> > "a1 a2" will perform (deterministically) the semantics of a2, but<br> > never a1.<br> ><br> > This doesn't make "peg" a bad language... But it does suggest my<br> > "formal" rule for testing concatenativity wants a weaker variant.<br> > Another example of the need for a weakening is words that perform<br> > control flow alteration, like "RETURN" and "call/cc", or Forth's R><br> > and EXIT.<br> ><br> > For "peg" itself, it's easy to see that concatenativity DOES hold for<br> > programs where the parse "continues" past the beginning of the<br> > program. For Forth, concatenativity holds when certain words in the<br> > dictionary are not used. Rice's theorem will tangle us up for both<br> > languages, but in general it's easy to see when a Forth program is<br> > concatenative. Parsing a peg program MIGHT be possible to explode to<br> > O(2^n), but I think it'll always terminate.<br> ><br> > > don<br> ><br> > -Wm<br> ><br> > <br> ><br> <br> -- <br> <br> --<br> Stephen De Gabrielle<br> <a href="mailto:stephen.degabrielle%40acm.org">[email protected]</a><br> Telephone +44 (0)20 85670911<br> Mobile +44 (0)79 85189045<br> <a href="http://www.degabrielle.name/stephen">http://www.degabrielle.name/stephen</a><br> ----<br> Professor: Oh God! I clicked without reading!<br> Cubert: And I slightly modified something I own!<br> Professor: We're monsters!<br> <br> [Non-text portions of this message have been removed]<br> <br> </p> </div> <!--~-|**|PrettyHtmlStart|**|-~--> <div style="color: #fff; height: 0;">__._,_.___</div> <div id="ygrp-actbar" style="clear: both; margin-bottom: 10px; white-space: nowrap; color: #666; padding-top: 15px;"> <div> <a href="mailto:[email protected]?subject=Re%3A%20%5Bstack%5D%20peg%3A%20a%20lazy%2C%20non-deterministic%20concatenative%20language" style="margin-right: 0; padding-right: 0;"> Reply to <span style="font-weight: 700;">sender</span></a> | <a href="mailto:[email protected]?subject=Re%3A%20%5Bstack%5D%20peg%3A%20a%20lazy%2C%20non-deterministic%20concatenative%20language"> Reply to <span style="font-weight: 700;">group</span></a> | <a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJwN2MxYTYzBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MjAEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzM0Njc3NTcw?act=reply&messageNum=4920">Reply <span style="font-weight: 700;">via web post</span></a> | <a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJlNnZzMHIzBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTMzNDY3NzU3MA--" style="font-weight: 700;">Start a New Topic</a> </div> <a href="http://groups.yahoo.com/group/concatenative/message/4915;_ylc=X3oDMTM0dXZocGRlBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MjAEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzM0Njc3NTcwBHRwY0lkAzQ5MTU-">Messages in this topic</a> (<span style="font-weight: 700;">6</span>) </div> <!------- Start Nav Bar ------> <!-- |**|begin egp html banner|**| --> <div id="ygrp-vital" style="background-color: #e0ecee; font-family: Verdana; font-size: 10px; margin-bottom: 10px; padding: 10px;"> <span id="vithd" style="font-weight: bold; color: #333; text-transform: uppercase; ">Recent Activity:</span> <ul style="list-style-type: none; margin: 0; padding: 0; display: inline;"> </ul> <div style="clear: both; padding-top: 2px; color: #1e66ae;"> <a href="http://groups.yahoo.com/group/concatenative;_ylc=X3oDMTJlZHBsaTJ2BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTMzNDY3NzU3MA--" style="text-decoration: none;">Visit Your Group</a> </div> </div> <div id="ft" style="font-family: Arial; font-size: 11px; margin-top: 5px; padding: 0 2px 0 0; clear: both;"> <a href="http://groups.yahoo.com/;_ylc=X3oDMTJkaGZkNW02BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzM0Njc3NTcw" style="float: left;"><img src="http://l.yimg.com/a/i/us/yg/logo/us.gif" height="15" width="137" alt="Yahoo! Groups" style="border: 0;"/></a> <div style="color: #747575; float: right;">Switch to: <a href="mailto:[email protected]?subject=Change Delivery Format: Traditional" style="text-decoration: none;">Text-Only</a>, <a href="mailto:[email protected]?subject=Email Delivery: Digest" class="margin-rt" style="text-decoration: none;">Daily Digest</a> • <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> • <a href="http://docs.yahoo.com/info/terms/" style="text-decoration: none;">Terms of Use</a></div> </div> <!-- |**|end egp html banner|**| --> </div> <!-- ygrp-msg --> <!-- Sponsor --> <!-- |**|begin egp html banner|**| --> <div id="ygrp-sponsor" style="width:160px; float:right; clear:none; margin:0 0 25px 0; background: #fff;"> <!-- Start Recommendations --> <div id="ygrp-reco"> </div> <!-- End Recommendations --> </div> <!-- |**|end egp html banner|**| --> <div style="clear:both; color: #FFF; font-size:1px;">.</div> </div> <img src="http://geo.yahoo.com/serv?s=97359714/grpId=1839274/grpspId=1705006764/msgId=4920/stime=1334677570/nc1=5191953/nc2=4507179/nc3=3848640" width="1" height="1"> <br> <div style="color: #fff; height: 0;">__,_._,___</div> <!--~-|**|PrettyHtmlEnd|**|-~--> </body> <!--~-|**|PrettyHtmlStart|**|-~--> <head> <style type="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; } a { color: #1e66ae; } #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; } 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.file-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-mlmsg a { color: #1E66AE; } #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; } #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; } --> </style> </head> <!--~-|**|PrettyHtmlEnd|**|-~--> </html> <!-- end group email --> --8lwVoLq5KNvYN3irnsi1SOh99WLmM5rQiT3j8qp--