Re: [stack] peg: a lazy, non-deterministic concatenative language
"William Tanksley, Jr" <[email protected]> Fri, 20 Apr 2012 10:21:38 -0700
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAFTBfO507DiOyUiLUu0KMAEPqPu_y_Wi_r1aYDyKpFdtd=VFaA@mail.gmail.com> |
--n2C-n9pbJWVIfc5k1-hePHyS-nSVYwnlb7A1uG4 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable dustin.deweese <[email protected]> wrote: > --- In [email protected], "William Tanksley, Jr" <wtanksleyjr= @...> wrote: >> Don Groves <dgpdx@...> 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? > The stack works essentially as a sort of caching structure. =A0Whichever = caching strategy you choose determines the data structure. > Last in, first out =3D queue > Highest/lowest weighted out =3D priority queue > First in, first out =3D stack > There can be only one =3D a single item (accumulator) > I can't think of any other strategies that have a single unambiguous "top= " element. =A0FIFO seems to be the only reasonable caching strategy, though= . That's a clever approach. Although I liked it at first glance, I think it's not quite complete. We know concatenative languages that use an accumulator and ones that use a stack; we also know ones that use multiples of each (for example, ANS Forth can have a separate floating point stack, and Machine Forth uses a memory fetch register; note that the return stack in Forth does NOT count, since accessing that makes the program NOT concatenative). The problem is that the choice between stack and accumulator changes the language in a profound way. So if it were possible to arrange a queue in some way instead of a stack, what would the resulting language look like? We have no semantics for such a language (yet). I'm also thinking about the statement that there should be only one unambiguous "top" element. This is essentially right, of course; accepting that when there are two top elements they can be disambiguated by the word that's needing the data (as with ANS Forth's floating point vocabulary, whose words may pull from a distinct stack). There are more details, of course, since some words accept more than one parameter, so at the time the word is called the structure must provide ALL of its elements to it unambiguously (so not just the top item). A stack meets that requirement by imposing a total ordering of all of its contents at all times. I think it's fair to say that an accumulator does as well (consider a language over matrices or quantum mechanical operators instead of over the integers). If the only possible data structure must impose a total ordering, then a stack is the only possibility. BUT... does peg impose a total ordering? Doesn't the nondeterminism hint that there's something other than a total ordering? Actually, because a peg program must be parsed backward, it occurs to me to take a lesson from Stevan Apter, and make the language's parse structure explicit. In order to be parsed backward, it would make sense to describe the start of a parse as pushing the REVERSE of the initial program onto a stack (which plays the same role as Forth's return stack and xy's dequeue. I'd better send this -- otherwise I'll never finish writing it. Undeniably peg is stack-based, but there's a lot more going on in terms of data structures and algorithms than just the usual return stack-data stack pair, and I think the additional stuff is interesting. >> 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. > Peg is a pure functional language, so it doesn't matter if a1 is executed= if a2 > yields no results; the execution of a1 has no observable effects. Oh, so I actually completely misunderstood. "False assert" doesn't halt the PROGRAM; rather, it halts the PARSE; it actually sends the program into a "never terminates" state. That makes perfect sense; and seems quite clever. >=A0The exception is if a1 performs I/O. =A0Unfortunately, I can't see any = way to fix > this, because the Peg interpreter could never perform any I/O for fear of= an > unseen 'False assert' being concatenated to the right. Then let's just note that performing IO renders undefined results in the presence of nonterminating programs. Good ol' "undefined results". > For Peg, it is formally concatenative with some modifications: > 1. The expression to the right must be fully evaluated before evaluation = of a sub-expression containing an IO token. That seems like a nice rule. > 2. Concatenation must be performed on the Cartesian products of the resul= ts of evaluation of the sub-expressions You MIGHT mean composition rather than concatenation. Is that the case? If so, you've discovered a new subvariant of a "concatenative language". The usual rule is "the syntax of concatenation implies the semantics of composition", but for your language the rule is "the syntax of concatenation implies the semantics of composition of all Cartesian products". I like it. Now, Enchilada did something similar, but IIRC it didn't do it with mere concatenation (van Dalen?); I don't know enough about Ripple to say anything, but it either did this or allowed some explicit operations to cause it (fortytwo, are you listening?). Either way, I just learned something new. -Wm --n2C-n9pbJWVIfc5k1-hePHyS-nSVYwnlb7A1uG4 Content-Type: text/html; charset=ISO-8859-1 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> <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>dustin.deweese <<a href=3D"mailto:dustin.deweese%40gmail.com">d= [email protected]</a>> wrote:<br> > --- In <a href=3D"mailto:concatenative%40yahoogroups.com">concatenativ= [email protected]</a>, "William Tanksley, Jr" <wtanksleyjr@...= > wrote:<br> >> Don Groves <dgpdx@...> wrote:<br> >> > Of course, any concatentative language doesn't have to use a = stack,<br> >> > it's just most convenient.<br> >> "Convenient" is kind of vague. A stack is the only param= eter-passing<br> >> data structure we know of that's computationally complete/Turing<b= r> >> 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 d= on't<br> >> we know about?<br> <br> > The stack works essentially as a sort of caching structure. =A0Whichev= er caching strategy you choose determines the data structure.<br> > Last in, first out =3D queue<br> > Highest/lowest weighted out =3D priority queue<br> > First in, first out =3D stack<br> > There can be only one =3D a single item (accumulator)<br> > I can't think of any other strategies that have a single unambiguous &= quot;top" element. =A0FIFO seems to be the only reasonable caching str= ategy, though.<br> <br> That's a clever approach. Although I liked it at first glance, I think<br> it's not quite complete. We know concatenative languages that use an<br> accumulator and ones that use a stack; we also know ones that use<br> multiples of each (for example, ANS Forth can have a separate floating<br> point stack, and Machine Forth uses a memory fetch register; note that<br> the return stack in Forth does NOT count, since accessing that makes<br> the program NOT concatenative). The problem is that the choice between<br> stack and accumulator changes the language in a profound way. So if it<br> were possible to arrange a queue in some way instead of a stack, what<br> would the resulting language look like? We have no semantics for such<br> a language (yet).<br> <br> I'm also thinking about the statement that there should be only one<br> unambiguous "top" element. This is essentially right, of course;<= br> accepting that when there are two top elements they can be<br> disambiguated by the word that's needing the data (as with ANS Forth's<br> floating point vocabulary, whose words may pull from a distinct<br> stack). There are more details, of course, since some words accept<br> more than one parameter, so at the time the word is called the<br> structure must provide ALL of its elements to it unambiguously (so not<br> just the top item).<br> <br> A stack meets that requirement by imposing a total ordering of all of<br> its contents at all times. I think it's fair to say that an<br> accumulator does as well (consider a language over matrices or quantum<br> mechanical operators instead of over the integers). If the only<br> possible data structure must impose a total ordering, then a stack is<br> the only possibility. BUT... does peg impose a total ordering? Doesn't<br> the nondeterminism hint that there's something other than a total<br> ordering?<br> <br> Actually, because a peg program must be parsed backward, it occurs to<br> me to take a lesson from Stevan Apter, and make the language's parse<br> structure explicit. In order to be parsed backward, it would make<br> sense to describe the start of a parse as pushing the REVERSE of the<br> initial program onto a stack (which plays the same role as Forth's<br> return stack and xy's dequeue.<br> <br> I'd better send this -- otherwise I'll never finish writing it.<br> Undeniably peg is stack-based, but there's a lot more going on in<br> terms of data structures and algorithms than just the usual return<br> stack-data stack pair, and I think the additional stuff is<br> interesting.<br> <br> >> Here's another question: is peg _formally_ concatenative? That is,= <br> >> given two valid programs, is their concatenation also a valid prog= ram?<br> >> Are the semantics of the resulting program the composition of the<= br> >> semantics of the original two?<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 concatenat= ion<br> >> "a1 a2" will perform (deterministically) the semantics o= f a2, but<br> >> never a1.<br> <br> > Peg is a pure functional language, so it doesn't matter if a1 is execu= ted if a2<br> > yields no results; the execution of a1 has no observable effects.<br> <br> Oh, so I actually completely misunderstood. "False assert" doesn'= t<br> halt the PROGRAM; rather, it halts the PARSE; it actually sends the<br> program into a "never terminates" state. That makes perfect sense= ; and<br> seems quite clever.<br> <br> >=A0The exception is if a1 performs I/O. =A0Unfortunately, I can't see a= ny way to fix<br> > this, because the Peg interpreter could never perform any I/O for fear= of an<br> > unseen 'False assert' being concatenated to the right.<br> <br> Then let's just note that performing IO renders undefined results in<br> the presence of nonterminating programs. Good ol' "undefined results&q= uot;.<br> <br> > For Peg, it is formally concatenative with some modifications:<br> > 1. The expression to the right must be fully evaluated before evaluati= on of a sub-expression containing an IO token.<br> <br> That seems like a nice rule.<br> <br> > 2. Concatenation must be performed on the Cartesian products of the re= sults of evaluation of the sub-expressions<br> <br> You MIGHT mean composition rather than concatenation. Is that the case?<br> <br> If so, you've discovered a new subvariant of a "concatenative<br> language". The usual rule is "the syntax of concatenation implies= the<br> semantics of composition", but for your language the rule is "the= <br> syntax of concatenation implies the semantics of composition of all<br> Cartesian products".<br> <br> I like it.<br> <br> Now, Enchilada did something similar, but IIRC it didn't do it with<br> mere concatenation (van Dalen?); I don't know enough about Ripple to<br> say anything, but it either did this or allowed some explicit<br> operations to cause it (fortytwo, are you listening?).<br> <br> Either way, I just learned something new.<br> <br> -Wm<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 <div id=3D"ygrp-actbar" style=3D"clear: both; margin-bottom: 10px; whit= e-space: nowrap; color: #666; padding-top: 15px;"> <div> <a href=3D"mailto:[email protected]?subject=3DRe%3A%20%5Bstack%= 5D%20peg%3A%20a%20lazy%2C%20non-deterministic%20concatenative%20language" s= tyle=3D"margin-right: 0; padding-right: 0;"> Reply to <span style=3D"font-weight: 700;">sender</span></a> | <a href=3D"mailto:[email protected]?subject=3DRe%3A%20%= 5Bstack%5D%20peg%3A%20a%20lazy%2C%20non-deterministic%20concatenative%20lan= guage"> Reply to <span style=3D"font-weight: 700;">group</span></a> | <a href=3D"http://groups.yahoo.com/group/concatenative/post;_ylc= =3DX3oDMTJwdmo5MHFvBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2= NzY0BG1zZ0lkAzQ5MjMEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzM0OTQyNTMx?act=3Drepl= y&messageNum=3D4923">Reply <span style=3D"font-weight: 700;">via web post</= span></a> | <a href=3D"http://groups.yahoo.com/group/concatenative/post;_y= lc=3DX3oDMTJlZmViMjliBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MD= A2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTMzNDk0MjUzMQ--" style=3D"font-weigh= t: 700;">Start a New Topic</a> </div> <a href=3D"http://groups.yahoo.com/group/concatenative/mess= age/4915;_ylc=3DX3oDMTM0cW9ycjRzBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3B= JZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MjMEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzM0OTQyNT= MxBHRwY0lkAzQ5MTU-">Messages in this topic</a> (<span style=3D"font-weight: 700;">9</span>) </div>=20 <!------- Start Nav Bar ------> <!-- |**|begin egp html banner|**| --> <div id=3D"ygrp-vital" style=3D"background-color: #e0ecee; font-family: Ver= dana; font-size: 10px; margin-bottom: 10px; padding: 10px;"> <span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-tran= sform: uppercase; ">Recent Activity:</span> <ul style=3D"list-style-type: none; margin: 0; padding: 0; display: inl= ine;"> <li style=3D"border-right: 1px solid #000; font-weight: 700; di= splay: inline; padding: 0 5px; margin-left: 0;"> <span class=3D"cat"><a href=3D"http://groups.yahoo.com/group/concaten= ative/members;_ylc=3DX3oDMTJmbDNuZnZnBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3= Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZtYnJzBHN0aW1lAzEzMzQ5NDI1MzE-?o=3D= 6" style=3D"text-decoration: none;">New Members</a></span> <span class=3D"ct" style=3D"color: #ff7900;">3</span> </li> </ul> =20=20=20=20 <div style=3D"clear: both; padding-top: 2px; color: #1e66ae;"> <a href=3D"http://groups.yahoo.com/group/concatenative;_ylc=3DX3oDMTJlO= W45Y3R1BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2= dGwEc2xrA3ZnaHAEc3RpbWUDMTMzNDk0MjUzMQ--" style=3D"text-decoration: none;">= Visit Your Group</a> </div> </div> =20=20 <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"http://groups.yahoo.com/;_ylc=3DX3oDMTJkNXBtODloBF9TAzk3MzU5Nz= E0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZ= QMxMzM0OTQyNTMx" style=3D"float: left;"><img src=3D"http://l.yimg.com/a/i/u= s/yg/logo/us.gif" height=3D"15" width=3D"137" alt=3D"Yahoo! Groups" style= =3D"border: 0;"/></a> <div style=3D"color: #747575; float: right;">Switch to: <a href=3D"mailto= :[email protected]?subject=3DChange Delivery Format= : Traditional" style=3D"text-decoration: none;">Text-Only</a>, <a href=3D"m= ailto:[email protected]?subject=3DEmail Delivery: Digest= " class=3D"margin-rt" style=3D"text-decoration: none;">Daily Digest</a> &bu= ll; <a href=3D"mailto:[email protected]?subject=3DU= nsubscribe" style=3D"text-decoration: none;">Unsubscribe</a> • <a href= =3D"http://docs.yahoo.com/info/terms/" style=3D"text-decoration: none;">Ter= ms of Use</a></div> </div> <!-- |**|end egp html banner|**| --> </div> <!-- ygrp-msg --> <!-- 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=3D4923/stime=3D1334942531/nc1=3D3848642/nc2=3D5758219/= nc3=3D4507179" width=3D"1" height=3D"1"> <br> <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; } 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; } =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-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; }=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 --> --n2C-n9pbJWVIfc5k1-hePHyS-nSVYwnlb7A1uG4--