Readable Flagless Short-Circuit Conditionals for Forth

[The first version of this was posted to comp.lang.forth on 2019-May-27]

The following was inspired by Wil Baden's short-circuit flag evaluation, but differs from it in using pure control flow, which is faster and more compact than ANDing and ORing flags. Such speed is particularly important in assembly language, which is what I originally developed this syntax for, and where I have been using it successfully for some years. The document linked below is about its implementation in non-Forth assemblers. There is an implementation for a Forth assembler at the end of the current document.

AddingStructuredControlFlowToAnyAssembler2.htm

I thought it was about time I ported it back to Forth, tested it, and shared it. To this end, I implemented and tested it in gForth.

There was some good discussion of flagless short-circuit conditionals between JennyB and Anton Ertl in the following comp.lang.forth thread in 2016. It seems it fizzled because no one came up with a readable syntax. I thank JennyB and others for subsequent discussions.

https://groups.google.com/d/msg/comp.lang.forth/V4hTh4-2qp8/w-anxmnMCQAJ

Here is my proposed syntax.

The equivalent of this C-like AND conditional with an ELSE clause:

IF test1 && test2 && test3 ... ELSE ... ENDIF

is written as:

COND

<test1>

AND-IF \ Note the hyphen to distinguish from Wil's ANDIF

<test2>

AND-IF

<test3>

AND-IF

ELSES \ Optional. Note the plural ELSES

ENDIF \ If no ELSES clause, use the plural ENDIFS

The equivalent of this C-like OR conditional with an ELSE clause:

IF test1 || test2 || test3 ... ELSE ... ENDIF

is written as:

COND

<test1>

OR-ELSE

<test2>

OR-ELSE

<test3>

OR-IFS \ Note the plural OR-IFS for the last OR condition

ELSE \ Optional

ENDIF

An alternative name for OR-IFS is IF-ANY (suggested by JennyB). Those who prefer THEN to ENDIF, would of course use Wil Baden’s THENS instead of ENDIFS.

Here I adapt Wil Baden's elegant flow charts, to show how these short-circuit conditionals work.

-------------------------------------------------------------------------------

| COND | COND | COND

| | |

< >-F-------. AND-IF < >-F-------. AND-IF .-----T-< > OR-ELSE

: | : : | : | : :

< >-F---. | AND-IF < >-F---. | AND-IF | .-T-< > OR-ELSE

| | | | | | | | |

| | | | | | | |___ | |

| | | | | | | \| |

+-------+ | | +-------+ | | |_______ : |

| | | | | | | | \| |

+-------+ | | +-------+ | | +-------+ |

|/ | | / | +-------+ |

: _________| | : _________| _____/ _____| ELSE

|/ | |/ | /

| | +-------+ | +-------+

| | | | | | |

| | +-------+ | +-------+

| |_____ | |_____ |

| \| ENDIF \| ENDIF

| | |

-------------------------------------------------------------------------------

Note that exactly one plural word is required to resolve each COND. This is either ENDIFS or ELSES for a short-circuit AND, and OR-IFS for a short-circuit OR.

What about short-circuit conditionals that combine ANDs and ORs? It’s a beautiful result that we don’t need any additional words for this, we just have to use the existing words in the right way. But it only works as an AND-of-ORs. I haven’t figured out any way to do an OR-of-ANDs, except by using De Morgan’s laws to transform it into an AND-of-ORs. i.e. by negating all the tests and swapping the contents of the IF and ELSE clauses.

The equivalent of this simple C-like AND-of-ORs conditional with an ELSE clause:

IF test1 && (test2 || test3) ... ELSE ... ENDIF

is written as:

COND \ An initial COND, enclosing the s/c ANDs

<test1>

AND-IF \ You can have as many AND-IFs here as you want

COND \ A second COND to bracket the s/c ORs.

<test2>

OR-ELSE \ You can have as many OR-ELSEs here as you want

