24 pipe — 하려는 일만 한 줄씩

24.1 같은 일, 두 가지 모양#

module digits .
rem run: digits_loop [97,49,50,98,51]
rem run: digits_pipe [97,49,50,98,51]

fn is_digit input c u8 . output bool .
do
  return and (ge c 48) (le c 57) .
end

fn digits_loop input s slice u8 . output u64 .
do
  var n u64 be 0 .
  var i u64 be 0 .
  while lt i (len s) . do
    if is_digit (index s i) . do
      set n (add n 1) .
    end
    set i (add i 1) .
  end
  return n .
end

fn digits_pipe input s slice u8 . output u64 .
do
  return pipe s do
    filter is_digit .
    count .
  end .
end

$ lowentc --run digits_loop digits.low [97,49,50,98,51]
digits_loop([97,49,50,98,51]) = 3
  arg0 (written) = [97,49,50,98,51]
$ lowentc --run digits_pipe digits.low [97,49,50,98,51]
digits_pipe([97,49,50,98,51]) = 3
  arg0 (written) = [97,49,50,98,51]

두 op 은 같은 답을 낸다. digits_loop 는 카운터 n, 색인 i, 끝 조건, 증가를 사람이 맞춘다. digits_pipe 는 두 줄이다.

• filter is_digit . — is_digit 이 참인 원소만 남긴다.
• count . — 남은 원소를 센다. 흐름을 끝내는 낱말(종결자)은 정확히 하나다.

pipe 는 문장이지만 값을 내는 종결자(count·fold·any·all)로 끝나면 식처럼 return pipe s do … end . 로 쓸 수 있다 — 끝의 점은 return 문장의 것이다(end 는 pipe 블록만 닫는다).

원소가 줄지어 흘러가는 관으로 그리면 이렇다.

 s = "a1b22"
               ┌─────────────────┐            ┌───────┐
  a 1 b 2 2 ─▶ │ filter is_digit │ ─▶ 1 2 2 ─▶ │ count │ ─▶ 3
               └─────────────────┘            └───────┘
                 스테이지: 거른다                종결자: 흐름을 끝내고 값을 낸다

원소는 하나씩 관을 지나간다. 중간에 «숫자만 모은 배열» 같은 것이 따로 만들어지지 않는다.

24.2 스테이지와 종결자#

filter·any·all 에 주는 op 은 판정이라 bool 을 내야 한다. 수를 내는 op 을 주면 E-PIPE-PRED 로 거절된다 — 0 아닌 수를 참으로 읽는 규칙은 이 언어에 없다(13장의 cast 와 같은 까닭).

pipe 를 return pipe … end . 처럼 값 자리에 쓰면 그 값은 종결자가 낸 값이다. 스테이지는 줄마다 하나씩 원소를 다음 줄로 넘기고, 종결자가 마지막에 받아 값 하나로 만든다.

 xs = [1, 5, 2, 7]
      │
      ▼  filter big      (big = gt x 2)       5, 7          1·2 는 여기서 버린다
      ▼  map dbl         (dbl = x + x)        10, 14
      ▼  collect into out                     out = [10, 14, …]   답 = 2 (담은 개수)

module stages .
rem run: big_doubled [1,2,3,4,5] [0,0,0,0,0]
rem run: sum_big [1,2,3,4,5]
rem run: has_zero [4,0,9]
rem run: all_small [1,2,3]
rem run: middle [10,20,30,40] [0,0]

fn over2 input a u8 . output bool .
do
  return gt a 2 .
end

fn dbl input a u8 . output u8 .
do
  return wrap_add a a .
end

fn addu input acc u64 . input x u8 . output u64 .
do
  return wrap_add acc (widen u64 x) .
end

fn is_zero input a u8 . output bool .
do
  return eq a 0 .
end

fn under10 input a u8 . output bool .
do
  return lt a 10 .
end

proc big_doubled input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    filter over2 .
    map dbl .
    collect into out .
  end
  return len out .
end

fn sum_big input xs slice u8 . output u64 .
do
  return pipe xs do
    filter over2 .
    fold 0 addu .
  end .
end

fn has_zero input xs slice u8 . output bool .
do
  return pipe xs do
    any is_zero .
  end .
end

fn all_small input xs slice u8 . output bool .
do
  return pipe xs do
    all under10 .
  end .
end

