From 45ab10cb6ebe1e4b7efc5ee6aecc3ebe24829d70 Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 18 Dec 2003 06:40:22 +0000 Subject: [PATCH] Check in patch that Reid submitted git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@10505 91177308-0d34-0410-b5e6-96231b3b80d8 --- docs/Stacker.html | 718 +++++++++++++++++++++++++--------------------- 1 file changed, 383 insertions(+), 335 deletions(-) diff --git a/docs/Stacker.html b/docs/Stacker.html index e8d68083981..df6aedfceab 100644 --- a/docs/Stacker.html +++ b/docs/Stacker.html @@ -57,7 +57,7 @@

This document is another way to learn about LLVM. Unlike the LLVM Reference Manual or -LLVM Programmer's Manual, we learn +LLVM Programmer's Manual, here we learn about LLVM through the experience of creating a simple programming language named Stacker. Stacker was invented specifically as a demonstration of LLVM. The emphasis in this document is not on describing the @@ -70,11 +70,10 @@ compiler system.

Amongst other things, LLVM is a platform for compiler writers. Because of its exceptionally clean and small IR (intermediate representation), compiler writing with LLVM is much easier than with -other system. As proof, the author of Stacker wrote the entire -compiler (language definition, lexer, parser, code generator, etc.) in -about four days! That's important to know because it shows -how quickly you can get a new -language up when using LLVM. Furthermore, this was the first +other system. As proof, I wrote the entire compiler (language definition, +lexer, parser, code generator, etc.) in about four days! +That's important to know because it shows how quickly you can get a new +language running when using LLVM. Furthermore, this was the first language the author ever created using LLVM. The learning curve is included in that four days.

The language described here, Stacker, is Forth-like. Programs @@ -136,7 +135,7 @@ expressed in stacker as: 1 + SWAP 1 + / ROT2 OR *. You could write a function using LLVM that computes this expression like this: 


 Value* 
-expression(BasicBlock*bb, Value* a, Value* b, Value* x, Value* y )
+expression(BasicBlock* bb, Value* a, Value* b, Value* x, Value* y )
 {
     Instruction* tail = bb->getTerminator();
     ConstantSInt* one = ConstantSInt::get( Type::IntTy, 1);
@@ -154,14 +153,16 @@ expression(BasicBlock*bb, Value* a, Value* b, Value* x, Value* y )
     return mult1;
 }
-

"Okay, big deal," you say. It is a big deal. Here's why. Note that I didn't +

"Okay, big deal," you say? It is a big deal. Here's why. Note that I didn't have to tell this function which kinds of Values are being passed in. They could be -Instructions, Constants, GlobalVariables, -etc. Furthermore, if you specify Values that are incorrect for this sequence of +Instructions, Constants, GlobalVariables, or +any of the other subclasses of Value that LLVM supports. +Furthermore, if you specify Values that are incorrect for this sequence of operations, LLVM will either notice right away (at compilation time) or the LLVM -Verifier will pick up the inconsistency when the compiler runs. In no case will -you make a type error that gets passed through to the generated program. -This really helps you write a compiler that always generates correct code!

+Verifier will pick up the inconsistency when the compiler runs. In either case +LLVM prevents you from making a type error that gets passed through to the +generated program. This really helps you write a compiler that +always generates correct code!

The second point is that we don't have to worry about branching, registers, stack variables, saving partial results, etc. The instructions we create are the values we use. Note that all that was created in the above @@ -235,26 +236,26 @@ BasicBlock* MyCompiler::handle_if( BasicBlock* bb, SetCondInst* condition ) { // Create the blocks to contain code in the structure of if/then/else - BasicBlock* then = new BasicBlock(); - BasicBlock* else = new BasicBlock(); - BasicBlock* exit = new BasicBlock(); + BasicBlock* then_bb = new BasicBlock(); + BasicBlock* else_bb = new BasicBlock(); + BasicBlock* exit_bb = new BasicBlock(); // Insert the branch instruction for the "if" - bb->getInstList().push_back( new BranchInst( then, else, condition ) ); + bb->getInstList().push_back( new BranchInst( then_bb, else_bb, condition ) ); // Set up the terminating instructions - then->getInstList().push_back( new BranchInst( exit ) ); - else->getInstList().push_back( new BranchInst( exit ) ); + then->getInstList().push_back( new BranchInst( exit_bb ) ); + else->getInstList().push_back( new BranchInst( exit_bb ) ); // Fill in the then part .. details excised for brevity - this->fill_in( then ); + this->fill_in( then_bb ); // Fill in the else part .. details excised for brevity - this->fill_in( else ); + this->fill_in( else_bb ); // Return a block to the caller that can be filled in with the code // that follows the if/then/else construct. - return exit; + return exit_bb; }

