Help with Array implementation

[program...@gmail.com]

I am trying to implement an Array word that makes arrays. The problem I am having is trying to make do some bounds checking. I don't want an array to access memory that doesn't belong to it, so I need this feature.

Here is my implementation so far. I'm having a problem keeping track of the size of the array in an Array instance. Maybe someone could tell me how to fix this implementation?


: ARRAY ( cellCount - )

\ Check if cellCount is greater than zero
dup dup ( cellCount cellCount cellCount )
1 < IF ( cellCount cellCount )
CR ." Please specify an array size greater than zero." CR
drop drop ( )
abort
THEN

\ Compile-time behavior
CREATE CELLS ALLOT ( cellCount ) \ Creates and initializes the instance
, \ store cellCount ( )

\ Run-time behavior
DOES> ( index address )

@ \ retrieves cellcount ( index cellCount )
swap ( cellCount index )

\ lower limit check
dup ( cellCount index index )
0 < IF ( cellCount index )
CR ." Please specify an index that is greater than zero." CR
drop \ Removes the address of the array instance
-1 throw \ Stop normal execution after error
THEN

\ upper limit check
< IF ( cellCount index -- )
CR ." Index out of bounds!"
abort
THEN

SWAP CELLS + \ Calculates address to return
; immediate

[program...@gmail.com]

This is how you use the Array word:

\ Creating an array instance

<element count> Array <array name>

\ Accessing the address of an Array element

<element number> <array name>

Example:

10 Array my-array
4 my-array ( addr )
99 ( addr n )
swap ( n addr )
! \ 99 stored in element number 4

[Hugh Aguilar]

I have a couple of implementations of arrays in my novice package:
http://www.forth.org/novice.html

I recommend that you not mess with implementing data structures until
you have attained some experience writing programs.

[Elizabeth D. Rather]

On 9/13/12 4:40 PM, program...@gmail.com wrote:
> I am trying to implement an Array word that makes arrays. The problem I am having is trying to make do some bounds checking. I don't want an array to access memory that doesn't belong to it, so I need this feature.
>
> Here is my implementation so far. I'm having a problem keeping track of the size of the array in an Array instance. Maybe someone could tell me how to fix this implementation?
>

I posted a similar definition as an example just recently.

>
> : ARRAY ( cellCount - )
>
> \ Check if cellCount is greater than zero

Why? Just on general principles? Unless you seriously think someone is
going to do such a dumb thing, it's wasted code.

> dup dup ( cellCount cellCount cellCount )

Don't do two DUPs here, because...

> 1 < IF ( cellCount cellCount )
> CR ." Please specify an array size greater than zero." CR
> drop drop ( )

...it makes you do two DROPs here. If you needed to do two DROPs, you
could always say 2DROP, ut even that is unnecessary.

> abort

ABORT is a really useless error response. ABORT" at least lets you issue
an error message. THROW is even better.

> THEN
>
> \ Compile-time behavior
> CREATE CELLS ALLOT ( cellCount ) \ Creates and initializes the instance
> , \ store cellCount ( )

This is where you needed the second copy of the length. It's always
better from a readability perspective to do your DUP where you need it,
which would be before the CELLS ALLOT.

>
> \ Run-time behavior
> DOES> ( index address )
>
> @ \ retrieves cellcount ( index cellCount )
> swap ( cellCount index )
>
> \ lower limit check
> dup ( cellCount index index )
> 0 < IF ( cellCount index )
> CR ." Please specify an index that is greater than zero." CR
> drop \ Removes the address of the array instance
> -1 throw \ Stop normal execution after error

You could really combine the message with the THROW by specifying a
meaningful THROW code that would trigger a message at the CATCH level.
And, again, what is the likelihood that you will get a negative index?
If your calling code is well-vetted, the likelihood is zero, so this is
a wasted check.

> THEN
>
> \ upper limit check
> < IF ( cellCount index -- )
> CR ." Index out of bounds!"
> abort
> THEN