proc middle input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    skip 1 .
    take 2 .
    collect into out .
  end
  return len out .
end

$ lowentc --run big_doubled stages.low [1,2,3,4,5] [0,0,0,0,0]
big_doubled([1,2,3,4,5], [6,8,10,0,0]) = 5
  arg0 (written) = [1,2,3,4,5]
  arg1 (written) = [6,8,10,0,0]
$ lowentc --run sum_big stages.low [1,2,3,4,5]
sum_big([1,2,3,4,5]) = 12
  arg0 (written) = [1,2,3,4,5]
$ lowentc --run has_zero stages.low [4,0,9]
has_zero([4,0,9]) = 1
  arg0 (written) = [4,0,9]
$ lowentc --run all_small stages.low [1,2,3]
all_small([1,2,3]) = 1
  arg0 (written) = [1,2,3]
$ lowentc --run middle stages.low [10,20,30,40] [0,0]
middle([10,20,30,40], [20,30]) = 2
  arg0 (written) = [10,20,30,40]
  arg1 (written) = [20,30]

• big_doubled 는 2 보다 큰 것만 남겨(filter) 두 배로 만들고(map) out 에 담는다(collect into). 결과 [6,8,10,0,0] 에서 담기지 않은 자리는 그대로다. 담을 버퍼는 부르는 쪽이 준다. pipe 는 할당하지 않는다.
• sum_big 의 fold 0 addu 는 0 에서 시작해 addu 로 누적한다.
• has_zero 는 any is_zero, all_small 은 all under10 이다.
• middle 은 skip 1 과 take 2 로 가운데 두 원소를 담는다.

스테이지에 주는 것은 이름 붙은 op 이다. 이 언어에는 이름 없는 함수(람다)가 없다. 스테이지 op 은 원소 하나를 받고 권한을 받지 않는다. fold·scan 의 op 은 누산값과 원소 둘을 받는다.

튜플이 없는데 순번이나 짝은 어떻게 다루는가? 쌍을 만들지 않고 op 에 인자로 건넨다.

module pairs .
rem run: with_index [10,10,10] [0,0,0]
rem run: added [1,2,3] [10,20,30] [0,0,0]
rem run: running [1,2,3,4] [0,0,0,0]

fn idxadd input i u64 . input e u8 . output u8 .
do
  return wrap_add e (narrow_wrap u8 i) .
end

fn addb input a u8 . input b u8 . output u8 .
do
  return wrap_add a b .
end

proc with_index input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    enumerate idxadd .
    collect into out .
  end
  return 0 .
end

proc added input xs slice u8 . input ys slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    zip ys addb .
    collect into out .
  end
  return 0 .
end

proc running input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    scan 0 addb .
    collect into out .
  end
  return 0 .
end

$ lowentc --run with_index pairs.low [10,10,10] [0,0,0]
with_index([10,10,10], [10,11,12]) = 0
  arg0 (written) = [10,10,10]
  arg1 (written) = [10,11,12]
$ lowentc --run added pairs.low [1,2,3] [10,20,30] [0,0,0]
added([1,2,3], [10,20,30], [11,22,33]) = 0
  arg0 (written) = [1,2,3]
  arg1 (written) = [10,20,30]
  arg2 (written) = [11,22,33]
$ lowentc --run running pairs.low [1,2,3,4] [0,0,0,0]
running([1,2,3,4], [1,3,6,10]) = 0
  arg0 (written) = [1,2,3,4]
  arg1 (written) = [1,3,6,10]

enumerate idxadd 는 idxadd 에 순번과 원소를 준다. zip ys addb 는 xs 의 원소와 ys 의 같은 자리 원소를 addb 에 준다. 짧은 쪽이 끝나면 흐름 전체가 끝나서 짝이 늘 맞는다. scan 0 addb 는 누적합을 원소로 흘린다. 쌍을 만들었다 곧장 풀지 않으므로 숨은 할당도 없다.

24.3 한 번에 훑는 것은 정의다#

한 pipe 는 한 번의 훑기로 실행되고 스테이지 사이에 중간 배열이 만들어지지 않는다. 이것은 처리기가 해 볼 수 있는 최적화가 아니라 pipe 의 정의이고, 중간 배열을 만드는 처리기는 적합하지 않다.

