CS-DROP "Request for Discussion"

Change History

2018-08-20 CS-DROP now operates only on control-flow dest items, simpler control-flow structure as typical use
2017-07-27 First version

Problem

Forth-94 and Forth-2012 provide explicit access to the control-flow stack by means of the words CS-PICK and CS-ROLL in the Programming-Tools extension wordset (TOOLS EXT). These words allow to copy and rearrange control flow (orig and dest) items.

BEGIN, IF and AHEAD (and other control structures) put control-flow dest resp. orig items onto the control-flow stack. orig items always go along with an yet unresolved forward branch. dest items mark backward branch targets.

There is however no way to remove an item from the control-flow stack without actually resolving it. This limits the abilty to define more complex control structures within the standard's scope.

For orig items this seems to be acceptable as not resolving a forward branch actually leads to malformed code that will eventually crash when executed.

There are however situations where control-flow dest items have been generated or duplicated by CS-PICK and then need no further resolution and thus should be simply removed.

Solution

A control-flow stack operator - CS-DROP - to discard the top most control flow dest item can be defined to supply the missing functionality. Combined with the re-arrangement capability of CS-ROLL this would allow to remove arbitrary dest items from the control-flow stack (up to the first colon-sys, do-sys, case-sys, or of-sys).

In contrast to the initial version of this proposal CS-DROP will no longer allow for removing orig items. Each orig items needs to be resolved exactly once, e.g. by THEN.

Proposal

Add the word CS-DROP to the Tools Extension wordset (TOOLS EXT).

CS-DROP "c-s-drop" TOOLS EXT

• Interpretation: Interpretation semantics for this word are undefined.

• Execution: ( C: dest -- )
  Remove the top item dest from the control-flow stack. An ambiguous condition exists if the top control-flow stack item is not a dest or if the control-flow stack is empty.

Typical Use

Typical use of CS-DROP would be in defining elaborated control structures.

As an example for the use of CS-DROP we create a simple control structure that allows to branch multiple times to an enclosing BEGIN. A corresponding END drops the BEGIN-generated control-flow dest item:

: END ( C: dest -- ) \ Compilation
     ( -- )         \ Run-time
    CS-DROP ; IMMEDIATE

: ?{ ( C: dest –– dest orig dest) \ Compilation
     ( f -- )                \ Run-time
    POSTPONE IF  1 CS-PICK ; IMMEDIATE

: }* ( C: orig dest -- )
    POSTPONE AGAIN  POSTPONE THEN ; IMMEDIATE

This can for example be used to define the Collatz function:

: even? ( u -- f )  1 AND 0= ;

: collatz ( u -- )
    BEGIN
       DUP .
       DUP even? ?{ 2 / }*
       DUP 1 <>  ?{ 3 * 1+ }*
    END
    DROP ;

19 collatz ( 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1  ok )

Remarks

Several Forth-94 and Forth-2012 systems already define CS-DROP or the same functionality under a different name. It is already common practice so it is only consequent to standardize its use.

Reference implementation

As standard systems are

• free to choose an appropriate representation for control-flow dest and orig stack items and also

• free to choose the data stack as control-flow stack or a separate stack for this purpose

a standard definition for CS-DROP cannot be provided.

An estimation would be the following definitions that however compile code in the dictionary.

: CS-DROP ( C: dest -- )  POSTPONE TRUE  POSTPONE UNTIL ;

: CS-DROP ( C: dest -- )  POSTPONE AHEAD  1 CS-ROLL  POSTPONE AGAIN  POSTPONE THEN ; 

CS-DROP can easily implemented in a system specific way if system knowledge about the control-flow stack implementation is available.

As an example SwiftForth uses a single cell on the data stack as control-flow dest item. A SwiftForth definition for CS-DROP, which also takes compiler security into account would be:

: CS-DROP ( C: dest -- )  DROP -BAL ;

Win32Forth uses two cells on the data stack as control-flow dest item including one cell for compiler security, so a defintion for CS-DROP in Win32Forth woul be:

: CS-DROP ( C: dest -- )  1 ?PAIRS DROP ;

Testing

The following test assures that CS-DROP actually removes the top most dest item from the control-flow stack:

t{ 99 :NONAME BEGIN [ CS-DROP ] ; DROP -> 99 }t

Experience

CS-DROP is already available in the following systems:

• gForth version 0.7.9 (not in 0.7.3)
• VFX version 4.7.2
• PFE version 0.33.71
• DXForth version 4.30

Similar functionality with a different name is supported by:

• FLT version 1.3.2 as (delete-cs-item)

CS-DROP is not (yet) supported in:

• SwiftForth version 3.6.3, sample definition given above
• Win32Forth version 6.15.04, sample definition given above

There are numerous discussions on comp.lang.forth (e.g. [3][4]) about control structure implementation using control-flow stack manipulations. Among the non standard system specific words mentioned in this context CS-DROP is widely accepted.

There seems to be a prior similar proposal probably by Guido U. Draheim as the PFE Forth documentation [2] suggests.

Discussion

Fall 2017

The initial version of the proposal was presented at the fall 2017 standards meeting. It proposed CS-DROP to drop both dest and orig items. Concerns were raised that using CS-DROP with control-flow orig items would lead to unresolved branch origins that eventually will result in run time errors when executed. Every orig created (e.g. by IF AHEAD ELSE WHILE) should be resolved exactly once (e.g. by THEN ELSE REPEAT).

The standardized behaviour of CS-PICK (15.6.2.1015) in both Forth-92 and Forth-2012 does not allow to copy control-flow orig stack items but requires a control-flow destination item dest-u to be copied. Although not explicitly stated we assume that copying orig items is an ambigous condition. Thus control-flow orig items cannot be copied within the standard scope, only control-flow dest items can. For this it is reasonable to restrict the to be standardized CS-DROP to also only drop control-flow dest items.

References

[1] http://dxforth.netbay.com.au/cfsext.html
[2] http://forth.sourceforge.net/word/cs-drop/
[3] https://groups.google.com/forum/#!topic/comp.lang.forth/64GKthsYVFs
[4] https://groups.google.com/forum/#!msg/comp.lang.forth/QCrKjzxodj0/RpPpq8Jp0AoJ

Author

Ulrich Hoffmann uho@xlerb.de