24 pipe — one line for each thing you mean to do

24.1 The same work, two shapes#

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]

The two ops give the same answer. digits_loop has a person line up the counter n, the index i, the end condition and the increments. digits_pipe is two lines.

• filter is_digit . — keeps only elements for which is_digit is true.
• count . — counts what is left. The word that ends the flow (the terminal) is exactly one.

pipe is a statement, but when it ends with a value-producing terminal (count, fold, any, all) it can be used like an expression, as in return pipe s do … end . — the final stop belongs to the return statement (end closes only the pipe block).

Drawn as a tube that elements flow through:

 s = "a1b22"
               ┌─────────────────┐            ┌───────┐
  a 1 b 2 2 ─▶ │ filter is_digit │ ─▶ 1 2 2 ─▶ │ count │ ─▶ 3
               └─────────────────┘            └───────┘
                 stage: filters                 terminal: ends the flow and gives a value

Elements pass through the tube one at a time. No separate “array of just the digits” is built in between.

24.2 Stages and terminals#

The op given to filter·any·all is a predicate and must answer bool. An op that answers a number is refused with E-PIPE-PRED — there is no rule here that reads a nonzero number as true (the same reason as cast in chapter 13).

Used as a value — return pipe … end . — a pipe is worth what its terminal gives. Each stage hands elements on to the next line, and the terminal takes them last and makes one value.

 xs = [1, 5, 2, 7]
      │
      ▼  filter big      (big = gt x 2)       5, 7          1 and 2 are dropped here
      ▼  map dbl         (dbl = x + x)        10, 14
      ▼  collect into out                     out = [10, 14, …]   answer = 2 (how many stored)

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 keeps only elements greater than 2 (filter), doubles them (map) and puts them into out (collect into). In the result [6,8,10,0,0], positions not filled stay as they were. The buffer is given by the caller; pipe does not allocate.
• fold 0 addu in sum_big starts from 0 and accumulates with addu.
• has_zero is any is_zero, and all_small is all under10.
• middle puts the middle two elements into out with skip 1 and take 2.

A stage is given a named op. This language has no anonymous functions (lambdas). A stage op takes one element and receives no capabilities. The ops of fold and scan take the accumulator and an element.

Without tuples, how are positions or pairs handled? The pair is not built but passed to the op as arguments.

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 gives idxadd the position and the element. zip ys addb gives addb an element of xs and the element of ys at the same position; when the shorter one ends the whole flow ends, so pairs always match. scan 0 addb passes the running sum on as the element. Since pairs are never built and immediately taken apart, there is no hidden allocation.

24.3 Walking once is the definition#

A single pipe runs in one pass, and no intermediate arrays are created between stages. This is not an optimisation the processor may try but the definition of pipe, and a processor that creates intermediate arrays does not conform.

Why make it the definition? If fusion were an optimisation, “how far fusion goes” would differ between processors, and users would hit cliffs — change one line and suddenly an intermediate array appears and things slow down. That cliff is invisible in the source. Lowent left operations that cannot be fused out of the stage words entirely. That is why operations needing to see everything, such as sorting, are not stages.

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

The list of stages is closed. pipe being a statement rather than an expression has the same reason: as an expression, stages could be detached and passed as values, and where one stream ends would not be visible in the source. do … end makes that boundary visible.

24.4 Reading only as much as needed#

any stops at the first element giving true, all at the first giving false, and take n after passing n elements. Elements after the stop are not read, and stages are not run for them. has_zero [4,0,9] never looks at 9. Only because this property is written into the meaning can pipe handle sources without an end.

A terminal ends the flow. A stage after the terminal is rejected.

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 The built-in map · filter with the same names#

map and filter also exist outside pipe. These are not stages but built-in operations that copy one slice into another in a single statement, and they take three arguments — map <sink> <op> <source> . · filter <sink> <op> <source> ..

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

Putting [1,2] into a three-slot out gives [2,4,0]. The other way round, putting [1,2,3] into two slots stops the run as the third is written — a full sink never drops the rest in silence (the same as collect into). The sink must be a mut slice (E-MAP-SINK) and the element a scalar (E-MAP-ELEM). The word is the same, but inside pipe it takes one op — the number of arguments tells which is meant.

24.6 Common mistakes#

module mistake_lambda .
rem expect: E-FOLD-OP

fn count_big input xs slice u8 . output u64 .
do
  return pipe xs do
    rem ✘ imitates an anonymous function --- a stage takes one named 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 give the condition a name --- the name becomes its explanation
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 ✘ a `map` producing `u64` is collected into a `u8` buffer --- 1000 becomes 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 ✘ takes the element first --- the accumulator arrives as `x`, the element as `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 ✘ the stage op can stop, yet the op using the `pipe` is written as a `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 the buffer has two slots --- two remaining elements fit; with four, the run stops as the third is stored
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 This chapter’s syntax at a glance#