Rebol Programming/Language Features/Series
Introducing series edit
Series were introduced to Rebol by its designer to represent sequences of values. The most typical series in Rebol are blocks.
Naturally, it would be quite nifty if you could access, manipulate, and refer to individual entries within a series.
Well, it just so happens that Rebol provides a quite extensive "data access technology" for accomplishing this.
Let's look at a first example which will help to sharpen our intuitive idea as to what a series looks like.
The following is a Rebol block which has two entries:
series1: [1 2] ; == [1 2]
You might read this as
| “ | The word series1 refers to a block having 2 entries, both of which happen to refer to integers. | ” |
Since any block has zero or more entries (you did know that a block can have nothing in it, n'est-ce pas?), and since as a point of fact this particular block happens to have 2 entries, you would be quite correct to say that the block can be treated as a series.
And of course, looking at this, you might wonder, how do you do things like "ask" what the second entry's value is? Or maybe you want to know if the n'th entry in a particular series exists? Or maybe you wish to change a particular entry within a series.
You can do all this and much more in Rebol.
So let's take a look at how we can access data in a series within Rebol.
Data access methods edit
In Rebol we can use several methods. The method using the first, second, etc. functions:
first series1 ; == 1
The method using the path notation:
series1/1 ; == 1
The method using the pick function:
pick series1 1 ; == 1
Using variables for data access edit
Let's suppose, that we have got a variable (e.g. i),
i: 2
that shall be used to access a specific entry within a series. How can this be done?
Although the method using the first function doesn't look useful for this, it can be used too. The details are described in the subsequent sections.
The method using the path notation is:
series1/:i ; == 2
The method using the pick function:
pick series1 i ; == 2
Why series/i doesn't work?
edit
Actually, series/i does work, but it doesn't interpret the word i as a variable. Example:
i: 20 series23: [1 i 3] series23/i ; == 3
Description: when the interpreter encountered the series23/i expression, it tried to find the word i in series23, i.e. it took the word as a value, not as a variable. The value returned is the value next to the value, that has been found.
But since core 2.6.0 series/(i) is implemented:
i: 1 series23: [1 i 3] series23/(i) ; == 1
By placing the word i into parentheses, the parenthesized expression is evaluated and the value of the third entry of the series is returned.
Changing series edit
Sometimes we need to change a series. Let's suppose, that we want to change series1. The first method uses the change function:
series1: [1 2] change series1 3 series1 ; == [3 2]
The path notation method:
series1: [3 2] series1/1: 1 ; == [1 2]
The poke function method:
series1: [1 2] poke series1 1 3 ; == [3 2]
Using variables edit
If we have got a variable i as above, we can still use the change method. The details are discussed in the subsequent sections.
The path notation method:
series1: [3 2] i: 2 series1/:i: 4
The poke method:
series1: [3 2] i: 2 poke series1 i 4 ; == [3 4]
Data access method differences edit
The three data access methods listed above exhibit different behaviour in special situations. Let's prepare series2 to see the differences:
series2: [1 2] f: does [""] poke series2 1 :f
The first function access method
edit
When we try to access an entry that doesn't exist, an error is caused:
third series2 ** Script Error: Out of range or past end ** Near: third series2
When we access a function using this method, the function is the result:
type? first series2 ; == function!
The path notation access method edit
When we try to get the value of an entry that doesn't exist, we obtain the none value:
series2/3 ; == none
When we access a function using the path method, the function is evaluated:
type? series2/1 ; == string!
The pick function access method
edit
When we try to get the value of an entry that doesn't exist, we obtain the none value:
pick series2 3 ; == none
When we access a function using the pick method, the function is the result:
type? pick series2 1 ; == function!
Why does Rebol need so many access methods? edit
Actually it doesn't, but the methods work differently as has been shown and that is why we can choose the method that is the most appropriate for our task.
If we prefer the most strict bound checking, we may prefer first.
If we need automatic evaluation of functions or automatic searching, we may prefer the path access.
If we want a simple access method, that doesn't evaluate functions, we may choose pick.
Length of a series edit
A series can have many entries. It may be useful to know the actual number for a given series. We can use the length? native to find it:
length? [1 2 3] ; == 3
On the other hand, it is even possible, that a series does not have any entry. There is a Rebol native empty? which tells us, whether a series "does not have any entry". In that case the length? native yields zero:
series3: [] ; == [] empty? series3 ; == true length? series3 ; == 0
From head to tail and back again edit
Sometimes we need to access series sequentially instead of using indexed access. Rebol series can be accessed sequentially without a need to use any additional datatype.
To move sequentially "one entry at a time" in a non-empty series we can use the next native. The next native yields a series with the first entry "skipped". The second entry of the original series becomes the first entry of the new series.
series8: [1 2 3 4] ; == [1 2 3 4] series9: next series8 ; == [2 3 4]
The first, second, etc. entries of the new series are the same, as the second, third, etc. entries of the original series:
series9/1 ; == 2 series8/2 ; == 2 series9/2: 5 ; == [2 5 4] series8/3 ; == 5
In the new series we can use even the skipped entries: (R2 only)
series9/-1 ; == 1
The length of the new series is equal to the length of the original series minus one:
length? series8 ; == 3 length? series9 ; == 2
Instead of skipping one entry at a time, we can skip more entries at once using the skip action. A Rebol description of the skip action for non-negative offset:
skip-def: func [
{Skips some places of a series}
series [series!]
offset [integer!] {Can be positive, or zero.}
][
loop offset [
series: next :series
]
:series
]
series8: [1 2 3 4] ; == [1 2 3 4]
series10: skip-def series8 2 ; == [3 4]
If we skip zero entries, we obtain the original series:
series8: [1 2 3 4] ; == [1 2 3 4] same? series8 skip series8 0 ; == true
If we skip all entries of a series, we obtain an empty series called its tail:
tail-def: func [
{Returns the tail of a series.}
series [series!]
][
skip :series length? :series
]
tail-def [1 2 3] ; == []
Here is a definition of a function that determines whether a series is a tail:
tail?-def: func [
{Finds out, if a given series is a tail}
series [series!]
][
empty? :series
]
tail?-def [1 2 3] ; == false tail?-def [] ; == true
Skipping further from tail using the next function, doesn't have any effect:
same? next tail [1 2 3] tail [1 2 3] ; == true
We can use the back action to skip one entry backwards, which means the reverse of next:
series11: tail [1 2 3 4] ; == [] series12: back series11 ; == [4]
Let's enhance the skip-def to use negative offset values:
skip-def: func [
{Skips some places of a series}
series [series!]
offset [integer!] {Can be positive, zero, or negative.}
][
either positive? offset [
loop offset [
series: next :series
]
][
loop negate offset [
series: back :series
]
]
:series
]
series11: tail [1 2 3 4] ; == [] series13: skip-def series11 -2 ; == [3 4]
The series we obtain from a given series by skipping the maximum possible number of entries backwards is called the head of the given series. Any subsequent back call doesn't skip any further and yields the head too:
series14: next [1 2 3] ; == [2 3] head series14 ; == [1 2 3] same? back head series14 head series14 ; == true
We can use the above definition to provide a Rebol function determining if a series is a head:
head?-def: func [
{Returns true for a head series.}
series [series!]
][
same? :series back :series
]
head?-def [] ; == true
With a help of head? we can even provide the Rebol description of head:
head-def: func [
{Returns the head of a series.}
series [series!]
][
while [not head? :series] [series: back :series]
:series
]
The number of the "backward" entries increased by one can be obtained as a result of the index? native:
index? next [1 2] ; == 2
Referring to values edit
Let's discover a less natural property of series. A series can refer twice (or more times) to a given value. The following function creates a block referring to a given value exactly twice:
twice: func [value [any-type!]] [
head insert/dup make block! 2 get/any 'value 2
]
Let's test the properties of the function we defined:
series3: twice 1 ; == [1 1] same? first series3 second series3 ; == true
series4: twice 'o1 ; == [o1 o1] same? first series4 second series4 ; == true
o2: make object! [attribute: "OK"] series5: twice o2 ; == [ ; make object! [ ; attribute: "OK" ; ] ; make object! [ ; attribute: "OK" ; ]] same? first series5 second series5 ; == true o2/attribute: "Surprise?" series5 ; == [ ; make object! [ ; attribute: "Surprise?" ; ] ; make object! [ ; attribute: "Surprise?" ; ]]
By analogy, one value can be referenced by two series:
o3: make object! [attribute: "OK"] series6: reduce [o3 1] ; == [ ; make object! [ ; attribute: "OK" ; ] 1]
series7: reduce [o3 2] ; == [ ; make object! [ ; attribute: "OK" ; ] 2] o3/attribute: "Surprised Again?" series6 ; == [ ; make object! [ ; attribute: "Surprised Again?" ; ] 1] series7 ; == [ ; make object! [ ; attribute: "Surprised Again?" ; ] 2]
Properties of the change action
edit
If we want to change a series, we can use the change action. Change can be said to change the series; it causes the affected entry to refer to another value. On the other hand, change doesn't affect the values:
a: make object! [attribute: "OK"]
series15: twice a ; == [ ; make object! [ ; attribute: "OK" ; ] ; make object! [ ; attribute: "OK" ; ]]
change series15 2 ; == [ ; make object! [ ; attribute: "OK" ; ]]
series15 ; == [2 ; make object! [ ; attribute: "OK" ; ]] probe a ; make object! [ ; attribute: "OK" ; ]
change doesn't return the original series. It skips the affected entries to facilitate subsequent changes.
Comparing entries and series edit
For any series we can use the copy action to create a new series referring to the same values. A copy of a series is not the same series as the original, though:
series16: reduce [make object! [attribute: "OK"]] ; == [ ; make object! [ ; attribute: "OK" ; ]]
series17: copy series16 ; == [ ; make object! [ ; attribute: "OK" ; ]]
same? series16 series17 ; == false change series16 1 ; == [] series16 ; == [1] series17 ; == [ ; make object! [ ; attribute: "OK" ; ]]
We have seen an example of a situation, when two distinct series entries refer to one Rebol value, or a situation, when two distinct series (prepared using e.g. the skip function) share some entries. Although series entries do not behave as stand-alone entities in Rebol, we can specify an individual entry by specifying a series and a number of the entry in the
series. Thus, we can find out, if two entries (references) specified are the same. The function doing this can be found at References.
Since we are able to compare entries, we can say, that non-empty series having the same datatype are the same, if they consist of the same entries. The trouble with this method is, that it is not usable for empty series, because in an empty series there is no entry we could use for the comparison purposes.
We call two series mutually independent, if they neither share any entries, nor they can be derived from one "mother" series using the skip function. In Rebol this definition can be written as follows:
independent?: func [
{Find out, if two series are mutually independent.}
series1 [series!]
series2 [series!]
] [
not same? head :series1 head :series2
]
series19: [1 2 3] ; == [1 2 3]
series20: next series19 ; == [2 3]
series21: copy series19 ; == [1 2 3]
independent? series19 series20 ; == false
independent? series19 series21 ; == true
Observation: a series and its copy are mutually independent.
Cumulative properties of series operations edit
A cumulative property of change/only: change/only changes the reference of its argument Series. From this description is immediately obvious, that change/only affects all series sharing the reference in question.
We can create a new reference using the insert action.
series22: [1 2 3] ; == [1 2 3] length? series22 ; == 3 insert/only series22 0 ; == [1 2 3] series22 ; == [0 1 2 3] length? series22 ; == 4
We can use insert to define the meaning of the same? action for empty series. We say, that two empty series are the same, if insert used for the first series causes the second series to become non-empty too.
The description of the insert/only work: insert/only defines a new entry in the series, enlarging the number of entries in the series by one. The newly inserted entry becomes the first entry of the series, while the numbers of the other entries in the series are therefore higher by one. insert/only causes the newly created entry to refer to its value argument. Note, that insert/only doesn't change Index of any series! It skips the inserted entry to facilitate subsequent inserts.
The cumulative property of insert/only: for all series dependent on the series affected by insert/only holds: the dependent series is enlarged by one entry too, moreover, if the index of the dependent series is lower than the index of the affected series, its first entry remains the same, if the index of the dependent series is equal to the index of the affected series, the first entry of the series after insert will be the newly inserted reference and if the index of the dependent series is higher than the index of the affected series, then the first entry of the dependent series will be the entry preceding the original first entry.
For lowering the number of entries in a series we can use the remove and clear actions. Probably every reader is now able to use the above described methods for exploring the cumulative properties of these. I shall leave that as an exercise for the reader.
Series with fast index access versus series with fast remove/insert operations edit
Series with fast index access edit
Rebol blocks are examples of series with fast index access. That means, that operations like
pick series index
have the same speed regardless of:
- the length of the series
- the value of the index
Generally, all Rebol series except for Rebol lists are of this type.
Advantages edit
- the speed of index access (pick, poke, skip, at, length?, index?, offset?, etc.)
Disadvantages edit
- general remove/insert operations are "slow", the time needed to perform a remove/insert operation is proportional to the length of the series in general case
- after any insert/remove operation the index of all related series remains the same, which means, that after an insert or a remove operation a series actually refers to different entries than before such an operation:
s: [1 2 3 4 5 6] t: skip s 2 ; == [3 4 5 6] remove s t ; == [4 5 6]
- due to the above property, it is even possible to obtain past-tail series, i.e. series having an index that is actually not "available" in the given series
Series with fast insert/remove edit
As already mentioned, there is only one Rebol series type having this property. It is the list! datatype.
Advantages edit
- remove/insert operations are fast
- after an insert operation, all Rebol lists remain "unaffected" in that they point to the entry they pointed to before the insert operation was performed
- after a remove operation, all Rebol lists (except for the ones directly affected, having a removed entry as the first) remain "unaffected" in that they point to the entry they did point to before the remove operation was performed
- no list can be caused to become past-tail
Disadvantages edit
- due to the way how Rebol lists are implemented in R2 currently, a removal of the first element of a list causes the list to become a "list having an invalid (removed) position"; but see my list prototype below coping with this problem without a significant slow-down of any operation; the prototype adjusts such lists to point to the first subsequent valid entry instead of the removed one
- general index operations are "slow"; time needed to perform such operations is proportional to the length of the list in the general case
List prototype edit
Since lists are not present in R3, and due to the above mentioned problem with removed entries I decided to implement a list prototype that can improve the situation.
use [] [
list-proto: make object! [
; the position of a list is not an integer index,
; it is a list entry
position: none
; to have fast tail tail? head head?
; we need to know the position of the list tail
tail: none
]
list-entry-proto: make object! [
; every list entry refers to a value
; the tail entry always refers to NONE
value: none
; for every list entry we want to know,
; where the previous entry is
; for convenience we define,
; that the previous entry of a head entry
; is the tail entry
; to be able to detect the deleted entries
; we define, that the previous entry
; of a deleted entry is NONE
previous: none
; for every list entry we want to know,
; where the subsequent entry is
; for convenience we define,
; that the subsequent entry of the tail entry
; is the head entry
subsequent: none
]
set 'make-empty-list func [
{create an empty list}
] [
make list-proto [
position: tail: make list-entry-proto []
; head entry is the tail entry for empty lists
tail/subsequent: tail/previous: tail
]
]
set 'tail-s func [
{return the tail of a list}
list [object!]
] [
make list-proto [position: tail: list/tail]
]
set 'head-s func [
{return the head of a list}
list [object!]
] [
make list-proto [
tail: list/tail
position: tail/subsequent
]
]
set 'last-s func [
{returns the last value of a list}
list [object!]
] [
return get/any in list/tail/previous 'value
]
adjust-position: func [
{this function adjusts the list position to not refer to a removed entry}
list [object!] {the list to check/adjust}
/local current valid subsequent
] [
; note:
; even though this function uses two while cycles,
; it is implemented so,
; that its running time is insignificant
; explanation:
; for the adjust-position call to take O(n) time
; it is necessary to perform n removes,
; and after the adjustment,
; all subsequent calls to the adjust-position function
; become O(1) again
; this means, that the adjust-position call adds just
; O(1) time to every remove call,
; in addition to the O(1) time needed for every adjust-position call
; when the list position is valid
; we look for the first valid entry
current: list/position
while [
; test, if the current entry is a removed entry
none? current/previous
] [current: current/subsequent]
valid: current
; now we "clean" the removed entries
; to not have to traverse them any more
current: list/position
while [
; test, if the current entry is a removed entry
none? current/previous
] [
subsequent: current/subsequent
; doing the cleanup
current/subsequent: valid
current: subsequent
]
; adjust the list position to be valid
list/position: valid
]
set 'head?-s func [
{returns TRUE if at head}
list [object!]
] [
adjust-position list
list/position = list/tail/subsequent
]
set 'tail?-s func [
{returns TRUE if at tail}
list [object!]
] [
adjust-position list
list/position = list/tail
]
set 'index?-s func [
{returns the index of a list}
list [object!]
/local current index
] [
adjust-position list
current: list/position
index: 1
while [
; the current entry is not head
current/previous <> list/tail
] [
index: index + 1
current: current/previous
]
index
]
set 'length?-s func [
{returns the length of a list}
list [object!]
/local current length
] [
adjust-position list
current: list/position
length: 0
while [
; the current entry is not tail
current <> list/tail
] [
length: length + 1
current: current/subsequent
]
length
]
set 'skip-s func [
{returns the list forward or backward from the current position}
list [object!]
offset [integer!]
/local current
] [
adjust-position list
current: list/position
either negative? offset [
; traversing the list towards its head
while [
all [
; not at the head?
current/previous <> list/tail
offset < 0
]
] [
current: current/previous
offset: offset + 1
]
] [
; traversing the list towards its tail
while [
all [
; not at the tail?
current <> list/tail
offset > 0
]
] [
current: current/subsequent
offset: offset - 1
]
]
make list-proto [
position: current
tail: list/tail
]
]
set 'first-s func [
{returns the first value of a list}
list [object!]
] [
adjust-position list
return get/any in list/position 'value
]
set 'remove-s func [
{removes an element from a list}
list [object!]
/local current
] [
adjust-position list
current: list/position
either current = list/tail [
; no removal needed, just return the argument
list
] [
; adjust links
current/previous/subsequent: current/subsequent
current/subsequent/previous: current/previous
; mark the current element as removed
current/previous: none
; return the next position
make list-proto [
position: current/subsequent
tail: list/tail
]
]
]
set 'insert-only func [
{insert one value into a list}
list [object!]
value [any-type!]
] [
adjust-position list
make list-proto [
; create a new list entry
position: make list-entry-proto [
previous: list/position/previous
subsequent: list/position
]
error? set/any in position 'value get/any 'value
; adjust links
position/previous/subsequent: position
position/subsequent/previous: position
tail: list/tail
]
]
set 'change-only func [
{change a value in a list}
list [object!]
value [any-type!]
/local new-entry
] [
adjust-position list
if list/position = list/tail [
; we are at tail, change is not possible
do make error! "out of range"
; (alternatively, we may insert a new entry, if preferred)
]
error? set/any in list/position 'value get/any 'value
; return the list at the next position
make list-proto [
position: list/position/subsequent
tail: list/tail
]
]
]