RfD: Third draft of Structures

[Stephen Pelc]

This the best compromise I can get to, taking into account all
contributions so far. The compromises in this draft take into
account name conflicts, stack effect conflicts, alignment and
fat/thin implementations.

Stephen


RfD: Structures - Version 3
30 August 2006, Stephen Pelc

Change History
==============
20060830 Removed some restrictions on FIELD: and children.
Moved some words to FLOATING EXT.
20060827 Added alignment to discussion.
20060822 Rewrite after criticism
20060821 First draft

To Do
=====
Test cases.


Rationale
=========

Problem
-------
Virtually all serious Forth systems provide a means of defining
data structures. The notation is different for nearly all of them.

Current practice
----------------
Current practice is too varied to merge or agree on one word set,
either of names or of stack effects. In particular there are two
camps, one which defines the name of the structure at the start,
and one which defines it at the end. Examples are:

STRUCT POINT \ -- len
1 CELLS FIELD: P.X
1 CELLS FIELD: P.Y
END-STRUCT

STRUCT{
1 CELLS FIELD: P.X
1 CELLS FIELD: P.Y
}STRUCT POINT \ -- len

Discussion
----------
The name first implementation of STRUCT and END-STRUCT is not
difficult.

: STRUCT \ -- addr 0 ; -- size
CREATE HERE 0 0 , DOES> @ ;
: END-STRUCT \ addr n --
SWAP ! ; \ set size
: FIELD: \ n1 n2 "name" -- n3 ; addr -- addr+n1
CREATE OVER , + DOES> @ + ;

The name last implementations of STRUCT{ and }STRUCT are trivial
even for native code compilers:

: STRUCT{ \ -- 0
0 ;
: }STRUCT \ size "name" --
CONSTANT ;
: FIELD: \ n1 n2 "name" -- n3 ; addr -- addr+n1
CREATE OVER , + DOES> @ + ;

In both cases the definition of FIELD: is the same. Further words
that operate on types can all use FIELD: and so can be common to
both camps.

For many modern compilers, implementing FIELD: to provide efficient
execution requires carnal knowledge of the system.

Compatibility between the name first and name last camps is by
defining the stack item struct-sys, which is implementation
dependent and can be 0 or more cells. In the name-first example
above, struct-sys corresponds to the "addr" stack items in the
stack comments of STRUCT and END-STRUCT above. After some
discussion on newsgroups and mailing lists, the consensus is that
struct-sys should not appear in the specification of FIELD:.

Mitch Bradley wrote the following about structure alignment:
"In practice, structures are used for two different purposes with
incompatible requirements:
a) For collecting related internal-use data into a convenient
"package" that can be referred to by a single "handle". For
this use, alignment is important, so that efficient native
fetch and store instructions can be used.
b) For mapping external data structures like hardware register
maps and protocol packets. For this use, automatic alignment
is inappropriate, because the alignment of the external data
structure often doesn't match the rules for a given processor.

C caters to requirement (a) but essentially ignores (b). Yet people
use
C structures for external data structures all the time, leading to
various custom macro sets, usage requirements, portability problems,
bugs, etc.

Since I do much more (b) than (a), I prefer a structure definition
basis
that is fundamentally unaligned. It is much easier to add alignment
than to undo it."

Solution
--------
The intention of this proposal is to find a portable notation
for defining data structures using word names that do not
conflict with existing systems, and to provide easy portability
of code between systems.

System implementors can then define these words in terms of
their existing structure definition words to enhance performance.

Authors of portable code will have a common point of
reference.

The approach is to define FIELD: so as to enable both camps to
co-exist. Since the name last approach is the simplest and only
requires synonyms to define the start and end words, we simply
recommend that these users write portable code in the form:

0
a FIELD: b
c FIELD: d
CONSTANT somestruct

We now turn to considering name first implementations, with the
objective of providing a simple means of porting to name last
implementations. Using the usual point and rectangle example,
we can define structures:

BEGIN-STRUCTURE point \ -- a-addr 0 ; -- lenp
1 CELLS FIELD: p.x \ -- a-addr cell
1 CELLS FIELD: p.y \ -- a-addr cell*2
END-STRUCTURE

