7 레코드, 풀, 찾아보기

먼저 알아야 할 것: 6장(모음), 5장(저장된 글).

이 장이 답하는 물음

필드가 여럿인 자료는 어떻게 담는가?
포인터 없이 나무나 목록 같은 연결된 자료는 어떻게 만드는가?
이름으로 줄을 찾으려면?
필드의 차례로 줄을 읽으려면?

7.1 레코드와 줄

record … end 는 필드의 나열이다. 필드마다 타입을 적는다(u8 u16 i32 int bool str(N) …): u8 필드는 읽으면 u8 이고 u8 만 받는다(2016 u16 b to book.year). 레코드는 값으로 돌아다니지 않는다. 레코드를 원소로 하는 목록(또는 배열, 풀)을 선언하고, 그 한 칸인 줄을 다룬다. 줄의 타입은 표의 이름이다.

07-records.pnx

use io
record book
  title str(32)
  year u16
  pages u16
end
list shelf book 8
row shelf ("The C Programming Language", 1978, 228)
row shelf ("Thinking Forth", 1984, 300)
row shelf lua ("Programming in Lua", 2003)          rem a named row; pages left out: 0
word show (b shelf) cat (b book.year, " ", b book.title, ", ", b book.pages, " pages") io.println end
shelf do (b shelf) b show end each
2016 u16 lua to book.year                               rem value, row, to record.field
388 u16 lua to book.pages
lua show

출력

$ pnx 07-records.pnx
1978 The C Programming Language, 228 pages
1984 Thinking Forth, 300 pages
2003 Programming in Lua, 0 pages
2016 Programming in Lua, 388 pages

필드는 레코드.필드 로 적는다: b book.year 는 읽기, 2016 lua to book.year 는 넣기다. row 는 정의 밖에서 목록에 줄을 더하고, 이름을 붙일 수도 있다. 돌면서 줄을 더하는 것은 add_row 다.

07-add-row.pnx

use io
record point
  x i32
  y i32
end
list path point 4
word add_point (x int, y int or fail)
  path add_row or_fail to p                         rem a new, zeroed row at the end
  x i32 p to point.x
  y i32 p to point.y
end
word walk (or fail) 0 0 add_point or_fail  3 4 add_point or_fail  6 0 add_point or_fail end
walk or_else (e) e err_text io.println end
path do (p path) cat ("(", p point.x, ", ", p point.y, ")") io.print end each
"" io.println

출력

$ pnx 07-add-row.pnx
(0, 0)(3, 4)(6, 0)

줄을 다루는 낱말을 주석과 함께 한 번에 보자. add_row 가 준 r 은 표 안의 번호이고, 필드에 넣는 꼴은 값 줄 to 레코드.필드 다. 읽는 꼴은 줄 레코드.필드 이고, 줄 하나를 내려 필드의 값을 올린다.

07-row-steps.pnx

use io
record item
  name str(12)                         rem stored text: 12 bytes inside the row
  price int
end
list cart item 4                       rem a table: room for 4 rows of item
word add_item (n str, p int or fail)
  cart add_row or_fail to r            rem a new row at the end; r is its number in the table
  n r to item.name                     rem value, row, to record.field: store a field
  p r to item.price
end
word total (gives int)
  0 to acc
  cart do (r cart) acc r item.price add to acc end each   rem each row of the table in turn
  acc
end
word main ()
  "pencil" 120 add_item or_else (e) end
  "eraser" 80 add_item or_else (e) end
  1 cart idx to second                 rem the row with number 1
  cat (second item.name, " costs ", second item.price) io.println
  cat ("total ", total) io.println
end
main

출력

$ pnx 07-row-steps.pnx
eraser costs 80
total 200

토큰	그 뒤의 스택	일어난 일
`cart add_row`	`1`	새 줄을 끝에 더하고 그 번호를 올린다(실패할 수 있어 뒤에 `or_fail`).
`to r`	`—`	번호를 `r` 에 담는다.
`n r`	`"eraser" 1`	넣을 값과 줄.
`to item.name`	`—`	줄 1 의 `name` 필드에 넣는다. 둘 다 내려간다.
`r item.price`	`80`	줄 하나를 내리고 그 줄의 `price` 를 올린다.

