6502.org Forum Projects Code Documents Tools Forum
It is currently Sun Nov 24, 2024 4:15 am

View unanswered posts | View active topics


Board index » 6502.org Users Forum » Forth

All times are UTC




Post new topic Reply to topic  Page 1 of 2
  [ 24 posts ]  Go to page 1, 2  Next
  Previous topic | Next topic 
Author Message
GARTHWILSON
 Post subject: Common D< Forth bug
PostPosted: Mon Aug 12, 2013 12:37 am 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8546
Location: Southern California
In the Forth 83 topic, I mentioned a bug in D< that I think is in the in the public-domain material (but if not, it's certainly nothing to defend if it is wrong!), but apparently I never discussed it. D< gets defined as:
Code:
: D<  D- D0<  ;

which looks quite innocent, and the D- and D0< do work right, but the algorithm doesn't take into account the underflow problems that occur when D1 minus D2 has a result that is so negative that it again becomes positive.

My first encounter with the problem occurred with the numbers -70007FFF and FFF8002. D< said the negative number was not less than the positive one, because -70007FFF (8FFF8001) minus FFF8002 gives 7FFFFFFF, which is positive. However if we add 1 to the first number making it -70007FFE, the D- gives an answer of 80000000, and D< correctly says that yes, the first number is indeed less than the second.

I redefined it in 6502 Forth as:
Code:
: D<  ROT
      2DUP =
      IF 2DROP U< EXIT THEN
      > -ROT 2DROP  ;

In my '816 Forth, I defined it as a primitive instead, because although D< is not used that much, the fact that it was not only faster as a primitive but even shorter than the secondary made it doubly worth it:
Code:
       HEADER "D<", NOT_IMMEDIATE    ; ( d1 d2 -- f )
DLT:   PRIMITIVE
       LDA  6,X
       CMP  2,X
       LDA  4,X
       SBC  0,X
       BVC  dlt1         ; If the resulting sign is wrong,
       EOR  #$8000       ; then invert it.
dlt1:  BPL  dult1        ; Now if N is set, d2 < d1.
       JMP  POP3_TRUE
 ;-------------------


Edited: See explanation below.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Mon Aug 04, 2014 9:37 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
There's something wrong with your second code sample; it looks like the BPL instruction should branch somewhere other than itself! Sorry that it took me nearly a year to notice ...

Mike
Top
 Profile  
Reply with quote  
GARTHWILSON
 Post subject: Re: Common D< Forth bug
PostPosted: Mon Aug 04, 2014 9:45 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8546
Location: Southern California
You're right. Thanks for catching that. It's on my DOS computer w/o internet or other networking, and I probably just copied it by hand instead of copying first to SD card and then over, which unfortunately requires resetting the DOS machine because the SD card is on an IDE converter. (Later it got backed up on this computer anyway, with the SD card.) I'll fix it above. I left out a letter. It should say BPL dult1, not dlt1. dult1 is at the end of DU<, and is a jump to POP3_FALSE.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
Top
 Profile  
Reply with quote  
edx
 Post subject: Re: Common D< Forth bug
PostPosted: Sun Sep 14, 2014 12:46 pm 
Offline

Joined: Sun Sep 14, 2014 11:18 am
Posts: 14
GARTHWILSON wrote:
In the Forth 83 topic, I mentioned a bug in D< that I think is in the in the public-domain material (but if not, it's certainly nothing to defend if it is wrong!), but apparently I never discussed it...
Most early Forths defined '<' and 'D<' in the same manner. It wasn't a bug but a "feature" - the characteristics of which are discussed in the polyForth manual (DB005-120825-PF-REF.pdf). By the time the Forth-79 Standard came out it required '<' operate over the full 16-bit signed range (though it's not clear whether similar provisions applied to 'D<').
Top
 Profile  
Reply with quote  
GARTHWILSON
 Post subject: Re: Common D< Forth bug
PostPosted: Sun Sep 14, 2014 3:22 pm 
Offline
User avatar

Joined: Fri Aug 30, 2002 1:09 am
Posts: 8546
Location: Southern California
edx wrote:
It wasn't a bug but a "feature" - the characteristics of which are discussed in the polyForth manual (DB005-120825-PF-REF.pdf).

Do you have a URL for it? Any way you look at it, for D< to say that -70007FFF was not less than 0FFF8002 in signed 32-bit numbers is just plain wrong.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?
Top
 Profile  
Reply with quote  
Klaus2m5
 Post subject: Re: Common D< Forth bug
PostPosted: Sun Sep 14, 2014 4:15 pm 
Offline

Joined: Sat Jul 28, 2012 11:41 am
Posts: 442
Location: Wiesbaden, Germany
The manual can be downloaded here: http://www.greenarraychips.com/home/doc ... PF-REF.pdf

off topic edit: The discussion wether something is a bug or a feature reminds me of Monty Python's dead parrot sketch.

"It is dead"
"No it's not. It is resting"

http://www.youtube.com/watch?v=4vuW6tQ0218

_________________
6502 sources on GitHub: https://github.com/Klaus2m5


Last edited by Klaus2m5 on Sun Sep 14, 2014 5:26 pm, edited 1 time in total.

Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Sun Sep 14, 2014 4:28 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
edx wrote:
... It wasn't a bug but a "feature" - the characteristics of which are discussed in the polyForth manual (DB005-120825-PF-REF.pdf).

I'm a bit fuzzy this morning (haven't gone to the gym yet), but a simple-minded search of the document yields no "discussion" of D< ... just a brief one-line definition.

Mike
Top
 Profile  
Reply with quote  
edx
 Post subject: Re: Common D< Forth bug
