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

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

Baden's recursive Quicksort revisited

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

Contents

  Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-11 01:31 +1000
    Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-10 15:49 +0000
    Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-10 17:42 +0000
      Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:16 +1000
      Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 03:18 -0500
        Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-21 16:33 +0000
    Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-11 12:03 +0200
      Re: Baden's recursive Quicksort revisited Alex McDonald <blog@rivadpm.com> - 2013-10-11 05:15 -0700
        Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:25 +1000
          Re: Baden's recursive Quicksort revisited "Alex McDonald" <blog@rivadpm.com> - 2013-10-13 08:59 +0100
            Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-13 04:50 -0500
              Comparing addresses (was: Baden's recursive Quicksort revisited) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-15 15:17 +0000
                Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-15 14:34 -0500
                  Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:15 +0000
                    Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-20 02:51 -0500
                      Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 11:18 +0000
                        Re: Comparing addresses albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-22 13:26 +0000
                          Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-22 13:39 +0000
                        Re: Comparing addresses Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-22 13:30 -0500
                          Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-23 07:48 +0000
                            Re: Comparing addresses m.a.m.hendrix@tue.nl - 2013-10-23 23:49 -0700
                              Re: Comparing addresses anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-24 09:01 +0000
          Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-13 12:06 +0000
            Re: Baden's recursive Quicksort revisited all2001@spambog.com (Wolfgang Allinger) - 2013-10-13 11:42 -0400
      Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-13 12:27 +1000
        Re: Baden's recursive Quicksort revisited Hans Bezemer <the.beez.speaks@gmail.com> - 2013-10-16 10:35 +0200
          Re: Baden's recursive Quicksort revisited Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-10-16 03:51 -0500
          Re: Baden's recursive Quicksort revisited albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-10-16 10:50 +0000
            Re: Baden's recursive Quicksort revisited anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-10-16 14:27 +0000
          Re: Baden's recursive Quicksort revisited "Ed" <invalid@invalid.com> - 2013-10-18 15:37 +1000

Page 1 of 2  [1] 2  Next page →

#26377 — Baden's recursive Quicksort revisited

Finding a recursive Quicksort that (a) works and (b) works over the full address
range is harder than one might imagine...

(p.s. Win32F developers:  There appears to be a bug in the Win32F console.
If the SHOW routine below is modified to print all 16000 sorted numbers,
the console locks up after the run and nothing can be entered at the keyboard.
No such problem with other Windows Forths tried.)

 -----------------------------------------------------

\ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
\ buggy (try it!).  Below is the version originally published in
\ FD Vol.6 No.5 which does seem to work.  Modified here to handle
\ cellsize other than 2.  Tested on several 16/32-bit Forths.
\ 2013-10-10 Ed.

\ Comment out what you already have.
-1 CELLS CONSTANT -CELL
 : CELL- ( a1 -- a2 ) [ -1 CELLS ] LITERAL + ;
\ : CELL+ ( a1 -- a2 ) [ 1 CELLS ] LITERAL + ;
 : NOT ( f1 -- f2 ) 0= ;  \ surely everyone has this by now

( C.A.R.HOARE'S QUICKSORT.                      WWB/WWB 811012 )

DEFER PRECEDES    ( a1,a2 -- f )                ( vectored execution )

' < IS PRECEDES

: QUICK  ( a[m],a[n] -- )                       ( partition a[m]..a[n] )
    2DUP  OVER - 2/ -CELL AND + @ >R      ( take middle value as pivot )
    2DUP SWAP
    BEGIN           ( m,n,j,i )                 ( m <= i <= j <= n )
        BEGIN  DUP @  R@  PRECEDES  WHILE  CELL+  REPEAT  SWAP
        BEGIN  R@ OVER @  PRECEDES  WHILE  CELL-  REPEAT  SWAP
        2DUP U< NOT
        IF  2DUP 2DUP @ >R  @ SWAP !  R> SWAP !  SWAP CELL- SWAP CELL+ THEN
        2DUP U<
    UNTIL  R> DROP  ( m,n,j,i )                 ( a <= j < i <= n )
    ROT  ( i,j,i,n )  2OVER 2OVER  - + > IF  2SWAP  ( i,n,m,j )  THEN
    2DUP U<  IF  RECURSE  ELSE  2DROP  THEN     ( shorter part )
    2DUP U<  IF  RECURSE  ELSE  2DROP  THEN     ( longer part )  ;

: SORT  ( a,n -- )              ( order a[0]..a[n-1] by "PRECEDES". )
    ?DUP 0= ABORT" nothing to sort."
    1- CELLS OVER +  ( a[0],a[n-1] )  QUICK ;

\ : (SORTED)  R> DUP 2+ >R  @ IS PRECEDES  SORT  ;
\ : SORTED   ( a,n --<relation> )  ( order a[0]..a[n-1] by <relation> )
\    STATE @
\    IF  COMPILE (SORTED)
\    ELSE  ' IS PRECEDES  SORT  THEN  ;  IMMEDIATE


1 [if] \ TESTING

\ Simple random number generator from 'Starting Forth'
variable RND  1 rnd !
: RAND ( -- U )  rnd @ 31421 * 6727 + dup rnd ! ;

16000 unused 1000 - 1 rshift min constant SIZE
create NUMS  size cells allot
size 100 / 1 max constant STEP

: INIT ( -- ) size 0 do rand i cells nums + ! loop ;
: SHOW ( -- ) cr size 0 do i cells nums + @ . step +loop ;

: TEST ( -- )
  cr ." <press any key to begin> " key drop
  cr ." Sorting " size . ." numbers ... "
  init  nums size sort
  cr ." Showing a sample of sorted numbers: "
  show ;

TEST

[then]

 -----------------------------------------------------

[toc] | [next] | [standalone]

#26378

In article <l36drg$t8$1@speranza.aioe.org>, Ed <invalid@invalid.com> wrote:
>Finding a recursive Quicksort that (a) works and (b) works over the full address
>range is harder than one might imagine...
>
>(p.s. Win32F developers:  There appears to be a bug in the Win32F console.
>If the SHOW routine below is modified to print all 16000 sorted numbers,
>the console locks up after the run and nothing can be entered at the keyboard.
>No such problem with other Windows Forths tried.)

With

WANT [IF]
WANT DEFER
WANT CASE-INSENSITIVE    CASE-INSENSITIVE

it works on lina, except ....

Who has ever said that [IF] is required to understand a lower
case `` [then] '' ?
[then] is *NOT* a Forth word, so switching to case-insensitive
doesn't help.

Bottom line I had to change

[then]

to
[THEN]

And the program is deemed non-portable in my book.

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]

#26379

"Ed" <invalid@invalid.com> writes:
>Finding a recursive Quicksort that (a) works and (b) works over the full address
>range is harder than one might imagine...

Bug reports for the sorting code I posted and discussed some weeks ago
<2013Aug15.191549@mips.complang.tuwien.ac.at> are welcome (but I have
not registered any).  Code at

http://www.complang.tuwien.ac.at/forth/programs/sort.fs

- 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 2013: http://www.euroforth.org/ef13/

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

#26624

Anton Ertl wrote:
> "Ed" <invalid@invalid.com> writes:
> >Finding a recursive Quicksort that (a) works and (b) works over the full address
> >range is harder than one might imagine...
>
> Bug reports for the sorting code I posted and discussed some weeks ago
> <2013Aug15.191549@mips.complang.tuwien.ac.at> are welcome (but I have
> not registered any).  Code at
>
> http://www.complang.tuwien.ac.at/forth/programs/sort.fs

No good.  Fails (b) above.

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

#26653

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> "Ed" <invalid@invalid.com> writes:
>>Finding a recursive Quicksort that (a) works and (b) works over the full address
>>range is harder than one might imagine...
> 
> Bug reports for the sorting code I posted and discussed some weeks ago
> <2013Aug15.191549@mips.complang.tuwien.ac.at> are welcome (but I have
> not registered any).  Code at
> 
> http://www.complang.tuwien.ac.at/forth/programs/sort.fs

You're comparing addresses here:

    2dup cell- begin ( al ah l r )
	2dup <= while

and here:

	    2dup <= if
		2dup exchange swap cell+ swap cell- then

Andrew.

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

#26659

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Bug reports for the sorting code I posted and discussed some weeks ago
>> <2013Aug15.191549@mips.complang.tuwien.ac.at> are welcome (but I have
>> not registered any).  Code at
>> 
>> http://www.complang.tuwien.ac.at/forth/programs/sort.fs
>
>You're comparing addresses here:
>
>    2dup cell- begin ( al ah l r )
>	2dup <= while
>
>and here:
>
>	    2dup <= if
>		2dup exchange swap cell+ swap cell- then

Thank you.  I have uploaded a new version where these bugs are
squashed.  I have also eliminated all non-standard words except "{"
(which is only used for the benchmarking code).

- 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 2013: http://www.euroforth.org/ef13/

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

#26389

Ed wrote:

> \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
> \ buggy (try it!).

Ed, this code (in some form or another) is still very much in use with
KForth, SwitftForth and 4tH. I never found any problem with it, but if you
have an example me and I assume the maintainers of other compilers would
very much like to know.

Hans Bezemer

\ Wil Baden's sorter, 4tH version
\ Set PRECEDES for different datatypes or sort order.

[UNDEFINED] sort     [IF]
[UNDEFINED] precedes [IF]
  defer precedes                       ( addr addr -- flag )
[THEN]                                 \ compatible with QSORT

: exchange                             ( addr_1 addr_2 -- )
    over over @ swap @ rot ! swap ! ;

: partition                            ( lo hi -- lo_1 hi_1 lo_2 hi_2 )
    2dup over - 2/ -1 cells and +  @ >r  ( r: median)
    2dup begin                         ( lo_1 hi_2 lo_2 hi_1)
         swap begin  dup @ r@   precedes while  cell+  repeat
         swap begin  r@ over @  precedes while  cell-  repeat
         2dup > not if  2dup exchange  >r cell+ r> cell-  then
    2dup > until                       ( lo_1 hi_2 lo_2 hi_1)
    r> drop swap rot                   ( lo_1 hi_1 lo_2 hi_2)
    ;

: qsort                                ( lo hi -- )
    partition                          ( lo_1 hi_1 lo_2 hi_2)
[UNDEFINED] QSORTUNOPTIMIZED [IF]      \ don't select smaller subset
    2>r 2dup 2r> 2swap 2>r 2dup 2r> 2swap - + < if 2swap then
[THEN]
    2dup < if recurse else 2drop then
    2dup < if recurse exit then  2drop ;
                                       \ force tail recursion
: sort                                 ( addr n -- )
    dup 2 < if  2drop  exit then
    1- cells over + qsort  ;           ( addr addr+{n-1}cells) 

[DEFINED] 4TH# [IF]
  hide exchange
  hide partition
  hide qsort
[THEN]
[THEN]

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

#26390

On Friday, 11 October 2013 11:03:20 UTC+1, The Beez  wrote:
> Ed wrote:
> 
> 
> 
> > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
> > \ buggy (try it!).
> 
> Ed, this code (in some form or another) is still very much in use with
> KForth, SwitftForth and 4tH. I never found any problem with it, but if you
> have an example me and I assume the maintainers of other compilers would
> very much like to know.

Ed's code uses U< and U< NOT instead of Wil's < and >. Systems that permit signed addresses, or systems that run under an OS that permits signed addresses, may find problems. That won't include Window's Forths that run in user space.

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

#26438

Alex McDonald wrote:
> On Friday, 11 October 2013 11:03:20 UTC+1, The Beez  wrote:
> > Ed wrote:
> >
> >
> >
> > > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
> > > \ buggy (try it!).
> >
> > Ed, this code (in some form or another) is still very much in use with
> > KForth, SwitftForth and 4tH. I never found any problem with it, but if you
> > have an example me and I assume the maintainers of other compilers would
> > very much like to know.
>
> Ed's code uses U< and U< NOT instead of Wil's < and >. Systems that permit signed addresses,
> or systems that run under an OS that permits signed addresses, may find problems. That won't
> include Window's Forths that run in user space.

I'm not familiar with Windows programming but I'm told DLL's can pose
problems because they load anywhere (?)  Apart from tempting fate, it would
be an error to use signed operators on systems with unsigned addresses.

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

#26458

on 13/10/2013 03:25:29, "Ed" wrote:
> Alex McDonald wrote:
>> On Friday, 11 October 2013 11:03:20 UTC+1, The Beez  wrote:
>> > Ed wrote:
>> >
>> >
>> >
>> > > \ The Recursive Quicksort "qsort.txt" on Wil Baden's website is
>> > > \ buggy (try it!).
>> >
>> > Ed, this code (in some form or another) is still very much in use with
>> > KForth, SwitftForth and 4tH. I never found any problem with it, but if you
>> > have an example me and I assume the maintainers of other compilers would
>> > very much like to know.
>>
>> Ed's code uses U< and U< NOT instead of Wil's < and >. Systems that permit signed 
addresses,
>> or systems that run under an OS that permits signed addresses, may find problems. 
That won't
>> include Window's Forths that run in user space.
> 
> I'm not familiar with Windows programming but I'm told DLL's can pose
> problems because they load anywhere (?) Apart from tempting fate, it
> would be an error to use signed operators on systems with unsigned
> addresses.
> 


http://msdn.microsoft.com/en-us/library/windows/desktop/aa366912%28v=vs.85%29.aspx
explains the use of the address space in Windows. In general though, I
agreee; it's bad practise. 

> 
> 
> 

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

#26461

Alex McDonald <blog@rivadpm.com> wrote:
> on 13/10/2013 03:25:29, "Ed" wrote:
>> Alex McDonald wrote:
>>> On Friday, 11 October 2013 11:03:20 UTC+1, The Beez  wrote:
>>> > Ed wrote:
>>> >
>>> > Ed, this code (in some form or another) is still very much in use with
>>> > KForth, SwitftForth and 4tH. I never found any problem with it, but if you
>>> > have an example me and I assume the maintainers of other compilers would
>>> > very much like to know.
>>>
>>> Ed's code uses U< and U< NOT instead of Wil's < and >. Systems
>>> that permit signed addresses, or systems that run under an OS that
>>> permits signed addresses, may find problems.
>>> That won't include Window's Forths that run in user space.
>> 
>> I'm not familiar with Windows programming but I'm told DLL's can pose
>> problems because they load anywhere (?) Apart from tempting fate, it
>> would be an error to use signed operators on systems with unsigned
>> addresses.
> 
> http://msdn.microsoft.com/en-us/library/windows/desktop/aa366912%28v=vs.85%29.aspx
> explains the use of the address space in Windows. In general though,
> I agreee; it's bad practise.

It's never been guaranteed, as far as I'm aware, that a block of
memory returned by ALLOT HERE or ALLOCATE can't contain address zero.
So, such a block might go from FFF0 ... 0010 , in which case you must
compare addresses in that block by using < , not U< .

It's one of the little details it would be nice to get fixed in the
standard, but it's not really important.

Andrew.

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

#26554 — Comparing addresses (was: Baden's recursive Quicksort revisited)

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>It's never been guaranteed, as far as I'm aware, that a block of
>memory returned by ALLOT HERE or ALLOCATE can't contain address zero.
>So, such a block might go from FFF0 ... 0010 , in which case you must
>compare addresses in that block by using < , not U< .
>
>It's one of the little details it would be nice to get fixed in the
>standard, but it's not really important.

3.1.1 says:

| a-addr => c-addr => addr => u;

I.e., addr is a subtype of u.  Therefore I consider programs that
compare addresses with U< standard-compliant.  And if you implement
Forth on hardware that has system stuff around MAX-N and where the
user RAM can straddle 0, it's your job to make sure that contiguous
regions don't straddle 0.

It would be good to add a guarantee that they don't start at 0, but
that's future work.

Concerning the importance of that, I think that there are a lot of
programs that are affected, so in that sense it is important.
However, it is already a de-facto standard (all important systems
implement it), so it's not that urgent to get it into the standard
document (but OTOH it should be relatively easy).

- 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 2013: http://www.euroforth.org/ef13/

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

#26565 — Re: Comparing addresses

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>It's never been guaranteed, as far as I'm aware, that a block of
>>memory returned by ALLOT HERE or ALLOCATE can't contain address zero.
>>So, such a block might go from FFF0 ... 0010 , in which case you must
>>compare addresses in that block by using < , not U< .
>>
>>It's one of the little details it would be nice to get fixed in the
>>standard, but it's not really important.
> 
> 3.1.1 says:
> 
> | a-addr => c-addr => addr => u;
> 
> I.e., addr is a subtype of u.  Therefore I consider programs that
> compare addresses with U< standard-compliant.

How does that follow?

> And if you implement Forth on hardware that has system stuff around
> MAX-N and where the user RAM can straddle 0, it's your job to make
> sure that contiguous regions don't straddle 0.

And that.  I don't quite see how a subtype relationship implies
ordering.  For example, every address between FFF0 ... 0010 is of type
u.
 
Andrew.

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

#26583 — Re: Comparing addresses

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> 3.1.1 says:
>> 
>> | a-addr => c-addr => addr => u;
>> 
>> I.e., addr is a subtype of u.  Therefore I consider programs that
>> compare addresses with U< standard-compliant.
>
>How does that follow?

6.1.2340 U< ( u1 u2 -- flag )

Also:

|A.3.1.3.3 Addresses
|
|An address is uniquely represented as a single cell unsigned number
|and can be treated as such when being moved to, from, or upon the
|stack. Conversely, each unsigned number represents a unique address
|(which is not necessarily an address of accessible memory). This
|one-to-one relationship between addresses and unsigned numbers forces
|an equivalence between address arithmetic and the corresponding
|operations on unsigned numbers.

>> And if you implement Forth on hardware that has system stuff around
>> MAX-N and where the user RAM can straddle 0, it's your job to make
>> sure that contiguous regions don't straddle 0.
>
>And that.  I don't quite see how a subtype relationship implies
>ordering.  For example, every address between FFF0 ... 0010 is of type
>u.

Ordering is defined for u (through U< and U>), and therefore for addr.

You seem to argue that each address has to be considered on its own,
but the addresses in a contiguous region are contiguous.

Sure, one can tighten the specification, but the intent is clear: to
compare addresses, programmers use U<, not <.  And implementors better
make sure that this works.

- 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 2013: http://www.euroforth.org/ef13/

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

#26651 — Re: Comparing addresses

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> 3.1.1 says:
>>> 
>>> | a-addr => c-addr => addr => u;
>>> 
>>> I.e., addr is a subtype of u.  Therefore I consider programs that
>>> compare addresses with U< standard-compliant.
>>
>>How does that follow?
> 
> 6.1.2340 U< ( u1 u2 -- flag )
> 
> Also:
> 
> |A.3.1.3.3 Addresses
> |
> |An address is uniquely represented as a single cell unsigned number
> |and can be treated as such when being moved to, from, or upon the
> |stack. Conversely, each unsigned number represents a unique address
> |(which is not necessarily an address of accessible memory). This
> |one-to-one relationship between addresses and unsigned numbers forces
> |an equivalence between address arithmetic and the corresponding
> |operations on unsigned numbers.
> 
>>> And if you implement Forth on hardware that has system stuff around
>>> MAX-N and where the user RAM can straddle 0, it's your job to make
>>> sure that contiguous regions don't straddle 0.
>>
>>And that.  I don't quite see how a subtype relationship implies
>>ordering.  For example, every address between FFF0 ... 0010 is of type
>>u.
> 
> Ordering is defined for u (through U< and U>), and therefore for addr.

I don't know that the language abve is strong enough.  There would
have to be something like

  For every address A in data space, the result of A A 1+ U< shall
  return true.

(this isn't right because it doesn't apply to the last byte, but you
get the idea)

and I'd like also to see

  For every address A in data space, the result of A 0= shall
  return false.

> You seem to argue that each address has to be considered on its own,
> but the addresses in a contiguous region are contiguous.

No, I'm not.  I'm arguing that I can't see any language that forbids
address overflow in a contiguous region.  We know that such contiguous
memeory regions exist in real physcial processors.

Andrew.

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

#26662 — Re: Comparing addresses

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>> 3.1.1 says:
>>>> 
>>>> | a-addr => c-addr => addr => u;
>>>> 
>>>> I.e., addr is a subtype of u.  Therefore I consider programs that
>>>> compare addresses with U< standard-compliant.
>>>
>>>How does that follow?
>> 
>> 6.1.2340 U< ( u1 u2 -- flag )
>> 
>> Also:
>> 
>> |A.3.1.3.3 Addresses
>> |
>> |An address is uniquely represented as a single cell unsigned number
>> |and can be treated as such when being moved to, from, or upon the
>> |stack. Conversely, each unsigned number represents a unique address
>> |(which is not necessarily an address of accessible memory). This
>> |one-to-one relationship between addresses and unsigned numbers forces
>> |an equivalence between address arithmetic and the corresponding
>> |operations on unsigned numbers.
>> 
>>>> And if you implement Forth on hardware that has system stuff around
>>>> MAX-N and where the user RAM can straddle 0, it's your job to make
>>>> sure that contiguous regions don't straddle 0.
>>>
>>>And that.  I don't quite see how a subtype relationship implies
>>>ordering.  For example, every address between FFF0 ... 0010 is of type
>>>u.
>> 
>> Ordering is defined for u (through U< and U>), and therefore for addr.
>
>I don't know that the language abve is strong enough.

It does not look strong enough, but until now it is: I have not heard
of a system that claims to be standard and does not satisfy the
condition above.  And for programs, if there is a conscious decision
involved, programmers choose unsigned operations for addresses (the
bigger problem here is that if the programmer writes a signed
operation, this big will probably not be found through testing).

Still, tightening the language is probably a good idea.

>  There would
>have to be something like
>
>  For every address A in data space, the result of A A 1+ U< shall
>  return true.
>
>(this isn't right because it doesn't apply to the last byte, but you
>get the idea)

Yes, that's not it, but that's also something that we want, because
the address beyond the end of a memory area is also computed commonly,
and the usual way to do comparisons should work for that, too.

>and I'd like also to see
>
>  For every address A in data space, the result of A 0= shall
>  return false.

That would be the condition above, plus the condition that a memory
area must not start at 0, which we also want.

Your wording is not in the style of the standard.  Maybe add something
like:

|3.3.3.7 Data space addresses
|
|The addresses 0 and MAX-U (largest usable unsigned integer) are not in
|data space.
|
|A.3.3.3.7
|
|This restriction allows programs to use a number of common programming
|techniques: 0 can be used as NIL; and unsigned comparisons can be used
|to compare all data space addresses, and also the first address beyond
|a memory region.

>No, I'm not.  I'm arguing that I can't see any language that forbids
>address overflow in a contiguous region.

Yes, it does not follow directly, only indirectly: If "addr is a
subtype of u" did not have this consequence, it would have none, so
there would be no point in specifying "addr is a subtype of u" (they
would have specified "addr is a subtype of x" instead).  In any case,
whether it already follows or not, it's probably a good idea to
tighten the language.  Will you make the RfD?

- 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 2013: http://www.euroforth.org/ef13/

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

#26663 — Re: Comparing addresses

In article <2013Oct22.131807@mips.complang.tuwien.ac.at>,
Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>>>> 3.1.1 says:
>>>>>
>>>>> | a-addr => c-addr => addr => u;
>>>>>
>>>>> I.e., addr is a subtype of u.  Therefore I consider programs that
>>>>> compare addresses with U< standard-compliant.
>>>>
>>>>How does that follow?
>>>
>>> 6.1.2340 U< ( u1 u2 -- flag )
>>>
>>> Also:
>>>
>>> |A.3.1.3.3 Addresses
>>> |
>>> |An address is uniquely represented as a single cell unsigned number
>>> |and can be treated as such when being moved to, from, or upon the
>>> |stack. Conversely, each unsigned number represents a unique address
>>> |(which is not necessarily an address of accessible memory). This
>>> |one-to-one relationship between addresses and unsigned numbers forces
>>> |an equivalence between address arithmetic and the corresponding
>>> |operations on unsigned numbers.
>>>
>>>>> And if you implement Forth on hardware that has system stuff around
>>>>> MAX-N and where the user RAM can straddle 0, it's your job to make
>>>>> sure that contiguous regions don't straddle 0.
>>>>
>>>>And that.  I don't quite see how a subtype relationship implies
>>>>ordering.  For example, every address between FFF0 ... 0010 is of type
>>>>u.
>>>
>>> Ordering is defined for u (through U< and U>), and therefore for addr.
>>
>>I don't know that the language abve is strong enough.
>
>It does not look strong enough, but until now it is: I have not heard
>of a system that claims to be standard and does not satisfy the
>condition above.  And for programs, if there is a conscious decision
>involved, programmers choose unsigned operations for addresses (the
>bigger problem here is that if the programmer writes a signed
>operation, this big will probably not be found through testing).

I would much prefer to require programs that fail to work with negative
addresses to declare an environmental dependancy. It would be the
normal case, much like requiring that C@ works on an octet.
In rare case this requirement is missing then.
So we fully accept that normal programs fail if you pass the boundary
between 0x7fff,ffff,ffff,ffff and 0x8000,0000,0000,0000.

" requires the search wordset. Plus usual restrictions."

P.S.
qsort is a kind of a problem. It is a would be general purpose
tool and at the same time a carnal thing.
(The QSORT in my library works with integers. It demands an
execution token for the swapping of records, and for the comparison.
It doesn't do well on benchmarks, but that is probably the way
to go, if you're worried. )


>- anton

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]

#26664 — Re: Comparing addresses

albert@spenarnc.xs4all.nl (Albert van der Horst) writes:
>In article <2013Oct22.131807@mips.complang.tuwien.ac.at>,
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>And for programs, if there is a conscious decision
>>involved, programmers choose unsigned operations for addresses (the
>>bigger problem here is that if the programmer writes a signed
>>operation, this big will probably not be found through testing).
>
>I would much prefer to require programs that fail to work with negative
>addresses to declare an environmental dependancy.

Sure, such programs can define such an environmental dependency.  And
if they don't, they are just plain non-standard; so if they want to
comply at least partially with the standard, they are required to
declare such a dependency.

>It would be the
>normal case, much like requiring that C@ works on an octet.

While nearly all standard systems have c@ working on an octect (and
few programs depend on that), many systems give you addresses with the
MSB set:


 VFX Forth for Linux IA32
 © MicroProcessor Engineering Ltd, 1998-2012 

 Version: 4.60 [build 0501]
 Build date: 18 July 2012

 Free dictionary = 7900479 bytes [7715kb]


cr 2500000000 allocate throw dup . 2499999999 + dup . c@ . 
1648668680 -146298617 0  ok
bye [b8:~:3222] sf
SwiftForth i386-Linux 3.4.8a 21-Jul-2013 
cr 2500000000 allocate throw dup . 2499999999 + dup . c@ . 
1645961224 -149006073 0  ok

[b8:~:3223] ~/gforth-386/gforth
Gforth 0.7.9_20130821, Copyright (C) 1995-2012 Free Software Foundation, Inc.
Gforth comes with ABSOLUTELY NO WARRANTY; for details type `license'
Type `bye' to exit
cr 2500000000 allocate throw dup . 2499999999 + dup . c@ . 
1640062984 -154904313 0  ok

So writing programs with such an environmental dependency is not wise.
So we do need a way to flag such environmental dependencies in
programs.

>P.S.
>qsort is a kind of a problem. It is a would be general purpose
>tool and at the same time a carnal thing.

What is carnal about it?

- 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 2013: http://www.euroforth.org/ef13/

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

#26665 — Re: Comparing addresses

Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>>> 
>>> Ordering is defined for u (through U< and U>), and therefore for addr.
>>
>>I don't know that the language above is strong enough.
> 
> It does not look strong enough, but until now it is: I have not heard
> of a system that claims to be standard and does not satisfy the
> condition above.  And for programs, if there is a conscious decision
> involved, programmers choose unsigned operations for addresses (the
> bigger problem here is that if the programmer writes a signed
> operation, this big will probably not be found through testing).
> 
> Still, tightening the language is probably a good idea.
> 
>>  There would
>>have to be something like
>>
>>  For every address A in data space, the result of A A 1+ U< shall
>>  return true.
>>
>>(this isn't right because it doesn't apply to the last byte, but you
>>get the idea)
> 
> Yes, that's not it, but that's also something that we want, because
> the address beyond the end of a memory area is also computed commonly,
> and the usual way to do comparisons should work for that, too.

Ah, yes.  That's required so that loops over an address range will
terminate.  But it's only adequate for byte ranges; if that's the
intention we have to forbid the last cell too.

>>and I'd like also to see
>>
>>  For every address A in data space, the result of A 0= shall
>>  return false.
> 
> That would be the condition above, plus the condition that a memory
> area must not start at 0, which we also want.

OK.

> Your wording is not in the style of the standard.  Maybe add something
> like:
> 
> |3.3.3.7 Data space addresses
> |
> |The addresses 0 and MAX-U (largest usable unsigned integer) are not in
> |data space.
> |
> |A.3.3.3.7
> |
> |This restriction allows programs to use a number of common programming
> |techniques: 0 can be used as NIL; and unsigned comparisons can be used
> |to compare all data space addresses, and also the first address beyond
> |a memory region.
> 
>>No, I'm not.  I'm arguing that I can't see any language that forbids
>>address overflow in a contiguous region.
> 
> Yes, it does not follow directly, only indirectly: If "addr is a
> subtype of u" did not have this consequence, it would have none, so
> there would be no point in specifying "addr is a subtype of u" (they
> would have specified "addr is a subtype of x" instead).
> In any case, whether it already follows or not, it's probably a good
> idea to tighten the language.  Will you make the RfD?

Sure, but we're discussing it at the moment, so let's allow this
discussion a few more days before a more formal RFD.

Andrew.

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

#26667 — Re: Comparing addresses

Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>Anton Ertl <anton@mips.complang.tuwien.ac.at> wrote:
>> Andrew Haley <andrew29@littlepinkcloud.invalid> writes:
>>>  For every address A in data space, the result of A A 1+ U< shall
>>>  return true.
>>>
>>>(this isn't right because it doesn't apply to the last byte, but you
>>>get the idea)
>> 
>> Yes, that's not it, but that's also something that we want, because
>> the address beyond the end of a memory area is also computed commonly,
>> and the usual way to do comparisons should work for that, too.
>
>Ah, yes.  That's required so that loops over an address range will
>terminate.  But it's only adequate for byte ranges; if that's the
>intention we have to forbid the last cell too.

Even for a cell array, a dfloat array, etc., the address beyond the
last element is also the address beyond the last byte of the memory
area.  So it's adequate for everything.

- 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 2013: http://www.euroforth.org/ef13/

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

Page 1 of 2  [1] 2  Next page →

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

csiph-web