CS-DROP "Request for Discussion"

Change History

2019-08-22 CS-DROP again should drop both, control-flow dest and orig item. Propsal extended to included CS-PICK modification
2018-08-20 CS-DROP now operates only on control-flow dest items, typical use example has simpler control-flow structure
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.

Control structures (BEGIN IF AHEAD WHILE ...) put control-flow dest resp. orig items onto the control-flow stack. orig items always go along with a 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.

In its Forth-94 and Forth-2012 version CS-PICK has only defined behaviour when copying dest items to the top of the control flow stack:

15.6.2.1015 CS-PICK “c-s-pick” TOOLS EXT
Interpretation: Interpretation semantics for this word are undefined.
Execution: ( C: dest_u ... orig_0|dest_0 –– dest_u ... orig_0|dest_0 dest_u) ( S: u – – )

Remove u. Copy dest_u to the top of the control-flow stack. An ambiguous condition exists if there are less than u+1 items, each of which shall be an orig or dest, on the control-flow stack before CS-PICK is executed.

If the control-flow stack is implemented using the data stack, u shall be the topmost item on the data stack.

See: A.15.6.2.1015 CS-PICK.

u has to index a dest item (dest_u in the above standard text). Trying to copying an orig item with CS-PICK results in an ambigous condition as this would violate the type compatibility with the dest_u input parameter:

4.1.2 Ambiguous conditions

A system shall document the system action taken upon each of the general or specific ambiguous conditions identified in this standard. See 3.4.4 Possible actions on an ambiguous condition.

The following general ambiguous conditions could occur because of a combination of factors:

[...]

– argument type incompatible with specified input parameter, e.g., passing a flag to a word expecting an n (3.1 Data types);

CS-DROPping orig items

So, with this Forth-94 and Forth-2012 behaviour of CS-PICK (trying to copy an orig item is an ambigous condition) it seems to be reasonable to deal with orig items only by resolving them e.g. by THEN or ELSE. Simply dropping an orig item leaves an unresolved forward branch which actually is malformed code and eventually will crash when executed.

If however CS-PICK could also copy orig items in a defined way, multiple identical orig items could exist in the control flow stack and dropping them later would be perfectly reasonable. The programmer would take care that exactly one of these orig items will be resolved and all other items dropped at the best convenience of her program.

CS-DROPping dest items

An addition, there are 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. As dest items designate branch targets, dropping them when not needed is of no further significance.

Solution

A control-flow stack operator - CS-DROP - to discard the top most control flow item can be defined to supply the missing functionality.

Combined with the duplication capability of CS-PICK and the re-arrangement capability of CS-ROLL this would allow to do arbitrary control flow stack changes of its top items (down to the first colon-sys, do-sys, case-sys, or of-sys).

Being able to CS-DROP both orig and dest items from the control flow stack calls for tightening the definition of CS-PICK to allow copying dest and also orig items. This would eliminate the ambigous condition of CS-PICK operating on orig items.

Proposal

Revise the word CS-PICK in the Tools Extension wordset (TOOLS EXT) so that it can copy both orig and dest items (replace 15.6.2.1015 with the following paragraph):

15.6.2.1015 CS-PICK “c-s-pick” TOOLS EXT  

Interpretation: Interpretation semantics for this word are undefined.  

Execution:
      ( C: orig_u|dest_u ... orig_0|dest_0 –– orig_u|dest_u ... orig_0|dest_0 orig_u|dest_u) ( S: u –– )  

Remove u. Copy orig_u|dest_u to the top of the control-flow stack. An ambiguous condition
exists if there are less than u+1 items, each of which shall be an orig or dest, on the
control-flow stack before CS-PICK is executed.

If the control-flow stack is implemented using the data stack, u shall be the topmost item
on the data stack.  

See: A.15.6.2.1015 CS-PICK.

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: orig|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, an orig, 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.

Neither Forth-94 nor Forth-2012 specify the size of orig or dest items. They are even not required to have identical sizes. Different sizes would complicate the implementation of CS-ROLL (and the proposed revised CS-PICK). Most systems therefore implement orig and dest items the same size. The implementation of the proposed revised CS-PICK should thus be straight forward in most systems (and in no case more complicated than CS-ROLL).

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 for dest items only 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 items. A SwiftForth definition for CS-DROP, which also takes compiler security into account would be:

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

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

: CS-DROP ( C: orig|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

The following test assures that CS-PICK can copy orig items and CS-DROP can discard them:

t{ 99 :NONAME IF    [ 1 CS-PICK  CS-DROP ] THEN ; 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

The Gforth 0.7.9 implementation of CS-PICK includes a check that actually only dest items are copied (by means of the check ?NON-ORIG). Its CS-DROP implementation does not check for dest items.

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 2018

In its 2018 (12–14 September) meeting in Edinburgh the Forth standards committee discussed the (2018-08-20 revised) CS-DROP proposal with the following outcome:

CS-DROP
Allowing CS-DROP to drop an orig was discussed, this would require allowing CS-PICK to pick an orig. Referred to author for further consideration.

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 Forth94 and Forth2012 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