Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #45424

Short-circuit evaluation (was: The extended Eaker-Pelc CASE ...)

Show all headers | View raw

JennyB <jennybrien@googlemail.com> writes:
>On Monday, 8 February 2016 18:31:15 UTC, Anton Ertl  wrote:
>> JennyB <jennybrien@googlemail.com> writes:
>> >On Monday, 8 February 2016 14:23:47 UTC, Anton Ertl  wrote:
>> >> Also, if we are going for representing conditions by using
>> >> control-flow, I think we should also eliminate the IF at the end and
>> >> the flag that controls it.  Maybe something along the lines of
>> >>=3D20
>> >> MULTI-COND
>> >>   cond1 -COND
>> >>   cond2 +COND
>> >>   cond3 +COND
>> >>   code-when-all-satisfied
>> >> OTHERWISE
>> >>   code-when-one-cond-failed
>> >> THEN
>> >>=3D20
>> >I don't see there how you would distinguish between the last condition a=
>nd =3D
>> >the code that follows it.
>>=20
>> If all of the conds match, you fall through to
>> CODE-WHEN-ALL-SATISFIED.  OTHERWISE is like ELSE, but it resolves all
>> the CONDs since MULTI-COND (or maybe there should just be a FIRST-COND
>> instead).
>>=20
>Now I look back at my old files, I see I did attempt something like this th=
>ree years ago.
>
>Wil's ANDIF is simply=20
>
>]] DUP IF DROP [[=20
>branching forwards on condition false=20
>
>and his ORIF  ]] DUP 0=3D IF DROP [[
>branching forwards on condition true
>
>producing the syntax
>
>  condition1 ORIF condition2 THEN IF  action THEN
>
>where condition can be any phrase that results in a flag.

This does not execute condition2 if condition1 is true, but it
performs two IFs in any case.  The second IF will probably predict
very well on a big CPU for the case where condition1 is true.

The other implementation disadvantage is that with a
not-too-sophisticated implementation you need to turn the flag into a
cell instead of optimizing, say, = IF into CMP JNE (something that
even relatively simple compilers manage), and this costs extra on
architectures with condition code registers (most popular ones, MIPS
is probably the best-known exception, and even MIPS has no instruction
for generating the equality flag in a register).

>I came up with this flagless version:
>
>: EITHER  1 cs-roll POSTPONE THEN ; IMMEDIATE
>
>condition1 IF ELSE condition2 IF EITHER action THEN
>
>Using ELSE in this fashion may seem odd and inefficient

IF ELSE should be replacable with 0= IF, but that may be not so great
for readability.

>What is missing from the CS wordset is a way, as with ENDCASE, to resolve a=
>ll remaining origs after a declared start to a common end-point (dests are =
>only ever resolved one at a time). Let's assume we have CS-MARK to mark the=
> start of such a structure and n CS-RESOLVE to close it, leaving the top n =
>items on the CS-STACK unchanged.
>
>Then=20
>    : COND  cs-mark ; immediate
>    : THENCE 0 cs-resolve ; immediate
>    : WHENCE 1 cs-resolve ; immediate
>
>COND and THENCE can be used with ANDIF and ORIF to define multipart conditi=
>ons (where the stack effects are tractable)
>
> A and ( B or ( C and D and E) or F)=20
>
> COND A andif  B orif=20
>   COND C andif D andif E THENCE orif F THENCE
>      =20
> (A and  B) or ( C and D and (E or F))=20
>
>COND A andif B THENCE ORIF
>  COND C andif D andif=20
>    COND E orif F THENCE
>  THENCE
>
>There is no easy flagless equivalent, though it is trivial to AND condition=
>s
>
>   COND A IF B IF C IF action THENCE
>
>or to OR them
>   =20
>  COND A IF ELSE
>       B IF ELSE
>       C IF WHENCE action THEN
>
>But ORs short-circuit to YES and ANDs to NO, so in the general case you wou=
>ld need to keep track of two different types of forward branches. Possible,=
> maybe, but worth doing?

For keeping the stack clean, probably not, because the flags are not
in the way in Wil Baden's approach.  For getting good code with low
compiler complexity, maybe; even if you introduce a few ELSE-like
things, an optimization for eliminating that is probably more often
useful than one for optimizing Wil Baden's approach.  Of course, one
has to balance that against the higher complexity at the Forth level.

As for keeping track of two kinds of forward branches: We already have
LEAVE where an unknown number of forward branches are resolved at
once, maybe we also need a multi-orig to which you can add forward
branches that jump to the same target.  Once we have that, we can
represent the YES and NO by two such multi-origs.  I have not thought
it through completely, but it seems workable.

I also have an implementation idea for such a multi-orig in
combination with Gforth's automatic locals: Every time we add another
orig to the multi-orig, we take the intersection of the locals of the
old multi-orig and the new orig; so we need to keep only one set of
locals around, the branches themselves can be linked together like in
the classical LEAVE implementation.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2015: http://www.rigwit.co.uk/EuroForth2015/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-06 18:15 +0000
  Re: The extended Eaker-Pelc CASE as general control structure JennyB <jennybrien@googlemail.com> - 2016-02-07 03:57 -0800
    Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 12:59 +0000
      Re: The extended Eaker-Pelc CASE as general control structure JennyB <jennybrien@googlemail.com> - 2016-02-08 09:48 -0800
        Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 18:10 +0000
          Re: The extended Eaker-Pelc CASE as general control structure JennyB <jennybrien@googlemail.com> - 2016-02-09 14:02 -0800
            Short-circuit evaluation (was: The extended Eaker-Pelc CASE ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-10 16:10 +0000
  Re: The extended Eaker-Pelc CASE as general control structure "WJ" <w_a_x_man@yahoo.com> - 2016-02-07 14:32 +0000
  Re: The extended Eaker-Pelc CASE as general control structure "WJ" <w_a_x_man@yahoo.com> - 2016-02-07 14:53 +0000
    Re: The extended Eaker-Pelc CASE as general control structure Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-07 15:56 +0000
      Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-07 18:11 +0000
        Re: The extended Eaker-Pelc CASE as general control structure "HAA" <someone@microsoft.com> - 2016-02-08 12:04 +1100
          Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-08 10:29 +0000
            Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 11:00 +0000
              Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-08 12:28 +0000
                Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 15:26 +0000
                Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-08 16:16 +0000
                Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 16:37 +0000
                Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 16:21 +0000
            Re: The extended Eaker-Pelc CASE as general control structure "HAA" <someone@microsoft.com> - 2016-02-11 21:12 +1100
              Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-11 10:46 +0000
      Re: The extended Eaker-Pelc CASE as general control structure JennyB <jennybrien@googlemail.com> - 2016-02-07 12:33 -0800
        Re: The extended Eaker-Pelc CASE as general control structure stephen@mpeforth.com (Stephen Pelc) - 2016-02-08 10:38 +0000
  Re: The extended Eaker-Pelc CASE as general control structure "HAA" <someone@microsoft.com> - 2016-02-08 12:07 +1100
    Re: The extended Eaker-Pelc CASE as general control structure anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2016-02-08 11:11 +0000
      Re: The extended Eaker-Pelc CASE as general control structure Albert van der Horst <albert@spenarnc.xs4all.nl> - 2016-02-08 14:49 +0000
      Re: The extended Eaker-Pelc CASE as general control structure "HAA" <someone@microsoft.com> - 2016-02-09 20:31 +1100
        Re: The extended Eaker-Pelc CASE as general control structure hughaguilar96@gmail.com - 2016-02-09 12:38 -0800
      Re: The extended Eaker-Pelc CASE as general control structure "WJ" <w_a_x_man@yahoo.com> - 2016-02-11 14:23 +0000
        Re: The extended Eaker-Pelc CASE as general control structure "WJ" <w_a_x_man@yahoo.com> - 2016-02-11 19:45 +0000

csiph-web