Case Statements... 
Author Message
 Case Statements...

I've recently found myself using a lot of nested if statements to try
and get the functionality of a case statement, and it's really ugly.

So I came up with the following use of a loop (uh, I guess I should
mention at this point that the system I'm using/developing isn't a
standard forth.  Actually, it's more like a Forth-Like system, although
I plan on making it ANSI compilant sometime in the near future.  
Anyways, the modifications are using [ for if, ][ for else, and ] for
then, as well as { for the start of a loop, } for the end, >} to break,
and >{ to restart.  The loops don't have an index, so if you want to
break out after a set number of times, you'll need to do something like
15 { 1- dup 0= [ >} ][ your code here ] } )

Anyways...  Here's my problem.
I don't like
: bigifword
dup 15 - 0= [ case1  ][
dup 14 - 0= [ case2  ][
dup 13 - 0= [ case3  ][
..
dup  1 - 0= [ case15 ][
] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ;

So I came up with
: smallerifword {
dup 15 - 0= [ case1  >} ]
dup 14 - 0= [ case2  >} ]
dup 13 - 0= [ case3  >} ]
..
     1 - 0= [ case15 >} ]
errorcase >} } ;

Which seems to me to be a bit of a perversion of the loop construct, so
I was wondering if there was a better way of doing something like this,
or rather if any of you had ways that you prefered (since better is
pretty much arbitrary).

I think I'll probably change it to an array of vectored execution
addresses at some point, which should make it a little simpler...

(maybe I'll put in a little error checking too...  we'll see. ;)

Later,
Blake.



Sat, 05 Feb 2000 03:00:00 GMT  
 Case Statements...

As I recall, FORTH DIMENSIONS has treated approximately 100 (or is it
1,000) versions of CASE statements.  Finding the optimal version appears
to be the main objective in life for many programmers.




Tue, 08 Feb 2000 03:00:00 GMT  
 Case Statements...


Quote:

>> As I recall, FORTH DIMENSIONS has treated approximately 100 (or is it
>> 1,000) versions of CASE statements.  Finding the optimal version appears
>> to be the main objective in life for many programmers.

> My personal search is to avoid CASE statements if possible. Use jump
> tables instead.

Yes, but this is memory inefficient when the input selectors are widely
spaced ( check for ^B, ^Z, 'Q', F1 and F3 ). I've always wondered if
programs exist to generate functions that can map a arbitrary (but
monotonously ascending) row of numbers to a row that increases by 4
(to solve the problem in one step they should map a row of numbers to
a row of function addresses). A restriction is (of course) that the
function must be cheaper to compute than the case construct's n/2
compare+2-branches (on average).

In a far and distant past a CS student once suggested to me that every
C-compiler implemented such a mapping module (Disassembly proved him
wrong for at least the "every" part of the statement).

Case statements (and IF ELSE THEN) could also be improved if Forth
checked, at run-time, which branches are taken most frequently and
modified the code to move them "up front". Anybody implemented
this? Just having the statistics collected is already interesting.

-marcel



Thu, 10 Feb 2000 03:00:00 GMT  
 Case Statements...

Quote:

> Well, off the top of my head, how about some sort of balanced tree? Or a
> hash table? That does not really perform the mapping that you ask for, but
> are standard ways of handling the problem under discussion.

A balanced tree isn't necessary. If you can sort your numbers (or
ranges, it's quite common to have ranges which result in the same
action), build a sorted table (sorted with the strange sort function
that the starting point is at element 0), and if it's smaller, look at
2*(current offset), if it's greater at 2*(current offset)+1. If you can
build a good hash function, do that anyway, it will reduce the number of
required compares even further.

I haven't seen hashed case table, nor have I seen C compilers that
generate the proposed table.

However, this is all fuzz, you can sometimes do much better with Forth.
Case tables are often data driven, and go through these datas more than
once. Assume a ray tracer with several graphic elements. A C programmer
would write

