Tutorial: Forth Memory Management

[+TheBF]

The Forth language is commonly used for the same type of programs that people might choose to use Assembler. Typically they are embedded programs for electronic devices, measurement instruments, drum machines, satellites and even electric toothbrushes. Forth works close to the hardware but gives you ways to make your own simple language so in short order, you are using your own high level functions to get the job done. This can make it faster to get a program ready and out the door in Forth versus doing it all in Assembler.

This tutorial illustrates how Forth manages memory, starting with nothing more than the raw memory addresses, just like you would see in Assembler programming. The difference is that with a few quick definitions, you create a simple memory management system. Using that memory management system you can build named variables, constants buffers and arrays.

 

To begin we have to assume we already have a Forth compiler somewhere that lets us add new routines, or as Forth calls them WORDs to the Forth Dictionary. The dictionary is actually just the memory space that we will be managing in this demonstration.

 

The Forth compiler is nothing more than the ‘:’ and ‘;’ WORDS. To compile a new word that does nothing in Forth you would type:

 

: MY_NEW_WORD ;

 

This would create a word in the Forth dictionary but since there is no other code after the name it does nothing.

We also need our compiler to have the Forth word ‘VARIABLE’. With these things in place we can create our simple memory management system.

We will create an empty memory location that will hold the next available memory address that we can use. In Forth this is called the dictionary pointer or DP for short we declare it like this:

VARIABLE DP \ holds the address of the next free memory location

Next we will create a function that returns the address that is held in DP. Forth calls that function ‘HERE’ as in “Where is the next available memory location?” Forth says “HERE”.

HERE uses the ‘FETCH’ operator which is the ampersand, ‘@’ in Forth.

 

: HERE ( -- addr) DP @ ; \ fetch the address in DP

 

Another thing that we will need to do is move the “dictionary pointer” by changing the value in DP so Forth creates a function that takes a number from the stack and adds it to DP using the function ‘+!” (Pronounced “plus-store”) Plus-store is very much like ‘+=’ for those familiar with ‘C’.

 

 

Forth calls this DP altering function ‘ALLOT’ and it is defined like this:

: ALLOT ( n --) DP +! ; \ add n to value in variable DP.

\ in other words allocate dictionary space

(Pretty simple huh)

 

So with these three definitions we have the beginnings of a simple memory manager. We can now say things in our program like:

HEX 2000 HERE 20 CMOVE \ move $20 bytes from HEX 2000 to HERE

\ Now move DP forward to “allocate” the space we just wrote to:

20 ALLOT

 

By using “20 ALLOT”. HERE is moved past our little 20 byte space so we won’t tromp on it later. So we have allocated 20 bytes of memory for our own use. To make it really practical we should have recorded the address of HERE somewhere because HERE is now pointing to a new address.

Getting Fancy

We can combine HERE and ALLOT and the STORE word ‘!’ in Forth to make an operator that ‘compiles” a number into memory. Forth uses the comma ‘,’ for this function and the definition is simple now.

: , ( n -- ) HERE ! \ store n at HERE,

2 ALLOT ; \ allocate 2 bytes (for a 16 bit computer)

 

To use the comma we simply type:

99 , 100 , 101 , 4096 ,

And the numbers go into memory like magic!

 

And of course we have a similar word that is used for bytes or characters called ‘C,’.

(pronounced “c-comma”) It works the same way a comma.

: C, ( c --) HERE C! 1 ALLOT ;

 

Getting Creative

There is a Forth word called CREATE that lets us add a new word to the dictionary. Words made with ‘CREATE’ simply return the dictionary memory address after the name. So with our new system making a variable called ‘X’ is as simple as:

 

CREATE X 2 ALLOT

In fact using the colon compiler we can take it to a higher level still:

 

: VARIABLE CREATE 0 , ; \ create a name and compile 0 in memory

 

Notice how we used the comma to automate the memory allocation of one unit of memory and initialize it to zero.

Now our programs can say:

VARIABLE X

VARIABLE Y

VARIABLE Z

 

And if we type:

CREATE ABUFFER 50 ALLOT

 

We have created a named memory space that we can use to hold data. Invoking the name ‘ABUFFER’ in our program will give us the beginning address of that buffer.

But why stop there? Use the compiler to make it better:

: BUFFER: CREATE ALLOT ;

 

Now it’s all done with one word!

 

