Re: Array foreach in scripting languages
"Mat Noguchi (BUNGIE)" <[email protected]> Sun, 13 Aug 2006 11:59:20 -0700
| Newsgroups | gmane.games.devel.windows |
|---|---|
| Message-ID | <1B678752C03CB44AAA5D9C90991EFEEC086C65BB@RED-MSG-42.redmond.corp.microsoft.com> |
If it's a scripting language, don't allow direct manipulation of a container while iterating through it. If you want the side effects of such an operation, defer them until all iterators have been destroyed. MSN ________________________________ From: [email protected] on behalf of Carsten Orthbandt Sent: Sun 8/13/2006 4:21 AM To: Game Development for MS Windows Subject: Re: [GD-Windows] Array foreach in scripting languages I'm afraid I wasn't clear. The actual data structure of the list or array may be anything. In the case at hand, it is not a linked list. The linked list I was referring to would be a linked list of all iterators attached to a specific array instance specifically for adjusting the iterators on list changes. So yes, that's what I was about to do. Modifying arrays poses some serious challenges for multi-threaded operation anyway, I don't think it's getting much harder with this iterator scheme in place. I was planning to do heavy multi-threading through thread pools and task lists that operate in higher level chunks as to not spend to much time on the threading itself. Best regards, Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de <http://www.sek-ost.de/> Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt ________________________________ Von: [email protected] im Auftrag von Richard Fabian Gesendet: So 13.08.2006 12:13 An: Game Development for MS Windows Betreff: Re: [GD-Windows] Array foreach in scripting languages Dunno if it suits how you work, but you could always attach the iterators to the linked list on iterator construction. this way you can tell all the currently attached iterators that element X is gone, handle it. with thiis in place, we've never had any problems with our iterators, but i suspect that we may have problems in the future with PS3 and such because this technique doesn't lend itself to threaded access. On 8/13/06, Carsten Orthbandt <[email protected]> wrote: The reason I'd like to have this work is that it is a recurring pattern in lots of code I see (iterating a list and deleting/inserting entries). If I go the route with tracked iterators, any insert or delete operation will work as expected since then I'm dealing with these cases per iterator: - delete item before or at current position -> decrement position and size - delete item after current position -> decrement size - insert item before or at current position -> increment position and size - insert item after current position -> increment size The case "delete item at current position" potentially has to deal with the actual element being deleted. In C++ this would be a problem but in my scripting language the list entry would go away but the actual value referenced will stay around due the iterator still holding onto it. I'm quite surprised that the C# docs don't even mention this situation. I'm even more surprised to find that MS added a "for each" to C++. It's supposed to be only for managed code but it worked fine in my standard STL unmanaged test. Simply banning this scenario would mean that users have to write such code: int i,iC=List.GetSize(); for(i=0;i<iC;i++) { if(Condition(List[i])) { List.Delete(i); i--;iC--; } }; manually. Which is goes against the whole idea of pro- viding a foreach and IMHO even more error-prone. I'm not sure if I more dislike the C#/STL behaviour of throwing an exception or the Python behaviour of simply ignoring the problem. <rant> In my case, an exception is not an option since I'm not going to clutter my cute little scripting language with a concept (exceptions) that I consider totally broken in the first place. There's no place in a game for such stuff. It has to run, period. So you have to handle all error conditions anyway. </rant> Best regards, Carsten Orthbandt Founder + Development Director SEK SpieleEntwicklungsKombinat GmbH http://www.sek-ost.de <http://www.sek-ost.de/> Wenn ich Visionen habe, gehe ich zum Arzt. - Helmut Schmidt ________________________________ Von: [email protected] im Auftrag von Kent Quirk Gesendet: So 13.08.2006 04:39 An: Game Development for MS Windows Betreff: Re: [GD-Windows] Array foreach in scripting languages 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. > > ------------------------------------------------------------------------- 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gamedevlists-windows Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=555 ------------------------------------------------------------------------- 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gamedevlists-windows Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=555 -- fabs(); ------------------------------------------------------------------------- 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gamedevlists-windows Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=555 ------------------------------------------------------------------------- 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 [email protected] https://lists.sourceforge.net/lists/listinfo/gamedevlists-windows Archives: http://sourceforge.net/mailarchive/forum.php?forum_id=555