<test3>

OR-IFS \ Plural OR-IFS, matches the second COND

ELSES \ Optional. Plural ELSES matches the initial COND

ENDIF \ Use plural ENDIFS if there is no ELSES clause

--------------------------------------

| COND

< >-F-------. AND-IF

| |

| | COND

| |

.-----T-< > | OR-ELSE

| | |

| .-T-< > | OR-ELSE

| | | |

| | < >-F---. | OR-IFS

| |___ | | |

| \| | |

|_______ | | |

\| | |

+-------+ | |

| | | |

+-------+ | |

_____/ _____| | ELSES

| / |

| | _________|

| |/

| +-------+

| | |

| +-------+

|_____ |

\| ENDIF

--------------------------------------

Some other AND-of-ORs examples:

IF (test1 || test2) && test3 ... ELSE ... ENDIF

is written as:

COND

COND <test1> OR-ELSE <test2> OR-IFS

<test3> AND-IF

...

ELSES

...

ENDIF

IF (test1 || test2) && (test3 || test4) ... ELSE ... ENDIF

is written as:

COND

COND <test1> OR-ELSE <test2> OR-IFS

COND <test3> OR-ELSE <test4> OR-IFS

...

ELSES

...

ENDIF

There are 6 new words in total. 3 singular: COND AND-IF OR-ELSE and 3 plural: OR-IFS ELSES ENDIFS. Here's one possible implementation of them.

\ Forth control-flow words for flagless short-circuit conditionals.

\ These work differently from Wil Baden's short-circuit flag-evaluation words,

\ but were inspired by them. -- Dave Keenan, 2019-05-27

\ The 6 words are: COND AND-IF OR-ELSE OR-IFS ELSES ENDIFS

\ Usage:

\ COND <test1> AND-IF <test2> AND-IF <test3> AND-IF ... ENDIFS

\ COND <test1> AND-IF <test2> AND-IF <test3> AND-IF ... ELSES ... ENDIF

\ COND <test1> OR-ELSE <test2> OR-ELSE <test3> OR-IFS ... ENDIF

\ COND <test1> OR-ELSE <test2> OR-ELSE <test3> OR-IFS ... ELSE ... ENDIF

\ COND <test1> AND-IF COND <test2> OR-ELSE <test3> OR-IFS ... ENDIFS

\ COND <test1> AND-IF COND <test2> OR-ELSE <test3> OR-IFS ... ELSES ... ENDIF

\ COND <test1> IF ... ELSE <test2> IF ... ELSE <test3> IF ... ELSE ... ENDIFS

\ Note that exactly one plural word is required to resolve each COND.

\ Use ENDIFS for an else-if chain, OR-IFS for a short-circuit OR,

\ and either ELSES or ENDIFS for a short-circuit AND.

\ The following 5 control-flow-stack helper words are implementation dependent.

\ This version is for gForth, which uses 3 cells on the data stack

\ for each control-flow stack item.

6 CONSTANT cs-marker

: cs-push-marker ( -- cs ) 0 0 cs-marker ;

: cs-not-marker? ( cs -- cs f ) dup cs-marker <> ;

: cs-drop ( cs -- ) drop 2drop ;

: cs-swap ( cs1 cs2 -- cs2 cs1 ) 5 roll 5 roll 5 roll ;

\ The 6 control-flow words for doing short-circuit conditionals:

: COND  ( -- ) ( CS: -- cond_marker )

\ Begin a short-circuit conditional of any kind

cs-push-marker

; immediate compile-only

: AND-IF  ( f -- ) ( CS: -- and_if_origin )

\ Short circuit AND condition

POSTPONE if

; immediate compile-only

: OR-ELSE  ( f -- ) ( CS: -- or_else_origin )

\ Short circuit OR condition except last

POSTPONE 0= \ Ideally we'd use a single 0=-?branch primitive

POSTPONE if

; immediate compile-only