50 BUFFER: ABUFFER

 

We could also ‘CREATE’ an array of numbers in memory like this:

CREATE MYNUMS 0 , 11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 , 99 ,

 

There are fancier ways to access this array but for this tutorial we will keep it simple. To get at these numbers in the array, we simply need to compute the address of the number we want. Since each number has been given 2 bytes of memory or 1 CELL as Forth calls it, the math is easy.

 

Given an index number, we multiply the index by the memory size, in bytes, of the CPU and add the result to the base address.

Let’s do it with the colon compiler:

: ]MYNUMS ( index –- addr) CELLS MYNUMS + ;

 

Explanation:

· CELLS is a forth function that multiplies a number by the memory address size of the CPU.

o As in x2 for a 16 bit CPU, x4 for 32 bit CPUs or x8 for a 64 bit computer.

o In this case it will multiply the index value on the stack

· MYNUMS returns the base address of the array

· ‘+’ simply adds the two numbers together giving us the address we need.

We can now fetch and see the value of any number in the array like this:

 

3 ]MYNUMS @ . \ the ‘.’ word prints the number on the top of the stack

 

 

The screen capture shows all of this entered at Forth console.

 

Conclusion

So this tutorial gives you examples of how Forth builds itself up from almost nothing to higher levels of programming. This approach is used to create the memory management words that you can use but it’s that the Forth compiler uses these same WORDs internally to compile words and numbers into memory and even to ASSEMBLE op-codes into memory in the Forth Assembler.

I know you are asking “Where did the compiler come from in the first place?” Well that’s a bit more black-belt level programming but the principals are the very same. You can start in Assembler or C and make a few primitive routines. Then you use those routines to make higher level WORDs. People have even built Forth compilers in Java and LISP. The method however is always the same. You begin with simple pieces and combine them to build something better and eventually you have built the compiler. It’s not for the faint-of-heart but the cool thing is that it is possible to understand every aspect of the system.

[+Lee Stewart]

Very well done, Brian!

 

...lee

[+TheBF]

Very well done, Brian!

 

...lee

 

Thanks. It's a little bit long, but I hope it helps folks understand a little more about how Forth works and why it keeps us fascinated.

[+TheBF]

Managing other TI-99 Memory Spaces

 

Using these concepts it becomes super easy to make a set of Forth words to manage the VDP memory as well.

 

All we need to begin is a VARIABLE to keep track of the last used memory address and then we create a set

of words like we have for CPU RAM but built for VDP RAM.

 

Here is how that could look.

\ Simple VDP RAM manager
\ Works the same way as the Forth dictionary
\ Best for static allocation

VARIABLE VP    \ VDP memory pointer (4K block)

HEX 1000 VP !   \ set the start of free VDP RAM

: VHERE   ( -- addr) VP @ ;   \ FETCH the value in VDP pointer
: VALLOT ( n -- )    VP +! ;  \ add n to the value in VDP pointer

Now we have VHERE which gives us the next free VDP address and VALLOT which lets us allocate VDP memory. Super simple.

 

So what can we do with that? We can create our little number compilers like we made for Forth CPU memory.

We will call them V, and VC, so we remember that they only work in VDP memory.

\ VDP number "compilers". Put a number or character in VDP RAM 
\ and advance the VP pointer by the proper amount (2 or 1)
: V,     ( n -- )  VHERE V!   2 VALLOT ;
: VC,    ( n -- )  VHERE VC!  1 VALLOT ;

So what does that give us? Well how about creating VDP variables?

: VAR:     ( -- <text>)             \ accessed with V@ and V!
            CREATE VHERE ,          \ compile time: compile VHERE address in CPU RAM,
​                   0 V,             \               put '0' in VDP RAM at that address

            DOES> ( -- addr)        \ run time:  DOES> returns the address after create
​                   @ ;              \ so we fetch the contents of that address, 
​                                    \  which is the VDP address we stored there at compile time.

This uses a feature of Forth that can make some people confused. Ask questions if you need help.

(hint: If you know object oriented programming, this is like creating an object that has only one method)

 

The new word VAR: above creates new Forth words. This has 2 aspects:

 

1. What happens when we create the new word in the dictionary? This is called "compile time action"

2. What happens when the word we created actually runs in a program. This is called "run time action"

 

#1 is handled by the code after the word CREATE.

 