bool intersect(ray, scene)
{
  switch(scene->type) {
  case sphere:
// is |up point from center to ray| < r
  case union:
// for all components intersect(ray, component) until hit
  case intersection:
// for all components intersect(ray, component), true if all hit
...
  }

Quote:
}

This isn't the right solution, since the scene will be the same for all
the 10 million rays you drive through it. A clever Forth programmer will
write

: compile_intersect ( scene -- )
  CASE  sphere  OF  postpone Literal  postpone sphere-intersect  ENDOF
        union   OF  postpone ((
                    elements 0 ?DO  I element  compile_intersect
                                    postpone ||  LOOP
                    postpone  ))  ENDOF
        intersect OF  postpone  ((
                      elements 0 ?DO  I element compile_intersect
                                      &&  LOOP
                      postpone  ))  ENDOF
...
  ENDCASE ;

Now do that with C! I don't know if anybody uses this technique, but
RenderMan, a quite popular commercial ray tracer, uses Forth, and you
can write procedural textures in it. If you have a good Forth compiler,
and the floating point primitives for the intersection of simple
elements are fast and/or can be inlined, you'll certainly beat every
C-based ray tracer.

Improvement: Don't write compile_intersect. Write a scene description
language and let the Forth compiler compile the rendering word(s) for
you. A Union writes as   ((  element ||  elemenet  ||  element  )), an
intersection writes as  ((  element  &&  element  &&  element  )), and
each element just is a Forth word itself. That's what I call avoidance
of case statement, and you've done another complex task at the same time
(complex for the C writer).

I bet that some time in the future, some C or Java compiler will contain
run time code generation for this kind of code. You write your switch
statement as usual, the compiler generates tokens for that (JavaVM
tokens, maybe), and at runtime, the runtime engine reduces all the data
you pass to this function and creates optimized code from it, which is
executed then.

--
Bernd Paysan
"Late answers are wrong answers!"
http://www.informatik.tu-muenchen.de/~paysan/



Thu, 10 Feb 2000 03:00:00 GMT  
 Case Statements...

Blake Winton Wrote:

Quote:
> ...
> So I came up with the following use of a loop (uh, I guess I should
> mention at this point that the system I'm using/developing isn't a
> standard forth.  

How do you implement your forth-like language, threaded code or
native code generation?  This is a very important issue, I think.
I suppose you use threaded code.

Quote:
> Actually, it's more like a Forth-Like system, although
> I plan on making it ANSI compilant sometime in the near future.  

I think the ANSI standard core extension words CASE-ENDCASE and
OF-ENDOF may be the best now, althought it has its own problem.
The standard word OF is defined as:

OF      ( x1 x2 -- | x1 )
IF x1 = x2, discard x1 x2 and continue execution in line, otherwise,
discard x2 and jump to the word following the word ENDOF.

The cell x1 is on the stack almost in every case.  Why not put x1 onto
the return stack and define the words CASE and OF as:

: CASE  ( x1 -- ) ( R: -- x1 )  >R ;
OF      ( x2 -- ) ( R: x1 -- | x1 )
The cell x1 is on the top of the return stack and it can be allocated in
the register.  But this definition has its own problem.

1. On a real stack architecture, the machine must compare the tops of
both data and return stack for executing the word OF.  It complicate
the execution.
2. On a register architecture, we had better not push onto and pop from
the return stack, or we may get performance loss.

Quote:
> Anyways, the modifications are using [ for if, ][ for else, and ] for
> then, as well as { for the start of a loop, } for the end, >} to break,
> and >{ to restart.  The loops don't have an index, so if you want to
> break out after a set number of times, you'll need to do something like
> 15 { 1- dup 0= [ >} ][ your code here ] } )

I think we had better not use the break >} within a case block.
It is an unusual feature of the C language that an explicit statment is
used to leave the switch block.  This feature was considered as a
design error by some experts.  It is error-prone and should be avoided.
However, it is not a bad idea to use the break within a loop.

Quote:

> Anyways...  Here's my problem.
> I don't like
> : bigifword
> dup 15 - 0= [ case1  ][
> dup 14 - 0= [ case2  ][
> dup 13 - 0= [ case3  ][
> ..
> dup  1 - 0= [ case15 ][
> ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ] ;

> So I came up with
> : smallerifword {
> dup 15 - 0= [ case1  >} ]
> dup 14 - 0= [ case2  >} ]
> dup 13 - 0= [ case3  >} ]
> ..
>      1 - 0= [ case15 >} ]
> errorcase >} } ;

> Which seems to me to be a bit of a perversion of the loop construct, so
> I was wondering if there was a better way of doing something like this,
> or rather if any of you had ways that you prefered (since better is
> pretty much arbitrary).
> ...

I have stated the best may be the ANS-standard CASE structure.
But in some cases we have to use the nested IF-ELSE-THEN structures
such as:

IF      
        IF      your-code
        ELSE    your-code
        THEN
ELSE    your-code
THEN
( nested in the IF part )

or

IF      your-code
ELSE
        IF      your-code
        ELSE    your-code
        THEN
THEN
( nested in the ELSE part )

Other languages such as Ada have elsif statements, the previous code
may be coded like:

IF      THEN    your-code
ELSIF   THEN    your-code
ELSE    your-code
END IF

This is clear and good-looking, but Forth use the RPN and it is
impossible to have an ELSIF word.  Anyway, I thought this problem before.
I devised a method to overcome it.  I assume you have known the meanings
of the Forth-83 optional words >MARK and >RESOLVE.  I must state here,
I have never implemented my method.

The standard structures IF-THEN and IF-ELSE-THEN are implented like:

( flag )        IF              ( if-mark )      
        if-part-code    
        THEN            ( resolve if-mark )

( flag )        IF              ( if-mark )
        if-part-code    
        ELSE            ( resolve if-mark then else-mark )
        else-part-code
        THEN            ( resolve else-mark )

We can extend the semantics of ELSE and THEN as:

( flag1 )       IF                      ( if-mark1 )
        ( flag2 ) IF            ( if-mark1 if-mark2 )
                if-part-code    
                ELSE            ( resolve if-mark2 then else-mark2
                                  if-mark1 else-mark2 remain )
                else-part-code1
        ELSE                    ( resolve if-mark1 then else-mark1
        else-part-code2           else-mark1 else-mark2 remain )
        THEN                    ( resolve else-mark2 and else-mark1 )
( nested in the if part )

( flag1 )       IF                      ( if-mark1 )
        if-part-code1
        ELSE                    ( resolve if-mark1 then else-mark1 )
        ( flag2 )       IF              ( else-mark1 if-mark2 )
                if-part-code2
                ELSE            ( resolve if-mark2 then else-mark2 )
                                ( else-mark1 else-mark2 remain )
                else-part-code
        THEN                    ( resolve else-mark2 and else-mark1 )
( nested in the else part )

The compile time of ELSE and THEN are respevctively:
ELSE - resolve only one if-mark
THEN - resolve only one if-mark or many else-marks.

I prefer nested-in-the-if-part to nested-in-the-else-part.  But the former
need some stack manipulation and harder to implement than the latter.
If compatibility with ANS is desired, the word "THEN" may be renamed
as "ENDIF".

                                Charles Liu



Sun, 13 Feb 2000 03:00:00 GMT  
 Case Statements...

Charles Liu wrote of extending IF as an answer to multiple-selection.

As I wrote at the beginning of this thread.

Quote:
>  >  The most useful extension of Standard Forth I have done -- in
>  >  fact the only extension of Standard Forth language I do -- is
>  >  COND ... THENS   (It took me a while to get the names right.)

>  >  It lets me easily write multiple selection dispatch functions
>  >  without THEN piling up.  Tests for constants, strings, and
>  >  compound properties can be made, with additions and other
>  >  changes made as I discover the need.

>  >  This does everything all the others do.

The example can be written.

COND  .. IF  your-code
ELSE  .. IF  your-code
ELSE         your-code
THENS

Here is the implementation I gave.

( Sample implementation with data stack used for control-flow stack. )

VARIABLE (COND-MARK)  ( This variable name should be hidden. )


