Memory management in Forth

Question

So I'm just learning Forth and was curious if anyone could help me understand how memory management generally works. At the moment I only have (some) experience with the C stack-vs-heap paradigm.

From what I understand, one can allocate in the Dictionary, or on the heap. Is the Dictionary faster/preferred like the stack in C? But unlike in C, there aren't scopes and automatic stack reclamation, so I'm wondering if one only uses the dictionary for global data structures (if at all).

As far as the heap goes, is it pretty much like C? Is heap management a standard (ANS) concept, or is it implementation-defined?

Answer 1

It is not Dictionary, or on the heap - the equivalent of the heap is the dictionary. However, with the severe limitation that it acts more like a stack than a heap - new words are added to the end of the dictionary (allocation by ALLOT and freeing by FORGET or FREE (but freeing all newer words - acting more like multiple POPs)).

An implementation can control the memory layout and thus implement a traditional heap (or garbage collection). An example is A FORTH implementation of the Heap Data Structure for Memory Mangement (1984). Another implementation is Dynamic Memory Heaps for Quartus Forth (2000).

A lot is implementation dependent or extensions. For instance, the memory layout is often with the two block buffers (location by BLOCK and TIB), the text input buffer and values and low-level/primitive functions of the language, in the lowest portion, dictionary in the middle (growing upwards) and the return stack and the parameter stack at the top ¹.

The address of the first available byte above the dictionary is returned by HERE (it changes as the dictionary expands).

There is also a scratchpad area above the dictionary (address returned by PAD) for temporarily storing data. The scratchpad area can be regarded as free memory.

The preferred mode of operation is to use the stack as much as possible instead of local variables or a heap.

¹ p. 286 (about a particular edition of Forth, MMSFORTH) in chapter "FORTH's Memory, Dictionary, and Vocabularies", Forth: A text and a reference. Mahlon G. Kelly and Nicholas Spies. ISBN 0-13-326349-5 / 0-13-326331-2 (pbk.). 1986 by Prentice-Hall.

Answer 2

The fundamental question may not have been answered in a way that a new Forth user would require so I will take a run at it.

Memory in Forth can be very target dependant so I will limit the description to the simplest model, that being a flat memory space, where code and data live together happily. (as opposed to segmented memory models, or FLASH memory for code and RAM for data or other more complicated models)

The Dictionary typically starts at the bottom of memory and is allocated upwards by the Forth system. The two stacks, in a simple system would exist in high memory and typically have two CPU registers pointing to them. (Very system dependant)

At the most fundamental level, memory is allocated simply by changing the value of the dictionary pointer variable. (sometimes called DP)

The programmer does not typically access this variable directly but rather uses some higher level words to control it.

As mentioned the Forth word 'HERE' returns the next available address in the dictionary space. What was not mentioned was that HERE is defined by fetching the value of the variable DP. (system dependancy here but useful for a description)

In Forth 'HERE' might look like this:

: HERE ( -- addr) DP @ ;

That's it.

To allocate some memory we need to move HERE upwards and we do that with the word 'ALLOT'.

The Forth definition for 'ALLOT' simply takes a number from the parameter stack and adds it to the value in DP. So it is nothing more than:

: ALLOT ( n --) DP +! ; \ '+!' adds n to the contents variable DP

ALLOT is used by the FORTH system when we create a new definition so that what we created is safely inside 'ALLOTed' memory.

Something that is not immediately obvious is the that ALLOT can take a negative number so it is possible to move the dictionary pointer up or down. So you could allocate some memory and return it like this:

HEX 100 ALLOT

And free it up like this:

HEX -100 ALLOT

All this to say that this is the simplest form of memory management in a Forth system. An example of how this is used can be seen in the definition of the word 'BUFFER:'

: BUFFER: ( n --) CREATE ALLOT ;

'BUFFER:' "creates" a new name in the dictionary (create uses allot to make space for the name by the way) then ALLOTs n bytes of memory right after the name and any associated housekeeping bytes your Forth system might use

So now to allocate a block of named memory we just type:

MARKER FOO \ mark where the memory ends right now

HEX 2000 BUFFER: IN_BUFFER

Now we have an 8K byte buffer called IN_BUFFER. If wanted to reclaim that space in Standard Forth we could type 'FOO' and everything allocated in the Dictionary after FOO would be removed from the Forth system.

But if you want temporary memory space, EVERYTHING above 'HERE' is free to use!

So you can simply point to an address and use it if you want to like this

: MYMEMORY here 200 + ; \ MYMEMORY points to un-allocated memory above HERE

                        \ MYMEMORY moves with HERE. be aware.