#2 is handled by the code after the word DOES> (in other words what the word "does" when you run it)

 

So read the code for VAR: and see that after it "creates" a word in the dictionary, it compiles VHERE into Forth memory and then... it compiles a '0' into VHERE.

which is a VDP address remember.

(read that again if you need to). The word is recording 2 pieces of information: The VDP address where it put something AND it puts a zero in that VDP address.

 

Usage of VAR:

VAR: X
VAR: Y
VAR: Z

So we have made 3 new Forth words X,Y and Z.

 

When we type X, Y, or Z at the Forth console, or use then in a program what happens?

The "DOES>" code will run for each one of them!

 

When DOES> runs it returns the address in Forth (CPU) ram right after the name of the word.

This is exactly where we put the VHERE address! How convenient!

 

So all we need to do is 'fetch' what is in the address using the Forth word "@" and that returns to us an address in VDP RAM.

 

That's what a Forth variable does. Gives us an memory address so we can put something there or read it.

 

CAMEL99 has the word V@ which reads 16 bits from VDP RAM and V! which stores 16 bits in VDP RAM.

These are like @ (peek) and ! (poke) in Forth memory space.

 

( Please note: TURBOFORTH also has V@ but it reads 1 byte, not 2 bytes as in CAMEL99 Forth )

( CAMEL99 has VC@ to read 1 byte from VDP RAM. )

 

So to use our new "VDP VARS" we would say:

DECIMAL 
9 X V!
1 Y V!

X V@  Y V@  +  Z V!

Z V@ .

Next we will create named VDP buffers and VDP strings.

Edited November 4, 2017 by TheBF

[+TheBF]

Creating VDP Constants

 

​Now that we know how to make a VDP variable in Forth it becomes trivial to create a constant that is stored in VDP RAM.

 

A variable remember, records a '0' in VDP RAM and simply returns the address where it is stored.

 

So VDP constant would need to take an input number and store that rather than '0' and... it would need to get that value

and return it to Forth when we use it in a program. Here's how we do it.

: VCONST:  ( n -- <text>)
            CREATE VHERE , ( n) V,  \ compile time: VDP address in CPU RAM, put n in VDP RAM
            DOES> @ V@ ;            \ run time: fetch the VDP address, 
                                    \ then fetch the const from that VDP address

​The screen capture shows how we could use them.

Edited November 4, 2017 by TheBF

[+Lee Stewart]

Managing other TI-99 Memory Spaces

...

Now we have VHERE which gives us the next free VDP address and VALLOT which lets us allocate VDP memory. Super simple.

...

 

Very nice!

 

I am a little upset that I did not think of doing something like this myself a long time ago! I was always going to work out a way to allocate VRAM in a predictable, non-destructive way—especially for file management, which must allocate VRAM for PABs and record/sector buffers for most disk controllers. One thing that makes this more difficult for VRAM is that the largest block of free VRAM is different for different graphics modes. The value of the User Variable PABS is changed when the user changes the graphics mode, but it is not updated as is DP (contains HERE value) and your VP .

 

Graphics, Multicolor and Text modes each have the same two free blocks of VRAM, 800 bytes pointed to by PABS and 9862 bytes (with maximum open files = 3) at 1152h (no pointer). Text80 mode has only the latter block of free VRAM, to which PABS points. Bitmap mode is the most problematic, with only one 750-byte block of free VRAM, to which PABS points. But I digress ....

 

...lee

[+TheBF]

 

Very nice!

 

I am a little upset that I did not think of doing something like this myself a long time ago! I was always going to work out a way to allocate VRAM in a predictable, non-destructive way—especially for file management, which must allocate VRAM for PABs and record/sector buffers for most disk controllers. One thing that makes this more difficult for VRAM is that the largest block of free VRAM is different for different graphics modes. The value of the User Variable PABS is changed when the user changes the graphics mode, but it is not updated as is DP (contains HERE value) and your VP .

 

Graphics, Multicolor and Text modes each have the same two free blocks of VRAM, 800 bytes pointed to by PABS and 9862 bytes (with maximum open files = 3) at 1152h (no pointer). Text80 mode has only the latter block of free VRAM, to which PABS points. Bitmap mode is the most problematic, with only one 750-byte block of free VRAM, to which PABS points. But I digress .... |

 

...lee

 

 

