cs-drop.txt

CS-DROP "Request for Discussion"
================================

Change History
--------------

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 put control flow orig resp. dest items onto the
control flow stack.

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

Solution
--------

A control flow stack operator - CS-DROP - to discard  the top most control
flow (orig or 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 orig or dest items from the control flow stack (up to the
first colon-sys, do-sys, case-sys, or of-sys).

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: orig|dest -- )
    Remove the top item orig|dest from the control flow stack.
    An ambiguous condition exists if the top control flow stack item
    is not an orig or dest.


Typical Use
-----------

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

As an example for the use fo CS-DROP we create a simple DSL for defining
finite state machines (FSMs).
This DSL builds up a table of branch targets on the control flow stack
at compile time when starting to define a new FSM. At the end of the FSM definition, this
table is removed from the control flow stack without resolving any further items in it.
See the definition of ;FSM below.

    : FSM: ( u -- u ) \ Define a finite state machine
           ( C: -- colon-sys dest_u-1 orig_u-1 ... dest_0 orig_0 )
        >r :
        POSTPONE ahead \ jump to first mentioned state
        r@ 0 ?DO  POSTPONE begin  POSTPONE ahead   LOOP \ construct jump table on control flow stack
        r@ 2* cs-roll  POSTPONE then
        r> ;

    : ;FSM ( u -- )
           ( C: colon-sys dest_u-1 orig_u-1 ... dest_0 orig_0 -- )
        -------------------------------------------
        2* 0 ?DO  CS-DROP  LOOP \ remove jump table
        -------------------------------------------
        POSTPONE ;
    ; immediate

Refer to appendix A for the complete FSM DSL.

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 stadardize its use.


Reference implementation
------------------------

As standard systems are

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

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

  - as there is no standard to way to inspect whether the topmost
    item on the control flow stack is an orig or dest

a standard definition for CS-DROP cannot be provided.

An estimation would be the following definitions that however
only allow to remove dest items from the control flow stack
and would create an ambigous condition if used with an orig.
They also 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 an
orig or dest control flow item, so a definition for CS-DROP in SwiftForth is:

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

Win32Forth uses two cells on the data stack as an orig or dest
control flow item, so a defintions for CS-DROP in Win32Forth is:

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


Testing
-------

The following tests assure that CS-DROP actually removes the top most
control stack item:

    t{ 99 :noname begin [ CS-DROP ] ; drop -> 99 }t  \ dest
    t{ 99 :noname if    [ CS-DROP ] ; drop -> 99 }t  \ origin


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.


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



Appendix
========

Sample Use of CS-DROP to implement a domain specific language for defining
finite state machines.

    \ Finite State Machine DSL to demonstrate use of CS-DROP    uho 2017-07-27

    : FSM: ( u -- u ) \ Define a finite state machine
           ( C: -- colon-sys dest_u-1 orig_u-1 ... dest_0 orig_0 )
        >r :
        POSTPONE ahead \ jump to first mentioned state
        r@ 0 ?DO  POSTPONE begin  POSTPONE ahead   LOOP \ construct jump table on control flow stack
        r@ 2* cs-roll  POSTPONE then
        r> ;

    : ;FSM ( u -- )
           ( C: colon-sys dest_u-1 orig_u-1 ... dest_0 orig_0 -- )
        2* 0 ?DO CS-DROP LOOP \ remove jump table
        POSTPONE ;
    ; immediate

    : State: ( u -- u+1 )  \ Define a new state name
        Create immediate dup , 1+ Does> @ ;

    : ) ( u i -- ) \ resolve state orig
        ( C: dest_u-1 orig_u-1 ... dest_0 orig_0 -- dest_u-1 orig_u-1 ... dest_0 orig_0 )
        swap >r   2* CS-PICK POSTPONE then  r> ; immediate

    : resolve ( i --  )
        ( C: dest_u-1 orig_u-1 ... dest_0 orig_0 -- dest_u-1 orig_u-1 ... dest_0 orig_0 )
        2* 1+ CS-PICK POSTPONE again ;

    : -> ( u -- u ) \ transfer to new state
        >r ' execute resolve r> ; immediate

    : cs--roll ( u -- )
       ( C: orig_u|dest_u ... orig_0|dest_0 -- orig_0|dest_0 orig_u|dest_u ... orig_1|dest_1 )
       dup 0 ?DO dup >r cs-roll r> LOOP drop ;

    : ->{ ( u -- u )
        ( C: dest_u-1 orig_u-1 ... dest_0 orig_0 -- dest_u-1 orig_u-1 ... dest_0 orig_0 dest orig )
        >r  POSTPONE begin  POSTPONE if  r> ; immediate

    : } ( u i -- u )
        ( C: dest_u-1 orig_u-1 ... dest_0 orig_0 dest orig -- dest_u-1 orig_u-1 ... dest_0 orig_0 )
        swap >r  1+ resolve  POSTPONE then  CS-DROP  r> ; immediate


    \ The FSM DSL is used like this:

    0
    State: init
    State: accept-As
    State: accept-Bs
    State: accept-Cs
    State: done

    FSM: A+(B*|C*) ( -- )  \ accept one or more As followed by any number of Bs or any numbers of Cs

      init )       '"' emit  key
                   dup 'A' =  ->{ emit      key accept-As }
                   -> done

      accept-As )  dup 'A' =  ->{ emit      key accept-As }
                   dup 'B' =  ->{ emit      key accept-Bs }
                   dup 'C' =  ->{ emit      key accept-Cs }
                   -> done

      accept-Bs )  dup 'B' =  ->{ emit      key accept-Bs }
                   -> done

      accept-Cs )  dup 'C' =  ->{ emit      key accept-Cs }
                   -> done

      done )       '"' emit
                   drop \ not accepted char

    ;FSM