6 Collections

Builds on: Chapter 4 (stems and blocks), chapter 5 (buffers).

Questions this chapter answers

What places hold several values, and how is their size decided?
What happens when you add to a full list or take from an empty queue?
How do I filter or transform an array into another place?

Every collection has its capacity fixed by its declaration, and its room is placed in the state’s block ahead of time. No storage grows while running. So “how much can it hold” is always written in the source.

6.1 Arrays

array NAME type capacity is a row of cells that is always full. Every cell starts at zero, and len is always the capacity. A cell is read with i ARRAY idx and stored with value i set ARRAY (the same set that stores into a global). assign fills it from the first cell, outside definitions.

06-array.pnx

use io
use str
const days 7
array rain int days                         rem always full: 7 cells, all 0 at first
assign rain (0, 5, 12, 0, 3)                rem cells 5 and 6 stay 0
8 6 set rain                                 rem value, index, set, array: cell 6 becomes 8
word show () rain do (r int) r str.to_str io.print " " io.print end each "" io.println end
show
cat ("rainy days: ", rain do (r int gives bool) r 0 gt end count, " of ", rain len) io.println

Output

$ pnx 06-array.pnx
0 5 12 0 3 0 8 
rainy days: 4 of 7

An index out of range is a fault. Compare an index you cannot be sure of with len before using it.

06-index-range.pnx

use io
array week int 7
word day (i int gives int) i week idx end
3 day drop
"day 3 is fine" io.println
7 day drop

Fault

$ pnx 06-index-range.pnx
day 3 is fine
06-index-range.pnx:3: index out of range
  i int = 7

6.2 Lists

A list is an array whose length grows from 0 up to its capacity. push adds at the end and pop takes from the end. Only indexes below the length may be used.

06-list.pnx

use io
use str
list stack u8 4                             rem grows from 0 to 4
word balanced (s str gives bool)            rem are the brackets of s balanced?
  stack clear
  s str.bytes do (b u8)
    b '(' eq if b stack push or_else (e) end end
    b ')' eq if stack pop or_else (e) 0 u8 end drop end
  end each
  stack is_empty
end
word check (s str) cat (s, " ", s balanced) io.println end
"(a(b)c)" check
"(a(b c)" check

Output

