Ternary computer in a browser

000. Background

In 1959, N. P. Brusentsov developed the unique Setun computer for Moscow State University. It was based on the ternary number system, and although the elemental base was partially binary, which led to cost overruns, the machine proved to be economical and reliable. Today, the ternary machine can only be seen in the museum, the binary code won.

But, as I said earlier , there will always be people who are ready to save the technology of the past in the form of emulators.

00+. Theoretical basis

This article discusses the ternary symmetric number system. The numbers in it are positive and negative, that is, -1/0/1 or more generally accepted - / 0 / +. This property implies the native support of negative numbers by our future computer.

There are a couple more arguments in defense of the ternary number system and ternary logic. The cost-effectiveness of data storage for each category is obvious, saving lines in the tires, a large capacity of the usual data types.



There is a formula y = ln (x) / x, the physical meaning of which I understand as “the ratio of the volume of stored information to the complexity of its storage”, where the complexity increases along the X axis.

The main drawback is the lack of a basic element that can be in three states and at the same time work effectively in modes suitable for building processors. But for the emulator, this is not a problem. Moreover, circuits of composite ternary elements are known. If you estimate how many transistors in modern processors are actually responsible for the command system, and how much for optimization, it turns out that the implementation of the ternary processor itself is not such a problem.

0 + -. Background

I learned about the work of N. P. Brusentsov relatively recently. Having studied some of the materials on Setuni, I realized that there is no need to go all the way again and you can use the knowledge of our days. As far as I know, the ternary virtual machine was also developed at Moscow State University. But there are few materials on it, but there are no source codes at all.

Just at that moment N. Wirth published the first achievements of the Oberon 2013 project.



Own command system of a RISC-like processor, a simple language and a simple compiler for him prompted me to the idea that it would be nice to combine the concepts of two smart people into one.

So the TRISC project, the ternary RISC, was born, within the framework of which the virtual machine and the Oberon language compiler into ternary code were implemented. Also, within the framework of this project, a simulator of logical ternary gates was implemented, but more on that another time.

The project was brought to the alpha stage and frozen. And in 2015, in the process of learning the Dart language, the idea arose to implement an emulator port for a browser.
An atypical web project, many strange goals, what could be more interesting?

0 + 0. Goals and means

Since the compiler in ternary code already worked, I also had ternary code. Therefore, the main goal of the project is to build a processor emulator. So that the task does not come down to a primitive set of switches, let's assume that the virtual machine must be controlled, asynchronous, so that the page does not freeze - this is the web.

Also, for the sake of interest, you can use your own data types that will be characteristic of ternary machines, and the processor itself can be implemented as separate modules, roughly corresponding to the real blocks of the processor - registers, ALU, etc. The advantage will be the use of many Dart features, because the project is needed for self-learning.

Before my eyes there is an original interpreter, with the algorithm, special problems should not arise.

0 ++. Maths

First, we implement logic and mathematics. Immediately interesting.

The main logical type of the ternary system is trilean (similar to boolean). I did not find a Russian analogue of the word. There are three values ​​for the trilean type, true / null / false. For these values, there are basic logical laws. They were formulated by Jan Lukasevich in the 20s of the last century. From the two laws, negation and implication, all basic logical operations are deduced.
Having described the Tril type in Dart, we use the operator overload capabilities.
A little testing, and the type is ready. We use a factory constructor so as not to produce many copies of objects like Tril, a kind of optimization.

With integers, it’s not so simple either. The smallest unit of information is trit (similar to a bit). In the Setun project, a six-digit trait was used (similar to byte). In my project, I used a nine-bit trait to be closer to an eight-bit byte in size. And although at first glance, nine is more than eight, this fact pays off with the power of the resulting data type - 19683 values. From -9841 to 9841 inclusive. Without inverse additions, without the need to distinguish arithmetic shift from logical shift.

In the alternative universe, people in the 80s had no problems finding the right characters in 256 values ​​of one byte. We will describe this data type tryte in the Dart language, we implement basic arithmetic operations for it.

In addition, we introduce the type int27, as you might guess, it has 27 trits, this will be the size of a machine word in our system. Of course, 27 trits fit more values ​​than 32 bits. Values ​​from -3,812,798,742,493 to 3,812,798,742,493. Here we can say that 64 bits will fit more values ​​than 27 trits, but you will need twice as many triggers for such a register.

For the most demanding, you can enter the type int81, which will tax even 128-bit numbers in minus. By the way, you can see that the number of trit increases in powers of three.
We implement the int27 type in the same way as tryte.

An additional type of our mathematical subsystem will be the Trits type, this is an analogue of the SET type in Oberon. A separate article by N. Wirth is devoted to the SET type, where he calls the SET type underestimated. We will appreciate it.

In short, the Trits (SET) type is a lot of trits. It is freely convertible to an integer, but all basic operations on sets, addition, multiplication, and so on are applicable to the Trits type. Support of this type will simplify the implementation of processing some instructions in the processor. It will also help to convert a ternary number to a string.

In addition to the ternary notation of numbers by the characters - / 0 / +, there is also a ninefold form of notation of ternary numbers, in it the symbols are ZXYW01234. We implement converters for such a record of numbers.

As an entertainment not related to the main task, we are implementing a converter into a ternary symmetric number system with an irrational basis.
The base will choose the square of the golden ratio. Such a number system is called Fibonacci. It has an interesting property - the notation of a number is symmetric with respect to its zero discharge.



