8 Expressions — prefix notation and the expr island

8.1 Nothing to memorise in prefix notation#

In prefix notation the operation’s name comes first and its arguments follow. An argument that is itself a form is wrapped in parentheses. This shape has no precedence; the parentheses say everything about what is computed first.

module island .
rem run: score 3 4
rem run: score_prefix 3 4
rem run: grouped 3 4
rem run: in_range 5 1 9
rem run: spread 3 9

fn score input a u32 . input b u32 . output u32 .
  requires le a 1000 .
  requires le b 1000 .
do
  return expr a + b * 2 .
end

fn score_prefix input a u32 . input b u32 . output u32 .
  requires le a 1000 .
  requires le b 1000 .
do
  return add a (mul b 2) .
end

fn grouped input a u32 . input b u32 . output u32 .
  requires le a 1000 .
  requires le b 1000 .
do
  return expr (a + b) * 2 .
end

fn in_range input x u32 . input lo u32 . input hi u32 . output bool .
do
  return expr (lo le x) and (x le hi) .
end

fn spread input a u32 . input b u32 . output u32 .
do
  return expr (max a b) - (min a b) .
end

$ lowentc --run score island.low 3 4
score(3, 4) = 11
$ lowentc --run score_prefix island.low 3 4
score_prefix(3, 4) = 11
$ lowentc --run grouped island.low 3 4
grouped(3, 4) = 14
$ lowentc --run in_range island.low 5 1 9
in_range(5, 1, 9) = 1
$ lowentc --run spread island.low 3 9
spread(3, 9) = 6

add a (mul b 2) in score_prefix and expr a + b * 2 in score are the same expression. The two ops give the same answer, and since the island is translated to prefix, the run-time cost is the same too. The island is a projection of notation, not a different operation.

The reason for words instead of symbols is the same. ^ is exponentiation in some languages and exclusive or in others. bit_xor means one thing wherever it is read. And words can be read aloud.

8.2 The island’s precedence table#

Precedence exists only inside the island, and this table is all of it.

Parentheses change the order, as in grouped’s expr (a + b) * 2. Operations not in the table — the remainder mod, bitwise operations, min and max — are written prefix and called in parentheses even inside the island. spread’s expr (max a b) - (min a b) has that shape.

in_range joins two comparisons with and. By the table, comparisons bind tighter than and, so parentheses seem unnecessary, but the compiler in this edition rejects expr lo le x and x le hi with E-TYPE-LOGICAL. When mixing comparisons with and or or, parenthesise each comparison. The reader no longer needs to recall the table either.

8.3 What the island cannot do#

The island is a world of infix operators, so two things are missing.

First, calling an op without parentheses. twice a + 1 could be twice (a + 1) or (twice a) + 1.

module app_bad .
rem expect: E-EXPR-APP

fn twice input a u32 . output u32 .
  requires le a 1000 .
do
  return mul a 2 .
end

fn use input a u32 . output u32 .
  requires le a 100 .
do
  return expr twice a + 1 .
end

$ lowentc --check app_bad.low
app_bad.low:13:0 E-EXPR-APP: an op call inside an `expr` island must be parenthesised — write `(len d) ge 4`, not `len d ge 4`. The island has infix operators only: without the parentheses nothing says where the argument list ends, and you and the compiler would read it differently

As the diagnostic’s example shows, a call inside the island is parenthesised, as in (twice a) + 1.

Second, unary operators. The island has no operator without a left operand.

module unary_bad .
rem expect: E-EXPR-UNARY

fn flip input a i32 . output i32 .
do
  return expr - a .
end

$ lowentc --check unary_bad.low
unary_bad.low:6:0 E-EXPR-UNARY: an `expr` island has INFIX operators only — there is no unary form. `expr - 5` has nothing on the left of `-`. Write the prefix op instead (`neg 5`, `not b`, `bit_not x`), or give the left operand. The island exists to read like arithmetic; a unary sign would make `a - 5` and `a (- 5)` two readings of the same letters (SPEC-002 §2.5 · RFC-0091)

To flip a sign, write neg a in prefix, or inside the island call (neg a) or write expr 0 - a. not b and bit_not x are the same.

8.4 Short-circuiting guards conditions#

and and or do not compute the right-hand side when the left-hand side already decides the answer. Using that, you can put the condition that makes the right-hand side safe on the left.

module shortcircuit .
rem run: safe_first_is_zero []
rem run: safe_first_is_zero [0,4]
rem run: ratio_ok 0 0
rem run: ratio_ok 10 5

fn safe_first_is_zero input xs slice u8 . output bool .
do
  return and (gt (len xs) 0) (eq (index xs 0) 0) .
end

fn ratio_ok input num u32 . input den u32 . output bool .
do
  return and (ne den 0) (ge (div num den) 2) .
end

$ lowentc --run safe_first_is_zero shortcircuit.low []
safe_first_is_zero([]) = 0
  arg0 (written) = []
$ lowentc --run safe_first_is_zero shortcircuit.low [0,4]
safe_first_is_zero([0,4]) = 1
  arg0 (written) = [0,4]