You have a stack underflow, I think. Try OVER instead of the SWAP DUP
above, with a DUP here.

What's on your stack now? You haven't tested this, have you?

>
> SWAP CELLS + \ Calculates address to return
> ; immediate
>

Why should this be IMMEDIATE? You would never want to execute this in
compile mode.

Cheers,
Elizabeth

--
==================================================
Elizabeth D. Rather (US & Canada) 800-55-FORTH
FORTH Inc. +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[Elizabeth D. Rather]

On 9/13/12 9:06 PM, Elizabeth D. Rather wrote:
...

> I posted a similar definition as an example just recently.

Re-post:

: BUFFER ( size -- ) CREATE DUP , CELLS ALLOT
DOES> ( i -- a ) DUP @ >R ( i a ) OVER 0 R> WITHIN IF \ Legal
SWAP 1+ CELLS + ELSE 10 THROW THEN ;

This takes an index and returns the indexed cell's address. Example:

10 CONSTANT SIZE
SIZE BUFFER MY-STUFF

: SHOW ( -- ) SIZE 0 DO I MY-STUFF @ . LOOP ;

This version uses 10 THROW in case of an error. All positive numbers are
available to be assigned as THROW codes by an application, so where
there is a CATCH you can detect a number and issue an appropriate error
message.

[Mark Wills]

On Sep 14, 8:29 am, "Elizabeth D. Rather" <erat...@forth.com> wrote:
> On 9/13/12 9:06 PM, Elizabeth D. Rather wrote:
> ...
>
> > I posted a similar definition as an example just recently.
>
> Re-post:
>
> : BUFFER ( size -- )   CREATE  DUP , CELLS ALLOT
>     DOES> ( i -- a )   DUP @ >R ( i a ) OVER 0 R> WITHIN IF  \ Legal
>           SWAP 1+ CELLS +  ELSE 10 THROW  THEN ;
>
> This takes an index and returns the indexed cell's address. Example:
>
> 10 CONSTANT SIZE
> SIZE BUFFER MY-STUFF
>
> : SHOW ( -- )   SIZE 0 DO  I MY-STUFF @ .  LOOP ;
>
> This version uses 10 THROW in case of an error. All positive numbers are
> available to be assigned as THROW codes by an application, so where
> there is a CATCH you can detect a number and issue an appropriate error
> message.
>
> Cheers,
> Elizabeth
>
> --
> ==================================================
> Elizabeth D. Rather   (US & Canada)   800-55-FORTH
> FORTH Inc.                         +1 310.999.6784
> 5959 West Century Blvd. Suite 700

> Los Angeles, CA 90045http://www.forth.com

>
> "Forth-based products and Services for real-time
> applications since 1973."
> ==================================================

Elizabeth, just out of interest, can you show SHOW with a CATCH in it
to show catching an error?

[Mark Wills]

Please see this thread from just a few days ago:

http://groups.google.com/group/comp.lang.forth/browse_thread/thread/b45e7a3d6ca9b15c#

I posted some code there (with comments) that does what you are
looking for. You should be able to (hopefully) follow the code. If you
have trouble following how it works please feel free to post questions
either in this or the original thread.

Mark

[Elizabeth D. Rather]

On 9/13/12 9:45 PM, Mark Wills wrote:
> On Sep 14, 8:29 am, "Elizabeth D. Rather" <erat...@forth.com> wrote:
>> On 9/13/12 9:06 PM, Elizabeth D. Rather wrote:
>> ...
>>
>>> I posted a similar definition as an example just recently.
>>
>> Re-post:
>>
>> : BUFFER ( size -- ) CREATE DUP , CELLS ALLOT
>> DOES> ( i -- a ) DUP @ >R ( i a ) OVER 0 R> WITHIN IF \ Legal
>> SWAP 1+ CELLS + ELSE 10 THROW THEN ;
>>
>> This takes an index and returns the indexed cell's address. Example:
>>
>> 10 CONSTANT SIZE
>> SIZE BUFFER MY-STUFF
>>
>> : SHOW ( -- ) SIZE 0 DO I MY-STUFF @ . LOOP ;
>>
>> This version uses 10 THROW in case of an error. All positive numbers are
>> available to be assigned as THROW codes by an application, so where
>> there is a CATCH you can detect a number and issue an appropriate error
>> message.
>

