Data space notion in Forth Standard

[ruv]

First of all, by memory region we mean a set of contiguous address units (an interval in the memory address space).

Sometimes people could think that data space is a single memory region. But it's wrong.

In the standard this term is defined in the following way:

data space: The logical area of the dictionary that can be accessed.

Actually, data space is a set of all those and only those address units which are accessible by a program. If a program may read or write an address unit, then this unit is a part of data space. If an address unit is not a part of data space, then a program is not allowed to read or write this unit ("A program shall not fetch from or store into locations outside data space" in 3.3).

So, data space is only one. Conceptually, there can be another data space (probably with another name), in a different address space (for example, the space of i/o ports). But there is no other data space that can be accessed by a standard program (3.3.3 "Data space is the only logical area of the dictionary for which standard words are provided to allocate and access regions of memory").

It is not required that all units of data space are contiguous. For example, in the section 3.3.3.2 the standard explicitly says: “the above operators need not produce contiguous regions of data space if definitions are added to or removed from the dictionary between allocations”.

Data space is not a constant set. For example, when a region is allocated (by means of allocate), new address units become members of this set. When a region is freed (by means of free), the corresponding address units are not members of this set anymore.

In contrast to allocations, a region reservation or releasing (by means of allot) usually does not change the set of address units available for a program. And the region returned by the phrase here unused ( -- addr u ) is a part of data space as long as contiguity of subsequent reservations is guaranteed (see 3.3.3.2).

Code space is not accessible by a program, so it cannot formally be a part of data space at all. An implementation may allocate or reserve data space regions for use by code (or by headers), but there is no way for a standard program to access these regions. So they don't belong to data space (that is, they are excluded from data space when the system reserves them for code or other internal purposes).

[SirWumpus]

An issue I face (with C-based OS hosted implementation) is the question of whether ALLOT et al. (3.3.3.2 Contiguous regions) accounts for the possible relocation of the current data-space when enlarged, such that previous values of HERE on the stack can be invalidated?

[MitchBradley]

An issue I face (with C-based OS hosted implementation) is the question of whether ALLOT et al. (3.3.3.2 Contiguous regions) accounts for the possible relocation of the current data-space when enlarged, such that previous values of HERE on the stack can be invalidated?

HERE is not necessarily a machine address. It could be an index into an array whose base address could be changed at any time. The only requirement is that the words that operate on data space addresses must do the right thing. It's entirely feasible to make a standard system where you cannot see machine addresses at all.

[ruv]

HERE is not necessarily a machine address. It could be an index into an array whose base address could be changed at any time.

Yes, it's yet another alternative to relocation of the dictionary.
But any indirection always costs performance, and this one too.

It's entirely feasible to make a standard system where you cannot see machine addresses at all.

Sure! For example, yoda — it's an almost standard toy Forth system implemented in Bash (it doesn't provide some obligated words and so imposes some environmental restrictions).

[SirWumpus]

You talk about relocating the (whole) dictionary. But I'm concerned with the relocation of just the data-space of a single word definition, that does not necessarily mean relocating the whole dictionary.

Does the Forth 200x Draft explicitly deny the possibility of relocating a word's data-space by some low level allocator, ie. does it assume fixed memory as one might find in embedded systems?

Again, I have a hosted implementation using C's realloc. A word's headers are part of the dictionary, but the data-space where the definition is held can grow separately and with realloc that could mean relocation. So my solution was to add specific words:

: reserve ( u -- addr ) DUP ALLOT HERE SWAP - ;

: >here ( -- u) ;  \ built-in that returns an offset into the data-space instead of an address.

[ruv]

I'm concerned with the relocation of just the data-space of a single word definition,

Does the Forth 200x Draft explicitly deny the possibility of relocating a word's data-space by some low level allocator

It doesn't explicitly deny that. But if a standard program obtains an address and then reserves it (or vise versa, reserves and then obtains) — the system is not allowed to invalidate this address. An address of data space may be only invalidated (excluded from the data space) in the moments when the system may use this address unit for internal purposes.

Obtaining and then reserving an address:

  here x ! \ obtaining
  ... \ code that never breaks contiguity of reservations
  1 cells allot \ reserving

Reserving and then obtaining an address:

  1 cells allot \ reserving
  ... \ code that never breaks contiguity of reservations
  here cell- x ! \ obtaining

Take into account that a program may perform address arithmetic within contiguously allocated regions (3.3.3.3). So, the system may only relocate content of a region if no one address was obtained within any set of contiguously allocated (reserved) regions it belongs to. It's true for a word's data field too.

[ruv]

@SirWumpus wrote:

: reserve ( u -- addr ) DUP ALLOT HERE SWAP - ;

Note that allot has type ( n -- ), so that is an incorrect use of allot.

Thus, either that reserve should have type ( +n -- addr ), or it's implementation should be something like this (from my another comment):

: (reserve) ( u -- )
  dup largest-n u< if ( +n ) allot exit then  dup 2 u/  dup recurse  - recurse
;
: reserve ( u -- addr ) here swap (reserve) ;

where largest-n and u/ can be defined as:

: u/ ( u u\0 -- u ) 0 swap um/mod nip ;

s" MAX-N" environment? invert [if] true 2 u/ 1 - [then]  constant largest-n