$ pnx 06-list.pnx
(a(b)c) true
(a(b c) false

Here are the words for lists in one place, with remarks saying what each line does.

06-list-steps.pnx

use io
use str
list scores int 3                          rem room for 3; it starts empty
word show () cat ("length ", scores len, " of ", scores capacity) io.println end
show                                       rem length 0 of 3
70 scores push or_else (e) end             rem push can fail (full), so its guard follows it
85 scores push or_else (e) end
show                                       rem length 2 of 3
cat ("first ", 0 scores idx, ", second ", 1 scores idx) io.println   rem i list idx reads cell i
90 1 set scores                            rem v i set list puts v into cell i
cat ("second is now ", 1 scores idx) io.println
scores pop or_else (e) -1 end str.to_str io.println    rem the last one comes off: 90
show                                       rem length 1 of 3

Output

$ pnx 06-list-steps.pnx
length 0 of 3
length 2 of 3
first 70, second 85
second is now 90
90
length 1 of 3

One push and one pop, followed on the stack. Both can fail, so a guard follows each.

Token	Stack after it	What happened
`70`	`70`	The value to put in.
`scores push`	`—`	Puts it at the end. Had the list been full, it would fail and leave nothing.
`or_else (e) end`	`—`	Skipped, since it succeeded. On failure the body runs; it is empty, so nothing is left.
`scores pop`	`90`	Takes the last value off.
`or_else (e) -1 end`	`90`	Success: skipped. On failure `-1` would fill the place.
`str.to_str io.println`	`—`	Prints it.

Written	Stack	What it does
`LIST len`	`— → int`	the length now
`LIST capacity`	`— → int`	the declared capacity
`i LIST idx`	`int → value`	reads cell `i`; outside the length the fault `range`
`v i set LIST`	`value int → —`	stores into cell `i`; outside the length the fault `range`
`v LIST push`	`value → —`	adds at the end; fails with `full` when full
`LIST pop`	`— → value`	takes from the end; fails with `range` when empty

push and pop can fail: a push into a full list fails with full, a pop from an empty list with range. A push that fails does not change the list.

06-list-full.pnx

use io
list two int 2
word fill (or fail) 1 two push or_fail 2 two push or_fail 3 two push or_fail end
fill or_else (e) cat ("the third push failed: ", e err_text) io.println end
cat ("the list holds ", two len) io.println

Output

$ pnx 06-list-full.pnx
the third push failed: full
the list holds 2

Because they can fail, push and pop are always followed by a guard (chapter 8); leaving it out is refused at load. To ignore the failure, write or_else (e) end, so that the source says it is ignored.

06-push-unguarded.pnx

list scores int 3
word add_score (n int) n scores push end   rem push can fail: what then? the guard is missing

Refused

$ pnx 06-push-unguarded.pnx
06-push-unguarded.pnx:2:38: a word that can fail is followed by or_fail, or_return or or_else

Q&A

Q. Isn’t a generous capacity a waste of memory?

A. It is. But the amount is in the source and fixed at load. Instead of a program stopping when memory runs out, it shows as a failing push, and that failure has to be handled before the program is even loaded.

6.3 Queues

In a queue, what goes in first comes out first. put puts in, take takes out, and peek looks without taking. wait_take and wait_put, which wait between tasks for an empty or full queue, are in chapter 13.

06-queue.pnx

use io
use str
queue line int 3
word arrive (n int) n line put or_else (e) cat ("turned away: ", n) io.println end end
word serve () line take or_else (e) cat ("nobody waits: ", e err_text) io.println return end to n  cat ("served ", n) io.println end
1 arrive 2 arrive 3 arrive 4 arrive
serve serve
5 arrive
serve serve serve

Output

$ pnx 06-queue.pnx
turned away: 4
served 1
served 2
served 3
served 5
nobody waits: range

Common mistake: A queue can be walked with each too

Only arrays and lists are stems, and a pool for each alone (chapter 7). Queues, buffers and indexes are not. To handle the elements of a queue in order, call take in a loop.

06-queue-stem.pnx

use io
queue q int 4
q do (x int) end each

Refused

$ pnx 06-queue-stem.pnx
06-queue-stem.pnx:3:14: only an array, a list or a pool is a stem (not a queue, a buffer or an index)

6.4 Filtering and mapping into a place

map_into and filter_into put the results of transforming or filtering the elements of a stem with a block into a place that already exists no new array is made. A list destination is added to at the end; an array is written from cell 0, and the number of cells written is given. When the destination is full, they fail.

06-map-filter.pnx

use io
use str
array prices int 6
assign prices (1200, 450, 3000, 780, 99, 2500)
list cheap int 6
array with_tax int 6
word go (or fail)
  prices do (p int gives bool) p 1000 lt end cheap filter_into or_fail
  prices do (p int gives int) p 11 mul 10 div end with_tax map_into or_fail to n
  cat ("cheap: ", cheap len, " items, the first ", 0 cheap idx) io.println
  cat ("with tax, ", n, " cells written, the first ", 0 with_tax idx) io.println
end
go or_else (e) e err_text io.println end

Output

$ pnx 06-map-filter.pnx
cheap: 3 items, the first 450
with tax, 6 cells written, the first 1320

6.5 Passing a collection to a word

A word can take a collection as a parameter. Write its kind and what its cells hold — list int, array city, queue int, list str(8) — or buffer, and give the collection’s name where you call the word. Inside, the parameter works wherever a collection’s name does (even as the destination of map_into). The same word now serves every list of that kind, whatever its capacity.

06-coll-param.pnx

use io
list morning int 8
list evening int 8
word record_all (l list int, a int, b int, c int)
  a l push or_else (e) end  b l push or_else (e) end  c l push or_else (e) end
end
word report (name str, l list int)
  cat (name, ": ", l len, " readings, highest ", l maximum or_else (e) 0 end) io.println
end
morning 12 15 11 record_all
evening 21 19 20 record_all
"morning" morning report
"evening" evening report

Output

$ pnx 06-coll-param.pnx
morning: 3 readings, highest 15
evening: 3 readings, highest 21

Common mistake: A table’s name as a parameter type takes the table

Written as a parameter type, the name of a table of records means one row of it (chapter 7). To take the whole table, write list RECORD or array RECORD.

06-coll-param-row.pnx

record reading
  value i32
end
list morning reading 8
word count_them (l morning gives int) 0 end      rem a table's name as a type: one row of it
morning count_them

Refused

$ pnx 06-coll-param-row.pnx
06-coll-param-row.pnx:6:9: this parameter takes one row of a table; a parameter that takes the whole table is written list RECORD or array RECORD

Q&A

Q. How do I empty a list, or make it shorter?

A. LIST clear sets its length to 0 and n LIST truncate to n. The cells keep their values, but past the length they are not seen. An array is always full, so it cannot be emptied; its cells are written one by one with set.

Summary

A word takes a collection as list T, array T, queue T or buffer (9.9).
The capacity of a collection is fixed by its declaration; no storage grows while running (standard 8.1).
An array is always full; a list’s length grows; an index out of range is a fault (8.4, 8.5).
push pop put take can fail: full when full, range when empty (8.5, 8.6).
Only arrays and lists are stems (10.6).
map_into and filter_into write into the destination they are given (10.6).