Presumably in the foregoing, the calls to the "fill_in" method would add @@ -264,15 +265,17 @@ terminator). Furthermore, they could even recurse back to handle_if should they encounter another if/then/else statement and it will just work.

Note how cleanly this all works out. In particular, the push_back methods on the BasicBlock's instruction list. These are lists of type -Instruction which also happen to be Values. To create +Instruction (which is also of type Value). To create the "if" branch we merely instantiate a BranchInst that takes as -arguments the blocks to branch to and the condition to branch on. The blocks -act like branch labels! This new BranchInst terminates -the BasicBlock provided as an argument. To give the caller a way -to keep inserting after calling handle_if we create an "exit" block -which is returned to the caller. Note that the "exit" block is used as the -terminator for both the "then" and the "else" blocks. This guarantees that no -matter what else "handle_if" or "fill_in" does, they end up at the "exit" block. +arguments the blocks to branch to and the condition to branch on. The +BasicBlock objects act like branch labels! This new +BranchInst terminates the BasicBlock provided +as an argument. To give the caller a way to keep inserting after calling +handle_if we create an exit_bb block which is returned +to the caller. Note that the exit_bb block is used as the +terminator for both the then_bb and the else_bb +blocks. This guarantees that no matter what else handle_if +or fill_in does, they end up at the exit_bb block.

@@ -318,8 +321,8 @@ pointer. The second index subscripts the array. If you're a "C" programmer, this will run against your grain because you'll naturally think of the global array variable and the address of its first element as the same. That tripped me up for a while until I realized that they really do differ .. by type. -Remember that LLVM is a strongly typed language itself. Everything -has a type. The "type" of the global variable is [24 x int]*. That is, its +Remember that LLVM is strongly typed. Everything has a type. +The "type" of the global variable is [24 x int]*. That is, its a pointer to an array of 24 ints. When you dereference that global variable with a single (0) index, you now have a "[24 x int]" type. Although the pointer value of the dereferenced global and the address of the zero'th element @@ -332,7 +335,7 @@ a lot of compiler writing headaches down the road.

Getting Linkage Types Right

Linkage types in LLVM can be a little confusing, especially if your compiler -writing mind has affixed very hard concepts to particular words like "weak", +writing mind has affixed firm concepts to particular words like "weak", "external", "global", "linkonce", etc. LLVM does not use the precise definitions of say ELF or GCC even though they share common terms. To be fair, the concepts are related and similar but not precisely the same. This can lead @@ -342,16 +345,19 @@ different. I recommend you read the carefully. Then, read it again.

Here are some handy tips that I discovered along the way:

@@ -423,7 +429,7 @@ the stack manipulting words that you wish define name as.

# This is a comment to end of line ( This is an enclosed comment ) -

See the example program to see how this works in +

See the example program to see comments in use in a real program.

@@ -446,9 +452,9 @@ the stack. It is assumed that the programmer knows how the stack transformation he applies will affect the program.

Words in a definition come in two flavors: built-in and programmer defined. Simply mentioning the name of a previously defined or declared -programmer-defined word causes that word's definition to be invoked. It +programmer-defined word causes that word's stack actions to be invoked. It is somewhat like a function call in other languages. The built-in -words have various effects, described below.

+words have various effects, described below.

Sometimes you need to call a word before it is defined. For this, you can use the FORWARD declaration. It looks like this:

FORWARD name ;

