Rebec is a programming language I've been working on that compiles to a single-instruction virtual machine.

This has been a long-term project I started awhile ago and have been working on it on and off for awhile now.

The great thing about the virtual machine is that it is so simple, it is very easy to port to any platform. So I ported it to the TI-84+. I plan to make it support the TI-84+CSE and TI-84+CE as well. This means all code written in Rebec can run on the TI-84+.

I plan to eventually build this virtual machine into a physical CPU. What the virtual machine does is simulate the imaginary CPU, and any time a write is made to the output pins of the virtual CPU, it displays the lower 8 bits as an ASCII character on the screen, and every time a read is made from the input pins, it pauses and lets the user type in what they want the values of the input pins to be at that time (in ASCII characters). So with the virtual machine you can use that to read and write characters to the screen, which can be used for interactive programs.

All of this will be on this Github. The project R313 is the assembler and virtual machine for PC. The project Z313 is the virtual machine for the TI-83+/TI-84+ calculators. The project Rebec is the compiler for the Rebec programming language. The project PI313 is a virtual machine for the Raspberry Pi that connects the virtual CPU's output and input pins to the physical CPU of the Raspberry Pi, allowing you to control external hardware with Rebec code.

To give you an example of this programming language, here's a simple "Hello, World!" program:




Code:


To get on the calculator, you first need to compile it, then assemble it, then convert it to an AppVar, then transfer it to the calculator. These are the commands to do so:


Code:


"rebec" is the programming language's compiler, "rasm" is the assembler for R313 assembly (the name I gave to the virtual machine's architecture), and "gen8xv" generates an appvar from a binary file.

You transfer this to your calc then you will have a program on your calc called "HELLO" and you can run it with:


Code:


The basics of Rebec

Rebec is the programming language that makes this a hell of a lot easier for the layman to program this virtual machine. The language is a wee bit ugly, I've never made a real programming language before and it's all coded in C. But it works. It compiles down to R313 assembly.

Semicolons are for comments. Rebec has "commands", and each command is 3 letters.

There are three different types of commands:

1. Definitions (def).
2. Functions/labels (fct/lbl).
3. Logic (anything else...).

Definitions are sort of like your variables. All variables are global. It's highly recommended to define all the data you need at the top of any function you create. Don't be afraid to use a lot of definitions if you have to. There's no speed penalty for defining a lot of things. (You are limited to 65k words of RAM though.)

Functions/labels can either be called or jumped to. "fct" and "lbl" both are identical keywords standing for "function" and "label". They literally do the exact same things and are interchangeable. But for neatness, I recommend using these differently.

You call functions but you jump to labels. Use labels while within a function to make it easier to understand where your function begins and where it ends.

Example:


Code:



Rebec implements a stack in R313 assembly for you, so you can call and return from subroutines. I wouldn't recommend using recursion, though, because the stack is rather small.

The final type of command, the logic commands, are everything else.
These take a number of arguments and do something.

Here's some examples:


Code:


Understanding these main commands you can see how the "Hello, World!" program works.