문답

물음. 줄은 레코드의 주소인가?

답. 아니다. 줄은 표 안의 번호다. 쓸 때마다 범위를 검사한다. 그래서 줄을 잘못 들고 있어도 메모리를 망가뜨리지 못하고, 기껏해야 결함으로 멈춘다.

7.2 줄로 잇기

레코드의 필드가 표의 이름을 타입으로 가지면 그 표의 줄을 담는다. 처음 값은 “없음” 이고 is_none 으로 묻는다. 이렇게 포인터 없이 나무를 만든다. 레코드가 자기를 담을 표를 가리키므로, 표를 forward 로 먼저 알린다. 배열과 목록의 칸도 같은 꼴로 줄을 담는다: list order cities 8(7.5절).

07-tree.pnx

use io
use str
rem A binary search tree in a pool: rows point to rows by number, never by address.
forward pool nodes
record node
  key int
  left nodes
  right nodes
end
pool nodes node 16
global root nodes
word put_key (k int or fail)
  nodes alloc or_fail to n
  k n to node.key
  root is_none if n set root return end
  root to at
  loop
    k at node.key lt if
      at node.left is_none if n at to node.left return end
      at node.left to at
    else
      at node.right is_none if n at to node.right return end
      at node.right to at
    end
  end
end
word show (t nodes)                                  rem in order: left, self, right
  t is_none if return end
  t node.left show
  t node.key str.to_str io.print " " io.print
  t node.right show
end
word build (or fail) 50 put_key or_fail 30 put_key or_fail 70 put_key or_fail 20 put_key or_fail 40 put_key or_fail end
build or_else (e) e err_text io.println end
root show
"" io.println

출력

$ pnx 07-tree.pnx
20 30 40 50 70

“없음” 줄의 필드를 읽거나 넣으면 결함이다. 줄을 따라갈 때는 is_none 으로 먼저 묻는다(위 show 의 첫 줄처럼).

07-none-field.pnx

use io
forward list nodes
record node
  value int
  next nodes                           rem a row of nodes, or none
end
list nodes node 4
row nodes last (3)                     rem its next is none: nothing was given
last node.next node.value drop         rem reading a field of none ends the run

결함으로 멈춤

$ pnx 07-none-field.pnx
07-none-field.pnx:9: index out of range

7.3 풀: 얻고 돌려주기

pool 은 줄을 얻고(alloc) 돌려주는(free) 표다. alloc 이 준 줄은 한 번만 쓰는 값이다. 모든 경로에서 정확히 한 번, 필드나 전역에 넣거나 free 에 줘야 한다. 처리기가 적재 때 그것을 검사한다.

07-pool-leak.pnx

record node
  key int
end
pool nodes node 4
word new_node (k int or fail)
  nodes alloc or_fail to n
  k n to node.key
end

거절

$ pnx 07-pool-leak.pnx
07-pool-leak.pnx:8:1: an owned value in a local is not given on every path (close, free or store it)

풀의 줄은 번호와 함께 세대를 담는다. 돌려준 줄을 다시 쓰면 — 그 사이 그 칸을 누가 다시 얻었더라도 — 결함으로 멈춘다.

07-stale.pnx

use io
record node
  key int
end
pool nodes node 4
global keep nodes
word demo (or fail)
  nodes alloc or_fail to n
  n set keep
  keep nodes free
  "the row is given back" io.println
  keep node.key drop
end
demo or_else (e) end

결함으로 멈춤

$ pnx 07-stale.pnx
the row is given back
07-stale.pnx:12: a row or handle was used after it was given back
  n nodes = 4294967297

7.4 찾아보기

index 이름 표 레코드.필드 는 한 필드로 줄을 찾는 해시 표다. lookup 이 키로 줄을 찾는다(없으면 not_found 로 실패). row 로 적은 줄은 처음부터 들어 있다.