BEGIN-STRUCTURE rect \ -- a-addr 0 ; -- lenr
point FIELD: r.tlhc \ -- a-addr cell*2
point FIELD: r.brhc \ -- a-addr cell*4
END-STRUCTURE

The proposal text below does not require FIELD: to align any
item. This is deliberate, and allows the construction of groups of
bytes. Because the current size of the structure is available on
the top of the stack, words such as ALIGNED (6.1.0706) can be used.

Although this is a sufficient set, most systems provide facilities
to define field defining words for standard data types. Note that
these also satisfy the alignment requirements of the host system,
whereas FIELD: does not.

The recommended field type definers are:
CFIELD: 1 character
IFIELD: native integer (single cell)
FFIELD: native float
SFFIELD: 32 bit float
DFFIELD: 64 bit float
The following cannot be done until the required addressing has
been defined. The names hould be considered reserved until then.
BFIELD: 1 byte (8 bit) field.
WFIELD: 16 bit
LFIELD: 32 bit field
XFIELD: 64 bit field

Name first minimalists are reminded that it is adequate to provide
the source code (even by reference) in this proposal.

Proposal
========
10.6.2.aaaa FIELD:
field-colon FACILITY EXT

( n1 n2 "<spaces>name" -- n3 )
Skip leading space delimiters. Parse name delimited by a space.
Create a definition for name with the execution semantics defined
below. Return n3=n1+n2 where n1 is the offset in the data
structure before FIELD: executes, and n2 is the size of the data
to be added to the data structure. N1 and n2 are in address units.

name Exection:
( addr -- addr+n1 )
Add n1 from the execution of FIELD: above to addr.


10.6.2.cccc BEGIN-STRUCTURE
struct FACILITY EXT

( "<spaces>name" -- struct-sys 0 )
Skip leading space delimiters. Parse name delimited by a space.
Create a definition for name with the execution semantics defined
below. Return a struct-sys (zero or more implementation dependent
items) that will be used by END-STRUCTURE
(10.6.2.dddd) and an initial offset of 0.

name Execution: ( -- +n )
+n is the size in memory expressed in adress units of the data
structure.

Ambiguous conditions:
If name is executed before the closing END-STRUCTURE has been
executed.

10.6.2.dddd END-STRUCTURE
end-structure FACILITY EXT
( struct-sys +n -- )
Terminate definition of a structure started by BEGIN-STRUCTURE
(10.6.2.cccc).


10.6.2.eeee CFIELD:
c-field-colon FACILITY EXT
The semantics of CFIELD: are identical to the execution
semantics of the phrase
1 CHARS FIELD:


10.6.2.ffff IFIELD:
i-field-colon FACILITY EXT
The semantics of IFIELD: are identical to the execution
semantics of the phrase
ALIGNED 1 CELLS FIELD:


12.6.2.gggg FFIELD:
f-field-colon FLOATING EXT
The semantics of FFIELD: are identical to the execution
semantics of the phrase
FALIGNED 1 FLOATS FIELD:


12.6.2.hhhh SFFIELD:
s-f-field-colon FLOATING EXT
The semantics of SFFIELD: are identical to the execution
semantics of the phrase
SFALIGNED 1 SFLOATS FIELD:


12.6.2.iiii DFFIELD:
d-f-field-colon FLOATING EXT
The semantics of DFFIELD: are identical to the execution
semantics of the phrase
DFALIGNED 1 DFLOATS FIELD:

Labelling
=========
ENVIRONMENT? impact - table 3.5 in Basis1
name stack condition

THROW/ior impact - table 9.2 in Basis1
value text


Reference Implementation
========================
Modified three times from original code in VFX Forth for Windows.

: begin-structure \ -- addr 0 ; -- size
\ *G Begin definition of a new structure. Use in the form
\ ** *\fo{BEGIN-STRUCTURE <name>}. At run time *\fo{<name>}
\ ** returns the size of the structure.
create
here 0 0 , \ mark stack, lay dummy
does> @ ; \ -- rec-len

: end-structure \ addr n --
\ *G Terminate definition of a structure.
swap ! ; \ set len

