From notes accompanying AS version 1.1 in December 1993:
The Story of Lists
Representation and Efficiency
The way in which lists are represented in memory has changed from
AppleScript 1.0 to AppleScript 1.1, and correspondingly, the characteristics
of these values has changed with respect to efficiency. Efficiency involves
both the amount of time it takes to perform certain operations, and the
amount of space these values consume. Additionally, certain operations can
generate intermediate values (garbage) that are automatically reclaimed by
AppleScript. The more of these intermediate values, the more often the
time-consuming operation of collecting them must occur.
In AppleScript 1.0, lists were represented as linked lists in memory. Linked
lists means that each item was linked to the next via an internal pointer.
On the positive side, linked lists didn’t take up much memory, and
concatenating new item (at least on the left-hand side) was relatively fast
and didn’t create any garbage:
On the negative side, linked lists took longer to reach elements at higher
indicies than they did to reach elements at lower indicies (i.e. the access
time was linear (increased proportionally) to the index of the item being
accessed). This is because the list had to be traversed from beginning,
counting up to the index of the item desired. Also, if you were unfortunate
enough to concatenate on the right-hand side, the entire left-hand side of
the list would have to be copied. This is because we mustn’t change the
left-hand side value to perminantly be concatenated with the right-hand side
because other parts of the program may still be using its old value.
In AppleScript 1.1, lists are represented as vectors. This means that
elements are stored in consecutive locations in memory rather than linked
together. This makes accessing elements by index fast (constant time – it
doesn’t matter about the value of the index), but makes concatenation
generate much more garbage, as both halves of the concatenate operator (&)
must be copied.
This trade-off was made because we found that people accessed items of lists
far more often than they concatenated, or more precisely, that this balance
lead to better overall performance characteristics. However, for certain
scripts, the previous list representation may have been more appropriate,
therefore we did two things: We allow linked lists to be explicitly created,
and we allow insertion operations on vectors.
Explicit Linked Lists
AppleScript 1.1 allows the old-style (linked) lists to be created by using a
square bracket notation. Whereas to put variables x, y and z into a vector,
we say:
{x, y, z}
we can now also write scripts that put these variables into a linked list
via:
[x, y, z]
Note, however, that both of these print results out with braces.
Furthermore, asking the class of either of these two representations will
return the class ‘list’:
class of {1, 2} → list
class of [1, 2] → list
If the two representations need to be distinguished, the ‘best type’
property may be used:
best type of {1, 2} → vector
best type of [1, 2] → linked list
For the concatenation operator (&), the representation of the result will be
the same as the representation of the left-hand side:
best type of ({1} & [2]) → vector
best type of ([1] & {2}) → linked list
When AppleScript 1.1 reads 1.0 script files, all lists stored in persistent
properties will actually be linked lists. However, the distinction will be
transparent to the script when run.
Linked lists are a very good representation for recursive programs that
“walk” lists, processing one item on each recursive step. This is usually
the case when the ‘rest’ property is being used. For example, the following
function computes the sum of the squares of the items in a list:
on SumOfSquares(theList)
if theList = {} then
return 0
else
set element to first item of theList
return (element * element) + SumOfSquares(rest of theList)
end if
end SumOfSquares
When this function is applied to a linked list or vector, the same answer
results (note that the empty list equals the empty vector, so the equality
test works in either case):
SumOfSquares([1, 2, 3]) → 14
SumOfSquares({1, 2, 3}) → 14
however the linked list case doesn’t generate any garbage. The vector case
must generate a new sub-list for each time the ‘rest’ property is accessed.
Vector Insertion
The second thing we did to enhance the performance when using vectors is to
allow items to be inserted at the beginning or end of a vector. E.g.:
set myList to {1, 2}
set end of myList to 3
myList → {1, 2, 3}
set beginning of myList to 0
myList → {0, 1, 2, 3}
Unlike concatenation, setting the beginning or end of a list actually
changes the list. Note that it’s not the variable that’s being changed, it’s
the list itself. That means that if two variables are referring to the same
list, and an item is inserted into the list, both variables will refer to
the changed list:
set x to {1, 2}
set y to x – y refers to the same value that x refers to
set end of x to 3
x → {1, 2, 3}
y → {1, 2, 3}
However, despite the “destructive” nature of insertion, often times we’re
only using lists to accumulate results, and don’t care that variables
referring to the list will be modified (presumably we don’t care because
only one variable is refering to that list anyway). In these cases, we can
greatly increase the efficiency of our scripts by inserting items rather
than concatenating them, forming new lists and leaving the old ones as
garbage. For example, this script that accumulates the squares of a list of
numbers:
set myNumbers to {1, 2, 3}
set resultList to {}
repeat with i in myNumbers
set resultList to resultList & {i * i}
end repeat
resultList → {1, 4, 9}
can be made more efficient (faster and generate less garbage) if rewritten
as:
set myNumbers to {1, 2, 3}
set resultList to {}
repeat with i in myNumbers
set end of resultList to i * i
end repeat
resultList → {1, 4, 9}
For the record, setting the end of a list is by far the most efficient, and
setting the beginning is second (because all the items must be slid down to
make room for a new first item).
Minor difference in Concatenation
There is one minor difference between the way concatenation works on linked
lists and vectors (and consequently between AppleScript 1.0 and AppleScript
1.1 using the curly brace notation for lists). When linked lists are
concatenated, only the left-hand argument is copied, the right-hand argument
is shared. For example:
set x to [1, 2, 3]
set y to [4, 5, 6]
set z to x & y
set item 2 of y to 999
z → {1, 2, 3, 4, 999, 6}
Here, x and y are two linked lists (or AppleScript 1.0 lists) that are
concatenated. Since y appears on the right-hand side of the concatenate
operator (&), it is shared between y and the last three elements of z. Then
when y is updated, these changes are reflected in z also.
However, if vectors are used, both x and y are copied to create z, and
updating y does not change z:
set x to {1, 2, 3}
set y to {4, 5, 6}
set z to x & y
set item 2 of y to 999
z → {1, 2, 3, 4, 5, 6}
Although this does constitute a change in the default behavior from
AppleScript 1.0 to 1.1, we believe the new behavior is more intuitive, and
the old behavior can be preserved using the square bracket syntax.