Notice that the only mathematical operation Rebec has is addition and subtraction. There are no bitwise operations nor are there multiplication, division, modulo, etc. Why? Because the virtual machine only has one instruction, thus one math operation (add/subtract). Anything like multiplation or bitwise operations would require a lot of code to write, so I leave that up to the programmer to import a library or something (currently I don't have an "#include" command but I will add one eventually). I am working on a library for bitwise stuff which you could then create multiplication/division/modulo out of.

The "Hello, World" code compiles down to R313, here is the assembly code that the program generates:


Code:


As you can tell, coding the "Hello, World!" program in R313 assembly would be rather tedious. That's why I created Rebec.

Here's Rebec code that asks the user "what's your name?" and waits for input, then spits out "Hello, [name]!" It only accepts up to 3 letters for the name.


Code:


Notice here I use "jnn". That's because it's a little more efficient than "jpe" or "jne".

Here's it running on the calculator:



Here's some PI313 code I wrote in Rebec to draw a smiley face to an 8x8 LED matrix display (the display is connected to a Raspberry Pi):




Code:


As you can see, Rebec can be used to drive hardware. You can see some of my bitwise functions I've been working on here. bin2word and word2bin can convert between binary strings and words (remember, words in this virtual CPU are signed 16-bit numbers).

Eventually I want to build the CPU on an FPGA in Verilog and make the CPU open source as well, but I'm still learning so that will take some time.

Understanding the Virtual Machine from Machine Code

If you're not satisfied just coding in Rebec and love machine code and assembly, I'll try to explain how the virtual machine actually works. It is purposefully designed to be incredible simple in its function, but that makes it incredibly complex when it comes to coding for it. Its simplicity makes porting the virtual machine really easy, and if I ever built this as a real CPU, it's be very cheap to manufacture and incredibly power efficient (as it would have barely any transistors).

But, these benefits come with a big cost, and that is (1) memory, as programs have to be quite large, and (2) difficulty in programming. This is why I created Rebec, because it makes programming this a lot easier. But if you want to understand machine code and assembly, I'll try my best to explain it.

The virtual CPU only has one instruction called "RSSB", which stands for "reverse subtract and skip on borrow". Because the CPU only has one instruction, it does not store store the instruction name in memory. Instead, only the operand of the instruction is stored in memory. And there is only one operand to RSSB, thus every word of memory is a single instruction.

It is a 16-bit, signed, 2s compliment, little Endian CPU.

The RSSB instruction can be summed up like this (this isn't my actual code but it's a nice way to visualize it):


Code:


The input "x" value is a pointer that point to a memory address. "pc" and "acc" are also pointers that specifically point to memory addresses 0 and 1 respectively. "pc" is your "program counter" and "acc" is your "accumulator".

It's important to note that pc and acc are NOT external registers. They are simple pointers to memory address 0 and 1, so they themselves refer to locations in RAM. (Technically if you built a physical version of this CPU you could make pc and acc external registers and map them to RAM, but on the programmer's end pc and acc refer to memory addresses.)

When you call "rssb" with some x value, both the accumulator and x are dereferenced and the accumulator is subtracted from x (hence the reverse subtract part). The results are then stored into both the accumulator and x at the same time.

You always want to increment the program counter after every instruction, but if the result of the subtraction was negative, then you increment the program counter an additional time, which skips the next instruction (hence the skip on borrow part).

After the rssb instruction finishes, some "otherStuff()" happens. In this case, I deal with memory mappings to the virtual CPU's RAM. In this case, I map "ZERO" to memory address 2, "POS" to memory address 3, "NEG" to memory address 4, "IN" to memory address 5, "OUT" to memory address 6, and "ROM" to memory address 7.

What are those? "ZERO" always holds the value 0, "POS" always holds the value 1, and "NEG" always holds the value -1. These are refreshed every CPU cycle by "otherStuff()". I put these here because they make programming the CPU a little easier.

"IN" and "OUT" are mapped to the 16 input pins and 16 output pins of the virtual CPU. Every CPU cycle, "otherStuff()" will read whatever data is written in OUT and write it to the output pins. It will then read whatever data is on the input pins and write that to IN.

In the case of the virtual machine on the TI-83+/TI-84+, anytime you write data to "OUT" it will display that to the screen as an ASCII character, and every time you read from it it will pause and allow the user to input text.

"ROM" is the final mapped memory address, it stands for "read-only memory". Its purpose is to allow the CPU to identify itself. ROM stores the part number of the CPU, so the software can read the part number and know what CPU it is. In the virtual machine, it just stores "313".

Now since we know how that works, let's look at a very simple program:


Code:


What does this program do? It copies the value stored in address 0015 to address 0014. To the 0C00 in 0014 should be erased and be replaced by 0F00.