: field: \ n <"name"> -- ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size n bytes.
create
over , +
does>
@ +
;

: cfield: \ n1 <"name"> -- n2 ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size 1 CHARS.
1 chars field:
;

: ifield: \ n1 <"name"> -- n2 ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size 1 CELLS.
\ ** The field is ALIGNED.
aligned 1 cells field:
;

: ffield: \ n1 <"name"> -- n2 ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size 1
FLOATS.
\ ** The field is FALIGNED.
faligned 1 floats field:
;

: sffield: \ n1 <"name"> -- n2 ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size 1
SFLOATS.
\ ** The field is SFALIGNED.
sfaligned 1 sfloats field:
;

: dffield: \ n1 <"name"> -- n2 ; Exec: addr -- 'addr
\ *G Create a new field within a structure definition of size 1
DFLOATS.
\ ** The field is DFALIGNED.
dfaligned 1 dfloats field:
;


Test Cases
==========
TBD.

[Anton Ertl]

...

Post by Stephen Pelc
Since I do much more (b) than (a), I prefer a structure definition
basis
that is fundamentally unaligned. It is much easier to add alignment
than to undo it."

He also wrote that he liked (the semantics of) Gforth's FIELD, which
does support, but not enforce alignment.

In particular, if you want unaligned fields, the only cost is that you
have to write an additional "1" per field. I would like to see a
rationale by you why you consider that worse than your proposal. The
only rationale I have seen by you is that you have had problems with
C; but Gforth is not C, and Gforth's FIELD does something different
than C; in particular:

|field ( align1 offset1 align size "name" - align2 offset2 )
|
|Create a field NAME with offset OFFSET1, and the type given by ALIGN
|SIZE. OFFSET2 is the offset of the next field, and ALIGN2 is the
|alignment of all fields.

If you want an unaligned 4-byte field, you write

1 4 field <name>

[Of course the name would have to be changed, and the specification
adjusted to a more standard-document style]

Post by Stephen Pelc
CFIELD: 1 character
IFIELD: native integer (single cell)
FFIELD: native float

Fill in the blank:

C@ F@ @
C! F! !
CFIELD: FFIELD:

Calling that word that fills the blank IFIELD: would be a severe
mistake, in breaking the usual Forth conventions and making both this
word hard to remember as well as all others that deal with single
cells. Ok, so this is would not be the first time that this mistake
is made (the order of locals in LOCALS| comes to mind), but we should
not repeat this mistake.

I see two possible solutions:

1) Call the single-cell word FIELD: and the general word differently.

2) Only propose the general FIELD:, but not the type-specific words.

fup2 clf.

- anton

[Charles Melice]

Post by Stephen Pelc
This the best compromise I can get to, taking into account all
contributions so far. The compromises in this draft take into
account name conflicts, stack effect conflicts, alignment and
fat/thin implementations.
Stephen
RfD: Structures - Version 3
30 August 2006, Stephen Pelc

[snip]

I hope that the text which follows will be interpreted only as a
material for reflection.

STRUCT POINT \ -- len
1 CELLS FIELD: P.X
1 CELLS FIELD: P.Y
END-STRUCT

It seems to me that this construction is purely lexicographical and is
filled with ambiguities.

Indeed, there is no relation between P.X and P.Y. They are not fields,
they
are independent offsets.

STRUCT is CONSTANT. POINT is not a STRUCT, it is a constant.
FIELD: is an OFFSET, not a field.
END-STRUCT don't terminates a STRUCT.

Finally, the only word which could possibly enter the standard would
be "OFFSET:".

0
1 CELLS OFFSET: P.X
1 CELLS OFFSET: P.X
CONSTANT POINT

Roughly, the word STRUCT in Forth cannot exist: Forth does not possess
at
present structures, except for the (refused) versions which parses.

This ends the reflection which I submit.

Charles

[jacko]

hi

5 ENUM ref x y z col row

0 ref ARRAY struct


: user x struct @ ;

: eg struct dup x swap @ dup * swap y swap @ dup * + sqr ;

thats my 2p.

cheers

[jacko]

Hi


5 IDX ref x y z col row

ref ARRAY struct


: eg struct dup x @ dup * swap y @ dup * + sqr ;

