`2/` is more fundamental than `0=`

[mitchblank]

First, consider the question whether we could remove 0= from the assembly and implement it in forth code instead, just using functionality built on top of + and nand.

I'm pretty sure the answer to that question is "no". The root of the problem is that there isn't any way to propagate bits rightward. (2* is trivially implementable with +, but there is no equivalent way of implementing 2/)

To see why this is a problem, start with the observation that we're trying to implement (x == 0) ? 0xFFFF : 0. Relax this to a more general problem where you want (x == 0) ? A : B where A and B differ in the least significant bit. If we can't implement that, then A=0xFFFF and B=0x0 is just one example of a function we can't implement.

If instead we wanted to make the top bit differ depending on if x is zero that would be quite easy: x | (x + 0x7FFF). However, since nand doesn't do any any bit-position-to-position rollover, and + only rolls over leftwards, there would be no way to "push" that bit to the least-significant position. We can't construct an 0= oracle without some further functionality.

Basically it's possible to implement the (x == 0) ? A : B but only in the case that A and B are either both even or both odd. For example, you can do A=0x7FFF and B=0xFFFF with x | (x + 0x7FFF) | 0x7FFF. If you tack on a + 1 you get A=0x8000 B=0. However no matter what +/nand operations you do A and B won't differ in the lowest bit.

Now, presume that the assembly core did provide a shift-right (2/) operation. Now it would be possible to implement 0=.

In C it would look like:

static uint16_t div4(uint16_t x)
{
    return div2(div2(x));
}

static uint16_t div16(uint16_t x)
{
    return div4(div4(x));
}

static uint16_t div256(uint16_t x)
{
    return div16(div16(x));
}

static uint16_t smear_right(uint16_t x)
{
    x |= div256(x);
    x |= div16(x);
    x |= div4(x);
    x |= div2(x);
    return x;
}

// returns (x == 0) ? 0 : 1
static uint16_t one_if_ne0(uint16_t x)
{
    return smear_right(x) & 1;
}

// returns (x == 0) ? 0xFFFF : 0
static uint16_t eq0(uint16_t x)
{
    return one_if_ne0(x) - 1;
}

or translated into Forth:

: 4/ 2/ 2/ ;
: 16/ 4/ 4/ ;
: 256/ 16/ 16/ ;
: 0=
     dup 256/ or
     dup 16/ or
     dup 4/ or
     dup 2/ or
     1 and
     1 -
;

Why does this matter:

1. Implementing 2/ instead of 0= in assembly probably saves an instruction, since it's just a shift-right. No condition-code magic needed
2. 2/ is the more powerful operation. It is true that you could implement 2/ using 0= (by testing the top 15 bits individually, i.e. ((x & 0x8000) ? 0x4000 : 0) + ((x & 0x4000 ? 0x2000 : 0) + ... but it's a lot more arduous!

Therefore it would be better for the assembly core to provide 2/ instead of 0=

Another possibility would be for the assembly to provide "rotate right" which is equally general. Then it would look like:

: ror2 ror ror ;
: ror4 ror2 ror2 ;
: ror8 ror4 ror4 ;
: 0=
   dup ror8 or
   dup ror4 or
   dup ror2 or
   dup ror or
   1 and
   1 -
;

[fuzzballcat]

While I agree with your points presented, and would gladly make this change given that it would indeed reduce the size to convert a conditional to a simple rshift, I am currently conducting my own investigation into whether you actually need three arithmetic primitives at all (rather than perhaps two). If that fails to yield results, I will definitely implement this.

[mitchblank]

Technically a rotate and nand are probably sufficient, since:

• If you have one rotate you can implement the other (i.e. if you have rol then you can implement ror by doing 15 rol calls)
• a one-bit a + b can be implemented as ((a & b) << 1) | (a ^ b) i.e. with the boolean operators and left-shift you can add two one-bit values into a two-bit result.
• with some effort you can then build up a full adder circuit from that

However I think it's pretty ugly. Also given that even the definition of 1 requires + you might end up in a chicken&egg situation anyway

[fuzzballcat]

Right, I suppose I should say "I'm looking into whether you can have just two arithmetic primitives without needing to actually manually implement a logic circuit" (as otherwise you could just get away with bit-by-bit NAND, and that's no fun).

[fuzzballcat]

The root of the problem is that there isn't any way to propagate bits rightward

Actually, I realized that this isn't true! Consider: All numbers are 2 bytes long. We can use ! to index into any byte. So you can swap the two bytes which comprise a given number, thereby moving the byte on the left one byte rightward. Of course, this is a bit hacky/unsavoury since it relies on the numeric word length, and it doesn't allow arbitrary byte movement...

EDIT: Hah, someone's beat me to it! https://github.com/cesarblum/sectorforth/issues/8. Well, I'm not satisfied with this solution, given that it relies on the fact that a number isn't just one byte long (feels too machine-level-hacky for me).

[mitchblank]

Oh wow, that is an clever/evil trick. I stand corrected.

[thamesynne]

It might be worth taking a tip from eForth (the original minimal Forth) here. Instead of +, its base addition operator is um+, which pushes carry to the stack too:

CODE UM+ ( u u -- u cy )
  bx pop  ax pop  bx ax add
  D# 0 ## bx mov  bx bx adc
  ax push  bx push  next,
END-CODE

This could be simplified a bit:

umplus: pop bx
        pop ax
        xor bx,bx
        add ax,bx
        adc bx.bx
        push ax
        push bx
        jmp NEXT

but it pushes up the size by 5 bytes. However, it might be worth that to be able to inherit the entire eForth aritmetic stack.

ed. never mind:

: um+ over + dup rot u< ;