MYMEMORY HEX 1000 ERASE \ fill it with 2K bytes of zero

Forth has typically been used for high performance embedded applications where dynamic memory allocation can cause un-reliable code so static allocation using ALLOT was preferred. However bigger systems have a heap and use ALLOCATE, FREE AND RESIZE much like we use malloc etc. in C.

BF

Answer 3

Peter Mortensen laid it out very well. I'll add a few notes that might help a C programmer some.

The stack is closest to what C terms "auto" variables, and what are commonly called local variables. You can give your stack values names in some forths, but most programmers try to write their code so that naming the values is unnecessary.

The dictionary can best be viewed as "static data" from a C programming perspective. You can reserve ranges of addresses in the dictionary, but in general you will use ALLOT and related words to create static data structures and pools which do not change size after allocation. If you want to implement a linked list that can grow in real time, you might ALLOT enough space for the link cells you will need, and write words to maintain a free list of cells you can draw from. There are naturally implementations of this sort of thing available, and writing your own is a good way to hone pointer management skills.

Heap allocation is available in many modern Forths, and the standard defines ALLOCATE, FREE and RESIZE words that work like malloc(), free(), and realloc() in C. The memory they return is from the OS system heap, and it's generally a good idea to store the address in a variable or some other more permanent structure than the stack so that you don't inadvertently lose the pointer before you can free it. As a side note, these words (along with the file i/o words) return a status on the stack that is non-zero if an error occurred. This convention fits nicely with the exception handling mechanism, and allows you to write code like:

variable PTR
1024 allocate throw PTR !
\ do some stuff with PTR
PTR @ free throw
0 PTR !

Or for a more complex if somewhat artificial example of allocate/free:

\ A simple 2-cell linked list implementation using allocate and free
: >link ( a -- a ) ;
: >data ( a -- a ) cell + ;
: newcons ( a -- a )    \ make a cons cell that links to the input
   2 cells allocate throw  tuck >link ! ;
: linkcons ( a -- a )   \ make a cons cell that gets linked by the input
   0 newcons dup rot >link ! ;
: makelist ( n -- a )   \ returns the head of a list of the numbers from 0..n
   0 newcons  dup >r
   over 0 ?do
     i over >data ! linkcons ( a -- a )
   loop  >data !  r> ;
: walklist ( a -- )
   begin   dup >data ?  >link @           dup 0= until drop ;
: freelist ( a -- )
   begin   dup >link @  swap free throw   dup 0= until drop ;
: unittest  10 makelist dup walklist freelist ;

Answer 4

Some Forth implementations support local variables on the return stack frame and allocating memory blocks. For example in SP-Forth:

lib/ext/locals.f
lib/ext/uppercase.f

100 CONSTANT /buf

: test ( c-addr u -- ) { \ len [ /buf 1 CHARS + ] buf }
  buf SWAP /buf UMIN DUP TO len CMOVE
  buf len UPPERCASE
  0 buf len + C! \ just for illustration
  buf len TYPE
;

S" abc" test \ --> "ABC"

Answer 5

With Forth you enter a different world.

In a typical Forth like ciforth on linux (and assuming 64 bits) you can configure your Forth to have a linear memory space that is as large as your swap space (e.g. 128 Gbyte). That is yours to fill in with arrays, linked lists, pictures whatever. There are no restrictions. Forth only provides you with a HERE pointer to help you keep track of memory you have used up. Even that you can ignore, and there is even a word in the 1994 standard that provides scratch space that floats in the free memory (PAD).

Is there something like malloc() free() ? Not necessarily in a small kernel of a couple of dozen kilobytes. But you can just include a file with an allocate utility and set aside a couple of Gbyte to use for dynamic memory.

As an example I'm currently working with tiff files. A typical 140 Mbyte picture takes a small chunk out of the dictionary advancing HERE. Rows of pixels are transformed, decompressed etc. For that I use dynamic memory, so I ALLOCATE space for the decompression result of a row. I've to manually FREE them again when the results have been used up for another transformation. It feels totally different from c. There is more control and more danger.

Your question about scopes etc. In Forth if you know the address, you can access the data structure. Even if you jotted F7FFA1003 on a piece of paper. Trying to make programs safer by separate name spaces is not prominent in Forth style. So called wordlist (see also VOCABULARY) provide facilities in that direction.

Answer 6

My idea is published at https://sites.google.com/a/wisc.edu/memorymanagement I'm hoping to put forth code on github soon. If you have an array (or several) with each array having a certain number of items of a certain size, you can pair a single-purpose stack to each array. The stack is initialized with the address of each array item. To allocate an array item, pop an address off the stack. To deallocate an array item, push its address onto the stack.