mikpa@massormetrix.ida.liu.se (Mikael Patel) (08/11/89)
Hi, Forth Lovers, how about a distributed problem solving session?
The quest is to find `the minimal Forth Machine'. What is the minimal set
of operations such a machine must implement?
I have started to attach this problem. My first group of operations to
study is the arithmetric operations, thus the sub-problem is; What is
the minimal set of operation to realize + - * /mod mod /?
Sofar I need:
not xor
0> 0< 0=
1+ 1-
dup swap rot drop
>r r>
if else then
tail-recurse ( compiles a branch to the beginning of the definition)
This list can be minimized further by defining control structure,
stack, logical, and memory operations.
The goal is to design this minimal machine and the definitions need
so that any teacher out there can take a net-list description of the
machine and a memory specification (in for instance EDIF) and hand it
over to students in a computer architecture/digital design classes.
"Forth for the Masses" -- Mikael Patel
----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
( Arithmetric operations with a small set of primitives, Mikael Patel, 1989)
( Requires: not xor 0> 0< 0= 1+ 1- dup swap rot drop >r r> if else then)
( Implements: 0 1 negate abs + - * /mod / mod)
0 constant 0 ( A bit crazy but...)
1 constant 1 ( ...you an't seen nothing yet)
: negate ( x -- y)
not 1+ ; ( Invert and increment)
: abs ( x -- y)
dup 0< if negate then ; ( Absolute value)
: + ( x y -- z)
dup 0= ( Check if there is still more to do)
if drop ( Return result)
else
dup 0> ( Check direction)
if 1- swap 1+ swap ( Decrement and increment)
else
1+ swap 1- swap ( Increment and decrement)
then
tail-recurse ( And go again)
then ;
: - ( x y -- z)
negate + ; ( Negate and add)
: (*) ( a x y -- z)
dup 0> ( Check if there is still more to do)
if 1- ( Decrement counter)
swap rot over + swap rot ( Add to result and put back in order )
tail-recurse ( And go again)
else
drop drop ( Drop temporary parameters)
then ;
: sign ( x y -- s)
0> swap 0> xor ; ( Return sign of arithmetric operation)
: * ( x y -- z)
dup 0= ( Check for zero)
if swap drop ( Drop parameter and return zero)
else
over over sign >r ( Save the sign of the result)
0 rot abs rot abs (*) ( Do it the hard way)
r> if negate then ( Check if negative then negate)
then ;
: (/mod) ( q r y -- r q)
swap over - dup 0< not ( Generate next reminder and check)
if swap ( Put reminer back into place)
rot 1+ rot rot ( Increment quotient)
tail-recurse ( And go again)
else
+ swap ( Restore and return result)
then ;
: /mod ( x y -- r q)
dup 0= ( Check if divide by zero)
if drop drop 0 0 ( Return zero)
else
over >r ( Save sign of divident)
over over sign >r ( Save sign of result)
0 rot abs rot abs (/mod) ( Setup initial quotient)
r> if negate then ( Check sign of quotient)
r> if swap negate swap then ( Check sign of reminder)
then ;
: / ( x y -- q)
/mod swap drop ; ( Do it and drop reminder)
: mod ( x y -- r)
/mod drop ; ( Do it and drop quotient)stevens@vms.macc.wisc.edu (PAul STevens -- MACC) (08/11/89)
In article <1330@massormetrix.ida.liu.se>, mikpa@massormetrix.ida.liu.se (Mikael Patel) writes... >Hi, Forth Lovers, how about a distributed problem solving session? > >The quest is to find `the minimal Forth Machine'. What is the minimal set >of operations such a machine must implement? > >I have started to attach this problem. My first group of operations to >study is the arithmetric operations, thus the sub-problem is; What is >the minimal set of operation to realize + - * /mod mod /? > >Sofar I need: > not xor > 0> 0< 0= > 1+ 1- > dup swap rot drop > >r r> > if else then > tail-recurse ( compiles a branch to the beginning of the definition) > I don't think you really want a minimal machine. I bet it would amount to no more than 4 words, including IF and THEN. One of the words might be -!, which subtracts a memory location from the top of the stack and puts the result both on the top of the stack and back in the memory location. -! ( 16b addr .. 16b-(addr)) (addr) = 16b-(addr) Let's try one: variable JUNKA ( scratch area for several words ) variable JUNKB ( scratch area ) : DROP ( 16b .. ) JUNKA -! JUNKA -! ( clear junka and stack entry ) JUNKB JUNKA -! ( junka and tos both = address of junkb ) -! JUNKB -! ( clear tos and junkb ) JUNKA -! ( junka=-junkb ) JUNKB -! JUNKB -! ( clear junkb and tos ) JUNKA -! -! ; ( subtract 0 from second entry on stack) ( leaves it unchanged and drops entry ) Could get inefficient! For example, you certainly don't need ROT in your example: : ROT >R SWAP R> SWAP ; In the limit you wind up with something about as efficient as a Turing machine. But very complete.
sdh@wind.bellcore.com (Stephen D Hawley) (08/12/89)
In article <2241@dogie.macc.wisc.edu> stevens@vms.macc.wisc.edu (PAul STevens -- MACC) writes: >In article <1330@massormetrix.ida.liu.se>, mikpa@massormetrix.ida.liu.se (Mikael Patel) writes... >In the limit you wind up with something about as efficient as a Turing >machine. But very complete. I think perhaps you missed the point. The original article mentioned that this would be for student use to implement. Efficiency is not really the question, but educational value. For example, I took an architecture class 2 semesters ago that covered the advantages of RISC machines as part of the curriculum. We were presented the a machine called the Machester Mark I (which was a real machine --the prof. gave us a program that simulated it). It had the following instruction set: BRA addr -branch unconditional to addr BRL disp -branch uncond with disp as a displacement LNG addr -load the negation of the contents of addr STA addr -store into addr SUB addr -subtract the contents of addr SKN -if negative, skip next instruction HLT -halt 7 instructions. That's all. The prof had a contest to write the most compact factorial. Mine came in 3rd (3 bytes longer than the winner). I also wrote an optimizing assembler for the machine. Below is my entry, for your amusement and perusal. This coming semester, I will be implementing a compiler for a FORTH-like language. Unlike most FORTH's, it will be suited to an environment which doesn't take kindly to you poking around at the address space, FORGET will not be so unforgiving (ie, only the function you want to forget will go away, not everything defined afterwards), and much more planned. Why? Purely for educational reasons. Oh dear. I seem to have gone off the deep end here. * factorial program for the MM I * Steve Hawley * has to be assembled at location 1!! * uses the fact that the data for "zero" is really just a branch to 1 * manchasm -a 1 ... ... fact lng n skn hlt sta 501 lng zero sta 500 bra ment mult lng 500 sub r sta 500 lng 500 sta 500 lng 501 sta 501 ment lng 501 sub one sta 501 skn bra mult lng 500 sta r lng r sta r lng n sta n lng n sub one sta n * data section. dat is a pseudo op zero dat 0 * this is actually a branch to location 1!! one dat 1 n dat 4 r dat 1 Steve Hawley sdh@flash.bellcore.com "Up is where you hang your hat." --Jim Blandy, computer scientist
tp@tut.fi (Lassila Timo-Pekka) (08/16/89)
In article <1330@massormetrix.ida.liu.se> mikpa@massormetrix.ida.liu.se (Mikael Patel) writes: > ( Arithmetric operations with a small set of primitives, Mikael Patel, 1989) > ( Requires: not xor 0> 0< 0= 1+ 1- dup swap rot drop >r r> if else then) ^^ ^^ ^^^ > ( Implements: 0 1 negate abs + - * /mod / mod) How about ... : >0 dup <0 if drop 0 else =0 if 0 else 1 then then ; : 1- not 1+ not ; : rot >r swap r> swap ; > : (*) ( a x y -- z) > dup 0> ( Check if there is still more to do) > if 1- ( Decrement counter) > swap rot over + swap rot ( Add to result and put back in order ) ^^^^ And you forgot this. : over >r dup r> swap ; -- Timo-Pekka Lassila # Tampere University of Technology # /Signal Processing Laboratory tp@tut.fi # PO Box 527, SF-33101 Tampere, Finland mcvax!tut!tp #
gamber@cosmo.UUCP (Johannes Teich) (09/10/89)
In a message of <11 Aug 89>, Mikael Patel (mikpa@massormetrix.ida.liu.se) writes: > Hi, Forth Lovers, how about a distributed problem solving session? > > The quest is to find `the minimal Forth Machine'. What is the minimal > set of operations such a machine must implement? Five days later, Mikael Patel writes: > After some discussions and help of Mitch Bradley (wmb@Sun.COM) and Peter > da Silva (peter@ficc.uu.net) the Minimal Forth Machine is down to nine > instructions. Three stack instructions may be added when considering > hardware structures as they are implict in the basic set. > > With this tiny set of instructions a Forth environment can be built; > may it be virtual on an other processor or directly in hardware. Hi Mikael, I am sad that I don't fully understand your concept of the Machine. Perhaps you could give some hints? > Some interesting observation are: > > 1. The machine does not have a branch instruction. How can _any_ machine work without a branch instruction? > 2. The machine has only three basic functions. Which functions do you mean? And which are the nine instructions mentioned? I find: "fetch", "drop", "dup", "swap", ">r", "r>", "unary", "1+", "0=", "binary", "nand", "@", "c@", "dup!", "dupc!", "call", "exit". Or do you mean: "ip -> b0,", "b0 -> ma,", "md -> b1,", and so on? > 3. All instructions can be realized so that they only take one > clock cycle. Even memory access! Hmmm... D other difficult stuff skipped \ > Below follows a description of the Machine in a toy hardware language > and Forth definitions for: > > 1. Stack manipulation > 2. Logical operations > 3. Arithmetric operations > 4. Control structures > 5. Some system dependent words > > ( Parameter stack) > 16 bits/word stack rt ( Return stack) > > wr bits/word port ma ( Port for address to memory) > rd/wr bits/word port md ( Port for data to and from memory) Is it possible that there got some text lost? > ( A simple register transfer language) > > fetch ( -- ) > ip -> b0, ( Fetch next instruction) > b0 -> ma, > md -> b1, > b1 -> ir ( Put into decode register) > * ( Execute instruction) > ip + 1 -> ip ( And incremenent instruction pointer) I have some imagination what steps a hardware must execute, but I cannot interpret your instructions. (If ip -> b0, and b0 -> ma, then ma = ip, isn't it?) Do you have a special processor in mind? How is its scheme? D stuff skipped \ > : + ( x y -- z) > begin > dup ( Check if there is still more to do) > while > dup 0< ( Check direction) > if 1+ swap 1- swap ( Decrement and increment) > else > 1- swap 1+ swap ( Increment and decrement) > then > repeat > drop ; ( Drop counter) At least these high-level things are clear. Although ... how about "if", "then", "else", "begin", "while", "repeat", ... ? Where are they defined at compile time? Do you assume a meta compiler? > : sqrt ( x -- x**1/2) > 1 11 0 do ( Newton's method-type algorithm) > over over / + 2/ ( Guess one and divide successive) > loop ( values) > swap drop ; ( Drop temporary value and return) num: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 23 24 25 34 35 36 48 49 sqrt: 1 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 5 5 5 6 6 6 7 ^ ^ ^ I tried to run the definitions on my PC. I replaced "begin" by "BEGIN" and ">r" by ">R" and "immediate" by "IMMEDIATE" and so on with my PC/Forth, but I'm still not quite happy. How did you check your routines? > : repeat ( -- ) > swap ( Access block start) > compile (branch) ( Compile a backward branch) > <resolve anch) ( flag -- ) > 0= dup r@ @ and ( Fetch branch address and mask) > swap not r> word+ and or >r ; ( Create skip address and select) There evidently some text got lost! :-( If you are willing to give some more information about your very interesting project, I would be glad to study it. Even without your hardware simulation I find it useful to implement a minimal instruction set on a new computer and blow the system up with this tool afterwards. cheers - Johannes +-----------------------------------------------------------------------------+ v Johannes Teich, Hauptmann-Bauer-Weg 16, D-8110 Murnau (FR Germany) v v Phone: 49-8841-1409 (FRG: 08841-1409) v FidoNet: TBUS-BBS 2:507/414.20 v v UUCP via CosmoNet: unido!cosmo!gamber v Zerberus: j*teich@infinet.zer v v Telex via CosmoNet-UK (051) 9312102426 cn g -- 1st_line: "to: cosmo:gamber" v +-----------------------------------------------------------------------------+