Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters
"William Tanksley, Jr" <[email protected]> Sat, 24 Mar 2012 13:51:05 -0700
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAFTBfO4bMmeEqjDhNVAc0nCyQwnebbebO=XR5pxo_JWSDCKNhA@mail.gmail.com> |
--69xP7YIq-gQf2zZ3psmUkxJWNymzlHA7zo9r4Ci Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Ruurd <[email protected]> wrote: > Hi, > I can't find q on iepos' webpage, but I do find cake. > Is q the same as cake ? I'm sorry -- I didn't realize that. Using the same notation as iepos' page: [B] [A] q == [[B]] [A B] So, q serves three purposes: it makes A and B into siblings in a list; it swaps the order of A and B; and it adds a layer of quotation to B. You noticed cake; it turns out that cake can serve in place of q, since it does all of the above things (although in a more complex way). > Can zeroone be used to write a brainfuck interpreter in 112 bytes > or less ? That would be interesting. No, because zeroone's underlying machine has no i/o capability of any kind. The obvious question pops to mind: is it possible to make a zeroone with i/o? It's taken me a while, but I finally realized what I needed -- the ability to pack an arbitrary number of primitives into the "zero" pseudocombinator. The zero combinator I used before was zero == [] [q] [k]. All three components are important -- the empty list gives us a starting point for building lists at runtime, the 'k' combinator allows us to take lists apart, and 'q' is the universal constructor. The combinators can be replaced by others that do similar jobs, though. I mentioned that "q" can be replaced by the "cake" combinator you found, and indeed anything that can do the same basic tasks that 'q' does can fill its place. So what I'm going to do is pack all those extra combinators into a binary tree in place of the [q] combinator, and make it quick and easy to climb that tree by making both 'k' and its stack-flipped version, 'z', easily available. Remember, the entire tree can be placed on the stack by itself with the code "0011" (which doesn't actually depend on what is inside the middle element of the 'zero' combinator); therefore, I'll simply use the name "tree" for that. So; let's make a tree that contains z, input, output, and q: [ [[input] [q]], [[output] [z]] ]. So to construct 'z' here, we write "tree 11"; read this as "get the tree, execute the right branch, then the right branch again." (I assume none of the spaces matter.) You'll recall that 'k' is simply "1", so we now have both 'k' and 'z'; and for our special purposes here, I'll use "left" and "right" as a synonym for "z" and "k", respectively. From this, we get q == "tree left right"; input == "tree left left", and "output" == "tree right left". Obviously, at this point we've proven that we can access anything in ANY binary tree; we can use any number of primitives we want. (I know, I haven't explained what "input" and "output" do. They do whatever we want them to do, and now we can define and provide primitives that manipulate what they produce.) Another thing I haven't done is to figure out how to get a shorter expression for "z". Right now it's much bigger than "k", and strong asymmetry is usually a hint of non-optimality. > R. -Wm --69xP7YIq-gQf2zZ3psmUkxJWNymzlHA7zo9r4Ci 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"> </span> <!--~-|**|PrettyHtmlStartT|**|-~--> <div id="ygrp-mlmsg" style="position:relative;"> <div id="ygrp-msg" style="z-index: 1;"> <!--~-|**|PrettyHtmlEndT|**|-~--> <div id="ygrp-text" > <p>Ruurd <<a href="mailto:r.wiersma26%40kpnplanet.nl">[email protected]</a>> wrote:<br> > Hi,<br> > I can't find q on iepos' webpage, but I do find cake.<br> > Is q the same as cake ?<br> <br> I'm sorry -- I didn't realize that. Using the same notation as iepos' page:<br> <br> [B] [A] q == [[B]] [A B]<br> <br> So, q serves three purposes: it makes A and B into siblings in a list;<br> it swaps the order of A and B; and it adds a layer of quotation to B.<br> <br> You noticed cake; it turns out that cake can serve in place of q,<br> since it does all of the above things (although in a more complex<br> way).<br> <br> > Can zeroone be used to write a brainfuck interpreter in 112 bytes<br> > or less ? That would be interesting.<br> <br> No, because zeroone's underlying machine has no i/o capability of any<br> kind. The obvious question pops to mind: is it possible to make a<br> zeroone with i/o? It's taken me a while, but I finally realized what I<br> needed -- the ability to pack an arbitrary number of primitives into<br> the "zero" pseudocombinator.<br> <br> The zero combinator I used before was zero == [] [q] [k]. All three<br> components are important -- the empty list gives us a starting point<br> for building lists at runtime, the 'k' combinator allows us to take<br> lists apart, and 'q' is the universal constructor. The combinators can<br> be replaced by others that do similar jobs, though. I mentioned that<br> "q" can be replaced by the "cake" combinator you found, and indeed<br> anything that can do the same basic tasks that 'q' does can fill its<br> place.<br> <br> So what I'm going to do is pack all those extra combinators into a<br> binary tree in place of the [q] combinator, and make it quick and easy<br> to climb that tree by making both 'k' and its stack-flipped version,<br> 'z', easily available. Remember, the entire tree can be placed on the<br> stack by itself with the code "0011" (which doesn't actually depend on<br> what is inside the middle element of the 'zero' combinator);<br> therefore, I'll simply use the name "tree" for that.<br> <br> So; let's make a tree that contains z, input, output, and q: [<br> [[input] [q]], [[output] [z]] ].<br> <br> So to construct 'z' here, we write "tree 11"; read this as "get the<br> tree, execute the right branch, then the right branch again." (I<br> assume none of the spaces matter.) You'll recall that 'k' is simply<br> "1", so we now have both 'k' and 'z'; and for our special purposes<br> here, I'll use "left" and "right" as a synonym for "z" and "k",<br> respectively.<br> <br> From this, we get q == "tree left right"; input == "tree left left",<br> and "output" == "tree right left".<br> <br> Obviously, at this point we've proven that we can access anything in<br> ANY binary tree; we can use any number of primitives we want. (I know,<br> I haven't explained what "input" and "output" do. They do whatever we<br> want them to do, and now we can define and provide primitives that<br> manipulate what they produce.)<br> <br> Another thing I haven't done is to figure out how to get a shorter<br> expression for "z". Right now it's much bigger than "k", and strong<br> asymmetry is usually a hint of non-optimality.<br> <br> > R.<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%20Re%3A%20Jon%20Purdy%3A%20Why%20Concatenative%20Programming%20Matters" 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%20Re%3A%20Jon%20Purdy%3A%20Why%20Concatenative%20Programming%20Matters"> Reply to <span style="font-weight: 700;">group</span></a> | <a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJwNm52ODFhBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTEEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzMyNjIyMjk3?act=reply&messageNum=4911">Reply <span style="font-weight: 700;">via web post</span></a> | <a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJlbjdhZTUyBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTMzMjYyMjI5Nw--" style="font-weight: 700;">Start a New Topic</a> </div> <a href="http://groups.yahoo.com/group/concatenative/message/4883;_ylc=X3oDMTM0YWh2M2g4BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTEEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzMyNjIyMjk3BHRwY0lkAzQ4ODM-">Messages in this topic</a> (<span style="font-weight: 700;">29</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=X3oDMTJla29qY2QxBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTMzMjYyMjI5Nw--" 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=X3oDMTJkN2Q4MzEyBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzMyNjIyMjk3" 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=4911/stime=1332622297/nc1=5898818/nc2=3848643/nc3=4507179" 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 --> --69xP7YIq-gQf2zZ3psmUkxJWNymzlHA7zo9r4Ci--