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

Groups > comp.lang.forth > #45329 > unrolled thread

The extended Eaker-Pelc CASE as general control structure

Back to article view | Back to comp.lang.forth

Contents

  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

Page 1 of 2  [1] 2  Next page →

#45329 — The extended Eaker-Pelc CASE as general control structure

A few weeks agod we were discussing (again) about using

begin .. while .. while .. again then then

and other ways to program multi-exit loops.  Someone pointed out
(again) that a generalized CASE achieves this in a nicer way.  At that
time I concluded that we probably don't really need this, based on the
observation that I had implemented it, but not used it.  I then looked
at my mails and postings, and found (again) that the CASE
implementation of Gforth is not standard-conformant (being based on
the flawed implementation in Section A.3.2.3.2 in the standard).  I
also found that the then-current implementation of the extended CASE
in Gforth was a little more complex than necessary.

So I set about to implement CASE again, in a standard-conformant way,
and while I was at it, also implemented the extensions.  The
extensions are three relatively simple words: ?OF, NEXT-CASE, and
CONTOF.

Given the relative cheapness in implementation and documentation, I
reconsidered my verdict: While one may rarely need the extensions,
they cost little, and IMO the benefit over the other approaches is
sufficient to justify them.  More on that below.

The new implementation is written in almost-standard Forth; it assumes
that control-flow stack items are on the data stack (at least
partially).  It has been tested and works on Gforth, SwiftForth, and
VFX.  You can find it in the package
<http://theforth.net/package/compat/current.zip> in file caseext.fs;
or, if you want to look at the source code, look at
<http://theforth.net/package/compat/current-view/caseext.fs>.

On the benefits: Consider a loop with three exit conditions, with a
different action necessary on each exit, and afterwards a common
action is necessary.  With the extended CASE you can write this as

case
  condition1 ?of exit-action1 endof
  condition2 ?of exit-action2 endof
  condition3 ?of exit-action3 endof
  ...
next-case
common-action

If you want to do this with EXIT or a multi-WHILE loop, things get
cumbersome.  Of course, Forthers often try to rationalize such
problems as encouraging factoring or somesuch, but if it really is
better factoring, do you really need to restrict your tools to achieve
this; and the workarounds for such problems are not always better
factoring.

That example does not demonstrate CONTOF: CONTOF is useful if you have
different iteration actions depending on the condition.  Here's an
example:

: gcd ( n1 n2 -- n )
    case
        2dup > ?of tuck - contof
        2dup < ?of over - contof
    endcase ;

Here the two ?OFs have different ways of continuing the loop; when
neither ?OF triggers, the two numbers are equal and are the gcd.
ENDCASE drops one of them, leaving the other as n (usually the
dropping nature of ENDCASE is a nuissance in combination with ?OF,
here it happens to work out).

Note that this kind of CASE usage is similar to Dijsktra's guarded
command "do", and
<https://en.wikipedia.org/wiki/Guarded_Command_Language#Original_Euclidean_algorithm>
gives the same algorithm as example.

And here's an example where the all words except ENDCASE are used:

: collatz ( u -- )
    \ print the 3n+1 sequence starting at u until we reach 1
    case
        dup .
        1 of endof
        dup 1 and ?of 3 * 1+ contof
        2/
    next-case ;

This example keeps the current value of the sequence on the stack.  If
it is 1, the OF triggers, drops the value, and leaves the
CASE structure.  For odd numbers, the ?OF triggers,
computes 3n+1, and starts the next iteration with CONTOF.
Otherwise, if the number is even, it is divided by 2, and the loop is
restarted with NEXT-CASE.

If you are a word-saver, you can note that ?OF is an alias of IF, and
one could do without it (however, IMO ?OF makes the intention
clearer).  Also, one could do without CONTOF (or alternatively without
NEXT-CASE) without losing generality (but one would lose conciseness
of expression).  But I think that three words is cheap enough.

But I already saved some words compared to what's currently in VFX:
CASE also has the function of VFX's BEGINCASE; and I only have ENDCASE
(no END-CASE) and NEXT-CASE (no NEXTCASE); I chose these because
ENDCASE is entrenched, and NEXT-CASE appears more useful than NEXTCASE
(which drops a value).

