Re: [stack] Re: Jon Purdy: Why Concatenative Programming Matters
"William Tanksley, Jr" <[email protected]> Sun, 25 Mar 2012 10:03:10 -0700
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAFTBfO6PPNuv5qXJzR3qcSzZjv_gM+ER0tShKguw8O+S=yji3g@mail.gmail.com> |
--jSQLqvFnAw2Tm-lPPGT64icJXZnF1QZfcDXOl1W Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 7bit Ruurd <[email protected]> wrote: > Hi, > You don't have to add i/o primitives to your language. All computers > are permutations of a Turing machine and a Turing machine does not > have i/o. Computers with i/o are categorically different from ones without it, capable of computing tasks in completely different time orders. Turing machines help to define the Chomsky hierarchy (they're at the top), but there are many types of Turing machines, not all of which are equivalent (and i/o is the big difference). > You feed this tape to the program that interpretes the zeroone universal evaluator and after executing, whatever is left on the tape > is the output. Most significantly, zeroone, unlike a Turing machine, has no access to its own code. This means that there is NO tape, no data left on the tape, no writing to the tape. There is a stack, but the stack isn't a simple list of symbols; rather, it's a stack of functions, and by definition there's no way to interpret a function consistently. So adding i/o is a major upgrade. > You can find the competitor here: http://homepages.cwi.nl/~tromp/cl/cl.html I'd clean forgotten that... Excellent, more citation materiel. Yes, his goal is similar to mine. > The author switched from combinatory calculus to the lambda calculus, > because the last one is more descriptive. The comparison was made, > based on the size of the self-interpreter. I recall that, yes. > I think that a comparison > based on a brainfuck interpreter is more realistic. If by that you mean that comparing the size of the *same* program is more useful than comparing the size of different programs -- I agree. But I wouldn't expect the results to change -- although that's just my gut feeling. The reason I expect that is that although a lambda combinator requires more program-bits to express, it's always the exact combinator that's needed, never an approximation that needs to be corrected. Meanwhile, a zeroone program carries no information in the arrangement of program-bits that isn't already encoded in the interpreter. Practically, this means that zeroone programs will always (well, normally) be bigger than the same program written in either other language. > Also, the > combinatory calculus was restricted to just S and K and I wonder > what difference it will make if more combinators are added. More combinators certainly means the program will be shorter; the worry is that one can define a combinator which makes the program VERY short. I'm reminded of a UCSD processor design task where one of the final goals was to run a median computation; I built a stack processor and included hardware to implement a "perfect bitonic shuffle" on the stack, which I'd made deep enough to handle all of the data on which the median was being computed. Since the assignment was graded on how many cycles our processor required to perform the tasks, my team broke the grade curve. That was fun. Especially since the TA didn't believe it would work at all. But adding more combinators has long been a goal of mine. Particularly because handling i/o will allow me to make a sensible comparison along the same line as the above, but also because it seems perfectly obvious that granting access to a neater selection of combinators would allow for shorter, clearer programs. Interestingly, adding more combinators should also force the interpreter's source code to be larger, especially if it's expressed in a different language. For this reason, I'd want to compare sizes of the language's interpreter written in a standard language (compared to the other interpreters written in the same standard language), then the sizes of a standard program (your suggestion of a brainfuck interpreter is perfectly valid) written in the language itself. Sadly, adding more combinators has revealed some kind of bug in the most important of my "tworing" utilities -- so I've got some work to do. > Also, I wonder if the comparison is still in favor of the lambda > calculus when concatenative combinators are used instead. Since zeroone not only loses the ability to define its own combinators, but also loses the ability to have the beginning of the program define the parse environment in which the latter part is read -- I expect short to medium length programs to be MUCH longer in zeroone. (Once the program size gets large, the data structures on the stack should begin to help, and the sizes should come out roughly similar.) > It is not my personal quest to find an answer, that's why I am > asking. I assume you meant "now" rather than "not". My personal most annoying typo :-). > R. -Wm --jSQLqvFnAw2Tm-lPPGT64icJXZnF1QZfcDXOl1W 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> > You don't have to add i/o primitives to your language. All computers<br> > are permutations of a Turing machine and a Turing machine does not<br> > have i/o.<br> <br> Computers with i/o are categorically different from ones without it,<br> capable of computing tasks in completely different time orders. Turing<br> machines help to define the Chomsky hierarchy (they're at the top),<br> but there are many types of Turing machines, not all of which are<br> equivalent (and i/o is the big difference).<br> <br> > You feed this tape to the program that interpretes the zeroone universal evaluator and after executing, whatever is left on the tape<br> > is the output.<br> <br> Most significantly, zeroone, unlike a Turing machine, has no access to<br> its own code. This means that there is NO tape, no data left on the<br> tape, no writing to the tape. There is a stack, but the stack isn't a<br> simple list of symbols; rather, it's a stack of functions, and by<br> definition there's no way to interpret a function consistently. So<br> adding i/o is a major upgrade.<br> <br> > You can find the competitor here: <a href="http://homepages.cwi.nl/~tromp/cl/cl.html">http://homepages.cwi.nl/~tromp/cl/cl.html</a><br> <br> I'd clean forgotten that... Excellent, more citation materiel. Yes,<br> his goal is similar to mine.<br> <br> > The author switched from combinatory calculus to the lambda calculus,<br> > because the last one is more descriptive. The comparison was made,<br> > based on the size of the self-interpreter.<br> <br> I recall that, yes.<br> <br> > I think that a comparison<br> > based on a brainfuck interpreter is more realistic.<br> <br> If by that you mean that comparing the size of the *same* program is<br> more useful than comparing the size of different programs -- I agree.<br> But I wouldn't expect the results to change -- although that's just my<br> gut feeling. The reason I expect that is that although a lambda<br> combinator requires more program-bits to express, it's always the<br> exact combinator that's needed, never an approximation that needs to<br> be corrected.<br> <br> Meanwhile, a zeroone program carries no information in the arrangement<br> of program-bits that isn't already encoded in the interpreter.<br> Practically, this means that zeroone programs will always (well,<br> normally) be bigger than the same program written in either other<br> language.<br> <br> > Also, the<br> > combinatory calculus was restricted to just S and K and I wonder<br> > what difference it will make if more combinators are added.<br> <br> More combinators certainly means the program will be shorter; the<br> worry is that one can define a combinator which makes the program VERY<br> short. I'm reminded of a UCSD processor design task where one of the<br> final goals was to run a median computation; I built a stack processor<br> and included hardware to implement a "perfect bitonic shuffle" on the<br> stack, which I'd made deep enough to handle all of the data on which<br> the median was being computed. Since the assignment was graded on how<br> many cycles our processor required to perform the tasks, my team broke<br> the grade curve. That was fun. Especially since the TA didn't believe<br> it would work at all.<br> <br> But adding more combinators has long been a goal of mine. Particularly<br> because handling i/o will allow me to make a sensible comparison along<br> the same line as the above, but also because it seems perfectly<br> obvious that granting access to a neater selection of combinators<br> would allow for shorter, clearer programs. Interestingly, adding more<br> combinators should also force the interpreter's source code to be<br> larger, especially if it's expressed in a different language.<br> <br> For this reason, I'd want to compare sizes of the language's<br> interpreter written in a standard language (compared to the other<br> interpreters written in the same standard language), then the sizes of<br> a standard program (your suggestion of a brainfuck interpreter is<br> perfectly valid) written in the language itself.<br> <br> Sadly, adding more combinators has revealed some kind of bug in the<br> most important of my "tworing" utilities -- so I've got some work to<br> do.<br> <br> > Also, I wonder if the comparison is still in favor of the lambda<br> > calculus when concatenative combinators are used instead.<br> <br> Since zeroone not only loses the ability to define its own<br> combinators, but also loses the ability to have the beginning of the<br> program define the parse environment in which the latter part is read<br> -- I expect short to medium length programs to be MUCH longer in<br> zeroone. (Once the program size gets large, the data structures on the<br> stack should begin to help, and the sizes should come out roughly<br> similar.)<br> <br> > It is not my personal quest to find an answer, that's why I am<br> > asking.<br> <br> I assume you meant "now" rather than "not". My personal most annoying typo :-).<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=X3oDMTJwaHR2NW1oBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTQEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzMyNjk1MDIz?act=reply&messageNum=4914">Reply <span style="font-weight: 700;">via web post</span></a> | <a href="http://groups.yahoo.com/group/concatenative/post;_ylc=X3oDMTJlanVibGJlBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTMzMjY5NTAyMw--" style="font-weight: 700;">Start a New Topic</a> </div> <a href="http://groups.yahoo.com/group/concatenative/message/4883;_ylc=X3oDMTM0bWdqaHVzBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5MTQEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQMxMzMyNjk1MDIzBHRwY0lkAzQ4ODM-">Messages in this topic</a> (<span style="font-weight: 700;">32</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=X3oDMTJlb251MnA4BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTMzMjY5NTAyMw--" 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=X3oDMTJkNmFhZmszBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZQMxMzMyNjk1MDIz" 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=4914/stime=1332695023/nc1=4507179/nc2=3848640/nc3=4836041" 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 --> --jSQLqvFnAw2Tm-lPPGT64icJXZnF1QZfcDXOl1W--