forth in (many lines of) javascript
Dave Long <[email protected]> Sun, 20 Oct 2013 19:23:29 +0200
| Newsgroups | gmane.culture.people.kragen.discuss |
|---|---|
| Message-ID | <[email protected]> |
--Apple-Mail-40-255684063
Content-Transfer-Encoding: 7bit
Content-Type: text/plain;
charset=US-ASCII;
delsp=yes;
format=flowed
Continuing with the general bootstrapping theme, a trip to the
virtual 1970's:
--Apple-Mail-40-255684063
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
x-unix-mode=0644;
name=virtual197x.htm
Content-Disposition: attachment;
filename=virtual197x.htm
<html><head>
<style>
.input { margin: 15px; }
pre { text-shadow: none; color: #000000; }
.input-e { background-color: #b0c0b0; margin: 0;}
.input-o { background-color: #c0c0b7; margin: 0;}
body { font-size: 1em; line-height: 1.5; background: #e7e7e7 0 0 repeat; =
font-family: 'Helvetica Neue', Helvetica, Arial, serif; text-shadow: 0 =
1px 0 rgba(255, 255, 255, 0.8); color: #4d4d4d; }
body { background: #e0e0f0; }
</style>
</head><body>
<h1>Virtual 1970's</h1>
What can we say about the data given here?
<pre id=3D"output"></pre>
It is (they are) the output of the following program,
which is a particular instance of a general program
<a =
href=3D"http://lists.canonical.org/pipermail/kragen-hacks/2013-August/0005=
63.html">
investigated by Dijkstra.</a> (I once heard a war story about an
Atari cartridge game in which the software square roots were deemed
too expensive — but when they switched to a cheap approximation,
the pixels were so chunky that everyone appreciated the gameplay
improvement and no one noticed that regions which should have been
circular were now, at least in principle, octagonal!)
<div class=3D"input" id=3D"800">
<pre class=3D"input-e">
VAR P VAR Q VAR R
</pre><pre class=3D"input-o">
: SQRT R ! 0 P !
1 REPEAT DUP R @ <=3D IF 2* 2* AGAIN THEN Q !
REPEAT Q @ 1 <=3D NOT IF
Q @ 2/ 2/ Q !
P @ DUP 2/ P ! Q @ +=20
</pre><pre class=3D"input-e">
DUP R @ <=3D IF P @ Q @ + P !
DUP R @ SWAP - R !
THEN
DROP
AGAIN THEN
</pre><pre class=3D"input-o">
P @ ;
: TAB DUP . SQRT . CR ;
CR
8 TAB
10 TAB
</pre><pre class=3D"input-e">
2013 TAB
</pre></div>
In, fact the output is (somewhat) live; it's possible to add to the
table by playing around with the <a href=3D"#1930">fragment </a><a
href=3D"#2002">identifier</a>.
<p/>
Inspired by a recent alpine hackers' hike, a conversation with
Kragen about bootstrapping, and Eduardo Ochs' <a
href=3D"http://angg.twu.net/miniforth-article.html">Boostrapping a
Forth in 40 lines of Lua code</a>, there's actually a full (in the
Turing-complete, not in the library, sense) language behind this
calculation. (as it is no <a =
href=3D"https://github.com/darius/ichbins">IchBins</a>, one winds up
calculating in an interpreted language whose interpreter is written
in another interpreted language, a practice which gives fresh
appreciation for O(log n) algorithms!)
<hr/>
We have taken a quick and dirty approach ("Pay no attention to that
man behind the curtain") to kludging up a minimal environment in
which we can bootstrap.
<p/>
What does minimal mean? We start with two stacks (DS and RS), a
memory (M), a dictionary (_D), a way to get blank-delimited tokens
(getword), and an inner interpreter, which executes primitives and
threaded numeric code (using IP to point within the memory). Not
so minimally, we also already have an outer interpreter, capable
of either executing or compiling source tokens.
<p/>
(Exercise for the reader: add the necessary primitives so that the
outer interpreter may be defined in threaded code)
<p/>
In what follows, we alternate between defining primitives (bracketed by =
:j and j;) in javascript —the equivalent of CODE words in a real =
forth— and defining high-level threaded words in Forth (bracketed =
by ":" and ";", with two exceptions ... can you guess which words they =
are?)
<p/>
We'll start by clearing the stacks and ensuring that the memory contains =
a primitive instruction at 0 that will return us to the outer =
interpreter when the inner interpreter is finished.
<!-- cat test.h test.f | python greenbar.py -->
<div class=3D"input" id=3D"100">
<pre class=3D"input-e">
:j quit mode =3D 'outer'; j;
:j BOOT DS=3D[];RS=3D[];M=3D[lookup('quit')]; IState=3D1; mode=3D"outer"; =
j;
BOOT
</pre></div>
You are not expected to understand the next section, at least not
upon the first reading. It is somewhat quine-like because we are
creating the high-level definition for the word (:) which defines
high-level words. Once we've managed to hand-compile colon, the
word which terminates definitions (;) is easier, with just a little
roundabout because we want to compile in a reference to the word
which exits compilation mode. (We have made a slightly non-traditional
choice to use one primitive to swap between compilation and
interpretation instead of two ... but as the Sheffer stroke
demonstrates, when one is being austere, keeping
both sides of a duality is superfluous)
<div class=3D"input" id=3D"200">
<pre class=3D"input-e">
:j ' DS.push(lookup(getword())) j;
:j , M.push(DS.pop()) j;
</pre><pre class=3D"input-o">
:j DO: IP =3D DS.pop() j;
:j IMM _I[LastDef] =3D 1 j;
:j [/] IState ^=3D 1; if(mode=3D=3D"inner") { RS.pop(); mode =3D =
"outer"; } j; IMM
:j LABEL _D[LastDef=3Dgetword()]=3DM.length; j;
:j LIT DS.push(M[IP++]) j;
</pre><pre class=3D"input-e">
:j NEXT IP =3D RS.pop() j;
' DO: , LABEL : [/] LIT DO: , LABEL [/] ' [/] ,
: ; LIT NEXT , [/] ' [/] , IMM
</pre></div>
Now that we have abstraction out of the way (by defining a high-level
word we can say that to do A, we must do P and Q, as in ": A P Q
;"), we can consider what we would like to have in the way of control
flow.
<p/>
Sequencing, Alternation, and Repetition are a reasonable basis set.
We already have <b>sequencing</b>, for the inner interpreter emulates a
traditional serial CPU, fetching codes in sequence along a thread.
<p/>
To implement <b>alternation</b>, we define words which will execute at
compilation time (IMM), and which will insert forward jumps into
the threaded code. Because these jumps are forward, we compile in
a dummy value when we encounter them, save the address on a stack,
and then fix it up when we arrive at the jump target.
<p/>
Exercise: implement ELSE for true, symmetrical, alternatives.
<div class=3D"input" id=3D"300">
<pre class=3D"input-e">
:j !~ v =3D DS.pop(); M[DS.pop()] =3D v j;
:j HERE DS.push(M.length) j;
</pre><pre class=3D"input-o">
:j JZ jt=3DM[IP++]; if(DS.pop()=3D=3D0) { IP=3Djt; } j;
: REF> HERE HERE , ;
: <DEF HERE !~ ;
: IF LIT JZ , REF> ; IMM
: THEN <DEF ; IMM
</pre></div>
<b>Repetition</b> is very similar; it is somewhat easier because we know
the destination by the time we reach the jump, it is a little more
difficult because we are stacking the destinations on the return
stack instead of the data stack, so that (a la Duff) we may interlace
the two kinds of control structures.
<p/>
Question: In what way are the Data and Return stacks like a zipper,
or a tape?
<p/>
Question: Why do we need the extra set of operations (R> >R) around
our return stack manipulations?
<div class=3D"input" id=3D"400">
<pre class=3D"input-e">
:j JMP IP=3DM[IP]; j;
:j >R RS.push(DS.pop()) j;
:j R> DS.push(RS.pop()) j;
: REPEAT R> HERE >R >R ; IMM
: AGAIN LIT JMP , R> R> , >R ; IMM
</pre></div>
Now that we've blown a dozen lines to get alternation and repetition,
we might as well take 4 more to implement the Forth version of OO,
or at least of partial application. Although colon definitions are
pure code, and CREATEd definitions are pure data, in general a named
(here, LABEL'd) object can push to both the data (directly) and
return (via the instruction pointer) stacks at the same time. (We
use this mechanism to implement the VARiables in the SQRT applications)
Instead of backpatching as we did earlier for branches, we backpatch
the creation code, so all words defined by the word we are currently
compiling will (as in a unix #!) be interpreted by the colon
definition thread following the DOES>.
<p/>
=46rom a language class point of view, alternations and repetitions
suffice for regular languages, and the colon abstractions allow us
to handle context free language (the return stack is our push-down),
but by adding unrestricted state we can handle problems which map to
context sensitive and even recursive languages.
<div class=3D"input" id=3D"500">
<pre class=3D"input-o">
:j CFA DS.push(_D[LastDef]-1) j;
:j DOES: RS.pop(); DS.pop() j;
: CREATE LIT NEXT , LABEL ;
: DOES> LIT CFA , LIT LIT , REF> LIT !~ , LIT NEXT , LIT DOES: , =
<DEF ; IMM
</pre></div>
Well, we now have turing completeness, with even a lagniappe, but to
clamber out of the turing tarpit it might help to add some domain
operations.
<p/>
The necessary implementations for the application domain are also
straightforward. Note that up until this point, we have been able
to do everything purely structurally*, with neither arithmetic nor
logic outside of the primitives — we haven't even needed to
use any literal values or stack manipulation! (for convenience,
we have kept the dictionary, stacks, and operations in the javascript
domain —how well does Dijkstra's implementation hold up?—,
but everything in the core is representable in small integers, so
in principle, one could use small fixed-size representations for the
former as well.) In any case, there are well over 700 different
ways to substitute particular domain operations articulated by these
fixed naming and structuring principles, <a
href=3D"http://www.cs.cmu.edu/~crary/819-f09/Landin66.pdf">if you see
what I mean</a>, a sentiment that appears to have been shared by
<a href=3D"http://www.colorforth.com/POL.htm">Chuck Moore</a>.
<div class=3D"input" id=3D"600">
<pre class=3D"input-o">
:j + DS.push(DS.pop() + DS.pop()) j;
</pre><pre class=3D"input-e">
:j - y =3D DS.pop(); DS.push(DS.pop()-y); j;
:j 2* DS.push(2*DS.pop()) j;
:j 2/ DS.push(Math.floor(DS.pop()/2)) j;
:j <=3D y =3D DS.pop(); DS.push(DS.pop()<=3Dy); j;
:j NOT DS.push(!DS.pop()); j;
</pre><pre class=3D"input-o">
:j @ DS.push(M[DS.pop()]) j;
:j DUP DS.push(DS[DS.length-1]) j;
:j DROP DS.pop(); j;
:j SWAP y =3D DS.pop(); x =3D DS.pop(); DS.push(y); DS.push(x); j;
:j . tout('\t'+DS.pop()) j;
</pre><pre class=3D"input-e">
:j CR tout('\n'); j;
: VAR 0 CREATE , DOES> ;=20
: ! SWAP !~ ;
</div>
<b>QEF</b> ... and that's enough to compile and run the small SQRT
supra. Perlis tells us that "A program without a loop and a
structured variable isn't worth writing", and sure enough, the SQRT
has a loop, and cleverly exploits the binary structure of natural
numbers. Moreover, it appears that EWD succeeded, in that the
implementation of his program seems to run as intended on this VM
despite the underlying javascript objects having a definitely larger
and probably more complicated domain than the registers in the
implementations of his time.
<hr/>
* "the uninterpreted manipulation of fomulae"?
<hr/>
(many thanks to Darius Bacon for commentary on the original)
<!--=20
we are only trying to get the forth environment up, and don't =
particularly
care what happens to the host environment. (compare to the regard that =
an
Alien chestburster has for the crew of the Nostromo)
-->
<script type=3D"text/javascript">
function tout(s) { document.getElementById("output").innerHTML +=3D s; }
function snarfto(pat) {
subj =3D window.subj;
var i =3D subj.indexOf(pat);
if(i =3D=3D -1) { i =3D subj.length; }
var r =3D subj.slice(0,i);
subj =3D subj.slice(i+pat.length);
return r;
}
function iswhite(s,i,o) {
return (i < s.length ? (s[i]=3D=3D' ' || s[i]=3D=3D'\n' || =
s[i]=3D=3D'\t') : o);
}
function getword() {
i =3D 0;
for(;;) { if(!iswhite(subj,i++,0)) { --i; break; } }
j =3D i;
for(;;) { if(iswhite(subj,j++,1)) { --j; break; } }
var r =3D subj.slice(i,j);
subj =3D subj.slice(j);
console.log('getword: {'+r+'}');
return r;
}
DS =3D []; RS =3D []; _D =3D {}; _I =3D {}
LastDef =3D ""
lookup =3D function(w) { return (_D[w]); }
Prims =3D [];
prim =3D function(nm,code) {_D[LastDef=3Dnm]=3D-Prims.length;
Prims.push((0,eval)('(function() { '+code+' =
})')); }
prim('', 'mode=3D"stop"');
prim(':j', 'prim(getword(),snarfto("j;"))');
prim(':p', 'snarfto("p;"); LastDef=3D"--bletcherous-hack--";'); /* =
kludge IMM */
dow =3D function(w) {
if (typeof(w) =3D=3D 'number') {
if(w > 0) { RS.push(mode=3D=3D"inner"?IP:0); DS.push(w);
IP=3Dw-1; mode=3D"inner"; }
else { Prims[-w](); }
} else { console.log('???'+w); mode =3D "stop"; }
}
modes =3D {
'inner': (function(){ dow(w =3D M[IP++]); }),
'outer': (function(){
n =3D lookup(w =3D getword());
if(!isNaN(n)) {
if(IState || w in _I) { dow(n); }
else { M.push(n); }
} else if(!isNaN(n=3DparseInt(w))) {
if(IState) { DS.push(n); }
else { M.push(lookup('LIT'));
M.push(n); }
} else { console.log('???'+w); mode=3D"stop"; }
}) }
mode =3D "outer"; IState=3D1; IP =3D 0
function htmlUnescape(value){
return String(value)
.replace(/"/g, '"')
.replace(/'/g, "'")
.replace(/</g, '<')
.replace(/>/g, '>')
.replace(/&/g, '&');
}
function getsrc() {
var rss =3D [];
var nodes =3D document.getElementsByClassName("input");
for(var i =3D 0; i < nodes.length; i++) {
if(1 || nodes[i].type =3D=3D "text/x-fooscript") {
rss.push([nodes[i].id
,htmlUnescape(nodes[i].textContent)
,nodes[i].innerHTML])
}
}
rss.sort()
var hs =3D []
var rs =3D []
for(i =3D 0; i < rss.length; i++) {
rs.push(rss[i][1]);
hs.push(rss[i][2]);
}
/* document.getElementById("input").innerHTML =3D hs.join(''); */
return rs.join('\n')
}
window.subj =3D '';
function interp(s) {
mode =3D 'outer';
window.subj =3D s;
var i =3D 0;
while(mode !=3D "stop" && i < 5000) {
modes[mode]();
console.log(mode);
i++;
}
console.log(i);
}
function init() { interp(getsrc()); }
window.onload =3D init;
window.onhashchange =3D function() {
interp(window.location.hash.slice(1)+' DUP . SQRT . CR'); }
function formsubmit(e) { if(e.keyCode =3D=3D 13) {
i =3D document.getElementById('inbox');
v =3D i.value;
i.value =3D "";
interp(v); } }
</script>
</body>
</html>
--Apple-Mail-40-255684063
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
--
To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-discuss
--Apple-Mail-40-255684063--