NML borrows a lot of good ideas from a wide variety of other languages. One of the best ideas from RSI/IDL and PVWave is their syntax for representing array slicing. NML takes those ideas several steps further.
An array slice represents some subregion of an array. For example, if a is an array defined as:
let a = Array.create [5,3]
then we can extract the middle column of this array by the syntax:
a.[*, 1].
The star-sign * represents all elements of that dimension.
We could extract only the first 3 elements of that middle column by writing:
a.[0 : 2, 1]
where the colon-symbol is used to indicate starting index on the left, and ending index on the right. Both of these indexes can be arbitrary expressions.
But an easier way to refer to the first 3 elements of that column would be to simply state:
a.[0 :# 3, 1]
where the colon-sharp symbol has the starting element index on the left, and the number of desired elements on the right.
If we wanted all of the elements in the middle column, starting from the second element of the column, we would write:
a.[1 : *, 1]
where the star-symbol on the right indicates that we should take all remaining elements.
Because NML is cyclic in array indexing, we can even do array reversal and extension by way of these array slice expressions. If s is the string “hello”, then
s.[1:#5] --> “elloh”
s.[1:#10] --> “ellohelloh”
s.[4:0] --> “olleh”
When the starting index is above the ending index, the array is read out in reverse order, as shown by the final example above.
Shifting of array contents is really just a special form of slicing, where the number of elements is conserved. For example, shifting the string s, from above, by 3 elements to produce “lohel” is performed by the slice expression:
s.[3:#(length s)]
So the shift-of-array operator could be written as:
let shift arr nel =
arr.[nel :# (length arr)]
NML has built-in shift operators that work in multiple dimensions, and so for example, after a 2-D FFT we can shift the entire result so that the old origin becomes the center of the FFT image by means of a simple “shifth” operation (shift-half). That operator shifts arrays by half their dimension size in each dimension. It works in an arbitrary number of dimensions.
So far we have shown “slice expressions”. In another chapter we will address “slice assignments” for the mutation of array subregions.
Slice expressions effectively create new arrays, vectors, lists, tuples, strings, etc., by extracting the indicated elements and producing a fresh copy. NML is very fast at this because, unlike most conventional programs that do slicing, NML performs an initial exploratory scan of the array under the direction of the slice expression, to find out where the actual boundaries of the array are in relation to the slice.
All IF-THEN-ELSE decisions about how many elements to extract, what starting index to use, how index wrapping is to be handled, are made during that initial exploratory scan. Along the way, NML builds up a tree of lambda closures that represents what work needs to be done to perform portions of the slicing operation, sans any decision making.
When the initial exploratory scan is completed, NML will have constructed a tree of lambda closures that represents all the work needed to be done to produce the slice sub-array. And then NML launches the tree from the top closure to actually perform that work.
So while a conventional approach will have repeated IF-THEN-ELSE decisions along the way, e.g., one for each row of a matrix array, NML will have already made those decisions and produced a decisive lambda closure that does the correct thing.
The result is a blazing fast slicing operation of arbitrary complexity.
Here’s an idea possibly worth considering... Many of the slice expressions encountered in actual use represent contiguous subregions of arrays. Arrays are mutable in the sense that individual elements, and subregions, can be altered by assignment. But instead of always making a fresh copy of array subregions, we could use a COPY-ON-WRITE protocol that only makes a fresh copy IFF the subregion is mutated.
That idea could also be extended to non-contiguous array subregions but then the accessor complexity grows without bound, and we would likely find that it is actually faster to just make a fresh copy of the extracted subregion.
Sunday, February 4, 2007