cheers

p.s. possible ref DROP to change search order context.

[Charles Melice]

Post by jacko
hi
5 ENUM ref x y z col row
0 ref ARRAY struct
thats my 2p.
cheers

I see you are using an array to have a structure of
cells sized members.

Notice the next texts descriptions related to structures:

[...A structure contains an ordered group of data objects. Unlike
the elements of an array, the data objects within a structure
can have varied data types. Each data object in a structure
is a member or field.]

[...All references to a struct member outside its accessibility
scope shall result in an error at compile time.]

I think members of a structure have to be accessed using a
special scope operator.

Perhaps the words RECORD: ... OFFSET: ... END-RECORD are
betters names for the ANS proposal.

--
Charles

[Ed]

Post by Charles Melice
...
Perhaps the words RECORD: ... OFFSET: ... END-RECORD are
betters names for the ANS proposal.

The following comment is less about the proposal and more about
the issue of word name choices - particularly when proposed for a
Standard.

The name STRUCT is typical of 'C' where short-hand (cryptic?)
names are the norm. Whereas forth standards have expressed the
goal that names be meaningful.

RECORD is a real english word and not too long. But why the trend
of appending colons? It wasn't done for CREATE VARIABLE etc.
If the structure's end was ;RECORD then perhaps but it further raises
the question of why everything has to look colon-like?

If the reasoning is that some long obsolete forth once used the name
RECORD etc andso we can't, then it is unfortunate.

When the ANS process began considerations of conflict with existing
forths had to be taken into account. But it's been 20 years and the world
has changed. If anyone still uses Forth-79 or 83 systems then clearly
they have no interest in, or need of, ANS-Forth. Hence they are not
going to be upset if ANS happens to adopt a name that conflicts with
one theirs. Forth standards should be using the best names available
- not ones which are compromised or second rate.

Perhaps forth now needs a new rule - "You can always do better than
add colons to names." :)

[s***@jedit.org]

Post by Ed
Perhaps forth now needs a new rule - "You can always do better than
add colons to names." :)

In Factor (which is definitely not an ANS Forth) I use the convention
that parsing words which read ahead from the input have names ending
with a colon. I find it makes code easier to follow.

Slava

[ward mcfarland]

Post by s***@jedit.org
In Factor (which is definitely not an ANS Forth) I use the convention
that parsing words which read ahead from the input have names ending
with a colon. I find it makes code easier to follow.

I find myself liking this style for words that require a termination
word.

Thus I would prefer
RECORD: .... ;RECORD
to
RECORD .... END-RECORD (or was it ENDRECORD, END_RECORD, RECORD-END)

and

CODE: ... ;CODE
to
CODE ... END-CODE


While I have no problem with CREATE VARIABLE VALUE etc since they do
not need a completion word.

[J Thomas]

Post by ward mcfarland

Post by s***@jedit.org
In Factor (which is definitely not an ANS Forth) I use the convention
that parsing words which read ahead from the input have names ending
with a colon. I find it makes code easier to follow.

I find myself liking this style for words that require a termination
word.
While I have no problem with CREATE VARIABLE VALUE etc since they do
not need a completion word.

I would like to start using some naming convention for parsing words
that don't use a termination word. Just to remind me that they *are*
parsing words. Of course we already have a collection of standard
parsing words that have no common naming convention. And we have
parsing words that imply their terminator like .( and ." . So it would
be hard to make it consistent.

What I see already is:

FOO: .... ;FOO for things that make new words.
FOO" .... " for things that parse to a "
FOO( .... ) for things that parse to a ) , usually they don't
compile

:NONAME is unfortunately not named NONAME: . I can live with that.

Of course you can give things whatever names you want. You can start
your project with a prologue

alias noname: :noname
alias endif then
alias create~ create \ is ~ a good convention for a parsing word that
quits on space after nonspace?
alias ....

But that makes it harder for other people to read your code, unless
enough of them copy your naming conventions. The requirement that other
people should be able to read your code easily will tend to keep
standard Forth poised around the early 1990's. But it's sometimes a
useful requirement despite that.

[s***@jedit.org]