왜 정의로 두는가. 융합을 최적화로 두면 “어디까지 융합되는가” 가 처리기마다 다르고, 쓰는 사람은 절벽을 만난다. 한 줄을 고쳤더니 갑자기 중간 배열이 생기고 느려지는 자리다. 그 절벽은 소스만 봐서는 안 보인다. Lowent 는 융합할 수 없는 연산을 스테이지 낱말에 아예 넣지 않았다. 정렬처럼 전체를 봐야 하는 연산이 스테이지에 없는 이유다.

module bad_stage .
rem expect: E-PIPE-STAGE

fn is_digit input c u8 . output bool .
do
  return and (ge c 48) (le c 57) .
end

fn broken input s slice u8 . output u64 .
do
  return pipe s do
    sort .
    count .
  end .
end

$ lowentc --check bad_stage.low
bad_stage.low:12:0 E-PIPE-STAGE: this word is not a `pipe` stage. The stage vocabulary is CLOSED (RFC-0010 G5/D-A): stages are `filter <op> .`, `map <op> .`, `take <n> .`, `skip <n> .`, `enumerate <op> .`, `zip <other> <op> .` and `scan <init> <op> .`, and the pipeline ends with exactly one terminal — `collect into <mut slice> .`, `fold <init> <op> .`, `count .`, `any <op> .` or `all <op> .`. Fusion here is the MEANING, not an optimization, so anything that could not fuse into the single loop is not writable as a stage — use an explicit loop, or break the pipeline with an explicit intermediate collect

스테이지 목록은 닫혀 있다. pipe 가 식이 아니라 문장인 것도 같은 이유다. 식이었다면 스테이지를 값으로 떼어 넘길 수 있고, 그러면 어디까지가 한 줄기인지 소스에서 안 보인다. do … end 가 그 경계를 눈에 보이게 한다.

24.4 필요한 만큼만 읽는다#

any 는 참을 내는 첫 원소에서, all 은 거짓을 내는 첫 원소에서, take n 은 n 개를 지나보낸 뒤 훑기를 멈춘다. 멈춘 뒤의 원소는 읽히지 않고 그 원소에 대한 스테이지도 실행되지 않는다. has_zero [4,0,9] 는 9 를 보지 않는다. 이 성질이 의미에 적혀 있어야 끝이 없는 원천도 pipe 로 다룰 수 있다.

종결자는 흐름을 끝낸다. 종결자 뒤에 스테이지가 오면 거절된다.

module no_terminal .
rem expect: E-PIPE-NO-TERMINAL

fn is_digit input c u8 . output bool .
do
  return and (ge c 48) (le c 57) .
end

fn broken input s slice u8 . output u64 .
do
  return pipe s do
    count .
    filter is_digit .
  end .
end

$ lowentc --check no_terminal.low
no_terminal.low:13:0 E-PIPE-NO-TERMINAL: a `pipe` stage may not come AFTER the terminal — the terminal ends the pipeline (RFC-0010 G1)

24.5 이름이 같은 내장 map·filter#

pipe 밖에도 map·filter 가 있다. 이쪽은 스테이지가 아니라 문 하나로 슬라이스를 옮겨 담는 내장 연산이고, 인자가 셋이다 — map <받는 자리> <op> <원천> . · filter <받는 자리> <op> <원천> ..

module sink_map .

fn dbl input a u8 . output u8 . do return wrap_add a a . end

proc doubled input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  map out dbl xs .
  return 0 .
end

[1,2] 를 세 칸짜리 out 에 담으면 [2,4,0] 이다. 거꾸로 [1,2,3] 을 두 칸에 담으려 하면 셋째를 쓰는 순간 멈춘다 — 받는 자리가 차도 말없이 멈추는 일은 없다(collect into 와 같다). 받는 자리는 mut slice 여야 하고(E-MAP-SINK), 원소는 스칼라여야 한다(E-MAP-ELEM). 낱말은 같지만 pipe 안에서는 op 하나만 받는다 — 인자 수를 보면 어느 쪽인지 안다.

24.6 흔한 실수#

module mistake_lambda .
rem expect: E-FOLD-OP

fn count_big input xs slice u8 . output u64 .
do
  return pipe xs do
    rem ✘ 이름 없는 함수를 흉내 냈다 --- 스테이지에는 이름 붙은 op 하나를 건넨다
    filter gt 2 .
    count .
  end .
