Ability to use arrays in LSL.

Name: Array()
Category: scripting
Subcategory: lsl functions
Author: Nexus Nash
Prop Date: 2005-04-13

Feature Detail
Ability to use arrays in LSL.

Feel free to discuss this feature request further...

Lists are bulky and a pain to use.

I was to be able to do. array data = (a,b,c,d,e...);

llSay(0,(string)data[1]);
OUTPUT: b

Further more, the ability to use them like in PHP,

array data= (apple => 1,banana => 5)
llSay(0,(string)data["banana"]);
OUTPUT: 5

I'm taking functionnality examples from here: www.php.net

Arrays? How about doubles first?


As for arrays, they could be helpful. But then, with a relatively small script buffer limiting the usefulness significantly and the fact intelligent list use can take the place of an array, I'm not sure if it's a priority, per se.

I'm with Jeffrey on this one. Arrays would be helpful, but certainly not high on my priority list.

- Ace

Arrays would be helpful, but the more important feature request here is not the array, but rather the ability to reference a variable with a variable. It would work just fine with lists as well, but we haven't the ability. ex:

list list0 = [ "abc", "def", "ghi" ];
list list1 = [ "123", "456", "789" ];
list list2 = [ "foo", "bar", woo" ];
integer listcount = 3;

function gimmeEnt(string searchString) {
  integer x = 0;
  integer y = 0;
  for (x = 0; x < listcount;x++) {
    for (y = 0; y < llListLength(list$x)) {
      if (llSubStringIndex....
    }
  }
}

AFAIK there is no good way to index/search or manipulate multiple lists because you can not reference the list variable by a variable name, you have to write a recursion function to pass in the static list of lists, which is a very wretchid way to do things.

For more complicated data management scripts (of which I have several) it would allow for much greater flexibility. For scripts in general, it would definitely allow us to do more in the memory constraints, because of the saved bytecode size of implementing your own list indexing/array script.

Didn't cory say we're moving to mono?

For this sort of thing, since SL lists are loosely typed, you can just combine your items and access by offsets. Of course, it requires knowing in advance one of the "dimensions" of your "array", but that info is usually available at design time for most applications.

So in your example, it's a bit trivial because your types are all strings (ostensibly); if using actual different types, it would be a bit more complicated because you'd have to switch on the offset to use the correct type.

Anyway, this boils down to the classic concept of "use co-ordinates x and y (two variables) versus use a single value co-ordinate and a known row/column divisor (one variable) to accomplish the same thing".

If you actually really have a problem that calls for what you outlined, see if it's possible to use the "one-dimensional" approach. If it's not, post your problem (if you can make that piece of code public), and maybe someone will come up with a fix for now.

i want doubles, decent *->string functions, and script comms that pass unadulterated lists.

arrays can wait.

I'd settle for run-time typing, so that cramming vectors into lists didn't suck so bad... Not that this is particularly related to the topic at hand, I suppose.

The code is easy, the problem lies in the limitations of list length. I don't need multiple lists because I don't know how to reference in steps, that's quite simple -- I need multiple lists because a single list does not have enough storage space for the entities needing to be stored.

I've already created my own multidimensional array scripts, it's just a huge waste of resources doing it in LSL, rather than having them as part of LSL.

The main reason we need arrays in LSL is because lists are o(n) and arrays are o(1).

Instead of arrays, how about *associative arrays* aka maps aka hashes (though it need not really be implemented as a hashtable).

Associative arrays can be used *as if* they are real arrays (with perhaps O(log(n)) access instead of O(1)), but can be useful for many other applications.

proposed syntax:

//use maps as arrays.

map myArray[ integer ] => string;

myArray[0] = "Hello";
myArray[1] = "World";

integer i;

//Says "hello" then "world" out loud.
for(i = 0; i < llArrayLength(myArray); i++) {
     llSay(0, myArray);
}

//use maps as a salary table

map salaries[ string ] => integer;

salaries["Philip Linden"] = 1000000;
salaries["Flyingroc Chung"] = salaries["Philip Linden"] * 100;


list names;
names = llArrayKeys(salaries);

for(i = 0; i < llListLength(names); i++) {
     //Note in reality we'd have an array from keys to ints (or floats)
     string name;
     name = llList2String(names, i);
     llGiveMoney( name, salaries[name]); 
}

//use maps as a dictionary

map dict[ string ] => string;

dict["tekki wikki"] = "Huh?";

//...

if( llArrayKeyExists(dict, word) ) {
     llSay(0, "The definition of " + word + " is " + dict[word]);
}

You also need llRemoveKey( map m, map_entry e );

You could also do multidimensional associative arrays.

Definitely. You beat me to saying it.

The number two reason we need arrays in LSL is because working with lists is a grade A pain in the butt. Try to do any kind of big, data-intensive thing in LSL, i.e. a non-simplistic boardgame. I got so sick of all of the annoyingly verbose function calls that I had to do for every single list access that I never wanted to see a list again. This was before llListReplaceList(), but even with it, things are still incredibly verbose. The syntactic sugar of arrays alone would be enough to make it an excellent idea, but O(1) access is also very important.

I understand that SL must work within limited memory, and that arrays may take up more of it, but what is the real reason to have lists and not arrays? I've always assumed it was a memory limitation.

*wishes someone would teach him to use lists

Arrays should be a part of the primitive data types in any language and it boggles my mind that we don't have them yet in LSL. This is basic stuff here. Having to mess with them using functions is lame.

I don't know why LL decided to use lists in LSL - you'd have to ask Cory Linden that. Typically one uses lists because it allows for inserting and removing items with relatively low overhead - all you have to do is fix up a couple pointers, as opposed to moving many array entries to make room for a new item. Also, LSL lists do a reasonably good job of working like both arrays and structures (using strides). If they were concerned about putting too many features in the language, I can see why they went the way they did. It's very LISP-like, in fact.

While there are a few nice features in LSL that I like (states, events), mostly I think they should have just gone with an existing language and adapted it for SL use. I'm looking forward to the Mono transition (next year?), so that we'll be able to use other languages instead of LSL.

I think the real reason is one of security. Linden Labs recognized that the one great thing about a call-by-value language is the level of security implied by such a scheme. The biggest disadvantage of a call-by-value scheme is the fact that all values are copied when modified. That's why LSL lists are even slower than normal lists; a normal list has O(1) insert/delete but call-by-value lists are O(N) for all opeations. However, they're not as slow as modifying an array. In a call-by-value language, the array is considered one value all by itsel, so any "modification" of an array is actually a copy of that array, meaning where populating a list takes sum(1..n,i)=n*(n-1)/2 actions, an array population takes n*n operations or twice as long. An array just isn't an array when an operation like a[5]=3 takes O(N) time.

There's a way around this though, and I'm not talking about Mono(although I can't wait for it either). You can either allow switch statements (curiously missing in LSL) or just use a huge if-then tree for a fixed size array-in-a-function, which takes up 2x or 3x the size. Of course you'd use some CASE tool to create the code (I don't think typing 2000 lines of code for a 500-word fixed size array is good for anyone's help) and cut-paste may be annoying to do in SL, but it's something.

Arrays: yes please !

Doubles: yes please !

more memory: yes please!

Thank you, that was the first thing I thought of.

You can emulate them using llListFindList() and so on, but it's a LOT of code, so even if it wasn't O(N^2) for operations that are O(logN) with associative arrays the big-O constant is a bunch bigger.

Plus they make the memory management problem a lot easier, because you're not copying lists over and over and over.

Think of how much simpler Franimation Overrider would be if all that listhacking code was replaced by references, AND think how much more reliable it would be if it wasn't playing so close to stack-heap collisions.

There's nothing inherently insecure in references. Pointers, yes, but references and pointers are not equivalent, and even lisp got references (property lists are basically associative arrays) thirty years ago.

Hopefully the entire .NET collections namespace will be available in the not to distant future. It's one of the first areas I'd like to open up to scripting as it's one of the most generally useful parts of the framework and has very few integration and security issues.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemcollections.asp

Cheers,

Babbage.

True, but Lisp and LSL are in completely different environments. Lisp wasn't originally designed to handle well in a multitasking environment: CommonLisp was able to handle it correctly only when enough MIT hackers were encouraged to work on it, and only when the speed was up to par, which was only 10 years ago.

Secondly, there are many issues with making LSL into a call-by-reference enabled world. If the developers could make the change quickly without running into too many bugs and not breaking too many scripts, I'd be all for it. But, you'd have to allow for variable typing, because the creation of a reference is a function of types on types, so you no longer have a finite number of types. Not only will you confuse the scripters, it would take the developers more time to implement than their Mono work will take. I'll be patient enough for Mono to bring us references without LL trying to hack them into LSL. (I mention some other problems with references in the thread on memoization that you cross-posted to).

BTW the name's long because it's an anagram.

How soon can we expect Mono! I'm really excited by the development!

That's true. LSL is less efficient than any Lisp environment I have ever used, as well as less reliable, more crash-prone, and less secure.

I was using Lisp 25 years ago on a PDP-11, a computer so slow that you could probably out-benchmark PDP-11 assembly with an LSL script. MAC-Lisp, at this time, was generating better code than DEC's Fortran-IV.

You can have the kind of references you need to implement associative arrays and call-by-reference without creating a reference as a first-class object. For example, you could simply make arrays always pass by reference:

vector floors[] = [ 0 -> <100,10,10>, 1 -> <100,10,20> ];

move_to(vector floors[], integer floor)
{
  llMoveToTarget(floors[floor], ...);
}

add_floor(vector floors[], vector position)
{
  integer new_floor = llGetArraySize(floors) + 1;
  floors[new_floor] = position;
}