Well of course these things make the programming look pretty, but there are overheads and I have the luxury of working with an unfinished system. With all the permutations you mention for the VDP modes it is probably best dealt with as you have done it. It's not truly a free block of memory that you can use and release. But if you lock the Graphics down like BASIC does these are great features to have in a TI-99 language.

 

And for tutorial purposes it does show how one can extend Forth to work with different kinds of memory in a system.

 

Part of my exploring this was to answer a personal question that I asked after I discovered Forth on the on 99 in the 1980s. Could TI have made a more responsive system if they had built it in Forth with code primitives? From what I see your work and Mark's and my own experiments, it would have been faster than GPL. That said to make it easily hook to other languages it might have required a byte code Forth system, which makes it one level slower than ITC but I think the virtual instructions per second would still be faster than GPL seems to do and with fast code primitives to support it I am pretty much convinced it would be faster.

 

All that deep thinking plus 5 bucks is enough to get you a big fancy coffee at Starbucks. :-)

[+TheBF]

VDP Strings exploration

 

​​Continuing with our VDP memory management tools, we can go further and make strings that are similar to BASIC.

​And just for fun we will add a few commands to make using the string look more like BASIC too.

 

Lets make a new command call "DIM" that takes a size input number and text name and makes space for string in VDP memory:

: DIM  ( n -- )
            CREATE  VHERE ,        \ compile time: compile the DP address into the Forth word
                    VALLOT         \ allocate 'n' bytes of VDP ram.

            DOES> @ ;              \ run time: fetch the VDP address

​

** EDIT **

​Although the code above works just fine, it is not optimal. For those whose looked closely you can see that DIM is actually a constant the gives us ithe address of VHERE at compile time,

​with the addition of VALLOT. Forth systems typically optimize the word CONSTANT in assembler to get a value to the top of stack very fast.

​CAMEL99 Forth is no exception so... a faster implementation is to do this:

: DIM    ( size -- )  VHERE CONSTANT   VALLOT ;    

We store VHERE as a fast constant and allocate the size from the number of the stack in VDP RAM.

Testing showed the 1st version takes 210uS when compiled. The second version takes 105uS.

Much better performance and we save space too!.

 

 

We can also use a VDP version of the Forth word COUNT which takes a counted string address and extracts the length

and adds 1 to the address to point to the start of the text. So here is VCOUNT.

The only difference form the standard word is VCOUNT uses VC@ to read the length byte from VDP RAM.

This we be used for printing strings.

: VCOUNT    ( vdp$adr -- vdpadr len ) DUP 1+ SWAP VC@ ;   \ convert counted string to addr,len

So to make a string the syntax is now:

80 DIM A$
80 DIM B$

Not quite BASIC but you could work with it.

 

 

We need a way to get text into these strings. The standard word PLACE takes an address and length of a string

and "PLACEs" it at a 2nd address as a counted string. We will make VDP version called VPLACE.

: VPLACE    ( $adr len VDP-adr -- )  2DUP VC! CHAR+ SWAP VWRITE ;  \ place $adr len in VDP-adr

So VPLACE will take a string in CPU RAM and PLACE it in VDP ram.

 

Now for a little syntax candy. We can PARSE the console input with word called ... PARSE .. what else?

PARSE returns Address and length of the parsed string. How convenient!

 

Let's do this:

\ collect characters up to final " and put in VDP memory
: ="       ( VDP$ -- )   [CHAR] " PARSE ROT VPLACE ;

So now we have made syntax for working with our VDP strings that looks like this:

80 DIM A$
80 DIM B$

A$ =" Now is the time for all good men "
B$ =" to come to the aid of their country."

And finally we need to print these strings. Forth has word called TYPE so we can just

emulate that word, but read the bytes from VDP RAM. VTYPE takes the address and length,

calculates the end and start address of the string with "BOUNDS" and then loops through

the addresses, reading a VDP byte and EMITing to the screen.

: VTYPE     ( vdp_addr len -- ) BOUNDS ?DO   I VC@ EMIT   LOOP ;

To continue with BASIC syntax emulation we can make a word called PRINT, that starts on a newline.

: PRINT   CR  VCOUNT VTYPE ;

So with these words we have a simple string system in Forth that puts strings in VDP RAM.

 

The GIF shows how it all works then prints A$ and B$ 100 times.

Edited November 5, 2017 by TheBF

[Willsy]

Behold the awesomeness! That was great!