end

$ lowentc --check mistake_lambda.low
mistake_lambda.low:8:0 E-FOLD-OP: this `pipe` stage names an op that does not exist

module lambda_fixed .
rem run: count_big [1,2,3,4,5]

rem 조건에 이름을 붙인다 --- 이름이 곧 설명이 된다
fn over2 input a u8 . output bool .
do
  return gt a 2 .
end

fn count_big input xs slice u8 . output u64 .
do
  return pipe xs do
    filter over2 .
    count .
  end .
end

$ lowentc --run count_big lambda_fixed.low [1,2,3,4,5]
count_big([1,2,3,4,5]) = 3
  arg0 (written) = [1,2,3,4,5]

module mistake_widecollect .
rem expect: E-TYPE-COLLECT

fn times1000 input a u8 . output u64 .
do
  return mul (widen u64 a) 1000 .
end

proc scale input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    rem ✘ `u64` 를 내는 `map` 을 `u8` 버퍼에 담는다 --- 1000 이 232 가 된다
    map times1000 .
    collect into out .
  end
  return 0 .
end

$ lowentc --check mistake_widecollect.low
mistake_widecollect.low:14:0 E-TYPE-COLLECT: this `collect into` would put a WIDER value into a narrower buffer, and that loses bits silently (measured: 1000 became 232). A conversion that loses value never happens implicitly here (§6.2.5) — put a `map` in front that says which narrowing you mean (`narrow`, `narrow_wrap`, `narrow_sat`, `narrow_try`), or collect into a buffer of the produced width

module mistake_foldorder .
rem expect: E-FOLD-ORDER

rem ✘ 원소를 먼저 받았다 --- 누산값이 `x` 로, 원소가 `acc` 로 들어온다
fn add_small_swapped input x u8 . input acc u64 . output u64 .
  requires le acc 1000000 .
do
  guard lt x 100 . else return acc .
  return add acc (widen u64 x) .
end

fn sum_small_wrong input xs slice u8 . output u64 .
do
  return pipe xs do
    fold 0 add_small_swapped .
  end .
end

$ lowentc --check mistake_foldorder.low
mistake_foldorder.low:15:0 E-FOLD-ORDER: the accumulator of a `fold`/`scan` is the FIRST input of its op and also its output, because each step computes `acc = op(acc, element)`. Here the first input and the output are declared with different types, so the running total is handed to a parameter that cannot hold it — a `u8` first input takes a total of 600 as 88 and the answer is silently wrong. Write the op as `input acc <out-type> . input x <element-type> .`

module mistake_stageeffect .
rem expect: E-EFFECT-CALC

proc nonzero input a u8 . output bool . effects panic .
do
  if eq a 0 . do panic "zero in input" . end
  return true .
end

rem ✘ 스테이지 op 이 멈출 수 있는데 `pipe` 를 쓴 op 을 `fn` 으로 적었다
fn count_checked input xs slice u8 . output u64 .
do
  return pipe xs do
    filter nonzero .
    count .
  end .
end

$ lowentc --check mistake_stageeffect.low
mistake_stageeffect.low:12:1 E-EFFECT-CALC: this fn is declared pure but performs `panic` — make it a `proc` with `effects …`, or remove the effect

module short_buffer .
rem run: big_doubled [1,3,4] [0,0]
rem trap: big_doubled [3,4,5,6] [0,0]

fn over2 input a u8 . output bool .
do
  return gt a 2 .
end

fn dbl input a u8 . output u8 .
do
  return wrap_add a a .
end

rem 버퍼는 두 칸 --- 남는 원소가 둘이면 담기고, 넷이면 셋째를 담으려는 순간 멈춘다
proc big_doubled input xs slice u8 . input out mut slice u8 . output u64 . effects none .
do
  pipe xs do
    filter over2 .
    map dbl .
    collect into out .
  end
  return len out .
end

$ lowentc --run big_doubled short_buffer.low [1,3,4] [0,0]
big_doubled([1,3,4], [6,8]) = 2
  arg0 (written) = [1,3,4]
  arg1 (written) = [6,8]
$ lowentc --run big_doubled short_buffer.low [3,4,5,6] [0,0]
== ir diagnostics (1) ==
0:0 E-VM-BOUNDS: slice index out of bounds on write (panic)

24.7 이 장의 문법 한눈에#