: end-prior-ifs  ( -- ) ( CS: cond_marker orig1 orig2 ... origN -- origN )

\ Helper for OR-IFS and ELSES

\ Resolves all prior IFs back to the preceding COND

BEGIN

cs-swap \ Get the prior IF, or marker, on top

cs-not-marker?

WHILE \ While not the marker put there by COND

POSTPONE endif \ Compile an ENDIF

REPEAT

cs-drop \ Drop the marker

;

: OR-IFS  ( condition_code -- )

          ( CS: cond_marker orig1 orig2 ... origN --- or_if_origin)

\ Last short-circuit OR condition

POSTPONE if \ Compile an IF

end-prior-ifs \ Resolve all prior IFs back to COND

; immediate compile-only

: ELSES  ( -- ) ( CS: cond_marker orig1 orig2 ... origN --- else_origin)

\ Used in place of ELSE for short-circuit AND.

POSTPONE else \ Compile an ELSE

end-prior-ifs \ Resolve all prior IFs back to COND

; immediate compile-only

: ENDIFS  ( -- ) ( CS: cond_marker orig1 orig2 ... origN --- )

\ Plural of ENDIF for short-circuit-AND with no ELSES

\ Resolves multiple IFs or ELSEs back to the preceding COND

BEGIN

cs-not-marker? WHILE \ While not the marker put there by COND

POSTPONE endif \ Compile an ENDIF

REPEAT

cs-drop \ Drop the marker

; immediate compile-only

David N. Williams, agrees that "ELSES" is the right name for that function. He beat me to it by many years.

http://www.umich.edu/~williams/archive/forth/strings/expr.html#templates

And once we have ELSES, the short-circuit AND is done. It's obvious enough to use AND-IF as an alias for IF, to make it more readable, and to use the hyphenated form to distinguish it from Wil's ANDIF.

I found the naming of the words for the short-circuit OR more difficult to get right. Wil used ORIF, while Williams and Harralson used NIF, but for the most efficient implementation of flagless s/c OR, the last OR condition must be treated differently from the others. Its branch condition is un-inverted where the others are inverted, and it must resolve the branches from the preceding conditions. When I used the name "OR-ELSE" for the preceding conditions, and the plural "OR-IFS" for the last condition, I felt it finally made sense to read.

But as dxforth points out, it’s still not easy to remember how to write these structures. I have trouble with that myself when I haven’t used them for a while. There is some mnemonic value in the fact that the two OR-specific words begin with “OR-“ and the three COND-resolving words end in “S”. Beyond that, my only solution is to look them up. I’d be happy to hear suggestions for other mnemonic schemes, in particular one that would include using IF-ANY instead of OR-IFS.

It’s clear that there is no real demand for flagless short-circuit conditionals in Forth, or they would have been standardised long ago. As dxforth points out, Forth automatically leaves the result of each test as a flag on the stack which facilitates combination. But I first developed these for use with assembly language, where this is not the case, and where you usually care more about speed. I thought it might be easier for Forth programmers to understand how they work, if I first gave an implementation for high-level Forth, rather than for a Forth assembler. Perhaps this was misguided. An implementation for a Forth assembler is given below.

An important property of the short-circuit structures defined in this document, is that they generate code that is as fast as that generated by a C compiler or an experienced assembly-language programmer. There are no redundant ELSEs, i.e. no unconditional-branches that can only be reached by other branches.

\ MSP430 Forth assembler control-flow words for short-circuit conditionals
\ -- Dave Keenan, 2019-05-29
\
\ Assumes existing definitions for IF, ELSE, ENDIF,
\ and the condition codes NZ Z NC LO HS NN GE L
\
\ The 6 new control-flow words are:

\ COND, AND-IF, OR-ELSE, OR-IFS, ELSES, ENDIFS,
\ Usage:
\ COND, <tst1> cc1 AND-IF, <tst2> cc2 AND-IF, <tst3> cc3 AND-IF, ... ENDIFS,
\ COND, <tst1> cc1 AND-IF, <tst2> cc2 AND-IF, <tst3> cc3 AND-IF,

