Tuesday, June 28, 2022

Non sequential computing environment and Forth -1-

Some things described in this article series can be used to implement the Forth programming language in a 'non sequential computing environment' and in a 'sequential computer environment..

My first reason to write this article series with the name 'Non sequential computing environment and Forth' is that non sequential computing can bring much computer power and will be easy to scale up if it is simple to use. It is called  'non sequential computing environment' as the terms parallel computing, parallel processing , concurrent computing or multitasking as give associations to to specific other things and solutions. ( https://en.wikipedia.org/wiki/Parallel_computing can help to give some background ) 

A second reason that this article series can be an inspiration for new Forth implementations and has items that can be used in a real implementation by others.

I am experimenting with new Forth implementations and want to report something about it. The third reason for writing this article series is that it can serve as an introduction to my experiments.

I the early days of computers was the cost of the hardware was an important limiting factor

You needed to spend a months salary for a 'simple' computer like a Commodore 64. To get more computing power the most easy way seemed to be is doing everything at a higher speed. Every evolution creating a next generation faster computers (and making the old computers obsolete).

A new fast computer is still relative expensive however there are also a lot of cheap computing devices available. Special hardware ( e.g. FPGA's , small micro controllers, memory ) is getting more and more available for low prices. Yes the newest and fastest hardware is still expensive however the price of getting computer power is extreme low compared to 40 years ago.

Small cheap processors and micro-controllers and FPGAs do have this interesting computing power. For only a few euro's or dollars it is possible to buy devices like raspberry (or other) pi systems or devices like ESP8266 or ESP32. When you look to the hours you need to work to earn sufficient to buy, several years ago, one computing device', nowadays can can buy more than hundred ESP32 devices. The only problem is that we do not (yet) have good software tools to handle that amount of computing power.  

In the 'classic' computer evolution the computer power was increased by a higher clock speed, adding memory caches special instructions and some other tricks. Processes and programs are executed sequential and the speed is increased to get more computing power. If we sacrifice some of the computer speed and could do things non sequential it is possible to scale up extremely by doing things in parallel. Perhaps this even creates 'greener' computers as old computer power does not become obsolete but can still be used as everything is non-sequential.

My opinion is that especially the programming language Forth can play a roll in a non sequential computing environment. Many programmers are trained in sequential programming and thinking. Also most programming languages are created in a sequential way.  Therefore also a mind shift is needed.
I will illustrate non sequential programming with some simple standard examples. Let say we have a simple problem with 2 variables. 

In a non Forth environment e.g.:
A = 5
B = 3
We want to swap the values so A will have the value of B and B will have the value of A.
In most languages it is not possible to put this in a program like
Let A = B
Let B = A
This as everything is executed sequential. In our example first A will get the value 3 ( the value of B ).
And in the second statement B will get the value of A. However at that moment A has the value of B (= 3 ) so in the end A as well as B both will have the value  3 .
In our sequential programming environment for swapping the values of A and B we need to introduce a third variable C and make a program like
Let C = A
Let A = B
Let B = C

In Forth it is a good practice to not use unneeded variables and do all calculations on the stack.
In Forth the values are manipulated on the stack.
Typing 5 3 will push the two values 5 and 3 on the stack.
With .S we can look on the stack and this can display something like (2) 5 3 showing that there a two items on the stack
When we want to swap the order in Forth we give the command SWAP
Checking again with .S gives 3 5

Can Forth do real magic and just SWAP these values in one step?
Unfortunately (most times) no!
This as SWAP (like many other Forth words) in most of the Forth implementations is build using multiple Forth high or low level commands that are executed sequential to do the 'swap'.
Sometimes a the second stack in Forth ( the return stack ) is used to temporary store the value.

A second example is the Forth word DROP . This word removes the top item from the stack. Depending how the stack is implemented in memory it also increments or decrements the Top Of Stack pointer ( the Forth variable TOS ). ( Incrementing or decrementing by 1 is a simple explanation. In fact it also depends on the hardware ( 8 or 16 bits) and the amount of bits of each item on the stack. If the stack items are 16 bits and the memory is just 8 bits the stack needs to be incremented or decremented by 2 and not by 1 ) 

A third, a little more complicated, example of Forth code. An addition.
For example
3 1 +
The values 3 and 1 are pushed on the stack. + does the addition so on top of the stack is now 4
In fact + does multiple things: Not only the two values are added. Also the top of the stack changed  (incremented or decremented depending how it is implemented in Forth.)

What if we could have a Forth that could do this in a non sequential way?
As a first step describing (and implementing) Forth commands in a non sequential way could help.
For most Forth words there are already descriptions in a more or less non sequential way. Often you see explanation of words described  like:

SWAP ( n1 n2 — n2 n1 )

n1 and n2 are the first and second item on the stack
We can represented most all (primitive) Forth words in using a (lookup ) table containing this information. See below a very simple lookup table (with the headers in bold).

Table 1.
  TOS n1  n2 n3 
 SWAP  TOS n2 n1 n3
 n2  n3
  + TOS - 1
 = n1 + n2 n3

n3 illustrates that n3 did not change with any of the words SWAP DROP + 
TOS the top of (parameter) stack was also added illustrate that it changes.
E.g. DROP or + will increment TOS.
In part 2 of this article series i will write more in detail about this table.

No comments: