Implement SWAP in Forth

8
votes

I saw that in an interview with Chuck Moore, he says:

The words that manipulate that stack are DUP, DROP and OVER period. There's no, well SWAP is very convenient and you want it, but it isn't a machine instruction.

So I tried to implement SWAP in terms of only DUP, DROP and OVER, but couldn't figure out how to do it, without increasing the stack at least.

How is that done, really?

3
forth
@AndréLaszlo His point is that SWAP is implemented in terms of other instructions, such as DUP, DROP, and OVER. But how do you do it, without increasing the stack? - sashoalm
@AndréLaszlo No, starting with stack '1 2', there is no way to end up with stack '2 1', using only those 3 instructions he mentions. You can use OVER to get '1 2 1', but that's not '2 1'. - sashoalm
I tried 1 2 OVER DROP . . here forthfreak.net/jsforth80x25.html Seems to work? - André Laszlo
@AndréLaszlo That way you end up with 1 2 again. The point was to swap them. - sashoalm
@AndréLaszlo It seems that's the way to do it, see the accepted answer, it never occured to me. - sashoalm

3 Answers

9
votes

You are right, it seems hard or impossible with just dup, drop, and over.

I would guess the i21 probably also has some kind return stack manipulation, so this would work:

: swap   over 2>r drop 2r> ;

Edit: On the GA144, which also doesn't have a native swap, it's implemented as:

over push over or or pop

Push and pop refer to the return stack, or is actually xor. See http://www.colorforth.com/inst.htm

6
votes

In Standard Forth it is 

: swap ( a b -- b a ) >r >r 2r> ;

or 

: swap ( a b -- b a ) 0 rot nip ;

or

: swap ( a b -- b a ) 0 rot + ;

or 

: swap ( a b -- b a ) 0 rot or ;
3
votes

This remark of Charles Moore can easily be misunderstood, because it is in the context of his Forth processors. A SWAP is not a machine instruction for a hardware Forth processor. In general in Forth some definitions are in terms of other definitions, but this ends with certain so called primitives. In a Forth processor those are implemented in hardware, but in all Forth implementations on e.g. host systems or single board computers they are implemented by a sequence of machine instruction, e.g. for Intel :

CODE SWAP pop, ax pop, bx push, ax push, bx END-CODE

He also uses the term "convenient", because SWAP is often avoidable. It is a situation where you need to handle two data items, but they are not in the order you want them. SWAP means a mental burden because you must imagine the stack content changed. One can often keep the stack straight by using an auxiliary stack to temporarily hold an item you don't need right now. Or if you need an item twice OVER is preferable. Or a word can be defined differently, with its parameters in a different order.

Going out of your way to implement SWAP in terms of 4 FORTH words instead of 4 machine instructions is clearly counterproductive, because those FORTH words each must have been implemented by a couple of machine instructions themselves.