\ ... ELSES, ... ENDIF,
\ COND, <tst1> cc1 OR-ELSE, <tst2> cc2 OR-ELSE, <tst3> cc3 OR-IFS, ... ENDIF,
\ COND, <tst1> cc1 OR-ELSE, <tst2> cc2 OR-ELSE, <tst3> cc3 OR-IFS,

\ ... ELSE, ... ENDIF,
\ COND, <tst1> cc1 AND-IF, COND, <tst2> cc2 OR-ELSE, <tst3> cc3 OR-IFS,

\ ... ENDIFS,
\ COND, <tst1> cc1 AND-IF, COND, <tst2> cc2 OR-ELSE, <tst3> cc3 OR-IFS,

\ ... ELSES, ... ENDIF,
\ COND, <tst1> cc1 IF, ... ELSE, <tst2> cc2 IF, ... ELSE, <tst3> cc3 IF,

\ ... ELSE, ... ENDIFS,

\ Note that exactly one plural word is required to resolve each COND,.

\ Use ENDIFS, for an else-if chain, OR-IFS, for a short-circuit OR,

\ and either ELSES, or ENDIFS, for a short-circuit AND.

HEX

5000 CONSTANT N     \ N condition code is only for use with OR-ELSE,

                    \ Other condition codes are already defined as the

                    \ jump instruction with the opposite condition.

                    \ There is no JNN instruction for the MSP430.

: inv-cc            \ Invert a condition code. Used by OR-ELSE,

    CASE

        NZ OF  Z ENDOF

         Z OF NZ ENDOF

        NC OF  C ENDOF  \ "C" remains twelve and is special-cased by IF,

         C OF NC ENDOF

      \ LO OF HS ENDOF  \ LO is the same as NC

        HS OF LO ENDOF

        NN OF  N ENDOF

         N OF NN ENDOF

        GE OF  L ENDOF

         L OF GE ENDOF

        0 swap

    ENDCASE             \ Because ENDCASE does a DROP

\ The 6 control-flow words for doing assembler short-circuit conditionals:

: COND,  ( -- ) ( CS: -- 0 )

    \ Begin a short-circuit conditional of any kind

    0                       \ Push a zero marker

: AND-IF,  ( condition_code -- ) ( CS: -- and_if_origin )

    \ Short circuit AND condition

if,

: OR-ELSE,  ( condition_code -- ) ( CS: -- or_else_origin )

    \ Short circuit OR condition except last

    inv-cc

if,

: ENDIFS,  ( -- ) ( CS: 0 orig1 orig2 ... origN -- )

    \ Plural of ENDIF for short-circuit-AND with no ELSES

    \ Resolves multiple IF,s or ELSE,s back to the preceding COND,

    BEGIN

    dup WHILE               \ While not the zero marker put there by COND,
        endif,                  \ Assemble an ENDIF,
    REPEAT
    drop                    \ Drop the zero marker
    ;

: OR-IFS,  ( condition_code -- ) ( CS: 0 orig1 orig2 ... origN -- or_if_orig)

    \ Last short-circuit OR condition

    if,                    \ Assemble an IF,

    >R                     \ Hide the origin of the above IF,

endifs, \ Resolve all prior IF,s back to COND,

R> \ Restore the origin of the above IF,

: ELSES,  ( condition_code -- ) ( CS: 0 orig1 orig2 ... origN -- else_orig)

    \ Used in place of ELSE, for short-circuit AND

    else,                  \ Assemble an ELSE,

    >R                     \ Hide the origin of the above ELSE,

endifs, \ Resolve all prior IF,s back to COND,
R> \ Restore the origin of the above ELSE,

;

-- Dave Keenan, 2019-May-29 (last updated 2019-Jun-02)