WITHIN

( n1 | u1 n2 | u2 n3 | u3 -- flag )

Perform a comparison of a test value n1 | u1 with a lower limit n2 | u2 and an upper limit n3 | u3, returning true if either (n2 | u2 < n3 | u3 and (n2 | u2 <= n1 | u1 and n1 | u1 < n3 | u3)) or (n2 | u2 > n3 | u3 and (n2 | u2 <= n1 | u1 or n1 | u1 < n3 | u3)) is true, returning false otherwise. An ambiguous condition exists n1 | u1, n2 | u2, and n3 | u3 are not all the same type.

See:

Rationale:

We describe WITHIN without mentioning circular number spaces (an undefined term) or providing the code. Here is a number line with the overflow point (o) at the far right and the underflow point (u) at the far left:
u---------------o
There are two cases to consider: either the n2 | u2... n3 | u3 range straddles the overflow/underflow points or it does not. Lets examine the non-straddle case first:
u-----[.....)-----o
The [ denotes n2 | u2, the ) denotes n3 | u3, and the dots and [ are numbers WITHIN the range. n3 | u3 is greater than n2 | u2, so the following tests will determine if n1 | u1 is WITHIN n2 | u2 and n3 | u3:
n2 | u2 <= n1 | u1 and n1 | u1 < n3 | u3.
In the case where the comparison range straddles the overflow/underflow points:
u.....)-----[.....o
n3 | u3 is less than n2 | u2 and the following tests will determine if n1 | u1 is WITHIN n2 | u2 and n3 | u3:
n2 | u2 <= n1 | u1 or n1 | u1 < n3 | u3.
WITHIN must work for both signed and unsigned arguments. One obvious implementation does not work:
: WITHIN ( test low high -- flag )
   >R OVER < 0= ( test flag1 ) SWAP R> < ( flag1 flag2 ) AND
;
Assume two's-complement arithmetic on a 16-bit machine, and consider the following test:

   33000 32000 34000 WITHIN

The above implementation returns false for that test, even though the unsigned number 33000 is clearly within the range {{32000 ... 34000}}.

The problem is that, in the incorrect implementation, the signed comparison < gives the wrong answer when 32000 is compared to 33000, because when those numbers are treated as signed numbers, 33000 is treated as negative 32536, while 32000 remains positive.

Replacing < with U< in the above implementation makes it work with unsigned numbers, but causes problems with certain signed number ranges; in particular, the test:

1 -5 5 WITHIN
would give an incorrect answer.

For two's-complement machines that ignore arithmetic overflow (most machines), the following implementation works in all cases:

: WITHIN ( test low high -- flag ) OVER - >R - R> U< ;

ContributeContributions

Maxavatar of Max sample implementation that can also be interpretedSuggested reference implementation2020-02-05 20:49:51

The current sample implementation uses >R and R>, which are compile-only (technically "Interpretation semantics for these words are undefined").

Instead WITHIN is expected to work also when interpreting.

The following implementation fixes that, and is correct under the same condition "For two's-complement machines that ignore arithmetic overflow" as the current sample implementation:

: WITHIN ( test low high -- flag ) OVER - ROT ROT - U> ;

ruvavatar of ruv

The original reference implementation does not have the mentioned issue, — it may work when interpreting.

You mean the ambiguous condition "interpreting a word with undefined interpretation semantics", but during interpretation of WITHIN word, the >R and R> words are not interpreted, since they names are not encountered by the text interpreter. Therefore, this ambiguous condition isn't met.

Moreover, during interpretation of WITHIN, it does not matter whether interpretation semantics of any other word is defined by the standard or not.

See also the terms definitions for "interpretation semantics" and "compilation semantics".

GeraldWodniavatar of GeraldWodni

The TC agrees that ruv's response is correct.

Closed
Reply New Version