07-index.pnx

use io
record user
  name str(16)
  age u8
end
list users user 8
index by_name users user.name
row users ("kim", 30)
row users ("lee", 25)
word register (name str, age int or fail)
  users add_row or_fail to u
  name u to user.name
  age u8 u to user.age
  u by_name insert or_fail                          rem without this, lookup does not see it
end
word age_of (name str gives int or fail) name by_name lookup or_fail user.age raw end
"park" 41 register or_else (e) e err_text io.println end
"kim" 31 register or_else (e) cat ("kim again: ", e err_text) io.println end
word show (name str) cat (name, ": ", name age_of or_else (e) -1 end) io.println end
"lee" show
"park" show
"choi" show

출력

$ pnx 07-index.pnx
kim again: failed
lee: 25
park: 41
choi: -1

흔한 오해: add_row 한 줄은 찾아보기에도 들어간다

들어가지 않는다. 돌면서 더한 줄은 insert 해야 lookup 이 찾는다. 위 예의 register 가 그렇게 한다. 같은 키가 이미 있으면 insert 는 실패하고, add_row 로 더한 줄은 목록에 남는다 — 키를 먼저 lookup 해 보고 더하는 것이 깔끔하다.

찾아보기는 풀 위에도 만들 수 있다. 그러면 저장소가 줄을 키로 찾으면서 줄을 돌려줄 수도 있다. free 는 그 풀 위의 모든 찾아보기에서 줄을 빼므로, 돌려준 키는 더 찾아지지 않고, 그 칸은 다음 alloc 이 다시 얻는다. 키 찾아보기 has 는 실패 없이 키가 있는지 묻는다. 풀은 each 로 걷고, 살아 있는 줄을 칸의 차례로 들른다. 다른 차례로 읽으려면 줄의 목록에 넣고 그 목록을 정렬한다.

07-pool-index.pnx

use io
record item
  name str(12)
  count int
end
pool items item 3
index by_name items item.name
list order items 3
word count_in (name str or fail)
  name by_name has not if
    items alloc or_fail to r              rem a free row: three at most
    name r to item.name
    r by_name insert or_fail              rem the index keeps it now
  end
  name by_name lookup or_fail to r
  r item.count 1 add r to item.count
end
word drop_out (name str)
  name by_name lookup or_else (e) return end items free
end
word show ()
  order clear
  items do (r items) r order push or_else (e) end end each
  order items sort_by item.name
  order do (r items) cat (r item.name, " ", r item.count) io.println end each
end
"pear" count_in or_else (e) end
"fig" count_in or_else (e) end
"pear" count_in or_else (e) end
"plum" count_in or_else (e) end
"kiwi" count_in or_else (e) cat ("kiwi: ", e err_text) io.println end
"fig" drop_out
"kiwi" count_in or_else (e) end           rem the row fig gave back
show

출력

$ pnx 07-pool-index.pnx
kiwi: full
kiwi 1
pear 2
plum 1

흔한 오해: insert 뒤에도 지역 변수가 새 줄을 담고 있다

담고 있지 않다. alloc 이 방금 준 줄은 한 번만 쓰는 값이고, insert 는 필드에 넣을 때처럼 그 줄을 넘겨받는다. 키가 이미 있으면 insert 는 줄을 풀에 돌려주고 실패하므로 잃는 것이 없다. insert 전에 줄을 채우고, 그 뒤에는 위의 count_in 처럼 키로 다시 찾는다.

07-pool-insert-gone.pnx

record item
  name str(12)
  count int
end
pool items item 3
index by_name items item.name
word enter (name str or fail)
  items alloc or_fail to r
  name r to item.name
  r by_name insert or_fail
  1 r to item.count
end

거절

$ pnx 07-pool-insert-gone.pnx
07-pool-insert-gone.pnx:11:5: this local gave its owned value away; it holds nothing to read

문답

물음. 한 표의 줄을 다른 표에 넣을 수 있는가?