@@ -472,7 +478,8 @@ depending on what they do. The groups are as follows:

  • ArithmeticThese words perform arithmetic computations on their operands.
    The words are: ABS NEG + - * / MOD */ ++ -- MIN MAX
  • StackThese words manipulate the stack directly by moving - its elements around.
    The words are: DROP DUP SWAP OVER ROT DUP2 DROP2 PICK TUCK
    • + its elements around.
    The words are: DROP DROP2 NIP NIP2 DUP DUP2 + SWAP SWAP2 OVER OVER2 ROT ROT2 RROT RROT2 TUCK TUCK2 PICK SELECT ROLL
  • MemoryThese words allocate, free and manipulate memory areas outside the stack.
    The words are: MALLOC FREE GET PUT
  • ControlThese words alter the normal left to right flow @@ -500,311 +507,331 @@ using the following construction:

  • p - a pointer to a malloc'd memory block
    • -
    - - - - - - - -
    Definition Of Operation Of Built In Words
    LOGICAL OPERATIONS
    WordNameOperationDescription
    <LTw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    + + + + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - + + + - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - - + + + - - - - + + + - - - - + + + @@ -989,9 +1031,9 @@ using the following construction:

    The following fully documented program highlights many features of both the Stacker language and what is possible with LLVM. The program has two modes of operations. If you provide numeric arguments to the program, it checks to see -if those arguments are prime numbers, prints out the results. Without any +if those arguments are prime numbers and prints out the results. Without any aruments, the program prints out any prime numbers it finds between 1 and one -million (there's a log of them!). The source code comments below tell the +million (there's a lot of them!). The source code comments below tell the remainder of the story.

    @@ -1321,7 +1363,13 @@ this exercise.

    interested, here are some things that could be implemented better:

    1. Write an LLVM pass to compute the correct stack depth needed by the - program.
      2. + program. Currently the stack is set to a fixed number which means programs + with large numbers of definitions might fail. +
    2. Enhance to run on 64-bit platforms like SPARC. Right now the size of a + pointer on 64-bit machines will cause incorrect results because of the 32-bit + size of a stack element currently supported. This feature was not implemented + because LLVM needs a union type to be able to support the different sizes + correctly (portably and efficiently).
    3. Write an LLVM pass to optimize the use of the global stack. The code emitted currently is somewhat wasteful. It gets cleaned up a lot by existing passes but more could be done.
      4. @@ -1335,10 +1383,10 @@ interested, here are some things that could be implemented better:

      technique out until I was nearly done with LLVM. As it is, its a bad example of how to insert instructions!
    4. Provide for I/O to arbitrary files instead of just stdin/stdout.
      5. -
    5. Write additional built-in words.
      6. +
    6. Write additional built-in words; with inspiration from FORTH
    7. Write additional sample Stacker programs.
      8. -
    8. Add your own compiler writing experiences and tips in the - Lessons I Learned About LLVM section.
      9. +
    9. Add your own compiler writing experiences and tips in the + Lessons I Learned About LLVM section.
    -- 2.34.1
    Definition Of Operation Of Built In Words
    LOGICAL OPERATIONS
    WordNameOperationDescription
    <LTw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is less than w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back on the stack.
    >GTw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    >GTw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is greater than w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back on the stack.
    >=GEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    >=GEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is greater than or equal to w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back on the stack.
    <=LEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    <=LEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is less than or equal to w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back on the stack.
    =EQw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    =EQw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is equal to w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back
    <>NEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and +
    <>NEw1 w2 -- bTwo values (w1 and w2) are popped off the stack and compared. If w1 is equal to w2, TRUE is pushed back on the stack, otherwise FALSE is pushed back
    FALSEFALSE -- bThe boolean value FALSE (0) is pushed onto the stack.
    TRUETRUE -- bThe boolean value TRUE (-1) is pushed onto the stack.
    BITWISE OPERATIONS
    WordNameOperationDescription
    <<SHLw1 w2 -- w1<<w2Two values (w1 and w2) are popped off the stack. The w2 +
    FALSEFALSE -- bThe boolean value FALSE (0) is pushed onto the stack.
    TRUETRUE -- bThe boolean value TRUE (-1) is pushed onto the stack.
    BITWISE OPERATORS
    WordNameOperationDescription
    <<SHLw1 w2 -- w1<<w2Two values (w1 and w2) are popped off the stack. The w2 operand is shifted left by the number of bits given by the w1 operand. The result is pushed back to the stack.
    >>SHRw1 w2 -- w1>>w2Two values (w1 and w2) are popped off the stack. The w2 +
    >>SHRw1 w2 -- w1>>w2Two values (w1 and w2) are popped off the stack. The w2 operand is shifted right by the number of bits given by the w1 operand. The result is pushed back to the stack.
    ORORw1 w2 -- w2|w1Two values (w1 and w2) are popped off the stack. The values +
    ORORw1 w2 -- w2|w1Two values (w1 and w2) are popped off the stack. The values are bitwise OR'd together and pushed back on the stack. This is not a logical OR. The sequence 1 2 OR yields 3 not 1.
    ANDANDw1 w2 -- w2&w1Two values (w1 and w2) are popped off the stack. The values +
    ANDANDw1 w2 -- w2&w1Two values (w1 and w2) are popped off the stack. The values are bitwise AND'd together and pushed back on the stack. This is not a logical AND. The sequence 1 2 AND yields 0 not 1.
    XORXORw1 w2 -- w2^w1Two values (w1 and w2) are popped off the stack. The values +
    XORXORw1 w2 -- w2^w1Two values (w1 and w2) are popped off the stack. The values are bitwise exclusive OR'd together and pushed back on the stack. For example, The sequence 1 3 XOR yields 2.
    ARITHMETIC OPERATIONS
    WordNameOperationDescription
    ABSABSw -- |w|One value s popped off the stack; its absolute value is computed +
    ARITHMETIC OPERATORS
    WordNameOperationDescription
    ABSABSw -- |w|One value s popped off the stack; its absolute value is computed and then pushed onto the stack. If w1 is -1 then w2 is 1. If w1 is 1 then w2 is also 1.
    NEGNEGw -- -wOne value is popped off the stack which is negated and then +
    NEGNEGw -- -wOne value is popped off the stack which is negated and then pushed back onto the stack. If w1 is -1 then w2 is 1. If w1 is 1 then w2 is -1.
    + ADDw1 w2 -- w2+w1Two values are popped off the stack. Their sum is pushed back +
    + ADDw1 w2 -- w2+w1Two values are popped off the stack. Their sum is pushed back onto the stack
    - SUBw1 w2 -- w2-w1Two values are popped off the stack. Their difference is pushed back +
    - SUBw1 w2 -- w2-w1Two values are popped off the stack. Their difference is pushed back onto the stack
    * MULw1 w2 -- w2*w1Two values are popped off the stack. Their product is pushed back +
    * MULw1 w2 -- w2*w1Two values are popped off the stack. Their product is pushed back onto the stack
    / DIVw1 w2 -- w2/w1Two values are popped off the stack. Their quotient is pushed back +
    / DIVw1 w2 -- w2/w1Two values are popped off the stack. Their quotient is pushed back onto the stack
    MODMODw1 w2 -- w2%w1Two values are popped off the stack. Their remainder after division +
    MODMODw1 w2 -- w2%w1Two values are popped off the stack. Their remainder after division of w1 by w2 is pushed back onto the stack
    */ STAR_SLAHw1 w2 w3 -- (w3*w2)/w1Three values are popped off the stack. The product of w1 and w2 is +
    */ STAR_SLAHw1 w2 w3 -- (w3*w2)/w1Three values are popped off the stack. The product of w1 and w2 is divided by w3. The result is pushed back onto the stack.
    ++ INCRw -- w+1One value is popped off the stack. It is incremented by one and then +
    ++ INCRw -- w+1One value is popped off the stack. It is incremented by one and then pushed back onto the stack.
    -- DECRw -- w-1One value is popped off the stack. It is decremented by one and then +
    -- DECRw -- w-1One value is popped off the stack. It is decremented by one and then pushed back onto the stack.
    MINMINw1 w2 -- (w2<w1?w2:w1)Two values are popped off the stack. The larger one is pushed back +
    MINMINw1 w2 -- (w2<w1?w2:w1)Two values are popped off the stack. The larger one is pushed back onto the stack.
    MAXMAXw1 w2 -- (w2>w1?w2:w1)Two values are popped off the stack. The larger value is pushed back +
    MAXMAXw1 w2 -- (w2>w1?w2:w1)Two values are popped off the stack. The larger value is pushed back onto the stack.
    STACK MANIPULATION OPERATIONS
    WordNameOperationDescription
    DROPDROPw -- One value is popped off the stack.
    DROP2DROP2w1 w2 -- Two values are popped off the stack.
    NIPNIPw1 w2 -- w2The second value on the stack is removed from the stack. That is, +
    STACK MANIPULATION OPERATORS
    WordNameOperationDescription
    DROPDROPw -- One value is popped off the stack.
    DROP2DROP2w1 w2 -- Two values are popped off the stack.
    NIPNIPw1 w2 -- w2The second value on the stack is removed from the stack. That is, a value is popped off the stack and retained. Then a second value is popped and the retained value is pushed.
    NIP2NIP2w1 w2 w3 w4 -- w3 w4The third and fourth values on the stack are removed from it. That is, +
    NIP2NIP2w1 w2 w3 w4 -- w3 w4The third and fourth values on the stack are removed from it. That is, two values are popped and retained. Then two more values are popped and the two retained values are pushed back on.
    DUPDUPw1 -- w1 w1One value is popped off the stack. That value is then pushed onto +
    DUPDUPw1 -- w1 w1One value is popped off the stack. That value is then pushed onto the stack twice to duplicate the top stack vaue.
    DUP2DUP2w1 w2 -- w1 w2 w1 w2The top two values on the stack are duplicated. That is, two vaues +
    DUP2DUP2w1 w2 -- w1 w2 w1 w2The top two values on the stack are duplicated. That is, two vaues are popped off the stack. They are alternately pushed back on the stack twice each.
    SWAPSWAPw1 w2 -- w2 w1The top two stack items are reversed in their order. That is, two +
    SWAPSWAPw1 w2 -- w2 w1The top two stack items are reversed in their order. That is, two values are popped off the stack and pushed back onto the stack in the opposite order they were popped.
    SWAP2SWAP2w1 w2 w3 w4 -- w3 w4 w2 w1The top four stack items are swapped in pairs. That is, two values +
    SWAP2SWAP2w1 w2 w3 w4 -- w3 w4 w2 w1The top four stack items are swapped in pairs. That is, two values are popped and retained. Then, two more values are popped and retained. The values are pushed back onto the stack in the reverse order but in pairs.

    OVEROVERw1 w2-- w1 w2 w1Two values are popped from the stack. They are pushed back +
    OVEROVERw1 w2-- w1 w2 w1Two values are popped from the stack. They are pushed back onto the stack in the order w1 w2 w1. This seems to cause the top stack element to be duplicated "over" the next value.
    OVER2OVER2w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2The third and fourth values on the stack are replicated onto the +
    OVER2OVER2w1 w2 w3 w4 -- w1 w2 w3 w4 w1 w2The third and fourth values on the stack are replicated onto the top of the stack
    ROTROTw1 w2 w3 -- w2 w3 w1The top three values are rotated. That is, three value are popped +
    ROTROTw1 w2 w3 -- w2 w3 w1The top three values are rotated. That is, three value are popped off the stack. They are pushed back onto the stack in the order w1 w3 w2.
    ROT2ROT2w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2Like ROT but the rotation is done using three pairs instead of +
    ROT2ROT2w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2Like ROT but the rotation is done using three pairs instead of three singles.
    RROTRROTw1 w2 w3 -- w2 w3 w1Reverse rotation. Like ROT, but it rotates the other way around. +
    RROTRROTw1 w2 w3 -- w2 w3 w1Reverse rotation. Like ROT, but it rotates the other way around. Essentially, the third element on the stack is moved to the top of the stack.
    RROT2RROT2w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2Double reverse rotation. Like RROT but the rotation is done using +
    RROT2RROT2w1 w2 w3 w4 w5 w6 -- w3 w4 w5 w6 w1 w2Double reverse rotation. Like RROT but the rotation is done using three pairs instead of three singles. The fifth and sixth stack elements are moved to the first and second positions
    TUCKTUCKw1 w2 -- w2 w1 w2Similar to OVER except that the second operand is being +
    TUCKTUCKw1 w2 -- w2 w1 w2Similar to OVER except that the second operand is being replicated. Essentially, the first operand is being "tucked" in between two instances of the second operand. Logically, two values are popped off the stack. They are placed back on the stack in the order w2 w1 w2.
    TUCK2TUCK2w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4Like TUCK but a pair of elements is tucked over two pairs. +
    TUCK2TUCK2w1 w2 w3 w4 -- w3 w4 w1 w2 w3 w4Like TUCK but a pair of elements is tucked over two pairs. That is, the top two elements of the stack are duplicated and inserted into the stack at the fifth and positions.
    PICKPICKx0 ... Xn n -- x0 ... Xn x0The top of the stack is used as an index into the remainder of +
    PICKPICKx0 ... Xn n -- x0 ... Xn x0The top of the stack is used as an index into the remainder of the stack. The element at the nth position replaces the index (top of stack). This is useful for cycling through a set of values. Note that indexing is zero based. So, if n=0 then you get the second item on the stack. If n=1 you get the third, etc. Note also that the index is replaced by the n'th value.
    SELECTSELECTm n X0..Xm Xm+1 .. Xn -- XmThis is like PICK but the list is removed and you need to specify +
    SELECTSELECTm n X0..Xm Xm+1 .. Xn -- XmThis is like PICK but the list is removed and you need to specify both the index and the size of the list. Careful with this one, the wrong value for n can blow away a huge amount of the stack.
    ROLLROLLx0 x1 .. xn n -- x1 .. xn x0Not Implemented. This one has been left as an exercise to +
    ROLLROLLx0 x1 .. xn n -- x1 .. xn x0Not Implemented. This one has been left as an exercise to the student. See Exercise. ROLL requires a value, "n", to be on the top of the stack. This value specifies how far into the stack to "roll". The n'th value is moved (not @@ -814,20 +841,25 @@ using the following construction:

    how much to rotate. That is, ROLL with n=1 is the same as ROT and ROLL with n=2 is the same as ROT2.
    MEMORY OPERATIONS
    WordNameOperationDescription
    MALLOCMALLOCw1 -- pOne value is popped off the stack. The value is used as the size +
    MEMORY OPERATORS
    WordNameOperationDescription
    MALLOCMALLOCw1 -- pOne value is popped off the stack. The value is used as the size of a memory block to allocate. The size is in bytes, not words. The memory allocation is completed and the address of the memory block is pushed onto the stack.
    FREEFREEp -- One pointer value is popped off the stack. The value should be +
    FREEFREEp -- One pointer value is popped off the stack. The value should be the address of a memory block created by the MALLOC operation. The associated memory block is freed. Nothing is pushed back on the stack. Many bugs can be created by attempting to FREE something @@ -839,20 +871,20 @@ using the following construction:

    the stack (for the FREE at the end) and that every use of the pointer is preceded by a DUP to retain the copy for FREE.
    GETGETw1 p -- w2 pAn integer index and a pointer to a memory block are popped of +
    GETGETw1 p -- w2 pAn integer index and a pointer to a memory block are popped of the block. The index is used to index one byte from the memory block. That byte value is retained, the pointer is pushed again and the retained value is pushed. Note that the pointer value s essentially retained in its position so this doesn't count as a "use ptr" in the FREE idiom.
    PUTPUTw1 w2 p -- p An integer value is popped of the stack. This is the value to +
    PUTPUTw1 w2 p -- p An integer value is popped of the stack. This is the value to be put into a memory block. Another integer value is popped of the stack. This is the indexed byte in the memory block. A pointer to the memory block is popped off the stack. The @@ -862,28 +894,33 @@ using the following construction:

    pushed back on the stack so this doesn't count as a "use ptr" in the FREE idiom.
    CONTROL FLOW OPERATIONS
    WordNameOperationDescription
    RETURNRETURN -- The currently executing definition returns immediately to its caller. +
    CONTROL FLOW OPERATORS
    WordNameOperationDescription
    RETURNRETURN -- The currently executing definition returns immediately to its caller. Note that there is an implicit RETURN at the end of each definition, logically located at the semi-colon. The sequence RETURN ; is valid but redundant.
    EXITEXITw1 -- A return value for the program is popped off the stack. The program is +
    EXITEXITw1 -- A return value for the program is popped off the stack. The program is then immediately terminated. This is normally an abnormal exit from the program. For a normal exit (when MAIN finishes), the exit code will always be zero in accordance with UNIX conventions.
    RECURSERECURSE -- The currently executed definition is called again. This operation is +
    RECURSERECURSE -- The currently executed definition is called again. This operation is needed since the definition of a word doesn't exist until the semi colon is reacher. Attempting something like:
    : recurser recurser ;
    will yield and error saying that @@ -891,24 +928,24 @@ using the following construction:

    to:
    : recurser RECURSE ;
    IF (words...) ENDIFIF (words...) ENDIFb -- A boolean value is popped of the stack. If it is non-zero then the "words..." +
    IF (words...) ENDIFIF (words...) ENDIFb -- A boolean value is popped of the stack. If it is non-zero then the "words..." are executed. Otherwise, execution continues immediately following the ENDIF.
    IF (words...) ELSE (words...) ENDIFIF (words...) ELSE (words...) ENDIFb -- A boolean value is popped of the stack. If it is non-zero then the "words..." +
    IF (words...) ELSE (words...) ENDIFIF (words...) ELSE (words...) ENDIFb -- A boolean value is popped of the stack. If it is non-zero then the "words..." between IF and ELSE are executed. Otherwise the words between ELSE and ENDIF are executed. In either case, after the (words....) have executed, execution continues immediately following the ENDIF.
    WHILE (words...) ENDWHILE (words...) ENDb -- b The boolean value on the top of the stack is examined. If it is non-zero then the +
    WHILE (words...) ENDWHILE (words...) ENDb -- b The boolean value on the top of the stack is examined. If it is non-zero then the "words..." between WHILE and END are executed. Execution then begins again at the WHILE where another boolean is popped off the stack. To prevent this operation from eating up the entire stack, you should push onto the stack (just before the END) a boolean value that indicates @@ -924,60 +961,65 @@ using the following construction:

    the top of stack is decremented to 0 at which the WHILE test fails and control is transfered to the word after the END.
    INPUT & OUTPUT OPERATIONS
    WordNameOperationDescription
    SPACESPACE -- A space character is put out. There is no stack effect.
    TABTAB -- A tab character is put out. There is no stack effect.
    CRCR -- A carriage return character is put out. There is no stack effect.
    >sOUT_STR -- A string pointer is popped from the stack. It is put out.
    >dOUT_STR -- A value is popped from the stack. It is put out as a decimal integer.
    >cOUT_CHR -- A value is popped from the stack. It is put out as an ASCII character.
    <sIN_STR -- s A string is read from the input via the scanf(3) format string " %as". The +
    INPUT & OUTPUT OPERATORS
    WordNameOperationDescription
    SPACESPACE -- A space character is put out. There is no stack effect.
    TABTAB -- A tab character is put out. There is no stack effect.
    CRCR -- A carriage return character is put out. There is no stack effect.
    >sOUT_STR -- A string pointer is popped from the stack. It is put out.
    >dOUT_STR -- A value is popped from the stack. It is put out as a decimal integer.
    >cOUT_CHR -- A value is popped from the stack. It is put out as an ASCII character.
    <sIN_STR -- s A string is read from the input via the scanf(3) format string " %as". The resulting string is pushed onto the stack.
    <dIN_STR -- w An integer is read from the input via the scanf(3) format string " %d". The +
    <dIN_STR -- w An integer is read from the input via the scanf(3) format string " %d". The resulting value is pushed onto the stack
    <cIN_CHR -- w A single character is read from the input via the scanf(3) format string +
    <cIN_CHR -- w A single character is read from the input via the scanf(3) format string " %c". The value is converted to an integer and pushed onto the stack.
    DUMPDUMP -- The stack contents are dumped to standard output. This is useful for +
    DUMPDUMP -- The stack contents are dumped to standard output. This is useful for debugging your definitions. Put DUMP at the beginning and end of a definition to see instantly the net effect of the definition.