Re: [stack] peg: a lazy, non-deterministic concatenative language

"William Tanksley, Jr" <[email protected]> Tue, 17 Apr 2012 07:48:21 -0700
Newsgroups	gmane.comp.lang.concatenative
Message-ID	<CAFTBfO5C2J-W1wOt==m1SRA5+zwDAbRbHGCvTmZ3x+dm80JX=w@mail.gmail.com>
--6Pg3cks9FVzMmfZTeYhbuDGtisjwTvsi1PJTrPf
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit

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?

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

--6Pg3cks9FVzMmfZTeYhbuDGtisjwTvsi1PJTrPf
Content-Type: text/html; charset=ISO-8859-1
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">&nbsp;</span>

<!--~-|**|PrettyHtmlStartT|**|-~-->
<div id="ygrp-mlmsg" style="position:relative;">
  <div id="ygrp-msg" style="z-index: 1;">
<!--~-|**|PrettyHtmlEndT|**|-~-->

    <div id="ygrp-text" >
      
      
      <p>Don Groves &lt;<a href="mailto:dgpdx%40comcast.net">[email protected]</a>&gt; wrote:<br>
&gt; Of course, any concatentative language doesn't have to use a stack,<br>
&gt; it's just most convenient.<br>
<br>
&quot;Convenient&quot; 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>
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 &quot;no&quot;. A program &quot;a1&quot; and &quot;a2&quot;, both of which<br>
deterministically execute something like &quot;False assert&quot; or an<br>
undefined word (which means that they always halt). The concatenation<br>
&quot;a1 a2&quot; will perform (deterministically) the semantics of a2, but<br>
never a1.<br>
<br>
This doesn't make &quot;peg&quot; a bad language... But it does suggest my<br>
&quot;formal&quot; 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 &quot;RETURN&quot; and &quot;call/cc&quot;, or Forth's R&gt;<br>
and EXIT.<br>
<br>
For &quot;peg&quot; itself, it's easy to see that concatenativity DOES hold for<br>
programs where the parse &quot;continues&quot; 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>
&gt; don<br>
<br>
-Wm<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=X3oDMTJwYWpjNzBrBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTkEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzM0Njc0MTM4?act=reply&messageNum=4919">Reply <span style="font-weight: 700;">via web post</span></a> |
            	<a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJlMmhjbHJxBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTMzNDY3NDEzOA--" style="font-weight: 700;">Start a New Topic</a>
      </div>

                <a href="http://groups.yahoo.com/group/concatenative/message/4915;_ylc=X3oDMTM0ajBiYmZqBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTkEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzM0Njc0MTM4BHRwY0lkAzQ5MTU-">Messages in this topic</a>
          (<span style="font-weight: 700;">5</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=X3oDMTJlcW1mdm5qBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTMzNDY3NDEzOA--" 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=X3oDMTJkY3A5NnZsBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzM0Njc0MTM4" 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> &bull; <a href="mailto:[email protected]?subject=Unsubscribe" style="text-decoration: none;">Unsubscribe</a> &bull; <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=4919/stime=1334674138/nc1=4507179/nc2=3848640/nc3=5741398" 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 -->


--6Pg3cks9FVzMmfZTeYhbuDGtisjwTvsi1PJTrPf--