$ lowentc --run ratio_ok shortcircuit.low 0 0
ratio_ok(0, 0) = 0
$ lowentc --run ratio_ok shortcircuit.low 10 5
ratio_ok(10, 5) = 1

safe_first_is_zero does not compute index xs 0 on an empty slice, because if gt (len xs) 0 on the left is false, the answer is already false. ratio_ok likewise skips the division when the denominator is 0. This shape suits conditions too small for a guard. If the condition is a fact about the whole op, guard is better (chapter 7).

8.5 Expressions computed at translation time#

Some expressions have values before the program runs.

module compt .
rem run: table_size
rem run: pick

fn table_size output u64 .
do
  return mul (size_of u32) 16 .
end

fn pick output u32 .
do
  match comptime (add 2 3) do
    case 0 . do return 100 . end
    case 5 . do return 500 . end
    case _ . do return 999 . end
  end
end

$ lowentc --run table_size compt.low
table_size() = 64
$ lowentc --run pick compt.low
pick() = 500

size_of u32 gives the number of bytes of one value of that type at translation time. It lets code that takes a type as a parameter compute its costs honestly instead of assuming the widest type (chapter 22).

comptime (add 2 3) marks an expression to be computed at translation time. When the value a match splits on is a translation-time constant, the match folds to the one matching arm and the run-time comparisons disappear. The folded-away arms are still type-checked, unlike code removed with C’s #ifdef, which is not even checked. config <option>, which reads the build configuration, is also used as a translation-time constant (chapter 31).

8.6 Common mistakes#

Comparison (level 2) binds tighter than and (level 1b), so mixing them without parentheses has exactly one meaning.

module mixcmp .
rem run: in_range 3 1 5
rem run: in_range 9 1 5

fn in_range input x u64 . input lo u64 . input hi u64 . output bool .
do
  rem comparison binds tighter than `and`, so mixing without parentheses has one meaning
  return expr lo le x and x le hi .
end

$ lowentc --run in_range mixcmp.low 3 1 5
in_range(3, 1, 5) = 1
$ lowentc --run in_range mixcmp.low 9 1 5
in_range(9, 1, 5) = 0

Writing the parentheses anyway spares the reader from recalling the table. Below is the same thing written that way.

module mixcmp_fixed .
rem run: in_range 5 1 9
rem run: in_range 12 1 9

fn in_range input x u64 . input lo u64 . input hi u64 . output bool .
do
  return expr (lo le x) and (x le hi) .
end

$ lowentc --run in_range mixcmp_fixed.low 5 1 9
in_range(5, 1, 9) = 1
$ lowentc --run in_range mixcmp_fixed.low 12 1 9
in_range(12, 1, 9) = 0

module mistake_percent .
rem expect: E-CHAR

fn last_digit input a u64 . output u64 .
do
  rem ✘ `%` is not an island operator --- call `mod` in parentheses for the remainder
  return expr a % 10 .
end

$ lowentc --check mistake_percent.low
7:17 E-CHAR: unexpected character
7:17 E-FORM-UNEXPECTED: unexpected token in form

module percent_fixed .
rem run: last_digit_plus 1234 1

fn last_digit_plus input a u64 . input k u64 . output u64 .
do
  rem operations missing from the table are written prefix inside the island, wrapped in parentheses
  return expr (mod a 10) + k .
end

$ lowentc --run last_digit_plus percent_fixed.low 1234 1
last_digit_plus(1234, 1) = 5

module mistake_pow .
rem expect: E-TYPE-KIND

fn square input a u64 . output u64 .
do
  rem ✘ `pow` on an integer; transcendental functions are floating-point only
  return pow a 2 .
end

$ lowentc --check mistake_pow.low
mistake_pow.low:7:0 E-TYPE-KIND: this is a floating-point-only operation (canon §6.3.9) and it was given an INTEGER. `pow` used to answer anyway — and the answer was wrong (`pow 5 2` gave 5 on both backends), which is the worst kind of wrong: quiet. Convert first (`cast f64 n`), or use repeated multiplication for an integer power

module pow_fixed .
rem run: square_f 1.5
rem run: square_i 5

fn square_f input a f64 . output f64 .
do
  rem `pow` works correctly on floats
  return pow a 2.0 .
end

fn square_i input a u64 . output u64 .
  requires le a 1000 .
do
  rem an integer power is written as multiplication; the name says what it does
  return mul a a .
end

$ lowentc --run square_f pow_fixed.low 1.5
square_f(1.5) = 2.25
$ lowentc --run square_i pow_fixed.low 5
square_i(5) = 25

module noparen .
rem run: with_parens 3 4
rem run: without_parens 3 4

fn with_parens input a u64 . input b u64 . output u64 .
do
  return add 1 (mul a b) .
end

fn without_parens input a u64 . input b u64 . output u64 .
do
  rem without parentheses, the grouping comes from `mul` taking two arguments --- the same 13
  return add 1 mul a b .
end

$ lowentc --run with_parens noparen.low 3 4
with_parens(3, 4) = 13
$ lowentc --run without_parens noparen.low 3 4
without_parens(3, 4) = 13

8.7 This chapter’s syntax at a glance#