Understanding the program isn't that hard. Addresses 0-7 are irrelevant. Remember, these are things like your accumulator, your output pins, your input pins, etc. Your actual program starts at memory address 8. The only important thing to know here is that you always want your program counter to start with the value 8 so the CPU will skip over the mapped RAM addresses and will start executing at the beginning of your program. You also want OUT to always start as 0, because that's what the Rebec programming language expects (there's a long reason to why this is I don't want to get into here).

The actual program starts at 0008. Remember, it's little Endian, so the first four instructions are all "rssb(14)". Why 14? 14 is the memory address we want to copy data to.

Thing about it what "rssb(14)" does if we call it just twice...


Code:


So if rssb(x) is called twice, then the memory address that x is pointing to will be cleared (and so will the accumulator).

So why did I call it 4 times instead of 2?

Well, if you're in the middle of a program, calling it twice is bad practice. Because if the value in x is negative, then the CPU will skip over your second rssb(x) and it won't execute. Or, even if it is positive, if you are in the middle of a program, it's possible the last routine that executed ended on a negative, so it'd skip your first instruction.

So calling it 4 times guarantees it will at least be executed twice and will clear out what x is pointing to (in this case, address 0014).

The next instruction is "rssb(15)". Since we know the accumulator was just cleared, what does "rssb(15)" do?


Code:


Effectively, this stores the value the operand is referencing into the accumulator. So, in this case, the accumulator now holds the value at memory address 15. It now holds 0F00.

The next two instructions are "rssb(2)". Remember, that is ZERO, which is a mapped location in RAM that always holds the value of 0. So what would that do?


Code:


Calling "rssb(2)" will negate the accumulator. Why do I call rssb(0) twice?

Because if we negate the accumulator, let's assume the number we just loaded is positive, then the second rssb(2) will be skipped since the resulting value in the accumulator is negative, thus we borrowed. Let's assume that we do not skip the next instruction, this means that the value loaded into the accumulator must've been negative. That would mean the first rssb(2) will be skipped.

So, no matter what, either the first or second rssb(2) will be skipped, and no matter what, one or the other will be executed. This guarantees that the accumulator will be negated.

The next instruction is another rssb(14).

Remember, our accumulator now holds the negation of the data stored in memory address 0015, or, -0F00. We also know that memory address 14 is empty. So what does calling rssb(14) at this point do?


Code:


Now memory address 14 holds 0F00! We did it, we copied the data!

But there's still 4 more lines of code. Why? Because if you just left your program like that, it would through an error when you run it, because you did not halt the CPU properly.

The last four instructions code are "rssb(1)" twice then "rssb(0)" twice. If you remember what 1 and 0 are mapped to, that's "rssb(acc)" and "rssb(pc)" respectively.

How the mapped RAM addresses are setup, these four instructions will always lead to the CPU freezing. Although, this is a very easily detectable state, so I refer to this as the "halting" state. The virtual machine recognizes this state as when to stop the program.

Understanding the Virtual Machine from Assembly Language

Coding for the R313 doesn't have to be done through machine code. It can be done through assembly with the R313 assembler.

The same machine code I wrote above can be rewritten like so:


Code:


Much more beautiful, wouldn't you say?

Notice how I don't define the first 8 words of memory. This is because the assembler does this for you, it always sets OUT to be initially 0 and PC to be initially 8. The other mapped memory addresses you have no control over so those don't matter.

Just like in any other assembly language, "x:" is used for defining symbols, which represent memory locations. For the operand to "rssb", you can also write expressions. Such as, these are all valid:


Code:


Comments begin with semicolons.

You can learn more about the assembly language by writing programs in Rebec, compiling them, and looking at the output. Rebec compiles to self-commenting assembly code that describes what it is doing.

The virtual machine itself is so simple I might even port it to TI-BASIC if I get bored enough. But the problem is it'd be hella slow. (The GIFs you see are using the TI-84+ with the CPU on its slow setting.)

Some other interesting fact I figured out while working on this

