CS-PICK

Interpretation:

Interpretation semantics for this word are undefined.

Execution:

( C: destu ... orig0 | dest0 -- destu ... orig0 | dest0 destu ) ( S: u -- )

Remove u. Copy destu 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:

Rationale:

The intent is to copy a dest on the control-flow stack so that it can be resolved more than once. For example:
\ Conditionally transfer control to beginning of
\ loop. This is similar in spirit to C's "continue"
\ statement.

: ?REPEAT ( dest -- dest ) \ Compilation
       ( flag -- )    \ Execution
   0 CS-PICK POSTPONE UNTIL
; IMMEDIATE

: XX ( -- ) \ Example use of ?REPEAT
   BEGIN
     ...
   flag ?REPEAT ( Go back to BEGIN if flag is false )
     ...
   flag ?REPEAT ( Go back to BEGIN if flag is false )
     ...
   flag UNTIL ( Go back to BEGIN if flag is false )
;

Testing:

: ?repeat
   0 CS-PICK POSTPONE UNTIL
; IMMEDIATE

VARIABLE pt4

: <= > 0= ;

T{ : pt5  ( n1 -- ) 
      pt4 ! 
      BEGIN 
        -1 pt4 +! 
        pt4 @ 4 <= ?repeat    \ Back to BEGIN if false 
        111 
        pt4 @ 3 <= ?repeat 
        222 
        pt4 @ 2 <= ?repeat 
        333 
        pt4 @ 1 = 
      UNTIL 
    ; -> }T

T{ 6 pt5 -> 111 111 222 111 222 333 111 222 333 }T

ContributeContributions

UlrichHoffmannavatar of UlrichHoffmann CS-DROP (revised 2018-08-20) Proposal2018-08-20 20:22:25

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

Reply