Credits: AFAIK the idea to generalize CASE, and for ?OF and NEXT-CASE
came from Stephen Pelc, and has been implemented in a similar way in
VFX for quite some time; the original CASE came from Chuck Eaker.

- 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/

[toc] | [next] | [standalone]

#45332

On Saturday, 6 February 2016 18:55:16 UTC, Anton Ertl  wrote:
> A few weeks agod we were discussing (again) about using
> 

> So I set about to implement CASE again, in a standard-conformant way,
> and while I was at it, also implemented the extensions.  The
> extensions are three relatively simple words: ?OF, NEXT-CASE, and
> CONTOF.
> 
> Given the relative cheapness in implementation and documentation, I
> reconsidered my verdict: While one may rarely need the extensions,
> they cost little, and IMO the benefit over the other approaches is
> sufficient to justify them.  More on that below.
> 
> The new implementation is written in almost-standard Forth; it assumes
> that control-flow stack items are on the data stack (at least
> partially).  It has been tested and works on Gforth, SwiftForth, and
> VFX.  You can find it in the package
> <http://theforth.net/package/compat/current.zip> in file caseext.fs;
> or, if you want to look at the source code, look at
> <http://theforth.net/package/compat/current-view/caseext.fs>.
>
THe obvious way to do this (and the way you have in fact done it) means that CONTOF and ENDOF do not need to be enclosed in a CASE statement (they are simply Continue and Break respectively in any uncounted loop), and OF can be used instead of DUP IF DROP

To completely integrate Eaker's Case into the control structure wordset we should expose the factor UNCASE, such that:

       : ENDCASE POSTPONE DROP POSTPONE UNCASE ; IMMEDIATE 

That gives us simple ANDifs

   CASE 
     cond1 IF
      ...
     cond n IF

     action
   UNCASE

 And Wil Baden's short-circuiting ORIF and AND IF

  If cond1 or (cond2 and cond3)

   CASE
    cond1 FALSE OF
    cond2 TRUE OF
    cond3
   UNCASE
    IF


> On the benefits: Consider a loop with three exit conditions, with a
> different action necessary on each exit, and afterwards a common
> action is necessary.  With the extended CASE you can write this as
> 
> case
>   condition1 ?of exit-action1 endof
>   condition2 ?of exit-action2 endof
>   condition3 ?of exit-action3 endof
>   ...
> next-case
> common-action
> 
> If you want to do this with EXIT or a multi-WHILE loop, things get
> cumbersome.  Of course, Forthers often try to rationalize such
> problems as encouraging factoring or somesuch, but if it really is
> better factoring, do you really need to restrict your tools to achieve
> this; and the workarounds for such problems are not always better
> factoring.
> 
> That example does not demonstrate CONTOF: CONTOF is useful if you have
> different iteration actions depending on the condition.  Here's an
> example:
> 
> : gcd ( n1 n2 -- n )
>     case
>         2dup > ?of tuck - contof
>         2dup < ?of over - contof
>     endcase ;
> 
> Here the two ?OFs have different ways of continuing the loop; when
> neither ?OF triggers, the two numbers are equal and are the gcd.
> ENDCASE drops one of them, leaving the other as n (usually the
> dropping nature of ENDCASE is a nuissance in combination with ?OF,
> here it happens to work out).

It works here, but more generally:

     begin
       cond1 if action contof
       ...
       condn while action repeat
     final_action

Maybe Continue is a better name for Contof?

> : collatz ( u -- )
>     \ print the 3n+1 sequence starting at u until we reach 1
>     case
>         dup .
>         1 of endof
>         dup 1 and ?of 3 * 1+ contof
>         2/
>     next-case ;
> 
Case is only needed where there is more than one Endof (While is equivalent to 0= If Endof)

       begin
           dup .
           1 of endof
           dup 1 and if 3 * 1+ continue
           2/
        repeat


> If you are a word-saver, you can note that ?OF is an alias of IF, and
> one could do without it (however, IMO ?OF makes the intention
> clearer).  Also, one could do without CONTOF (or alternatively without
> NEXT-CASE) without losing generality (but one would lose conciseness
> of expression).  But I think that three words is cheap enough.

