CONST-DOES> proposal

CONST-DOES>

Problem

Many uses of create...does> are just for shifting data from the create time to the execution time of the code after does>; i.e., after the word is fully defined, the data remains constant. A prototypical example of this use is the definition

: constant ( n "name" -- )
  create ,
does> ( -- n )
  @ ;

42 constant answer

Here, n is just shifted from create time to name execution time.

It would be nice if a native-code compiler could optimize a use of answer in the same way that it would optimize a use of 42. However, this is not possible, because the compiler has to consider the following possibility:

5 ' answer >body !

I.e., the data in a create...does>-defined word can change at almost any time. So at best a compiler can compile answer to the same code as

[ ' answer >body ]
literal @

The effects of this difference on the resulting code depend on the context. E.g., consider the code answer cells + @: If the compiler could optimize answer to 42, it could compile this sequence to one instruction on the MIPS architecture:

lw        v0,168(a0) ; 42 cells + @

Without this optimization, it needs at least five instructions:

lui       v1,...    ; [ ' answer >body ] literal
lw        v0,...(v1); @
sll       v0,v0,2   ; cells
addu      v0,v0,a0  ; +
lw        v0,0(v0)  ; @

So, the problem is how to communicate to the compiler that the data in answer will not change.

Proposal

(See Remarks for an informal, easier-to-understand description.)

CONST-DOES> ``const-does'' core

Interpretation:: Interpretation semantics for this word are undefined.
Compilation:: ( C: colon-sys1 -- colon-sys2 )
Append the run-time semantics below to the current definition. Whether or not the current definition is rendered findable in the dictionary by the compilation of const-does> is implementation defined.
Run-time:: ( u1*x u2*r u1 u2 ``name'' R: nest-sys1 -- )
Create a word name with execution semantics given below. Return control to the calling definition specified by nest-sys1. The u1 cells and u2 floats can be interleaved in any order.
name execution:: ( ... -- ... )
Perform initiation semantics below. Transfer control to the code right after the const-does>.
Initiation:: ( -- u1*x u2*r R: nest-sys2 )
Save information next-sys2 about the calling definition. After pushing the u1 cells and u2 floats, they are in the same order as they were at the start of the run-time semantics.

Typical use

: constant ( n "name" -- )
1 0 const-does> ( -- n )
  ;

: fconstant ( r "name" -- )
0 1 const-does> ( -- r )
  ;

: simple-field ( n "name" -- )
1 0 const-does> ( addr1 -- addr2 )
  + ;

Note that the stack comments after const-does> reflect the total stack effect of name (including initiation semantics), not the stack effect of the following code.

Remarks

The ANS-Forth-style formal proposal may be a bit hard to penetrate, so here are the essentials: Const-does> defines a word (the role of create) and its behaviour (the role of does>). The main other thing it does is to shift u1 cells and u2 floats from the definition time of name to its execution time. As a consequence, a simple definition like constant specifies just how many cells and floats it wants to shift, and needs to do nothing else.

Note that this works for both separate and combined data/FP stacks: On a system with separate stacks const-does> shifts u1 cells and u2 floats from definition to execution. On system with a combined stack is just shifts as many cells as these cells and floats take.

An optimizing native code compiler could compile a word defined with const-does> by compiling the u1 cells and u2 floats as literals, and then compiling (and possibly inlining) a call to the code behind the const-does>. The compiler would know that these literals are constant, and could optimize accordingly.

There are several alternative approaches to attack the problem:

An ANS-compliant way is to use colon definitions and literals. E.g.:
```
: constant ( n "name" -- )
\ name execution: ( -- n )
  >r : r> POSTPONE literal POSTPONE ; ;

: fconstant ( r "name" -- )
\ name execution: ( -- r )
\ environmental dependency: separate FP stack
  : POSTPONE fliteral POSTPONE ; ;

: simple-field ( n "name" -- )
\ name execution: ( addr1 -- addr2 )
  >r : r> POSTPONE literal POSTPONE + POSTPONE ; ;
```
A good compiler could inline the resulting colon definitions and optimize the results.
The downside of this approach is that it is hard to read (even with ]]...[[ to eliminate the POSTPONEs). And to avoid the environmental dependency for passing floats, we would have to save them in global variables, which would make the code even harder to read.
An alternative syntax would make does-const> behave like does>, but it would remove the ability to apply >body to the execution token of words it is applied to. Advantage: The syntax would be familiar and thus easier to learn. Disadvantages: Optimizing this would require a more complex compiler. The defining word is cluttered with code for saving and restoring the data to be shifted between definition and execution, making the code harder to read. Simple implementations would not enforce the restriction on not applying >body, leading to portability bugs (in contrast, the proposed const-does> does not expose the placement of the data, so a programmer cannot even access the data without learning implementation details).
In a similar vein, Stephen Pelc suggested defining the idiom constant...does> (currently non-standard, but widely used) to mean that the body must not be changed. The advantages and disadvantages are similar to does-const> above. Additional disadvantages: hard to implement in Forth systems where constants are not implemented in the traditional way; the syntax becomes quite unnatural when more than two cells or one float have to be transferred from definition-time to run-time.
Stephen Pelc also suggested a word invariant ( addr u -- ) that would just tell the compiler that a memory area would not change; this could be used to solve the problem like this:
```
: constant ( n "name" -- )
  create here >r ,
  r> 1 cells invariant
does> ( -- n )
  @ ;
```
The advantage of this approach is that it is more general (invariant could also be used to optimize accesses to other unchanging memory areas). The disadvantages are decreased readability and more complexity in optimizing (it requires a new optimization, whereas const-does> can be optimized through inlining).
One implementation issue for this proposal is that u1 and u2 are supplied at run-time. If the numbers were supplied at compile-time (with a syntax like [ 1 0 ]does-code>), a native-code compiler using this for optimization could be slightly simpler (and the reference implementation below could be faster). However, a native-code compiler probably can use the same mechanism here that it uses for optimizing pick, and supplying the number at run-time is easier for the user (both syntactically and mentally) and more flexible.

Reference implementation

This ANS Forth implementation of const-does> behaves as it should, but does not give you the performance advantages (rather to the contrary).

: const-does>-prelude ( u1*x u2*r u1 u2 ``name'' -- )
    \ create name and store u1*x u2*r there
    create 2dup 2,
    over cells allot here >r
    falign dup floats allot here ( u1*x u2*r u1 u2 addr2 )
    swap 0 ?do
        -1 floats + dup f!
    loop
    drop r> ( u1*x u1 addr1 )
    swap 0 ?do
        -1 cells + tuck !
    loop
    drop ;

: const-does>-postlude ( addr -- u1*x u2*r )
    \ fetch u1*x u2*r from addr
    dup 2 cells +
    swap 2@ >r
    0 ?do
        dup @ swap cell+
    loop
    faligned
    r> 0 ?do
        dup f@ float+
    loop
    drop ;

: const-does> ( compilation: colon-sys1 -- colon-sys2 )
    \ run-time: ( u1*x u2*r u1 u2 ``name'' R: nest-sys1 -- )
    \ name initiation: ( -- u1*x u2*r R: nest-sys2 )
    POSTPONE const-does>-prelude
    POSTPONE does>
    POSTPONE const-does>-postlude
; immediate

The following implementation is used in Gforth; it translates the defined words into colon definitions containing literals and a call, like this:

\ input:
: simple-field ( n "name" -- )
1 0 const-does> ( addr1 -- addr2 )
    + ;

8 simple-field field1

\ SEE output:
: simple-field  
  1 0 249544 (const-does>) ;

\ 249544 xt-see
noname : 
  + ;

: field1  
  8 <249544> ;

The implementation code itself is not quite ANS Forth compliant, but porting it to other systems should not be hard:

: compile-literals ( w*u u -- ; run-time: -- w*u ) recursive
    \ compile u literals, starting with the bottommost one
    ?dup-if
	swap >r 1- compile-literals
	r> POSTPONE literal
    endif ;

: compile-fliterals ( r*u u -- ; run-time: -- w*u ) recursive
    \ compile u fliterals, starting with the bottommost one
    ?dup-if
	{ F: r } 1- compile-fliterals
	r POSTPONE fliteral
    endif ;

: (const-does>) ( w*uw r*ur uw ur target "name" -- )
    \ define a colon definition "name" containing w*uw r*ur as
    \ literals and a call to target.
    { uw ur target }
    header docol: cfa, \ start colon def without stack junk
    ur compile-fliterals uw compile-literals
    target compile, POSTPONE exit reveal ;

: const-does> ( run-time: w*uw r*ur uw ur "name" -- )
    here >r 0 POSTPONE literal
    POSTPONE (const-does>)
    POSTPONE ;
    noname : POSTPONE rdrop
    lastxt r> cell+ ! \ patch the literal
; immediate

Experience

Const-does> is implemented in Gforth since November 2000.

Comments

Stephen Pelc pointed out that const-does> is not practical for defining words that contain larger tables (you don't want to pass the table from definition-time to use-time on the stack).

This is true, but such words are rare in my experience, and uses of such words where the fetches can be optimized are probably even more rare (usually you will index the table with a value that has to be computed at run-time, and then you cannot optimize the fetch anyway). For the exceptions a solution based on invariant would help. Guido Draheim:

`const-does>` is good stuff - although I would like to have an alias `does>@`
where just the specification says that `to` won't work.

Anton Ertl