A Better BETWEEN

Revision  2016-09-25

Background

Forth-94 WITHIN was intended to replace BETWEEN but it hasn't been a comfortable fit.

A characteristic of  WITHIN is that the upper limit is not included in the range.  This is useful when comparing memory addresses. In other situations it is less appropriate, leading to clumsy or obfuscated code e.g.

    ( char )  CHAR a  CHAR z 1+  WITHIN  ( flag )

BETWEEN is better suited to this application as its limits are inclusive:

    ( char )  CHAR a  CHAR z  BETWEEN  ( flag )

Since WITHIN and BETWEEN each have their uses, some forth systems elect to provide both.

Implementation

Early versions of BETWEEN used only signed arguments. Today BETWEEN is commonly implemented as:

: BETWEEN  ( n1|u1 n2|u2 n3|u3 -- flag )  1+ WITHIN ;

This is simple and works with either signed or unsigned numbers. Unfortunately it has a problem - it fails when  u2 = 0 and u3 = MAX-U .

There is an alternative implementation available which does not have this limitation.

: BETWEEN  ( n1|u1 n2|u2 n3|u3 -- flag )  OVER - -ROT - U< 0= ;

This works over the entire number range and is based on the same algorithm most Forths use to implement WITHIN.

Note: As with the algorithm for WITHIN (ANS-Forth 1994, A.6.2.2440), this implementation is restricted to 2's complement machines.

A useful feature of BETWEEN is the ability to make the limits exclusive. This is achieved by reversing their order and inverting the result e.g.

3  7 4 BETWEEN 0= . 0
4  7 4 BETWEEN 0= . 0
5  7 4 BETWEEN 0= . -1
6  7 4 BETWEEN 0= . -1
7  7 4 BETWEEN 0= . 0
8  7 4 BETWEEN 0= . 0

Formal definition

BETWEEN

 

( 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 if n1|u1, n2|u2, and n3|u3 are not all the same type.

Sample machine-code implementation

\ Intel 80386 (32-bit native-code forth)

code BETWEEN  ( n1|u1 n2|u2 n3|u3 -- flag )
   sub ebx, 0 [ebp]
   mov ecx, 4 [ebp]
   sub ecx, 0 [ebp]
   cmp ebx, ecx
   sbb ebx, ebx
   not ebx
   lea ebp, 8 [ebp]
   ret
end-code

\ Intel 8086 (16-bit DTC/ITC forth)

code BETWEEN  ( n1|u1 n2|u2 n3|u3 -- flag )
   bx pop  ax pop  cx pop
   ax bx sub  ax cx sub  cx bx cmp
   bx bx sbb  bx not  bx push  next
end-code

History

2008-12-02  First release
2010-05-24  Corrected formal definition and the conditions under which
            1+ WITHIN fails.
2013-04-11  Add note describing exclusive limits.
2016-09-25  Correct typo in the exclusive limits example

Top    Home    Forth

Page updated: 2016-09-25