The options I see (provided OF is available outside CASE)

CASE ... UNCASE is used only to resolve forward branches. The basic Eaker Case is unchanged. ENDOF is a synonym for ELSE

New words:  UNCASE CONTINUE BREAK (for the new use of Endof)  

New structure is (CASE) BEGIN (IF/OF...CONTINUE/BREAK) AGAIN/REPEAT/UNTIL (THEN/UNCASE)

Alternatively:

CASE always includes an implicit BEGIN, which UNCASE removes.  ENDOF is a synonym of BREAK. This is compatible with the above, but also allows NEXT-CASE/UNCASE/ENDCASE without an explicit BEGIN.

I prefer the first alternative.  If you are going to have uncounted looping of any form, you should signal it with an explicit BEGIN.

[toc] | [prev] | [next] | [standalone]

#45360

JennyB <jennybrien@googlemail.com> writes:
>THe obvious way to do this (and the way you have in fact done it) means that CONTOF and ENDOF do not need to be enclosed in a CASE statement (they are simply Continue and Break respectively in any uncounted loop), and OF can be used instead of DUP IF DROP

OF could be used instead of OVER = IF DROP.

And yes, you can use these implementations of ENDOF and CONTOF without
CASE.  I am not sure it is a good idea, though.  We can do everything
with BEGIN AGAIN UNTIL IF AHEAD THEN CS-ROLL, but we usually choose a
more restricted approach (some more restricted, some less restricted);
I guess most programmers are not that keen on thinking about the
control-flow stack and in terms of conditional and unconditional
branches.  They rather prefer to think that, e.g., ENDOF jumps behind
ENDCASE, never mind the control-flow stack.  And I think that using
ENDOF, CONTOF, and NEXT-CASE as intended gives one this simplified,
more abstract world-view.

>
>To completely integrate Eaker's Case into the control structure wordset we should expose the factor UNCASE, such that:
>
>       : ENDCASE POSTPONE DROP POSTPONE UNCASE ; IMMEDIATE 

Your UNCASE is VFX's END-CASE.  My thinking is that I write 0 ENDCASE
when I need that.

>That gives us simple ANDifs
>
>   CASE 
>     cond1 IF
>      ...
>     cond n IF
>
>     action
>   UNCASE

In my implementation, the ENDOFs are needed to deal with the dest that
allows CONTOF and NEXT-CASE to work.

> And Wil Baden's short-circuiting ORIF and AND IF
>
>  If cond1 or (cond2 and cond3)
>
>   CASE
>    cond1 FALSE OF
>    cond2 TRUE OF
>    cond3
>   UNCASE
>    IF

Same here.  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

MULTI-COND
  cond1 -COND
  cond2 +COND
  cond3 +COND
  code-when-all-satisfied
OTHERWISE
  code-when-one-cond-failed
THEN

A disadvantage of control-flow-based approaches for combining
conditions is that we get more control flow paths to test.  For
multi-exit loops with different exit actions that's unavoidable, but
for this kind of code it is not; however, this disadvantage may be
balanced by simpler data stack handling (only very short-lived flags
on the data stack).

How would one implement this in the context of CASE?

CASE
  cond1 ?OF ENDOF
  cond2 0= ?OF ENDOF
  cond3 0= ?OF ENDOF
  action-when-all-satisfied
AHEAD [ SAVE-ORIG ] ENDCASE
  actions-when-one-cond-failed
[ RESTORE-ORIG ] THEN

We are not quite there.  More generally, if we want to use the
control-flow method of dealing with multiple conditions, we would need
to be able to express that one (or both?) of the two resulting actions
are again conditions on whose result we want to jump again to one of
two actions, which may again be conditions.  I don't have a good idea
how to express this nicely.

>It works here, but more generally:
>
>     begin
>       cond1 if action contof
>       ...
>       condn while action repeat
>     final_action
>
>Maybe Continue is a better name for Contof?

CONTINUE does not make it clear that it concludes the OF/IF part; it
certainly does not in C.

