Overview of prefix vs postfix notations + evaluation schemes.
"Artjom Kossow [email protected] [concatenative]" <[email protected]> Sat, 5 Jul 2014 19:38:43 +0200
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <CAFVLW5jnb2hwUw2LHxS7oscW6bkk=Nydqpu9AV5ugAFi_0KS8g@mail.gmail.com> |
--001a11c2f32498c7a804fd75b63a
Content-Type: text/plain; charset=UTF-8
Hi All,
First of all, I am very glad to be a part of this awesome mailing list.
Lets keep it alive :) Now, to the topic:
I have tried to find a decent overview or an open discussion (if there is
one) about the substantial differences of prefix vs postfix notation for
concatenative languages, but I couldn't. Also, I would like to discuss
potential advantages of different evaluation schemes. I would be grateful
if any could provide clarifications to the statements and give some
examples, maybe. So:
1. Postfix, left-to-right evaluation
Well, this is like any FORTH-like language we know. Values and
quotations are pushed onto the stack, operations and combinators are
directly executed.
2. Postfix, right-to-left evaluation
This one is used, as far as I know only in Ripple
<https://github.com/joshsh/ripple>. Values, execution tokens and such
are pushed onto the stack and only evalueted once explicit apply "." is
encountered. Are there any direct advantages to that scheme, aside from the
"inehrent" lazyness for all operations (say: we save some quoting here and
there...)?
3. Prefix, left-to-right evaluation
As far as I know, this one is Om Language <http://om-language.org/>. The
author itself mentions following advantages of a prefix notation:
- *Prefix notation more closely models function composition. Instead of
storing a data stack in memory, the Om evaluator stores a composed partial
function.*
- So? We can do that in a normal postifx notation as well, as XY
<http://www.nsl.com/k/xy/xy.htm> does.
- *The evaluator can read, parse and evaluate the input stream in a
single pass, sending results to the output stream as soon as they are
evaluated. This cannot be done with a postfix, stack-based language because
any data on the stack must remain there as it may be needed by a function
later.*
- Could someone give some examples here (and/or counter-examples)? I
can't get this :(
-
*Functions can be optimized to only read into memory the data that is
required; stack-based postfix languages have no knowledge of the function
to apply until the data is already in memory, on the stack. -* I guess
we can get this for free with postfix, right-to-left evaluation, right?
-
*Incoming data, such as events, become simple to handle at a language
level: a program might evaluate to a function that acts as a state machine
that processes any additional data appended to the program and transitions
to a new state, ready to process new data. -* Damn, I don't get that
either :(
-
*An integrated development environment can provide hints to the user about
the data that is expected by a function. *- Why we can't do the same for
posfix? Almost every definition in forth-like languages has stack-effect
diagram, so IDE can use that, right? What is a benefit of having prefix
here? BTW, why there is no IDE that will show stack effect diagram inside a
definition automatically, based on a current cursor position?
4. Prefix, right-to-left evaluation
I guess this is totally useless and not possible, right? :)
Thank you very much for your time.
Best Regards,
Artjoms.
--001a11c2f32498c7a804fd75b63a
Content-Type: text/html; charset=UTF-8
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>
=20
<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><div dir=3D"ltr"><span style=3D"font-family:arial,sans-serif;font-=
size:13px;">Hi All,</span><div style=3D"font-family:arial,sans-serif;font-s=
ize:13px;"><br></div><div style=3D"font-family:arial,sans-serif;font-size:1=
3px;">First of all, I am very glad to be a part of this awesome mailing lis=
t. Lets keep it alive :) Now, to the topic:<br>
I have tried to find a decent overview or an open discussion (if there is o=
ne) about the substantial differences of prefix vs postfix notation for con=
catenative languages, but I couldn't. Also, I would like to discuss pot=
ential advantages of different evaluation schemes. I would be grateful if a=
ny could provide clarifications to the statements and give some examples, m=
aybe. =C2=A0So:</div>
<div style=3D"font-family:arial,sans-serif;font-size:13px;"><br></div><div =
style=3D"font-family:arial,sans-serif;font-size:13px;"><ol><li style=3D"mar=
gin-left:15px;">Postfix, left-to-right evaluation<br>Well, this is like any=
FORTH-like language we know. Values and quotations are pushed onto the sta=
ck, operations and combinators are directly executed.=C2=A0</li>
<li style=3D"margin-left:15px;">Postfix, right-to-left evaluation<br>This o=
ne is used, as far as I know only in=C2=A0<a href=3D"https://github.com/jos=
hsh/ripple" target=3D"_blank">Ripple</a>. Values, execution tokens and such=
are pushed onto the stack and only evalueted once explicit apply ".&q=
uot; is encountered. Are there any direct advantages to that scheme, aside =
from the "inehrent" lazyness for all operations (say: we save som=
e quoting here and there...)?</li>
<li style=3D"margin-left:15px;">Prefix, left-to-right evaluation<br>As far =
as I know, this one is=C2=A0<a href=3D"http://om-language.org/" target=3D"_=
blank">Om Language</a>. The author itself mentions following advantages of =
a prefix notation:</li>
</ol><ul><li style=3D"margin-left:15px;"><i>Prefix notation more closely mo=
dels function composition. Instead of storing a data stack in memory, the O=
m evaluator stores a composed partial function.</i><br>- So? We can do that=
in a normal postifx notation as well, as=C2=A0<a href=3D"http://www.nsl.co=
m/k/xy/xy.htm" target=3D"_blank">XY</a>=C2=A0does.=C2=A0</li>
<li style=3D"margin-left:15px;"><i>The evaluator can read, parse and evalua=
te the input stream in a single pass, sending results to the output stream =
as soon as they are evaluated. This cannot be done with a postfix, stack-ba=
sed language because any data on the stack must remain there as it may be n=
eeded by a function later.</i><br>
- Could someone give some examples here (and/or counter-examples)? I can=
9;t get this :(</li><li style=3D"margin-left:15px;"><i>Functions can be opt=
imized to only read into memory the data that is required; stack-based post=
fix languages have no knowledge of the function to apply until the data is =
already in memory, on the stack.<br>
-</i>=C2=A0I guess we can get this for free with=C2=A0postfix, right-to-lef=
t evaluation, right?</li><li style=3D"margin-left:15px;"><i>Incoming data, =
such as events, become simple to handle at a language level: a program migh=
t evaluate to a function that acts as a state machine that processes any ad=
ditional data appended to the program and transitions to a new state, ready=
to process new data.<br>
-</i>=C2=A0Damn, I don't get that either :(</li><li style=3D"margin-lef=
t:15px;"><i>An integrated development environment can provide hints to the =
user about the data that is expected by a function.<br></i>- Why we can'=
;t do the same for posfix? Almost every definition in forth-like languages =
has stack-effect diagram, so IDE can use that, right? What is a benefit of =
having prefix here? BTW, why there is no IDE that will show stack effect di=
agram inside a definition automatically, based on a current cursor position=
?</li>
</ul><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A04. Prefix, right-to-left evalua=
tion<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0I guess this is tot=
ally useless and not possible, right? :)</div><div><br></div><div><br></div=
><i></i><div>Thank you very much for your time.</div></div>
<div style=3D"font-family:arial,sans-serif;font-size:13px;"><br></div><div =
style=3D"font-family:arial,sans-serif;font-size:13px;">Best Regards,</div><=
div style=3D"font-family:arial,sans-serif;font-size:13px;">Artjoms.</div></=
div>
</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
=20=20=20=20
<div style=3D"clear:both"> </div>
<div id=3D"fromDMARC" style=3D"margin-top: 10px;">
<hr style=3D"height:2px ; border-width:0; color:#E3E3E3; background=
-color:#E3E3E3;">
Posted by: Artjom Kossow <[email protected]> <hr styl=
e=3D"height:2px ; border-width:0; color:#E3E3E3; background-color:#E3E3E3;"=
>
</div>
<div style=3D"clear:both"> </div>
<table cellspacing=3D4px style=3D"margin-top: 10px; margin-bottom: 10px=
; color: #2D50FD;">
<tbody>
<tr>
<td style=3D"font-size: 12px; font-family: arial; font-weight: bo=
ld; padding: 7px 5px 5px;" >
<a style=3D"text-decoration: none; color: #2D50FD=
" href=3D"https://groups.yahoo.com/neo/groups/concatenative/conversations/m=
essages/4997;_ylc=3DX3oDMTJwanJmN2Q5BF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3J=
wc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5OTcEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxNDA0NT=
gxOTI0?act=3Dreply&messageNum=3D4997">Reply via web post</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"mailto:[email protected]?subject=3DRe%3A%20Overview=
%20of%20prefix%20vs%20postfix%20notations%20%2B%20evaluation%20schemes%2E" =
style=3D"text-decoration: none; color: #2D50FD;">
Reply to sender </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;">
<a href=3D"mailto:[email protected]?subject=3DRe%3A=
%20Overview%20of%20prefix%20vs%20postfix%20notations%20%2B%20evaluation%20s=
chemes%2E" style=3D"text-decoration: none; color: #2D50FD">
Reply to group </a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;" >
<a href=3D"https://groups.yahoo.com/neo/groups/concatenative/co=
nversations/newtopic;_ylc=3DX3oDMTJlc2M0djI0BF9TAzk3MzU5NzE0BGdycElkAzE4Mzk=
yNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTQwNDU4MTkyNA=
--" style=3D"text-decoration: none; color: #2D50FD">Start a New Topic</a>
</td>
<td>•</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px;color: #2D50FD;" >
<a href=3D"https://groups.yahoo.com/neo/groups/=
concatenative/conversations/topics/4997;_ylc=3DX3oDMTM0aTZrc2pzBF9TAzk3MzU5=
NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5OTcEc2VjA2Z0cgR=
zbGsDdnRwYwRzdGltZQMxNDA0NTgxOTI0BHRwY0lkAzQ5OTc-" style=3D"text-decoration=
: none; color: #2D50FD;">Messages in this topic</a>
(1)
</td>
</tr>
</tbody>
</table>
=20=20=20=20=20=20=20=20
<!------- Start Nav Bar ------>
=20
<!-- |**|begin egp html banner|**| -->
<div id=3D"ygrp-vital" style=3D"background-color: #f2f2f2; font-family: Ver=
dana; font-size: 10px; margin-bottom: 10px; padding: 10px;">
<span id=3D"vithd" style=3D"font-weight: bold; color: #333; text-transf=
orm: uppercase; "><a href=3D"https://groups.yahoo.com/neo/groups/concatenat=
ive/info;_ylc=3DX3oDMTJldmVsOTFsBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3B=
JZAMxNzA1MDA2NzY0BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWUDMTQwNDU4MTkyNA--" style=3D=
"text-decoration: none;">Visit Your Group</a></span>
<ul style=3D"list-style-type: none; margin: 0; padding: 0; display: in=
line;">
</ul>
</div>
<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"https://groups.yahoo.com/neo;_ylc=3DX3oDMTJkcmwzYm45BF9TAzk3ND=
c2NTkwBGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzd=
GltZQMxNDA0NTgxOTI0" style=3D"float: left;"><img src=3D"http://l.yimg.com/r=
u/static/images/yg/img/email/new_logo/logo-groups-137x15.png" height=3D"15"=
width=3D"137" alt=3D"Yahoo! Groups" style=3D"border: 0;"/></a>
<div style=3D"color: #747575; float: right;"> • <a href=3D"https://i=
nfo.yahoo.com/privacy/us/yahoo/groups/details.html" style=3D"text-decoratio=
n: none;">Privacy</a> • <a href=3D"mailto:concatenative-unsubscribe@ya=
hoogroups.com?subject=3DUnsubscribe" style=3D"text-decoration: none;">Unsub=
scribe</a> • <a href=3D"https://info.yahoo.com/legal/us/yahoo/utos/ter=
ms/" style=3D"text-decoration: none;">Terms of Use</a> </div>
</div>
<br>
<!-- |**|end egp html banner|**| -->
</div> <!-- ygrp-msg -->
=20
<!-- 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=3D4997/stime=3D1404581924" width=3D"1" height=3D"1"> <=
br>
<img src=3D"http://y.analytics.yahoo.com/fpc.pl?ywarid=3D515FB27823A7407E&a=
=3D10001310322279&js=3Dno&resp=3Dimg" width=3D"1" height=3D"1">=20
<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;
}
#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-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 -->
--001a11c2f32498c7a804fd75b63a--