Re: [stack] positional postfix evaluation
John Nowak <[email protected]> Mon, 27 May 2013 19:59:01 -0400
| Newsgroups | gmane.comp.lang.concatenative |
|---|---|
| Message-ID | <[email protected]> |
--AJWkSo1ZxV9euGhcAfZHSwZ7CTmWEFmCczNWMv3
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
On 05/27/2013 03:30 PM, Robbert van Dalen wrote:
> so why the need for positions?
> it allows the data flow of a program to be easily eyeballed.
Only when you're writing expressions that compute to values. Most of the
time, however, you're defining functions and your technique will be of
no use. For example, suppose I want to write a simple function that
computes the length of a list in a Joy:
length == [null] [drop 0] [uncons [drop] dip length 1 +] ifte
As can be clearly seen, there's no obvious way to group any of this.
> so why the need for subexpressions and parenthesis?
> solely because of efficiency reasons.
Why would this make any difference in terms of efficiency? So long as
your compiler knows the arity of the words involved before it compiles
them, it can do whatever optimizations you have in mind automatically.
If you're interested in allowing the programmer to get a better handle
on the stack effects of functions, I would suggest applying a typing
discipline. Not only would this work properly in the presence of (higher
order) functions, it would also allow information regarding stack
effects to be computed automatically via type inference.
For example, we can assume the following primitive types:
null : ∀ R a. R (list a) -> R bool
drop : ∀ R a. R a -> R
uncons : ∀ R a. R (list a) -> R a (list a)
dip : ∀ R S a. R a [R -> S] -> S a
+ : ∀ R. R int int -> R int
ifte : ∀ R S T. R [R -> S bool] [R -> T] [R -> T] -> T
Above, the uppercase type variables represent stacks. The lowercase type
variables and lowercase types represent single elements consed onto
stacks. Types like '(list a)' denote the type of a single element equal
to the type constructor 'list' applied to the type 'a'.
With all this in place, we can compute the following type of 'length'
via Hindley–Milner type inference:
length : ∀ R a. R (list a) -> R int
The fact that all this is precise and automatic is of tremendous benefit
to the programmer. We can tell from the type that only the top element
will be inspected (because the function is parametrically polymorphic
with respect to 'R'). We also can tell the function has an arity of '1
-> 1'. Finally, we can tell it works for all lists (because the function
is parametrically polymorphic with respect to 'a') and that the result
will be an integer on top of the stack.
- jn
--AJWkSo1ZxV9euGhcAfZHSwZ7CTmWEFmCczNWMv3
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>
<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>On 05/27/2013 03:30 PM, Robbert van Dalen wrote:<br>
<br>
> so why the need for positions?<br>
> it allows the data flow of a program to be easily eyeballed.<br>
<br>
Only when you're writing expressions that compute to values. Most of th=
e <br>
time, however, you're defining functions and your technique will be of =
<br>
no use. For example, suppose I want to write a simple function that <br>
computes the length of a list in a Joy:<br>
<br>
length =3D=3D [null] [drop 0] [uncons [drop] dip length 1 +] ifte<br>
<br>
As can be clearly seen, there's no obvious way to group any of this.<br=
>
<br>
> so why the need for subexpressions and parenthesis?<br>
> solely because of efficiency reasons.<br>
<br>
Why would this make any difference in terms of efficiency? So long as <br>
your compiler knows the arity of the words involved before it compiles <br>
them, it can do whatever optimizations you have in mind automatically.<br>
<br>
If you're interested in allowing the programmer to get a better handle =
<br>
on the stack effects of functions, I would suggest applying a typing <br>
discipline. Not only would this work properly in the presence of (higher <b=
r>
order) functions, it would also allow information regarding stack <br>
effects to be computed automatically via type inference.<br>
<br>
For example, we can assume the following primitive types:<br>
<br>
null : =E2=88=80 R a. R (list a) -> R bool<br>
drop : =E2=88=80 R a. R a -> R<br>
uncons : =E2=88=80 R a. R (list a) -> R a (list a)<br>
dip : =E2=88=80 R S a. R a [R -> S] -> S a<br>
+ : =E2=88=80 R. R int int -> R int<br>
ifte : =E2=88=80 R S T. R [R -> S bool] [R -> T] [R -> T] -&g=
t; T<br>
<br>
Above, the uppercase type variables represent stacks. The lowercase type <b=
r>
variables and lowercase types represent single elements consed onto <br>
stacks. Types like '(list a)' denote the type of a single element e=
qual <br>
to the type constructor 'list' applied to the type 'a'.<br>
<br>
With all this in place, we can compute the following type of 'length=
9; <br>
via Hindley=E2=80=93Milner type inference:<br>
<br>
length : =E2=88=80 R a. R (list a) -> R int<br>
<br>
The fact that all this is precise and automatic is of tremendous benefit <b=
r>
to the programmer. We can tell from the type that only the top element <br>
will be inspected (because the function is parametrically polymorphic <br>
with respect to 'R'). We also can tell the function has an arity of=
'1 <br>
-> 1'. Finally, we can tell it works for all lists (because the func=
tion <br>
is parametrically polymorphic with respect to 'a') and that the res=
ult <br>
will be an integer on top of the stack.<br>
<br>
- jn<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
<table cellspacing=3D4px style=3D"margin-top: 20px; margin-bottom: 10px=
;">
<tbody>
<tr>
<td style=3D"font-size: 12px; font-family: arial; font-weight: bo=
ld; padding: 7px 5px 5px; color: #FFF; background-color: #F2F2F2; border: 1=
px solid #EAEAEA " >
<a style=3D"text-decoration: none; color: #2D50FD=
" href=3D"http://groups.yahoo.com/group/concatenative/post;_ylc=3DX3oDMTJwZ=
zZhN3NmBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lk=
AzQ5NDMEc2VjA2Z0cgRzbGsDcnBseQRzdGltZQMxMzY5Njk5MTIy?act=3Dreply&messageNum=
=3D4943">Reply via web post</a>
</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; "=
>
<a href=3D"mailto:[email protected]?subject=3DRe%3A%20%5Bstack=
%5D%20positional%20postfix%20evaluation" style=3D"text-decoration: none; co=
lor: #2D50FD;">
Reply to sender </a>=20
</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; "=
>
<a href=3D"mailto:[email protected]?subject=3DRe%3A=
%20%5Bstack%5D%20positional%20postfix%20evaluation" style=3D"text-decoratio=
n: none; color: #2D50FD">
Reply to group </a>=20
</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px; color: #FFF; background-color: #F2F2F2; border: 1px solid #EAEAEA; "=
>
<a href=3D"http://groups.yahoo.com/group/concatenative/post;_yl=
c=3DX3oDMTJlbjI0b2kxBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA=
2NzY0BHNlYwNmdHIEc2xrA250cGMEc3RpbWUDMTM2OTY5OTEyMg--" style=3D"text-decora=
tion: none; color: #2D50FD">Start a New Topic</a>
</td>
<td style=3D"font-size: 12px; font-family: arial; padding: 7px 5p=
x 5px; color: #2D50FD; background-color: #F2F2F2; border: 1px solid #EAEAEA=
; " >
<a href=3D"http://groups.yahoo.com/group/concat=
enative/message/4942;_ylc=3DX3oDMTM0ZmpxNml0BF9TAzk3MzU5NzE0BGdycElkAzE4Mzk=
yNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BG1zZ0lkAzQ5NDMEc2VjA2Z0cgRzbGsDdnRwYwRzdGltZQ=
MxMzY5Njk5MTIyBHRwY0lkAzQ5NDI-" style=3D"text-decoration: none; color: #2D5=
0FD;">Messages in this topic</a>
(2)
</td>
</tr>
</tbody>
</table>
=20=20=20=20=20=20=20=20
<!------- Start Nav Bar ------>
<!-- |**|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-tran=
sform: uppercase; ">Recent Activity:</span>
<ul style=3D"list-style-type: none; margin: 0; padding: 0; display: inl=
ine;">
</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=3DX3oDMTJlZ=
3MxZ3FwBF9TAzk3MzU5NzE0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwN2=
dGwEc2xrA3ZnaHAEc3RpbWUDMTM2OTY5OTEyMg--" 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=3DX3oDMTJkbmhhbmRpBF9TAzk3MzU5Nz=
E0BGdycElkAzE4MzkyNzQEZ3Jwc3BJZAMxNzA1MDA2NzY0BHNlYwNmdHIEc2xrA2dmcARzdGltZ=
QMxMzY5Njk5MTIy" 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> • <a href=3D"mailto:[email protected]=
?subject=3DFeedback on the redesigned individual mail v1" style=3D"text-dec=
oration: none;">Send us Feedback </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=3D4943/stime=3D1369699122" 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;
}
#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 -->
--AJWkSo1ZxV9euGhcAfZHSwZ7CTmWEFmCczNWMv3--