I figured out how to get around the fact "_GetKey" is blocking. If you want to use _GetKey but still want other things to happen on the screen while waiting for a key input (without writing an interrupt, which isn't difficult just unnecessary), simply use "_GetCSC" in a loop until the A register no longer holds 0, then after the loop breaks (when the user presses a key), stick the value of the A register into "(kbdScanCode)", and THEN call "_GetKey".

What that does is after _GetCSC (which is non-blocking) detects you pressed a key, it will then trick the OS to think you pressed the key again so when you call "_GetKey" it will immediately register you pressed the key without blocking. Within the "_GetCSC" loop you can do whatever you want while waiting for a key press, and then you just pass whatever _GetCSC reads into _GetKey.

This is how it's implemented in my code to make a blinking cursor when typing:


Code:


I thought this might be a useful thing. I only figured this out recently.

That's a valuable learning project, and also a good writeup
A single-instruction processor is easy to emulate and implement in hardware, but as you wrote, some more instructions and transistors would proper performance up, ease of use up, binary size down, memory consumption down. For instance, even BrainF* has multiple instructions.

Single-instruction programs remind me of domas' https://github.com/xoreaxeaxeax/movfuscator , based on an outdated compiler (but this can be worked around).

Keep going on

Thanks! I do plan to keep it single-instruction, though. Every computer that exists is multiple instructions. I'm trying to do something different, ya know?

That's part of the challenge here, making a single-instruction computer that's easy to use.

Memory consumption and performance will always be a problem, but it could also be insanely power efficient and incredibly inexpensive.

I'm not really a hardware person, I'm more of a software person, so that's one reason I decided to do this as a side project. The hardware part would be pretty basic, but the software part would be difficult. So I get to write a ton of software while not having to get too much into the weeds of hardware.

I don't plan for this to run the next Crysis or anything. If I can get it to reliably and easily work as a microprocessor to control small projects, even as a toy, that would satisfy my goal.

Yes, I noticed
I wish you good luck with that endeavour - as I wrote, it's a great learning project

There is much confusion throughout this project between borrow (opposite of 17-bit sign) and 16-bit sign. Since my arguments on irc didn't appear to have an effect, here is a program exhibiting these issues:
Code:
Which when run under rvm outputs:
Code:

This bug has nothing to do with that. It wouldn't make sense for it to be, as it does not matter how you define the word "borrow" because Rebec is based on how the machine actually works, not how you define words. The definition comes from here.

Again, Rebec is built in regards to the virtual machine as it exists. It is built taking into consideration that "borrowing" occurs when you get a negative from a subtraction, meaning the in a - b, b > 0. Calling this "borrowing" or not calling it "borrowing" cannot create bugs. Bugs aren't created from what you call a machine.

The bug has to do with how the current code detects if a number if greater than another number. It effectively works like this:


Code:


That seems great on paper but it can get buggy.

-20,000 - 20,000 = -40,000, but -40,000 cannot fit into a word. It underflows and the result of the subtraction is 12,768.

Basically, very large comparisons can fail due to overflow/underflow and I need a better algorithm.

It states a is not less than b even though it clearly is.

Making very large subtractions will simply underflow and give you the wrong result. There's nothing wrong with the virtual machine itself, even Rebec is working as intended, since I specifically wrote the greater-than and less-than functions to behave this way, I just didn't think through that it was a flawed algorithm.

Brooding over this problem for a few hours, I did manage to come up with a solution.

There are four cases when subtracting two numbers (pretend 0s are "positive"):

1. Positive - Positive
2. Negative - Positive
3. Positive - Negative
4. Negative - Negative

The first case cannot produce an underflow under any condition, the fourth should be fine as well. The second and fourth could produce and underflow, the third could produce an overflow.

However, we don't need to worry about case 2 and 3. Because if we are subtracting a positive from a negative, we know already it's that the negative is less than the positive. We don't need to subtract anything. Same with the third, we know just from looking at the signs that the positive is greater than the negative.

So the only case we have left is the 4th. How do we fix it?

Effectively, I have to modify the algorithm to look like this:


Code:


If anyone knows of any other solution to this, please let me know.

Also, as a side note, you don't need to use character codes in Rebec. Just write characters like you do in C. Don't type 60, type '<'.

My point is that if you replace short c = a - b; with int c = a - b; that jge algorithm does work. This is the difference between sign and borrow. The esolang page is completely ambiguous with respect to which way it behaves, just like it is ambiguous with respect to how it handles overflow (in both cases this is something you need to know in order to be able to use the language, but the actual behavior is implementation dependent). Also, I haven't thought of a better way than more or less what you said:
Code:


Edit: I was trying to optimize the codegen when I noticed another problem. The rssb zero \ rssb zero trick fails when acc = -32768 since it can't be negated so an extra instruction gets skipped.

You are just being ridiculous at this point. It is objectively borrowing by all definitions of the word.



I don't know what you mean. It is not ambiguous, I explained exactly why it gives the results it does and I just need to put aside some time to patch it.



I currently have the number -32768 in my known bug list. The fact it can't be negated cause minor issues here can there. Such as, if you look up at my binary string algorithm, I subtract the sign bit from the number if it is negative. I do this by adding -32768 to it. But -32768 wouldn't work, because it just becomes 0. So I had to add -32767 to it then decrement.

This is a bug I am aware of but it is rather minor as I have yet to encounter an instance where specifically needing the number -32768 was crucial to an algorithm and there wasn't some easy workaround. I am more concerned about fixing the jumps at the moment and getting something akin to "#include" statements to import libraries.

Yes I am being ridiculous. I am being ridiculous because it matters as we have seen with the jge case. Since you appear to know some z80, have you ever noticed that the sign flag and carry flag are different flags. That's because they behave differently. To quote a reference you linked (emphasis mine):
That borrow bit is the carry flag, believe it or not, not the sign flag. You can tell because the sbc instruction uses the carry flag as input instead of the sign flag, and as you have repeatedly mentioned, borrow is used by adc and sbc for multi-precision arithmetic.

I believe that this confusion stems from the fact that most C programmers, not knowing about or having access to assembly flags, and never caring about overflow behavior, just do the thing that works "most of the time", instead of doing something harder and/or slower that only fixes numbers they don't care about. Because when it comes down to it, for 15 bit signed numbers, the sign of a 16 bit arithmetic operation is identical to the borrow of that operation. This is just no longer the case for 16 bit inputs.

Keep in mind that everything I have been saying is functionally identical to what you are saying: that sign and carry are the same thing until overflow is involved.

I still would have to change the jge case. I can change the definition of "borrowing" in the virtual machine, the bug will still remain, because the machine is built consistently with this definition.

If you think it is that important, I will change it as the change is trivial, but the bug in jge and jpl will remain until I write new code for those.

Thanks for your input.

Alright, so the first bug that this change fixes is that rssb zero \ rssb zero now works correctly for all inputs due to 0-(-32768) now correctly not triggering a borrow. The second thing is that it makes signed comparisons fairly easy to implement correctly for all inputs:
Code:

Oh, nice routine.

I've been working on it and I think the comparisons work now, you can try it yourself if you want to check.


Code:


I also found a ton of other bugs while working on this that I've fixed and some I'm still working on fixing. There was a pretty significant bug in the evaluator that I fixed. (The evaluator evaluates mathematical expressions.)

One thing I did not mention is that in Rebec you can type out the arguments for commands as mathematical expressions.

Such as,


Code:


If you run the virtual machine in "numeric" mode (which displays the output as numbers rather than ASCII characters, do it by typing the word "numeric" after the file name), you get this as output:


Code:


You can also type characters with single quotes:


Code:


Although, characters cannot be part of expressions ('Q' + 2 won't work, for example). This may be something I'll add in the future, though.

You can also type expressions including variables, like:


Code:


It's important to note that when using variables in expressions, you don't get the value of the variable. You get its memory address. So "y + 3" would evaluate to the memory address 3 after y.

You can also load a variable's memory address into itself:


Code:


I fixed a couple other minor bugs as well.