gamedevlists-windows

[GD-Windows] Array foreach in scripting languages

[Carsten O. <car...@se...>]

I'm currently building a small scripting language for interactive stuff. =
Now I
know there's plenty out there, I'm just doing this for fun.
=20
A tricky question came up and I'd like to collect opinions and =
experiences on
this. It's about foreach for dynamic arrays. Consider this C++-like =
pseudo code:
=20
DynamicArray<int> list;
int i;
for(i=3D0;i<20;i++){list.Add(i);};
foreach(i in list){
    print(i);
    if(i=3D=3D8){list.Delete(12);};
};
=20
The obvious question is how should an active iterator react if the =
traversed list
changes? To answer this, I simply tried it out in two languages I know =
that do
provide both dynamic arrays and foreach: STL, Tcl and C#.
=20
In STL C++ code, I get an exception because of iterator incompatibility.
In Tcl this problem isn't one because the iterator takes a snapshot of =
the list
object on start and there's no language construct to actually change =
this instance.
In C# with the List<int> generic, I get an exception because the =
iterated object
changes (interestingly, this happens on ANY change to the list, even =
appending).
=20
Now what I'd like to know:
- how do other languages cope with this? (Tcl doesn't need to, C++/C# =
simply fails)
- what do YOU think would be sensible behaviour?
=20
Currently I'm considering having all iterators be elements of a =
double-linked list
and let the array object be the dl-list head. So if the number of array =
elements
changes, it can run through all attached iterators and fix their indices =
or stop them.
=20
=20
Carsten Orthbandt
Founder + Development Director
SEK SpieleEntwicklungsKombinat GmbH
http://www.sek-ost.de

Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt
 =20
=20

Re: [GD-Windows] Array foreach in scripting languages

[Kent Q. <ken...@co...>]

In Python, I was shocked to find that this succeeds:

L = range(20)
for i in L:
    print i
    if i==4:
        del L[6]

Result:
-------
0
1
2
3
4
5
7
8
9

I fully expected it to fail. I consider messing with the list you're 
traversing with an iterator to be on a par with sawing off the branch 
you're standing on, unless, as you imply, the list is known to be 
implemented as a linked list. In python, you can surprise yourself. 
Consider this:

for i in L:
    print i
    if i==4:
        del L[3]       # delete one of the items BEFORE the one you're on

       
0
1
2
3
4
6
7
8
9

So what happened is that we ended up skipping element #5, even though we 
deleted element 3.

This is really dependent on the implementation details of the particular 
interpreter, and probably isn't guaranteed by the average language spec.

If you feel strongly about being able to do this, you have to deal with 
the case of deleting the item you're on right now, and also about 
deleting the last element while you're at the last element. Check this out:

 >>> L
['h', 'e', 'l', 'l', 'o']
 >>> for c in L:
            if c=='l':
                L.remove(c)

 >>> L
['h', 'e', 'l', 'o']

In other words, even though I intended to remove BOTH 'l' characters, 
only one of them was removed because deleting one caused me to skip the 
next element.

I think this stuff is so fraught with potential errors by the user, even 
if YOU get it right, that I'd prefer to just ban the practice and make 
people use a "filter" concept like in python, or a remove_if as in STL.

    Kent


Carsten Orthbandt wrote:
> I'm currently building a small scripting language for interactive stuff. Now I
> know there's plenty out there, I'm just doing this for fun.
>  
> A tricky question came up and I'd like to collect opinions and experiences on
> this. It's about foreach for dynamic arrays. Consider this C++-like pseudo code:
>  
> DynamicArray<int> list;
> int i;
> for(i=0;i<20;i++){list.Add(i);};
> foreach(i in list){
>     print(i);
>     if(i==8){list.Delete(12);};
> };
>  
> The obvious question is how should an active iterator react if the traversed list
> changes? To answer this, I simply tried it out in two languages I know that do
> provide both dynamic arrays and foreach: STL, Tcl and C#.
>  
> In STL C++ code, I get an exception because of iterator incompatibility.
> In Tcl this problem isn't one because the iterator takes a snapshot of the list
> object on start and there's no language construct to actually change this instance.
> In C# with the List<int> generic, I get an exception because the iterated object
> changes (interestingly, this happens on ANY change to the list, even appending).
>  
> Now what I'd like to know:
> - how do other languages cope with this? (Tcl doesn't need to, C++/C# simply fails)
> - what do YOU think would be sensible behaviour?
>  
> Currently I'm considering having all iterators be elements of a double-linked list
> and let the array object be the dl-list head. So if the number of array elements
> changes, it can run through all attached iterators and fix their indices or stop them.
>  
>   

Re: [GD-Windows] Array foreach in scripting languages

[Jon W. <hp...@mi...>]

What's confusing is that your code uses the name DynamicArray (which I 
suppose is close to ArrayList in .NET), and your C++ test sample 
probably used std::vector, but you keep referring to the container as a 
"list". They are very different kinds of containers.