답. 아니다. 줄의 타입은 표의 이름이다. cart 의 줄은 cart 에만 쓰이고, 다른 표의 필드나 목록에 주면 타입이 달라 거절된다. 같은 레코드를 담은 표 둘 사이에 줄을 옮기려면 필드를 하나씩 읽어 새 줄에 넣거나, filter_into 로 복사한다(6장).

7.5 차례대로 놓인 줄

sort 는 배열이나 목록의 칸을 가장 작은 것부터 차례로 놓는다. sort_desc 는 가장 큰 것부터 놓는다. 줄은 그렇게 정렬하지 않는다. 찾아보기, 필드, 전역이 줄을 번호로 붙들고 있을 수 있어서, 줄을 옮기면 그것들이 틀린다. 대신 줄의 목록을 줄의 필드로 정렬한다. order cities sort_by city.name 이고, order 는 list order cities 8 로, 칸이 cities 의 줄인 목록으로 선언한다. 줄은 제자리에 있고, order 가 어떤 차례로 읽을지를 말한다. 줄 번호(int)의 목록도 같은 꼴로 정렬한다.

07-sort.pnx

use io
record city
  name str(16)
  people int
end
list cities city 8
list order cities 8                           rem rows of cities
list sizes int 8
word city_of (n str, p int or fail)
  cities add_row or_fail to r
  n r to city.name
  p r to city.people
  p sizes push or_fail
end
word main (or fail)
  "Lyon" 522 city_of or_fail  "Nice" 342 city_of or_fail  "Paris" 2103 city_of or_fail  "Lille" 236 city_of or_fail
  sizes sort_desc
  cat ("largest: ", 0 sizes idx) io.println
  cities do (c cities gives cities) c end order map_into or_fail
  order cities sort_by city.name
  order do (c cities) c city.name io.println end each
end
main or_else (e) e err_text io.println end

출력

$ pnx 07-sort.pnx
largest: 2103
Lille
Lyon
Nice
Paris

07-sort-rows.pnx

record city
  name str(16)
  people int
end
list cities city 8
index by_name cities city.name
word order_them () cities sort end

거절

$ pnx 07-sort-rows.pnx
07-sort-rows.pnx:7:27: rows do not move: sort a list of their numbers by a field: order table sort_by record.field

문답

물음. 두 필드로 정렬하려면?

답. 두 번 정렬한다. 덜 중요한 필드를 먼저 한다. order t sort_by r.name 한 뒤 order t sort_by_desc r.count 하면 개수가 큰 것부터 놓이고, 개수가 같으면 이름 차례다. 정렬은 키가 같은 것의 차례를 지키므로, 두 번째 정렬은 같다고 보는 줄 사이에 첫 번째 정렬의 차례를 남긴다.

흔한 오해: sort_desc 는 sort 를 거꾸로 읽은 것이다

칸에서만 그렇다. 같은 두 칸은 서로 구별되지 않기 때문이다. 줄에서는 그렇지 않다. sort_by_desc 도 sort_by 처럼 키가 같은 것의 차례를 지킨다. sort_by 를 거꾸로 읽으면 그 차례가 뒤집힌다.

정리

칸은 sort 와 sort_desc 로 정렬한다. 줄은 줄의 목록(또는 줄 번호의 목록)을 거쳐 sort_by 와 sort_by_desc 로 정렬하고, 키가 같은 것의 차례를 지킨다(표준 15.3).
레코드는 표의 줄로 다룬다. 필드는 레코드.필드 로 읽고 넣는다(표준 8.8).
줄은 번호이고, 쓸 때마다 검사된다. 없음 줄의 필드는 결함이다(8.8).
풀의 줄은 한 번 넘겨야 하고, 돌려준 줄은 결함이다(8.9, 12.4).
찾아보기는 row 의 줄을 담고, 돌면서 더한 줄은 insert 한다(8.10).
찾아보기는 풀 위에도 둔다. insert 는 방금 얻은 줄을 넘겨받고, free 는 줄을 찾아보기에서 빼고, has 는 키를 묻고, each 는 살아 있는 줄을 걷는다(8.9, 8.10).