>The options I see (provided OF is available outside CASE)
>
>CASE ... UNCASE is used only to resolve forward branches. The basic Eaker Case is unchanged. ENDOF is a synonym for ELSE

In my implementation it is not.

>New words:  UNCASE CONTINUE BREAK (for the new use of Endof)  
>
>New structure is (CASE) BEGIN (IF/OF...CONTINUE/BREAK) AGAIN/REPEAT/UNTIL (THEN/UNCASE)

That's also an interesting variant.  So we would either write things as

CASE ... OF/IF ... ENDOF ... OF/IF ... ENDOF ... ENDCASE

or 

CASE BEGIN ... OF/IF ... BREAK/CONTINUE ... OF/IF ... BREAK/CONTINUE ... AGAIN ENDCASE

NEXT-CASE would become unnecessary, but you introduce the need for
BREAK.  CONTINUE is just the same as CONTOF, and IF is the same as
?OF, and UNCASE is 0 ENDCASE.  So, in word-counting mode, we have not
reduced the number of words necessary.  Is it clearer than the
extended CASE I suggested?

>Alternatively:
>
>CASE always includes an implicit BEGIN, which UNCASE removes.  ENDOF is a synonym of BREAK. This is compatible with the above, but also allows NEXT-CASE/UNCASE/ENDCASE without an explicit BEGIN.

Yes, that's what I proposed and implemented, modulo name variations.

- 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/

[toc] | [prev] | [next] | [standalone]

#45372

On Monday, 8 February 2016 14:23:47 UTC, Anton Ertl  wrote:
> JennyB <jennybrien@googlemail.com> writes:

> 
> Your UNCASE is VFX's END-CASE.  My thinking is that I write 0 ENDCASE
> when I need that.

Fair enough. I was thinking that there were enough uses for it to be given its own name, and I always get confused between ENDCASE and END-CASE (and similar pairs)
> 
> >That gives us simple ANDifs
> >
> >   CASE 
> >     cond1 IF
> >      ...
> >     cond n IF
> >
> >     action
> >   UNCASE
> 
> In my implementation, the ENDOFs are needed to deal with the dest that
> allows CONTOF and NEXT-CASE to work.

So I realised later :(  But if we separate the functions and use an explicit BEGIN for loops, it does work.
> 
> > And Wil Baden's short-circuiting ORIF and AND IF
> >
> >  If cond1 or (cond2 and cond3)
> >
> >   CASE
> >    cond1 FALSE OF
> >    cond2 TRUE OF
> >    cond3
> >   UNCASE
> >    IF
> 
> Same here.  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
> 
> MULTI-COND
>   cond1 -COND
>   cond2 +COND
>   cond3 +COND
>   code-when-all-satisfied
> OTHERWISE
>   code-when-one-cond-failed
> THEN
> 
I don't see there how you would distinguish between the last condition and the code that follows it. It seems simpler to think of the CASE block as returning a unified flag.  I had a lot of trouble getting my head round ANDIF and ORIF until I realised that there is no need to test further after a true OR or a false AND.

> 
> CONTINUE does not make it clear that it concludes the OF/IF part; it
> certainly does not in C.

My mistake then, but I don't see how it could be otherwise.
> 
> >The options I see (provided OF is available outside CASE)
> >
> >CASE ... UNCASE is used only to resolve forward branches. The basic Eaker Case is unchanged. ENDOF is a synonym for ELSE
> 
> In my implementation it is not.
> 
> >New words:  UNCASE CONTINUE BREAK (for the new use of Endof)  
> >
> >New structure is (CASE) BEGIN (IF/OF...CONTINUE/BREAK) AGAIN/REPEAT/UNTIL (THEN/UNCASE)
> 
> That's also an interesting variant.  So we would either write things as
> 
> CASE ... OF/IF ... ENDOF ... OF/IF ... ENDOF ... ENDCASE
> 
> or 
> 
> CASE BEGIN ... OF/IF ... BREAK/CONTINUE ... OF/IF ... BREAK/CONTINUE ... AGAIN ENDCASE
> 
> NEXT-CASE would become unnecessary, but you introduce the need for
> BREAK.  CONTINUE is just the same as CONTOF, and IF is the same as
> ?OF, and UNCASE is 0 ENDCASE.  So, in word-counting mode, we have not
> reduced the number of words necessary.  Is it clearer than the
> extended CASE I suggested?


Possibly not. Mine allows the familiar loop structures to be extended by adding extra IF .. CONTINUE of IF ... BREAK clauses and only needs a surrounding CASE if there more than one BREAKs.  If there are not more than one, then it isn't a  CASE as normally understood. 

However, having a WHILE (or BREAK) resolved outside its enclosing loop seems to trouble a lot of people. Consider the possible:

   WHILE   ... UNTIL  ... THEN

in an extended CASE this would be:

   WHILE ...   0= ?OF CONTOF   ...  ENDCASE 

   where I might write

   WHILE  ... UNTIL ... UNCASE

in fact, I have to write  AGAIN or UNTIL for the final loop, and could if I were so minded, put a THEN or ELSE between it and UNCASE. That would probably not be a good idea.

[toc] | [prev] | [next] | [standalone]

#45373

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
>>=20
>> MULTI-COND
>>   cond1 -COND
>>   cond2 +COND
>>   cond3 +COND
>>   code-when-all-satisfied
>> OTHERWISE
>>   code-when-one-cond-failed
>> THEN
>>=20
>I don't see there how you would distinguish between the last condition and =
>the code that follows it.

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).