: THENS

    (COND-MARK) !
; IMMEDIATE

If your implementation is based on Fig-Forth or F83 or Classical polyForth
this can be done instead.

: COND 0 ; IMMEDIATE
: THENS BEGIN ?DUP WHILE POSTPONE THEN REPEAT ; IMMEDIATE

It is one of the most productive means I have to help get a job done.
--
Procedamus in pace.    Wil Baden   Costa Mesa, California



Mon, 14 Feb 2000 03:00:00 GMT  
 Case Statements...

***

Quote:
>  [The second implementation is] much better, as the first version is
>  non-reentrant (due to its use of a variable) and won't work on a
>  multitasking Forth.  Cannot a variable be avoided in a portable manner?  
>  I can't think of any easy way right now.  

***

It shouldn't be a problem, as the variable would be a USER variable.  The second
version is the one I use in practice.  It's interesting that the size of control
stack elements is irrelevant in both versions.  Both versions do expect the
data stack to be used for the control flow stack.  The second is based on the
0 not being a syntox-flag.  If 0 is used then just replace the two references to
it.  -1 should do.
--
Wil



Mon, 14 Feb 2000 03:00:00 GMT  
 Case Statements...


: ***
: >  [The second implementation is] much better, as the first version is
: >  non-reentrant (due to its use of a variable) and won't work on a
: >  multitasking Forth.  Cannot a variable be avoided in a portable manner?  
: >  I can't think of any easy way right now.  
: ***

: It shouldn't be a problem, as the variable would be a USER variable.  

I'd be very reluctant to add a user variable to every terminal task
for the sake of a little syntatcic sugar.

Andrew.



Mon, 14 Feb 2000 03:00:00 GMT  
 Case Statements...

: I'd be very reluctant to add a user variable to every terminal task
: for the sake of a little syntatcic sugar.

Then use 0 as it has been done in polyForth, F83, FPC, ThisForth, PowerMacForth,
PFE.
--
Wil



Mon, 14 Feb 2000 03:00:00 GMT  
 Case Statements...

Quote:

> Charles Liu wrote of extending IF as an answer to multiple-selection.

> As I wrote at the beginning of this thread.

> >  >  The most useful extension of Standard Forth I have done -- in
> >  >  fact the only extension of Standard Forth language I do -- is
> >  >  COND ... THENS   (It took me a while to get the names right.)

        Except for naming "BLOCK{ }BLOCK" this is exactly the same as
the remark I made ... and is the same as where this thread ended up
last time it arose (though I had different names then) in the context
of discussing what "then" means.
        And, as the other strand of this thread emphasized, for the type
of problems for which BLOCK{ ... IF ... ELSE ... IF ... ELSE }BLOCK is
unwieldy, a state machine is probably better than a jump-based case, so
why not implement the state machine directly?

Virtually,

Bruce R. McFarling, Newcastle, NSW



Tue, 15 Feb 2000 03:00:00 GMT  
 Case Statements...

But suppose the branch taken less frequently is more time critical?

The programmer should retain control. Its why I like FORTH. If I
wanted all that other junk I'd use C.

Simon
---------------------------------------------------------------------------------------------------

Quote:



>>>> As I recall, FORTH DIMENSIONS has treated approximately 100 (or is it

>>Case statements (and IF ELSE THEN) could also be improved if Forth
>>checked, at run-time, which branches are taken most frequently and
>>modified the code to move them "up front". Anybody implemented
>>this? Just having the statistics collected is already interesting.

>>-marcel

>That's interesting because it looks like a fairly simple, legitimate
>use of self-modifying code.

>--

>Any action meets with an equal and opposite reaction. This includes
>innovation, and is proportional to the degree of innovation.



Mon, 21 Feb 2000 03:00:00 GMT  
 Case Statements...

wilbaden> If your implementation is based on Fig-Forth or F83 or Classical polyForth
wilbaden> this can be done instead.
wilbadbe>
wilbaden> : COND 0 ; IMMEDIATE
wilbaden> : THENS BEGIN ?DUP WHILE POSTPONE THEN REPEAT ; IMMEDIATE

This reminds me of a set of unusual control structur words I have
written to simplify the detection of multiple (possibly subsequent)
events.  As COND and THENS they are just shorthands for something
you could write in ordinary Forth as well, but are much handier to
describe the problem.

An example. Keystrokes have to be analyzed and a sequencs of three
'A's pressed in a row has to be detected. I finally came up with
the following:

: demo ( -- )
    ." Press 3 times 'A' to exit!" cr
    detect
    BEGIN
      key dup emit  ascii A =
      IF  ."  Again! " CR 3 times? IF ." Yesss! "   EXIT THEN
      ELSE  restart ."  3 times 'A' in a sequence" cr THEN
    AGAIN ;

I use 4 words for detecting mutiple events: DETECT, GIVEUP, TIMES?,
and RESTART; they manage an event counter on top of the return stack.

DETECT ( -- ) (R -- 0 )
  Start detecting multiple events. This initializes the event
  counter to 0.  After executing DETECT, EXIT must not be called
  until GIVEUP or a succesful TIMES? has been executed.

GIVEUP ( -- ) (R x -- )
  Stop detecting multiple events, remove the event counter.

TIMES? ( n -- ) (R x -- x' ff | tf )
  If the event counter x is greater or equal to n, then (at least)
  n events have been detected (TIMES? is succesfull). Remove the
  event counter and return a true flag.  If on the other hand,
  x is less than n, then there are still events to be detected
  (TIMES? has failed). Increment the event counter by one and
  return a false flag.

RESTART ( -- ) (R x -- 0 )
   Reset the event counter to 0.

----------------------------------------------------------------------
Here is the implementation in ANS-Forth. I use EVALUATE to
implement them as macros. EVALUATE is not called at runtime of the
words which use the macros. I usually have a macro defining word this,
but that's a completly different story...

: giveup ( -- )   S" R> DROP" EVALUATE ; IMMEDIATE

: times? ( n -- f )
   S" R> 1+ DUP >R > 0= DUP IF  giveup  THEN " EVALUATE ; IMMEDIATE

: detect ( -- )   S" 0 >R" EVALUATE ; IMMEDIATE
: restart ( -- )  S" giveup detect" EVALUATE ; IMMEDIATE

Regards,
      Ulrich

--
Ulrich Hoffmann, Uni Kiel        http://www.informatik.uni-kiel.de/~uho/

Preusserstr 1-9, D-24105 Kiel, Germany  Tel: +49 431 560426  Fax: 566143



Mon, 21 Feb 2000 03:00:00 GMT  
 Case Statements...


Quote:

>: demo ( -- )
>    ." Press 3 times 'A' to exit!" cr
>    detect
>    BEGIN
>      key dup emit  ascii A =
>      IF  ."  Again! " CR 3 times? IF ." Yesss! "   EXIT THEN
>      ELSE  restart ."  3 times 'A' in a sequence" cr THEN
>    AGAIN ;

Your words look very good.  There's the usual problem of debugging
return-stack errors, if I were to leave off the GIVEUP or whatever I
could get a peculiar error, but written with caution they look very
nice.

What prompted me to comment was the demo, which looks like you wrote it
on the spot without testing it.  Since you RESTART after every
keystroke, it looks hard to count 3 events.

This doesn't detract from your excellent method; I was pleased to catch
someone else publishing a short buggy untested demo, as I've done on
occasion.



Tue, 22 Feb 2000 03:00:00 GMT  
 
 [ 41 post ]  Go to page: [1] [2] [3]

 Relevant Pages 

1. case statement flipflop statement

2. difference if statement with case statement?

3. [Fwd: Case statements, decision trees, and good OO design]

4. CASE STATEMENT

5. Case statements in parallel

6. Detecting Multiple Events (was: Case Statements...)

7. SIMPLE Case statement

8. RFI: Simple CASE Statement

9. Eaker CASE statement words ....

10. programatically add item to case statement

11. Controlling program flow and case statements

12. case statements

 

 
Powered by phpBB® Forum Software