You will note that C++ allows you to insert and delete objects in a 
std::list, but not in a std::vector. The reason is that vectors are 
guaranteed to be contiguous, and thus iterators (which may be simple 
pointers) would get invalidated when resizing the underlying storage. 
Meanwhile, when deleting from a list, the only iterator that gets 
invalidated is an iterator pointing to the element being deleted.

Cheers,

                      / h+


Carsten Orthbandt wrote:
> The obvious question is how should an active iterator react if the traversed list
> changes? To answer this, I simply tried it out in two languages I know that do
> provide both dynamic arrays and foreach: STL, Tcl and C#.
>   

Re: [GD-Windows] Array foreach in scripting languages

[Research <res...@ga...>]

Although it can have other side effects, you may be able to live with "Lazy 
Deletion". You mark a list entry as "deleted" when deleted during an 
iterator but not do the delete until your done iterating. Even if you bail 
out of the iteration, the list header can indicate that there are "deleted" 
members in the list and clean them up before the next iteration begins 
(and/or add the list to a list of stuff that needs maintenance between 
frames). Of course this can have side effects, but there are cases where 
this is acceptable and can allow an iterator to split up a list among 
processing units by knowing that the part of the list they are working on is 
safe.

Brett Bibby
GameBrains

----- Original Message ----- 
From: "Carsten Orthbandt" <car...@se...>
To: <Gam...@li...>
Sent: Saturday, August 12, 2006 9:46 PM
Subject: [GD-Windows] Array foreach in scripting languages


> I'm currently building a small scripting language for interactive stuff. 
> Now I
> know there's plenty out there, I'm just doing this for fun.
>
> A tricky question came up and I'd like to collect opinions and experiences 
> on
> this. It's about foreach for dynamic arrays. Consider this C++-like pseudo 
> code:
>
> DynamicArray<int> list;
> int i;
> for(i=0;i<20;i++){list.Add(i);};
> foreach(i in list){
>    print(i);
>    if(i==8){list.Delete(12);};
> };
>
> The obvious question is how should an active iterator react if the 
> traversed list
> changes? To answer this, I simply tried it out in two languages I know 
> that do
> provide both dynamic arrays and foreach: STL, Tcl and C#.
>
> In STL C++ code, I get an exception because of iterator incompatibility.
> In Tcl this problem isn't one because the iterator takes a snapshot of the 
> list
> object on start and there's no language construct to actually change this 
> instance.
> In C# with the List<int> generic, I get an exception because the iterated 
> object
> changes (interestingly, this happens on ANY change to the list, even 
> appending).
>
> Now what I'd like to know:
> - how do other languages cope with this? (Tcl doesn't need to, C++/C# 
> simply fails)
> - what do YOU think would be sensible behaviour?
>
> Currently I'm considering having all iterators be elements of a 
> double-linked list
> and let the array object be the dl-list head. So if the number of array 
> elements
> changes, it can run through all attached iterators and fix their indices 
> or stop them.
>
>
> Carsten Orthbandt
> Founder + Development Director
> SEK SpieleEntwicklungsKombinat GmbH
> http://www.sek-ost.de
>
> Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt
>
>
>
> -------------------------------------------------------------------------
> Using Tomcat but need to do more? Need to support web services, security?
> Get stuff done quickly with pre-integrated technology to make your job 
> easier
> Download IBM WebSphere Application Server v.1.0.1 based on Apache Geronimo
> http://sel.as-us.falkag.net/sel?cmd=lnk&kid=120709&bid=263057&dat=121642
> _______________________________________________
> Gamedevlists-windows mailing list
> Gam...@li...
> https://lists.sourceforge.net/lists/listinfo/gamedevlists-windows
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_id=555