> Elizabeth, just out of interest, can you show SHOW with a CATCH in it
> to show catching an error?
>

Since the SIZE parameter was used both for the definition of MY-STUFF
and its display in SHOW, there is not really an opportunity for an
error, so a CATCH would be inappropriate.

The best approach to managing errors is to design and write your code so
that they can't occur. Much cheaper than adding code to handle them.

Theoretically, you could get in trouble by writing, say,

MY-STUFF 1000 ERASE

...but if your application needs to initialize it, much better to provide:

: CLEAR-STUFF ( -- ) MY-STUFF SIZE CELLS ERASE ;

...and use that.

The best way to manage errors is to design your code such that they are
avoided. The only general areas in which you really have to check are
where you're getting values from the user interface or values from
hardware. In both cases, the parameters should be checked at the point
at which you get them, so lower-level code doesn't have to worry.

Cheers.

[Doug Hoffman]

On 9/14/12 3:06 AM, Elizabeth D. Rather wrote:

> And, again, what is the likelihood that you will get a negative index?
> If your calling code is well-vetted, the likelihood is zero, so this is
> a wasted check.

When the index is computed this could be more likely than one might
think. If we remove checks for the debugged production program, what is
the harm in checking for negatives during development?

-Doug

[program...@gmail.com]

>
>
>
> I have a couple of implementations of arrays in my novice package:
>
> http://www.forth.org/novice.html
>
>
>
> I recommend that you not mess with implementing data structures until
>
> you have attained some experience writing programs.

Does you Array implementation have bounds checking?

[Jason Damisch]

> Does you Array implementation have bounds checking?

does your code tend to be so error prone, and your testing regimen so lax that you need bounds checking?

[Coos Haak]

Op Thu, 13 Sep 2012 21:55:06 -1000 schreef Elizabeth D. Rather:

As MY-STUFF needs an index, write
0 MY-STUFF 1000 ERASE

>
> ...but if your application needs to initialize it, much better to provide:
>
> : CLEAR-STUFF ( -- ) MY-STUFF SIZE CELLS ERASE ;
>
> ...and use that.
>

Add a zero (index of the first element) before MY-STUFF here too.

> The best way to manage errors is to design your code such that they are
> avoided. The only general areas in which you really have to check are
> where you're getting values from the user interface or values from
> hardware. In both cases, the parameters should be checked at the point
> at which you get them, so lower-level code doesn't have to worry.
>
> Cheers.
> Elizabeth


--

Coos

CHForth, 16 bit DOS applications
http://home.hccnet.nl/j.j.haak/forth.html

[Elizabeth D. Rather]

On 9/14/12 9:10 AM, Coos Haak wrote:
> Op Thu, 13 Sep 2012 21:55:06 -1000 schreef Elizabeth D. Rather:

...

>>>>
>>>> Re-post:
>>>>
>>>> : BUFFER ( size -- ) CREATE DUP , CELLS ALLOT
>>>> DOES> ( i -- a ) DUP @ >R ( i a ) OVER 0 R> WITHIN IF \ Legal
>>>> SWAP 1+ CELLS + ELSE 10 THROW THEN ;
>>>>
>>>> This takes an index and returns the indexed cell's address. Example:
>>>>
>>>> 10 CONSTANT SIZE
>>>> SIZE BUFFER MY-STUFF
>>>>
>>>> : SHOW ( -- ) SIZE 0 DO I MY-STUFF @ . LOOP ;
>>>>

...