Post by ward mcfarland
Thus I would prefer
RECORD: .... ;RECORD
to
RECORD .... END-RECORD (or was it ENDRECORD, END_RECORD, RECORD-END)
and
CODE: ... ;CODE
to
CODE ... END-CODE

In Factor, the ; word goes through a layer of indirection, so we have:

: ... ; colon definitions
M: .... ; methods
C: .... ; constructors

etc. I find this is more readable than ;M ;C and so on.

Slava

[Elizabeth D Rather]

Post by s***@jedit.org

Post by ward mcfarland
Thus I would prefer
RECORD: .... ;RECORD
to
RECORD .... END-RECORD (or was it ENDRECORD, END_RECORD, RECORD-END)
and
CODE: ... ;CODE
to
CODE ... END-CODE

: ... ; colon definitions
M: .... ; methods
C: .... ; constructors
etc. I find this is more readable than ;M ;C and so on.

To me, the : and ; denote a particular family of definitions, that is,
those compiled by the Forth : compiler. Words that are built other ways
shouldn't use that notation, it causes confusion. Without knowing a lot
about Factor, I'd guess that M: ... ; etc is appropriate, but CODE: ...
;CODE is not.

Cheers,
Elizabeth
--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. [phone]
5155 W. Rosecrans Ave. #1018 Fax: [phone]
Hawthorne, CA 90250
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[Charles Melice]

Post by Ed

Post by Charles Melice
...
Perhaps the words RECORD: ... OFFSET: ... END-RECORD are
betters names for the ANS proposal.

The following comment is less about the proposal and more about
the issue of word name choices - particularly when proposed for a
Standard.

Yes.

What I wanted to say is that the next construction is not
a structure definition. It is a (convenient) parody for a
structure definition.

struct: Point
cell field: X
cell field: Y
end-struct

The reason is that X is not a dedicaced member of a Point
structure (and Point is not a structure). But the presentation
seems to say that it is.

'X' is only an apparence of a structure field, on the screen,
by a proximity effect.

Post by Ed
The name STRUCT is typical of 'C' where short-hand (cryptic?)
names are the norm. Whereas forth standards have expressed the
goal that names be meaningful.
RECORD is a real english word and not too long. But why the trend
of appending colons? It wasn't done for CREATE VARIABLE etc.
If the structure's end was ;RECORD then perhaps but it further raises
the question of why everything has to look colon-like?
If the reasoning is that some long obsolete forth once used the name
RECORD etc andso we can't, then it is unfortunate.
When the ANS process began considerations of conflict with existing
forths had to be taken into account. But it's been 20 years and the world
has changed. If anyone still uses Forth-79 or 83 systems then clearly
they have no interest in, or need of, ANS-Forth. Hence they are not
going to be upset if ANS happens to adopt a name that conflicts with
one theirs. Forth standards should be using the best names available
- not ones which are compromised or second rate.
Perhaps forth now needs a new rule - "You can always do better than
add colons to names." :)

Yes. My preference is to define only OFFSET.

0
cell offset +X
cell offset +Y
constant Point

In that construction, each word have a correct sense.
They can also be used to define structures.

--
Charles

[Ian Osgood]

Post by Stephen Pelc
This the best compromise I can get to, taking into account all
contributions so far. The compromises in this draft take into
account name conflicts, stack effect conflicts, alignment and
fat/thin implementations.
Stephen
RfD: Structures - Version 3
30 August 2006, Stephen Pelc

[snip]

I'd like to add a data point to this discussion. BigForth was recently
added to the computer language shootout, and gforth is faster than
bigForth on only one test, where the only significant difference is the
implementation of structures (used to define a node in the tree). Here
are links to the comparision:

http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=binarytrees
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=all&lang=bigforth&lang2=gforth

I think structures would be a great addition to the standard. It would
help interoperability with foreign libraries and APIs.

Ian

[Bernd Paysan]

Post by Ian Osgood
I'd like to add a data point to this discussion. BigForth was recently
added to the computer language shootout, and gforth is faster than
bigForth on only one test, where the only significant difference is the
implementation of structures (used to define a node in the tree).