>It seems simpler to think of the CASE block as re=
>turning a unified flag.  I had a lot of trouble getting my head round ANDIF=
> and ORIF until I realised that there is no need to test further after a tr=
>ue OR or a false AND.

Yes.  Now, the general case for compiling any arbitrarily deeply
nested conditional expression with short-circuit operators is to
realize that you always only have two branch targets: one for true,
and one for false.  If you have

condition IF ( A ) ... ELSE ( B ) ... THEN

then the general target for true is A and for FALSE is B.  No need to
push flags on the stack across a longer distance.  When you have just
a sequence of ANDIFs or ORIFs, you only need to consider these two
targets.  When you have some nested conditional, you may get different
true and false targets for sub-expressions.

One advantage of this approach would be that it reduces the stack
depth at run-time (at the cost of increased compile-time control-flow
stack depth).  Disadvantages are a potential for more branch
mispredictions and the testing disadvantage I mentioned.  I don't know
of a syntax and implementation for the general case, however.

>> CONTINUE does not make it clear that it concludes the OF/IF part; it
>> certainly does not in C.
>
>My mistake then, but I don't see how it could be otherwise.

Yes, in Forth it's the only way that makes sense, but it still has a
different meaning than in C, so I chose a different name.

>Possibly not. Mine allows the familiar loop structures to be extended by ad=
>ding extra IF .. CONTINUE of IF ... BREAK clauses and only needs a surround=
>ing CASE if there more than one BREAKs.

I don't consider that an advantage.  Then someone wants to add another
case, and needs to change the whole loop.  And when reading the code,
it produces more variation for no gain.

- 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/

[toc] | [prev] | [next] | [standalone]

#45416

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
> >>=20
> >> MULTI-COND
> >>   cond1 -COND
> >>   cond2 +COND
> >>   cond3 +COND
> >>   code-when-all-satisfied
> >> OTHERWISE
> >>   code-when-one-cond-failed
> >> THEN
> >>=20
> >I don't see there how you would distinguish between the last condition and =
> >the code that follows it.
> 
> 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).
> 
Now I look back at my old files, I see I did attempt something like this three years ago.

Wil's ANDIF is simply 

]] DUP IF DROP [[ 
branching forwards on condition false 

and his ORIF  ]] DUP 0= 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.

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, but it works very well for readibility, especially in a CASE where tests need to preserve a selector that matches only one of them, but two tests produce the same result.

For example:

: RANGE  ]] 2>R DUP 2R> WITHIN IF DROP [[ ; IMMEDIATE

   0  20 range else 
       7F of either ." Control char " endof
          

using ORIF:

  dup 0 20 within orif 
  dup 7f = then ?of drop  ." Control char " endof

seems more low-level, since it cannot use RANGE or OF as factors.

What is missing from the CS wordset is a way, as with ENDCASE, to resolve all 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 
    : 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 conditions (where the stack effects are tractable)

 A and ( B or ( C and D and E) or F) 

 COND A andif  B orif 
   COND C andif D andif E THENCE orif F THENCE
       
 (A and  B) or ( C and D and (E or F)) 

COND A andif B THENCE ORIF
  COND C andif D andif 
    COND E orif F THENCE
  THENCE

There is no easy flagless equivalent, though it is trivial to AND conditions

   COND A IF B IF C IF action THENCE

or to OR them
    
  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 would need to keep track of two different types of forward branches. Possible, maybe, but worth doing?

[toc] | [prev] | [next] | [standalone]

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

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/

[toc] | [prev] | [next] | [standalone]

#45336

Anton Ertl wrote:

> : gcd ( n1 n2 -- n )
>     case
>         2dup > ?of tuck - contof
>         2dup < ?of over - contof
>     endcase ;

Oforth:

: gcd3
  while (2dup <>) [2dup min tor max over -] drop ;

-- 
Amazon bans book.  After nearly a month on the site, all traces of the book and
its 80 reviews have been removed.
http://jamesfetzer.blogspot.com/2015/11/debunking-sandy-hook-debunkers-5.html
https://www.youtube.com/watch?v=EEl_1HWFRfo

[toc] | [prev] | [next] | [standalone]

#45337

Anton Ertl wrote:

> : collatz ( u -- )
>     \ print the 3n+1 sequence starting at u until we reach 1
>     case
>         dup .
>         1 of endof
>         dup 1 and ?of 3 * 1+ contof
>         2/
>     next-case ;

Ruby:

def collatz n
  n = n.odd? ? n*3+1 : n/2 while (print n, " "; n>1)
end

collatz 22
22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

-- 
The report card by the American Society of Civil Engineers showed the national
infrastructure a single grade above failure, a step from declining to the point
where everyday things simply stop working the way people expect them to. ---
washingtonpost.com/local/trafficandcommuting/us-infrastructure-gets-d-in-annual-report/2013/03/19/c48cb010-900b-11e2-9cfd-36d6c9b5d7ad_story.html

[toc] | [prev] | [next] | [standalone]

#45338

"WJ" <w_a_x_man@yahoo.com> writes:

>Anton Ertl wrote:

>> : collatz ( u -- )
>>     \ print the 3n+1 sequence starting at u until we reach 1
>>     case
>>         dup .
>>         1 of endof
>>         dup 1 and ?of 3 * 1+ contof
>>         2/
>>     next-case ;

>Ruby:

>def collatz n
>  n = n.odd? ? n*3+1 : n/2 while (print n, " "; n>1)
>end

>collatz 22
>22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

I hate it when CASE is transformed into a disguised loop.
If I'd redesign the Forth looping, I'd totally ignore the pseudo
general control flow stack and I'd go for

do   : start of loop
od   : end of loop:
       if there are loop parameters, increment like LOOP else
       just restart (like AGAIN)

break : formerly leave
continue : restart at start of loop
and then
?break
?continue
with obvious meanings.

setting up loop parameters is a separate issue

The above example becomes
: hail
   DO
      DUP 1 = ?break
      DUP 1 AND IF 3 * 1+ continue THEN
      2/
   OD
   DROP ;

\ Finding an item in a linked list becomes
: find   ( item list -- where/null )
    DO
       DUP 0= ?break
       2DUP >ITEM = ?break
       >next
    OD NIP ;
(This probably beats the usual Forth code.)

We'd have some unused loop parameters here, because there is no
iterator, who cares.

DO OD could be abused as a case, but I doubt that is a good idea,
same as CASE ENDCASE abused as loop.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#45341

On 07 Feb 2016 15:56:16 GMT, Albert van der Horst
<albert@spenarnc.xs4all.nl> wrote:

>I hate it when CASE is transformed into a disguised loop.

There's nothing disguised about the NEXT-CASE solution. It is
explicitly about a loop.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#45343

Stephen Pelc wrote:
> On 07 Feb 2016 15:56:16 GMT, Albert van der Horst
> <albert@spenarnc.xs4all.nl> wrote:
>
> >I hate it when CASE is transformed into a disguised loop.
>
> There's nothing disguised about the NEXT-CASE solution. It is
> explicitly about a loop.
>
> Stephen

Doesn't VFX require BEGINCASE be used with NEXT-CASE ?
The example given in 'Programming Forth' (2011) p.40 specifies
CASE.  Out of date?

[toc] | [prev] | [next] | [standalone]

#45351

On Mon, 8 Feb 2016 12:04:36 +1100, "HAA" <someone@microsoft.com>
wrote:

>Doesn't VFX require BEGINCASE be used with NEXT-CASE ?
>The example given in 'Programming Forth' (2011) p.40 specifies
>CASE.  Out of date?

Originally CASE ... NEXTCASE worked fine. We then changed to BEGINCASE
... NEXTCASE because we could then align the head of the loop for a
then measurable speed improvement. When we next decide to update the
kernel, we'll permit both.

From a standards point of view, just adding NEXTCASE or NEXT-CASE is
preferable because we only add one word.

END-CASE and NEXT-CASE that do not drop the selector are MPEisms, 
just micro-optimisations that nowadays are probably redundant.
Having accepted the original Eaker CASE ... ENDCASE words into
the standard, it would be cleaner for NEXTCASE to behave similarly
to ENDCASE except for the branch. It is very unlikely that the
previous selector will be need on the next iteration of the loop.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#45353

stephen@mpeforth.com (Stephen Pelc) writes:
>END-CASE and NEXT-CASE that do not drop the selector are MPEisms, 
>just micro-optimisations that nowadays are probably redundant.
>Having accepted the original Eaker CASE ... ENDCASE words into
>the standard, it would be cleaner for NEXTCASE to behave similarly
>to ENDCASE except for the branch. It is very unlikely that the
>previous selector will be need on the next iteration of the loop.

On the contrary: It is highly likely that you have a value on the top
of the stack that is needed in the next iteration of the loop; e.g.,
if you traverse a linked list, the address of the next node.  And it
is not very likely that you have some extra value on top of the stack
at that point that you don't need.  That's why I chose to implement
NEXT-CASE, and not NEXTCASE.

I also have received an email from someone who writes that he uses
END-CASE as often as ENDCASE, so even in that context the dropping
behaviour of ENDCASE is not such a good idea; but that was a decision
taken >30 years ago, so we'll have to stick with ENDCASE as it is.

- 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/

[toc] | [prev] | [next] | [standalone]

#45355

On Mon, 08 Feb 2016 11:00:16 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>On the contrary: It is highly likely that you have a value on the top
>of the stack that is needed in the next iteration of the loop; e.g.,
>if you traverse a linked list, the address of the next node.  And it
>is not very likely that you have some extra value on top of the stack
>at that point that you don't need.  That's why I chose to implement
>NEXT-CASE, and not NEXTCASE.

But it is not the selector. How often do you need to reuse the
selector?

>I also have received an email from someone who writes that he uses
>END-CASE as often as ENDCASE, so even in that context the dropping
>behaviour of ENDCASE is not such a good idea; but that was a decision
>taken >30 years ago, so we'll have to stick with ENDCASE as it is.

An interesting email. I have rescanned the VFX tree to count the
occurrences of ENDCASE and END-CASE.
  ENDCASE   772 times
  END-CASE  352 times
It seems that they both justify their existence. However, the
usage conditions for NEXTCASE and NEXT-CASE may well not be the
same. All counts for these were for documentation! My conclusion
is that we only need one of NEXTCASE and NEXT-CASE. I don't mind 
which apart from an aesthetic tendency to NEXTCASE. Perhaps
END-CASE (or some other name) should be added?

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#45364

stephen@mpeforth.com (Stephen Pelc) writes:
>On Mon, 08 Feb 2016 11:00:16 GMT, anton@mips.complang.tuwien.ac.at
>(Anton Ertl) wrote:
>
>>On the contrary: It is highly likely that you have a value on the top
>>of the stack that is needed in the next iteration of the loop; e.g.,
>>if you traverse a linked list, the address of the next node.  And it
>>is not very likely that you have some extra value on top of the stack
>>at that point that you don't need.  That's why I chose to implement
>>NEXT-CASE, and not NEXTCASE.
>
>But it is not the selector. How often do you need to reuse the
>selector?

That assumes you have a selector, which is not necessarily the case in
the presence of ?OF.  But even if you have a selector, usually you
discard it when you compute the loop-carried value(s) for the next
iteration, so by the time you reach the end, it is likely gone.

E.g., if you search through a linked list:

0
field: list-next
field: list-val
drop

: ...
  ( list ) case
    0 of endof \ end of list?
    dup list-val @ ( list1 selector )
    0 of ... endof
    5 of ... endof
    drop list-next @ ( list2 )
  next-case
  ... ;

Despite having a selector in this example, it does not survive until
the end.

The use of OF for the end-of-list test may be misleading (suggesting
that the value checked is the same for all OFs), so it may be better
to use ?OF there.

> Perhaps
>END-CASE (or some other name) should be added?

If so, with a different name; END-CASE is confusing by having the same
pronounciation as ENDCASE, and I suspect that bugs are likely to arise
from having both words.  But for now 0 ENDCASE is good enough for me.

- 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/

[toc] | [prev] | [next] | [standalone]

#45366

On Mon, 08 Feb 2016 15:26:26 GMT, anton@mips.complang.tuwien.ac.at
(Anton Ertl) wrote:

>> Perhaps
>>END-CASE (or some other name) should be added?
>
>If so, with a different name; END-CASE is confusing by having the same
>pronounciation as ENDCASE, and I suspect that bugs are likely to arise
>from having both words.  But for now 0 ENDCASE is good enough for me.

0 ENDCASE works for me too for standardisation.
And presumably 0 NEXTCASE too.

Stephen

-- 
Stephen Pelc, stephenXXX@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads

[toc] | [prev] | [next] | [standalone]

#45368

stephen@mpeforth.com (Stephen Pelc) writes:
>0 ENDCASE works for me too for standardisation.
>And presumably 0 NEXTCASE too.

ENDCASE is already standardized, so there we have little choice.  For
NEXT(-)CASE we have the choice, and standardizing the one that
requires to prepend a 0 for the large majority of uses would be
idiotic.  I am not wedded to the name, though, so if you prefer the
name NEXTCASE for the word that's now called NEXT-CASE, that would be
fine with me (VFX users might not like the change of the meaning of
NEXTCASE, though).  Or if it's just the dash that you dislike, maybe
CONTCASE, AGAINCASE, REPEATCASE, LOOPCASE or somesuch.

- 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/

[toc] | [prev] | [next] | [standalone]

#45367

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>stephen@mpeforth.com (Stephen Pelc) writes:
>>But it is not the selector. How often do you need to reuse the
>>selector?
>
>That assumes you have a selector, which is not necessarily the case in
>the presence of ?OF.  But even if you have a selector, usually you
>discard it when you compute the loop-carried value(s) for the next
>iteration, so by the time you reach the end, it is likely gone.
>
>E.g., if you search through a linked list:
>
>0
>field: list-next
>field: list-val
>drop
>
>: ...
>  ( list ) case
>    0 of endof \ end of list?
>    dup list-val @ ( list1 selector )
>    0 of ... endof
>    5 of ... endof
>    drop list-next @ ( list2 )
>  next-case
>  ... ;
>
>Despite having a selector in this example, it does not survive until
>the end.

Here's an example of a search in a list for a passed value x.  In this
case you can consider x to be the selector.  You need to reuse the
selector in every iteration, so having it dropped at the end of the
iteration does not make sense.

: member? ( list1 x -- list2|0 )
\ list2 is the first node with list-val=x
  case
    over 0= ?of drop endof \ end of list?
    over list-val @ of endof \ x found?
    swap list-next @ swap
  next-case ;

- 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/

[toc] | [prev] | [next] | [standalone]

#45439

Stephen Pelc wrote:
> ...
> From a standards point of view, just adding NEXTCASE or NEXT-CASE is
> preferable because we only add one word.

Standardize?  In the 397 source files included with the VFX demo, not a
single use of NEXTCASE or NEXT-CASE.  Oh yes - Forth desperately
needs this.

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web