>> MY-STUFF 1000 ERASE
> As MY-STUFF needs an index, write
> 0 MY-STUFF 1000 ERASE
>>
>> ...but if your application needs to initialize it, much better to provide:
>>
>> : CLEAR-STUFF ( -- ) MY-STUFF SIZE CELLS ERASE ;
>>
>> ...and use that.
>>
> Add a zero (index of the first element) before MY-STUFF here too.

Yep, good catch, thanks!

Cheers,

[hughag...@yahoo.com]

On Friday, September 14, 2012 9:58:02 AM UTC-7, (unknown) wrote:
> > > > > I have a couple of implementations of arrays in my novice package: > > http://www.forth.org/novice.html > > > > I recommend that you not mess with implementing data structures until > > you have attained some experience writing programs. Does you Array implementation have bounds checking?

Yes. 1ARRAY etc. have bounds checking. There is a compile-time switch that turns this on and off. As I recall, I am only checking for too large of an index and not for negative indices --- you might want to add the check for negative indices as an exercise. As I recall, ARY doesn't have bounds checking at all.

For the most part, I recommend gaining experience by writing programs. It is pretty cool that Forth allows the language to be extended, but there are too many Forthers who treat Forth as a science-fair experiment --- they get bogged down in extending the language and they never write any programs. There are many who go straight to writing a Forth compiler without having ever written any programs and without really knowing very much about Forth *programming* (as opposed to Forth internal workings).

Use the novice package as a foundation for some programs. If you don't like it, then you can write your own or at least upgrade what I've got --- but you will have some actual experience behind you by that time.

[Doug Hoffman]

On 9/14/12 1:56 PM, Jason Damisch wrote:
>
>> Does you Array implementation have bounds checking?
>
> does your code tend to be so error prone, and your testing regimen so lax that you need bounds checking?
>

Most Forths I've seen have other "checks" such as matched conditionals.
I don't think users of these Forths tend to write error prone code or
inadequate testing regimens. Catching mismatched conditionals is just
low hanging fruit and simply reduces headaches during development.
Similarly, array index checking is a way to catch low hanging fruit,
IMO. I've caught array index errors in code posted to clf on at least
two different occasions (by simply using my own array defs). But I can
understand the other point of view, and so don't get dogmatic about it.

-Doug

[rickman]

On 9/14/2012 4:38 PM, hughag...@yahoo.com wrote:
> On Friday, September 14, 2012 9:58:02 AM UTC-7, (unknown) wrote:
>>>>>> I have a couple of implementations of arrays in my novice package:> > http://www.forth.org/novice.html> > > > I recommend that you not mess with implementing data structures until> > you have attained some experience writing programs. Does you Array implementation have bounds checking?
>
> Yes. 1ARRAY etc. have bounds checking. There is a compile-time switch that turns this on and off. As I recall, I am only checking for too large of an index and not for negative indices --- you might want to add the check for negative indices as an exercise. As I recall, ARY doesn't have bounds checking at all.

I did something like this with help from this group I seem to recall. I
used "within" to check both the upper and lower bound of the index. The
funny part is that this code uses a lot of forth words that I use no
where else, so every time I return to this code I have to relearn it all
over again. I guess the arteries are starting to harden...

Rick

[Hugh Aguilar]

On Sep 14, 1:38 pm, hughaguila...@yahoo.com wrote:
> Yes. 1ARRAY etc. have bounds checking. There is a compile-time switch that turns this on and off. As I recall, I am only checking for too large of an index and not for negative indices --- you might want to add the check for negative indices as an exercise. As I recall, ARY doesn't have bounds checking at all.

Actually, I wasn't thinking straight when I wrote that post. And
nobody caught it!

You don't need to explicitely check for negative indices. You just
check for too large of an index with an unsigned comparison --- a
negative index will seem like a really large index and will get caught
that way.

This is now the novice package does it.

[Mark Wills]

Ooh! Nice little trick!