An example of all converters in one picture.
Let's do some tests. The math subsystem is ready.

+ -. Iron

First, we describe the memory. It's pretty simple, memory is just an array of traits. We will supplement it with only one function in the form of an additional class - the ability to read whole words of data.

Additionally, for memory, we describe the MMU, a device for controlling access to various areas of memory. Our MMU is simple, it will allow you to connect to some memory cells as I / O pins, and it will also allow you to use negative addresses to access these pins from executable programs.

For the processor, I used the asynchronous features of the Dart language. Each processor cycle is planned for the future and runs asynchronously. At the same time, I still cheated and accelerated the performance by increasing the clock frequency by 100 times. The result was a kind of overclocking. So, the main processor activity occurs in the next () method.

It's time to develop a processor command system. As I said, I was based on the materials of the Oberon 2013 project. N. Wirth developed a simple command system for implementing his RISC processor on the FPGA. I upgraded this command system for ternary code. Two- or three-operand arithmetic, conditional jumps, direct and indirect memory addressing.

The processor will have 27 general-purpose registers, an additional PC register will indicate the location of the next command in memory, the IR register will contain the current command. There is also an additional NZ trit, which will contain an additional result of operations on registers. Some general purpose registers will be picked up by the Oberon system for placing return addresses, tops of the stack, etc.

As you know, RISC processors usually use separate instructions for loading and unloading data into RAM, and all operations are performed on registers and data in them.

So, the processor’s action algorithm is as follows: a word is read from memory at the PC address, the value is written to IR and sent to the command decoder, which sends signals to one or another unit to perform actions. Such actions can change the value of the register, while information is written to the NZ register whether the value is zero or greater than zero. So, one trit answer two questions. Subsequently, this trit can be used when executing conditional branch instructions. As a result of the command, the state of memory changes in places that the executable code considers to be variables, the transition address of the processor in the next step changes, the iteration ends. The processor shuts down when switching to -1 memory cell, since a command with the format - (-13) is written in it.

It makes no sense to paint the entire system of commands. It can be found in github.com/kpmy/tri/blob/master/doc/trinary-0.pdf .

Communication with the outside world occurs by writing to a memory cell with a predefined address of a value that the host executes. For example, you can implement a primitive debugging console in this way.
Since we have a web application, we display this console in an authentic black window with white letters. To do this, we’ll take advantage of the ready-made component and capabilities of the standard Dart library for managing web content.

+ -0. First steps

Since I already had the code from the working virtual machine, I will briefly describe the features of its execution.

So, for the firmware in the memory of the finished code, we will describe the loader class, which will download the code from the server and write it to memory. The code in JSON format is strange, but a fact, because any binary recording format would not be completely compatible with the ternary code.

According to the canons of the Oberon system, the loader modifies the transition addresses, simple mathematics corrects the code for the code offset of the loaded module relative to the zero position, which the compiler sets when compiling.

Bootstrap is a separate module, these are several commands that install the machine constants in memory (memory size, module table address, etc.) and transfer the processor to the address of the first executable command. Bootstrap was prepared manually.

The Core module is created in the image of the Oberon system core, the Kernel module, since it is a kernel, it has a lot of direct memory operations, the implementation of the allocator of dynamic structures (sometimes glitches), the implementation of the exception catch, etc.
Just in the Core module we implement the primitive console. To output strings and numbers, we will write the values ​​of the characters in the memory cell, as described above. The platform-dependent SYSTEM module is virtual; the compiler translates its calls directly to the machine code.

Inexpressive screenshot.
Check the performance of the resulting virtual machine here . Of course, complex debugging of both the processor and the compiler at the same time led to some bugs (which I have not found yet), but as a proof of concept the result of work seemed to me sufficient.

+ - +. Summary

As a result, we got a fully functional, expandable analogue of the N. Wirth processor from the Oberon 2013 project with a modification for the ternary number system and ternary code and several modules for working in the resulting system.

In the original interpreter, I made an attempt to develop success and implement communication with the outside world by analogy to the rs232 port, with a file system based on the 9p protocol. And this is what I came across. Both technologies, although they are declared cross-platform, when introduced into the concept of a platform of trits and traits, they rapidly lose their cross-platform. A base in the form of bytes and bits makes porting such technologies a nontrivial task.

Of course, one can object here that the significance and prevalence of the ternary systems is zero, but as in the anecdote about Vovochka, there is trinity, but there are no words about cross-platform for it. Perhaps this is some hindrance to the spread of ternary systems. After all, everything works like that.

Personally, I saw only one justified use of ternary machines - this is the organization of communication channels protected from intrusions. Indeed, even with direct access to the channel, the hacker will need at least a hardware signal decoder, which still needs to be developed. Thus, the struggle of armor and shell can give life to the industrial application of the described technologies.

+ 0-. References

Well, perhaps a few links for those who are interested.

• trinary.ru is a beautiful site with calculators, calendars, an OS simulator of the original Setuni.
• ternarycomp.cs.msu.ru is a more serious site, with a description of patents, algorithms
• www.inf.ethz.ch/personal/wirth/ProjectOberon/index.html copyright page of the Oberon 2013 project.
• github.com/kpmy/tri project repository
• bitbucket.org/petryxa/trisc repository of the original emulator

+00. PS

N.P. Brusentsov died on December 4, 2014. I hope the work of his life will not be forgotten.