I will go back to GEOS stuff soon, but last week I was occupied by a question: can you write and run any program using VASYL instruction set? Can I have a shader that will process bitmap for PBS?
In other words - is VASYL's instruction set Turing complete?
After a week I already know the answer: big fat YES and I have a proof for this: https://github.com/ytmytm/c64-beamracer-subleq
SUBLEQ is an esoteric (meaning: real, working, just not very practical) computer architecture that has only one instruction: SUBLEQ.
The only possible instruction for such CPU is "SUBtract and branch if Less-than or EQual to zero".
It turns out that this is all you need for general-purpose computing and it was proven that SUBLEQ is Turing complete. In fact, there are even more of these One-Instruction Set Computer architectures.
SUBLEQ seemed feasible for me to try with VASYL: we only have DECA/B and BRA for arithmetic and conditional jumps, but having two independent memory ports with configurable step after every read/write was very promising. Especially since the step can go both ways - positive and negative.
The Display List Virtual Machine goes through SUBLEQ instruction - four word-sized pointers and updates itself using both memory ports:
Arithmetic was a bit tricky. We need to know the result of b-a when we have a and b. So we use one lookup table to transform value a into -a and then second lookup table to find the result of 0+b+(-a).
Much bigger obstacle was the program counter implementation. First I wanted to use PORT0 exclusively for that, but it's not possible - there is no temporary register and I need both memory ports for lookups (read from PORT0, write into PORT1).
But how to preserve PORT0? We can't - there is no way to read anything from the registers. We can only read from memory.
The solution was to extend SUBLEQ programs to be fully linked with explicit addresses of targets for jump when result is negative or zero and also for the positive branch. Any examples for SUBLEQ that you can find in the Internet will have the positive jump pointing implicitly to the next instruction.
The VASYL SUBLEQ VM can process about 214 SUBLEQ instructions per frame, so the virtual SUBLEQ CPU runs at about 10.7kHz.
Almost whole bank 0 is available for program and data - about 62.5KB.
I'm not an experienced SUBLEQ programmer and all I have right now is a debug program that does simple calculations and modifies a value stored into $d020 while the VM is running.
To conclude: yes, I have proven that VASYL ISA is Turing complete and you can port any program to it, at least indirectly through SUBLEQ.
This just opens the gate for flood of software running natively on VASYL: quasi-assembly language, Forth, shaders and even BrainFuck
Thank you guys for VBASIC, without VLIST and VPEEK it would be very hard to debug this.
In other words - is VASYL's instruction set Turing complete?
After a week I already know the answer: big fat YES and I have a proof for this: https://github.com/ytmytm/c64-beamracer-subleq
SUBLEQ is an esoteric (meaning: real, working, just not very practical) computer architecture that has only one instruction: SUBLEQ.
The only possible instruction for such CPU is "SUBtract and branch if Less-than or EQual to zero".
Code:
Mem[b] = Mem[b]-Mem[a]
if (Mem[b]<=0) then goto cIt turns out that this is all you need for general-purpose computing and it was proven that SUBLEQ is Turing complete. In fact, there are even more of these One-Instruction Set Computer architectures.
SUBLEQ seemed feasible for me to try with VASYL: we only have DECA/B and BRA for arithmetic and conditional jumps, but having two independent memory ports with configurable step after every read/write was very promising. Especially since the step can go both ways - positive and negative.
The Display List Virtual Machine goes through SUBLEQ instruction - four word-sized pointers and updates itself using both memory ports:
- to setup loads into VREG_ADR0/1 when data is read/written or when we need to set starting point of a lookup table
- to setup loads into VREG_STEP0/1 when we traverse lookup table to add numbers, negate them or read the sign
- to load into VREG_ADR0 the address of the next instruction
Arithmetic was a bit tricky. We need to know the result of b-a when we have a and b. So we use one lookup table to transform value a into -a and then second lookup table to find the result of 0+b+(-a).
Much bigger obstacle was the program counter implementation. First I wanted to use PORT0 exclusively for that, but it's not possible - there is no temporary register and I need both memory ports for lookups (read from PORT0, write into PORT1).
But how to preserve PORT0? We can't - there is no way to read anything from the registers. We can only read from memory.
The solution was to extend SUBLEQ programs to be fully linked with explicit addresses of targets for jump when result is negative or zero and also for the positive branch. Any examples for SUBLEQ that you can find in the Internet will have the positive jump pointing implicitly to the next instruction.
The VASYL SUBLEQ VM can process about 214 SUBLEQ instructions per frame, so the virtual SUBLEQ CPU runs at about 10.7kHz.
Almost whole bank 0 is available for program and data - about 62.5KB.
I'm not an experienced SUBLEQ programmer and all I have right now is a debug program that does simple calculations and modifies a value stored into $d020 while the VM is running.
To conclude: yes, I have proven that VASYL ISA is Turing complete and you can port any program to it, at least indirectly through SUBLEQ.
This just opens the gate for flood of software running natively on VASYL: quasi-assembly language, Forth, shaders and even BrainFuck
Thank you guys for VBASIC, without VLIST and VPEEK it would be very hard to debug this.
) and some other minor tweaks.