Nah, the difference that costs bigFORTH's performance is the implementation
of allocate. I'll probably rewrite allocate in the next revision of
bigFORTH to use the fast fixed-size object allocater for small regions, and
the slow, memory-saving allocater for larger objects. If bigFORTH had
Gforth's structure package, it would perform no better or worse than it
does now.

Post by Ian Osgood
Here

http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=binarytrees
http://shootout.alioth.debian.org/gp4sandbox/benchmark.php?test=all&lang=bigforth&lang2=gforth

Post by Ian Osgood
I think structures would be a great addition to the standard. It would
help interoperability with foreign libraries and APIs.

[Ed]

Post by Charles Melice
[snip]
I think structures would be a great addition to the standard. It would
help interoperability with foreign libraries and APIs.

My, how things have changed. There was a time when forthers would
have spoken out against including structures in the Standard.

[Tim Trussell]

I have been using the EDO system by GT Hawkins, circa 1987, which
uses the second of the two creation conventions you show, namely:

STRUCT{
1 CELLS FIELD: P.X
1 CELLS FIELD: P.Y
}STRUCT POINT \ -- len

Instead of STRUCT{, EDO uses S{

Instead of }STRUCT, EDO uses }S

Instead of FIELD: or OFFSET, EDO uses :: which, as Stephen Pelc
notes, has exactly the same definition of FIELD:

It has a number of additional 'features' that lend it to use in a
variety of programming utilizations.

One of those additional features is a barebones vector array
creation that takes a basic structure and extends it for use in a
much larger environment.

My including this isn't meant to obscure the thread, but rather to
give another example of what's been done. Since there isn't a
standard at the moment, and since most all structure packages do
pretty much the same things, I haven't worried about changing the
names of the definitions in this package to conform to any other
system.

\ ---[ EDO - Extended Data Objects ]---------------------------------
\ Note that this listing is different from the basic EDO file that is
\ present on the Taygeta archive site, as I have included definitions
\ that I use in my day-to-day programming tasks
\ -------------------------------------------------------------------

: [EDO] ;

1 CONSTANT 1BYTE
cell CONSTANT 1WORD ( -- n )
8 CONSTANT 1FLOAT

: BYTE* ;
: WORD+ ( n -- n+WORD ) 1WORD + ;
: WORD* ( n -- n*WORD ) 1WORD * ;
: FLOAT* ( n -- n*FLOAT ) FLOATS ;

: DEF ( size -- ) CONSTANT ;

: S{ ( -- 0 ) 0 ;

: :: ( offset object-definition -- offset )
CREATE OVER , + DOES> @ + ;

: }S ( size -- ) CONSTANT ;


\ ---[ Define Vector/Operator ]--------------------------------------

: [] ( object-definition #objects -- )
OVER * CONSTANT \ define the vector
CREATE , \ define the vector operator
DOES> @ * + ;

\ ---[ Extended Definitions ]----------------------------------------

1BYTE DEF {1BYTE}-DEF
2 BYTE* DEF {2BYTE}-DEF
4 BYTE* DEF {4BYTE}-DEF
1WORD DEF {1WORD}-DEF
2 WORD* DEF {2WORD}-DEF
8 BYTE* DEF {1FLOAT}-DEF

\ ---[ Usage Example ]-----------------------------------------------

\ Define the structure

S{
{1BYTE}-DEF :: p.red
{1BYTE}-DEF :: p.green
{1BYTE}-DEF :: p.blue
}S palette-obj

\ Define a vector array of this structure

palette-obj 256 [] palette[]-obj palette-ndx

\ Create the array in the dictionary

create Palette[] here palette[]-obj dup allot 0 fill

\ Access the vector array

: GetPalette \ loads palette data from the VGA
256 0 do
i $03C7 P!
$03C9 P@ Palette[] i palette-ndx p.red C!
$03C9 P@ Palette[] i palette-ndx p.green C!
$03C9 P@ Palette[] i palette-ndx p.blue C!
loop
;

: SetPalette \ sets VGA palette to data in Palette[]
256 0 do
i $03C8 P!
Palette[] i palette-ndx
dup p.red C@ $03C9 P!
dup p.green C@ $03C9 P!
p.blue C@ $03C9 P!
loop
;