PostPosted: Mon Sep 15, 2014 9:45 am 
Offline

Joined: Sun Sep 14, 2014 11:18 am
Posts: 14
barrym95838 wrote:
I'm a bit fuzzy this morning (haven't gone to the gym yet), but a simple-minded search of the document yields no "discussion" of D< ... just a brief one-line definition.
See section 2.2.2
GARTHWILSON wrote:
Any way you look at it, for D< to say that -70007FFF was not less than 0FFF8002 in signed 32-bit numbers is just plain wrong.
Clearly that wasn't the way C.Moore and Forth Inc looked at it.

If there be a mistake it lies in expecting modern behaviours from 35+ year software and being caught out by it. :wink:
Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Mon Sep 15, 2014 3:14 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
edx wrote:
... If there be a mistake it lies in expecting modern behaviours from 35+ year software and being caught out by it. :wink:

To me, it's not a matter of modern vs. vintage, but more of a matter of correct vs. incorrect. The 6502's overflow flag worked correctly for signed binary from its inception ... it was up to the programmer to make proper use of it. In the case of Forth, I believe that access to the overflow flag was limited for application programs, so that duty should have fallen on the person writing the primitives.

The discussion in Section 2.2.2 makes clever use of the phrases "handles the vast majority" and "is generally safe", so I guess it boiled down to a matter of efficiency vs. exhaustive correctness. I have little doubt that a non-zero percentage of modern software hides similar trade-offs, documented or not.

Mike
Top
 Profile  
Reply with quote  
BigEd
 Post subject: Re: Common D< Forth bug
PostPosted: Mon Sep 15, 2014 4:00 pm 
Offline
User avatar

Joined: Thu Dec 11, 2008 1:28 pm
Posts: 10986
Location: England
That clock view of binary arithmetic reminded me - rightly or wrongly - of the timer arithmetic used by Occam for the Transputer. The chip has built in timers, and you want to be able to calculate time intervals regardless of the actual value of the time. You need a circular model.
Top
 Profile  
Reply with quote  
edx
 Post subject: Re: Common D< Forth bug
PostPosted: Tue Sep 16, 2014 7:05 am 
Offline

Joined: Sun Sep 14, 2014 11:18 am
Posts: 14
barrym95838 wrote:
To me, it's not a matter of modern vs. vintage, but more of a matter of correct vs. incorrect. ... In the case of Forth, I believe that access to the overflow flag was limited for application programs, so that duty should have fallen on the person writing the primitives.
In Borland Pascal I can mistakenly enter a literal number which exceeds the range of an int and the compiler will detect it. Not so with Borland C which will happily accept the number and produce nonsense leaving me to find the error myself. Which behaviour is "correct"?

IMO it depends on the language and the extent to which it's prepared to protect users from themselves. Could I live with the signed relationals of Fig-Forth and PolyForth? Possibly. I've never had to because my Forth follows later Standards. For all I know it may be as easy as Forth Inc claim - particularly when there is D< to handle the exceptional cases.
Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Tue Sep 16, 2014 3:21 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
edx wrote:
... Which behaviour is "correct"?

That's a rhetorical question, right? :wink:

Quote:
... particularly when there is D< to handle the exceptional cases.

But that was Garth's original beef. D< DIDN'T handle the exceptional cases for him, and he had to re-write the primitive.

Mike
Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Tue Sep 16, 2014 6:36 pm 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
Hey, Garth. Did you try checking the most significant half first? I haven't tested this, but I think that I might have saved you a whole byte!

Code:
       HEADER "D<", NOT_IMMEDIATE    ; ( d1 d2 -- f )
DLT:   PRIMITIVE
       LDA  4,X        ; compare high words first
       CMP  0,X
       BMI  dlt1
       BNE  dult1      ; ( POP3_FALSE )
       LDA  6,X        ; only need to compare low words
       CMP  2,X        ;  if the high words were equal
       BPL  dult1
dlt1:  JMP  POP3_TRUE
 ;-------------------


Mike
Top
 Profile  
Reply with quote  
White Flame
 Post subject: Re: Common D< Forth bug
PostPosted: Wed Sep 17, 2014 4:19 am 
Offline

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679
I see you fell into the same trap as the original D<. ;)

BMI/BPL are insufficient for detecting signed less-than; you need to involve the overflow flag as well.

http://www.6502.org/tutorials/compare_beyond.html#5

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor
Top
 Profile  
Reply with quote  
barrym95838
 Post subject: Re: Common D< Forth bug
PostPosted: Wed Sep 17, 2014 5:19 am 
Offline
User avatar

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1950
Location: Sacramento, CA, USA
White Flame wrote:
I see you fell into the same trap as the original D<. ;)

Oops! ... brain hiccup. Sorry, folks.

But ... looking at the other technique at your link, involving flipping the sign bits then doing an unsigned compare:
Code:
       HEADER "D<", NOT_IMMEDIATE    ; ( d1 d2 -- f )
DLT:   PRIMITIVE
       LDA  4,X        ; flip sign bit of d1
       EOR  #$8000
       STA  4,X
       LDA  0,X        ; flip sign bit of d2
       EOR  #$8000
       STA  0,X
       BRA  DULT+2     ; exit through DULT machine code
dlt1:  JMP  POP3_TRUE
 ;-------------------


Meh, cost me a byte, unless I can be sure that it's okay to get rid of the JMP POP3_TRUE ... never mind!

Mike
Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  Page 1 of 2
  [ 24 posts ]  Go to page 1, 2  Next

Board index » 6502.org Users Forum » Forth

All times are UTC


Who is online

Users browsing this forum: No registered users and 6 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
6502.org is an ongoing project by Mike Naberezny and contributors.