Programming+ did not start. It has to be served by a web server (pixi run dev, or the site), not opened as a file, and its scripts must be allowed to run. Reload to try again.

Programming in the age of agents

Anyone can produce the code. Someone has to answer for it.

Work is now done by human agents and artificial ones. Writing a program or plotting a dataset, skills that took years to earn, now takes minutes and a budget for tokens. Judging whether the result is right still takes deep knowledge, and that knowledge is worth more now, not less. Programming+ exists to help you build it.

Programming+ takes a procedure from an idea to Mojo to the machine. Write it as English steps, equations or pseudocode, step through the Mojo made from it, and step the x86-64 the compiler makes from that on a model machine.

Made by
  • a junior engineer
  • an LLM agent
  • a contractor
  • a Nobel laureate
  • you, last spring
I take responsibility for this output.
signed
The maker changes. The signature does not. Programming+ is for the person who signs.

Why Programming+ exists

Producing got cheap

An assistant writes a working function in seconds, in any language, and it usually looks right. So does the analysis around it: the fit, the figure, the pipeline. Output is no longer the scarce thing.

Ownership did not

Quality is something a person answers for. Whoever made it, someone has to read it and say: I take responsibility for this. That person needs to know what it does, step by step.

The gap is where tools are missing

Going from novice to expert takes years, and few tools are built to shorten it. Most are either so easy that anyone can run them, or so hard that people automate them without the expertise to judge what comes out.

We see it everywhere. When AlphaFold became something anyone with a browser could run, far more people could produce a predicted structure than could review one. Computational science is going the same way: getting the code to run used to be the bar. Knowing what happens at each step is now the minimum.

From an idea, to Mojo, to the machine

Everything here can be learned the hard way: decompiling binaries, reading instruction sets, reading the MLIR a compiler leaves behind. Programming+ walks that road with you, in three areas. Each one shows a real run, made by the same engines the areas use, the moment this page loaded.

Bridge

Take a written problem or idea into Mojo: write it as plain-English steps (lingo), equations (matho) or pseudocode (pseudo), and Mojo is generated from the pseudo.

mathoequations, in LaTeX
\bar{x} = \frac{1}{n} \sum_{i=0}^{n-1} x_i
pseudopseudocode precise enough to run
FUNCTION X_BAR(N : INTEGER, X : LIST OF FLOAT) RETURNS FLOAT
    DECLARE Total : FLOAT
    Total <- 0.0
    FOR I <- 0 TO N
lingosteps in plain English
To x bar for N and X:
    Start with Total at 0.0.
    For each I from 0 up to but not including N:
MojoModular's languageGenerated from pseudo
def x_bar(n: Int, x: List[Float64]) -> Float64:
    var total: Float64
    total = 0.0
    for i in range(n):

Developer

Write Mojo: the checker, the stepper, lifetimes, tests, and the real compiler.

Advice before you compile
def main():
    var s = String("hi")
    var t = s^
    print(s)
  • ●line 4 use of uninitialized value 's'
  • ○line 2 's' declared here
The run, step by step
  1. count_base(b="A", t="GATTACA")
  2. var total = 0 writes total
  3. i = 0 writes i
  4. String(t[codepoint=i]) == b → no
  5. i = 1 writes i
  6. String(t[codepoint=i]) == b → yes
  7. total += 1 writes total

Hardware

See the machine: Mojo and the x86-64 it compiles to, stepped on a model machine with its registers, memory and chip in view.

Step 8: mov r10, qword ptr [rdi + r8*8]
rdi0x1000
rdx0x2000
r80x0
r100x1was 0x0
r110x0

The cache line it touched

Load of 8 bytes at 0x1000: line 0x1000 (16 bytes), an L1d miss, fetched from memory.

08

The program has used 8 of this line's 16 bytes so far, and uses 16 in the whole run.

loaded nowstored nowused earlierused laternever used

Machine: teaching; every cache line is 16 bytes.

Why Mojo

To build understanding that lasts, the language has to go the whole distance with you, from a first loop to the hardware. Mojo does, in one language.

It reads plainly.
Its syntax stays close to Python, so a beginner can read a program before they can write one.
It is compiled, with strict rules.
Types, ownership and lifetimes are checked before the program runs, so there is always a precise answer to "is this right?" for Programming+ to show you.
It suits the sciences.
We believe it will become a leading language for computational biology, chemistry and physics, where speed and correctness both matter.

Programming+ is pinned to Mojo 1.2.0. Its checker and its interpreter are held to the real compiler's answers on every program in its corpus; for a program of your own, Compile & run asks the compiler.

  1. A first programprint, a variable, a loop
  2. Proceduresstrings, lists, functions and their tests
  3. Ownershipeach value made, copied, moved and destroyed
  4. The machinethe x86-64 it compiles to, the caches it touches
  5. Hand-written GPU kernelsthe same language, at the far end (Programming+ does not show them yet)

What each area does

Everything but Compile & run runs in your browser, with nothing to install; Compile & run sends the Mojo and its input to godbolt.org, and asks before the first time. Each area is its own page with its own tools; a problem opens in every area it has something to show in, and Edit in Developer and Open in Hardware carry your work from one to the next.

Bridge

From an idea to Mojo. Write the procedure in whichever notation fits, and the others follow as you type.

Open Bridge →

Translation as you type

lingo, matho, pseudo and speco (a specification: what a routine requires and ensures) are kept in step through pseudo, the hub: the pane you edit leads, the others are regenerated from it, and a notation that cannot say something keeps its last good text and tells you why, rather than going blank.

lingo  ⇄  pseudo  ⇄  matho
speco  ⇄  pseudo  →  Mojo

Mojo, labeled as generated

The Mojo is a literal line-for-line translation of the pseudo. Where a line has no faithful Mojo, the translation says so and stops there instead of guessing, and it always says it was generated and not reviewed for Mojo best practices. Compile & run asks the real compiler about it; Edit in Developer makes it yours.

Generated from pseudo

Prove, then fuzz

Prove checks every claim the speco makes about the pseudo. Tests fuzzes each routine: edge cases, every DNA string up to three letters for a routine that reads one, random values and mutations that reach new lines, every case listed with what was checked and what happened, and a failure shrunk to a smaller input that fails the same way.

count_base no failures on 300 generated inputs
MATCH 1 way to fail among 300
MATCH("AA", "A") — T[I + J] asks for position 1, and T holds 1 character, at positions 0 to 0.

Developer

Mojo only, nothing else in the way.

Open Developer →

The real compiler's verdict

Compile & run sends the pane to the pinned Mojo 1.2.0 compiler on godbolt and brings back what it printed, what it said, and the listing. The first time, it says what it sends and asks. Programming+ never says a program compiles without asking one.

ran, exit 0did not compile

Advice on your lines

A value used after it was moved, a name not in scope, a missing main: found as you type, on your own line numbers, with a one-click fix where there is one. Best practices, off until you turn it on, adds notes on how a Mojo programmer would write it.

def main():
    var s = String("hi")
    var t = s^
    print(s)
  • ●line 4 use of uninitialized value 's'
  • ○line 2 's' declared here

The run, top to bottom

One view of the whole run: a row per step, a column per variable you follow, the value written in color, reads underlined, and each value made, copied, moved and destroyed marked where it happens. Programming+'s interpreter reads a subset of Mojo, and says why when it declines a program.

  1. count_base(b="A", t="GATTACA")
  2. var total = 0 writes total
  3. i = 0 writes i
  4. String(t[codepoint=i]) == b → no
  5. i = 1 writes i

Hardware

The machine under the code, arranged the way you want to look at it.

Open Hardware →

Mojo and its x86-64

Compile, open a function in Hardware, and its listing opens in the x86-64 tab, each instruction linked to the Mojo line it came from. Step the instructions on a model machine.

        xor     eax, eax
        xor     ecx, ecx
.scan:
        cmp     rcx, rsi
        jae     .done
        movzx   r8d, byte ptr [rdi + rcx*1]

A board you arrange

Registers, flags, memory, the stack, the cache line each access touches, the L1 cache, the hierarchy, virtual memory, the pipeline, micro-ops, the out-of-order core and the instruction bytes: choose the views, drag them into order, or start from a preset.

Registers and memoryCachesPipelineWhole chip

Two model machines

A teaching machine with caches small enough that misses happen on small data, and a realistic one shaped like a desktop core; virtual memory on or off. Their cycle counts are a teaching model, not a measurement of a real processor.

One procedure, every way it can be written

Syntax is the last thing to learn, not the first. The hard part of programming is turning an idea ("count the As") into steps a machine can follow: what to keep track of, where a loop starts and stops, what to do when the input is empty. Write that procedure in whichever notation fits the moment, from plain English to the instructions the processor runs, and step every one of them through the same run.

lingoBridge

Steps in plain English the reader can run.

To count the B bases in T:
    Start with Count at 0.
    For each letter c of T:
        If c is B, add 1 to Count.
    The answer is Count.

mathoBridge

Equations, written in LaTeX: sums become loops, cases become IF.

\bar{x} = \frac{1}{n} \sum_{i=0}^{n-1} x_i
\sigma^2 = \frac{1}{n - 1} \sum_{i=0}^{n-1} (x_i - \bar{x})^2

count_base has no matho form: B is a character, not a number. So this box shows a mean and a variance, and the Bridge says why when a procedure will not go into equations.

pseudoBridge

Pseudocode precise enough to run, prove and translate: the hub every translation goes through.

FUNCTION COUNT_BASE(B : CHAR, T : STRING) RETURNS INTEGER
    DECLARE N : INTEGER
    DECLARE Total : INTEGER
    N <- LENGTH(T)
    Total <- 0
    FOR I <- 0 TO N
        IF T[I] == B THEN
            Total <- Total + 1
        ENDIF

specoBridge

The specification you prove against: what a routine requires and ensures, and what each loop keeps.

SPEC COUNT_BASE(B, T)
    ENSURE result = |{ K ∈ [0, |T|) : T[K] = B }|
    LOOP FOR I
        INVARIANT Total = |{ K ∈ [0, I) : T[K] = B }|

MojoDeveloper

Modular's language. Compile & run builds and runs it with the real Mojo 1.2.0 compiler.

def count_base(b: String, t: String) -> Int:
    var total = 0
    for i in range(t.count_codepoints()):
        if String(t[codepoint=i]) == b:
            total += 1
    return total
def main():
    print(count_base("A", "GATTACA"))

x86-64Hardware

Registers, flags, memory, and the cycles each instruction costs on the model machine.

        xor     eax, eax
        xor     ecx, ecx
.scan:
        cmp     rcx, rsi
        jae     .done
        movzx   r8d, byte ptr [rdi + rcx*1]
        cmp     r8b, dl
        jne     .next

Say what must be true, then check it

In the Bridge, speco is the specification as a document: what a routine requires, what it ensures, and the invariant each loop keeps. It is woven into the pseudo, so the claims survive an edit in English or in equations; Programming+ proves every claim it can, reports the ones it cannot finish as open, and fuzzes them, so a claim is marked proved only when the prover proved it.

speco

SPEC COUNT_BASE(B, T)
    ENSURE result = |{ K ∈ [0, |T|) : T[K] = B }|
    LOOP FOR I
        INVARIANT Total = |{ K ∈ [0, I) : T[K] = B }|
4 proved0 broken0 open

In your own pages, with Quarto

Keep a program in a file beside a Quarto page and write one line where it should appear. When the page renders, Programming+ runs the program with these same engines and draws the view into the page: no iframe and nothing loaded from elsewhere. A program that stops printing its EXPECT lines is reported on the page, and with pplus-strict: true it fails the render. Or embed this app, live, for readers to edit.

You write
{{< pplus-steps lingo="count-base.lingo" >}}
The reader gets
lingo0 / 23
To count the B bases in T:
    Start with Count at 0.
    For each letter c of T:
        If c is B, add 1 to Count.
    The answer is Count.
Before the first step.
B—
T—
Count—
c—
printed so far
Programming+ · pplus-steps in the gallery

Problems

Worked problems, most of them from computational biology, where Programming+ began, grouped by technique. Each opens in every area it has something to show in, each one with Mojo has a program verified on the real compiler, and any of them can be shared as a link to exactly what you see.

The linear scan

Bugs to find

Loop forms

Collections

Beyond the scan

The machine

Your own

Language reference

Everything each pane reads, generated from the same tables the editors use for highlighting and hover help, so the reference and the tool cannot drift apart. Hover any word in an editor to see its entry.

lingo

Plain-English steps with exactly one meaning each. The reader knows a fixed set of sentence shapes; anything else is a phrase you define, or a question it asks you.

Starting a routine

SentenceExample
To <do something with P and T>:
To find every start of P in T:
The answer is <value>.
The answer is Starts.
Stop and answer <value>.
Stop and answer i.

Giving a value a name

SentenceExample
Start with <name> at <value>.
Start with Count at 0.
Start with an empty list called <name>.
Start with an empty list called Starts.
Start with an empty tally called <name>.
Start with an empty tally called Counts.
Set <name> to <value>.
Set Best to i.

Changing a value

SentenceExample
Add <value> to <name>.
Add 1 to Count.  Add i to Starts.
Add <letter> to the end of <text>.
Add the complement of b to the end of R.
Subtract <value> from <name>.
Subtract 1 from Left.
Count <value> in <tally>.
Count the window in Counts.
Swap <name> and <name>.
Swap A and B.

Loops

SentenceExample
For each position <i> of <T>:
For each position i of T:
For each letter <b> of <T>:
For each letter b of T:
For each <i> from <A> up to but not including <B>:
For each i from 0 up to but not including the length of T minus 1:
For every third position <i> of <T>:
For every third position i of T:
Repeat while <condition>:
Repeat while i is less than the length of T:
Stop the loop. Skip to the next position.

Tests

SentenceExample
If <condition>, <step>.
If the letter of T at i is B, add 1 to Count.
If <condition>: ... Otherwise:
If Score is at least 30:
<x> is <y>, is not, is less than, is at most, is at least, is one of
the letter is 'G' or 'C'
<x> is neither <a> nor <b>
b is neither 'G' nor 'C'
<text> is empty / <text> contains <piece>
T is empty
(<condition> or <condition>) and <condition>
(b is 'A' or b is 'T') and i is more than 0
for every <j> from <A> up to but not including <B>, <condition>
for every j from 0 up to but not including the length of P, the letter of P at j is the letter of T at i + j

Values

SentenceExample
the letter of <T> at <i>
the letter of T at i + 1
the length of <T>
the length of T minus the length of P
the <K> letters of <T> starting at <i>
the 3 letters of T starting at i
the number of positions <k> of <T> where <condition>
the number of positions k of T where the letter of T at k is 'G'
the count for <key> in <tally>
the count for w in Counts
the larger of <A> and <B>
the larger of Best and Run

Defining a phrase

SentenceExample
<phrase> when <condition>.
P matches at i when for every j from 0 up to but not including the length of P, the letter of P at j is the letter of T at i + j.
The <phrase> is <value>.
The GC count of S is the number of letters of S that are 'G' or 'C'.
The <phrase> is <a> when <c>, ..., and <z> otherwise.
The complement of b is 'T' when b is 'A', 'A' when b is 'T', 'G' when b is 'C', and 'C' otherwise.

Comparison phrasings

Every phrase in a column means the same operator.

MeansPhrasings
!=is not equal to · is not the same as · are not the same as · is different from · are different from · does not equal · differs from · is not · are not · !=
<=is less than or equal to · is at most · is no more than · is not more than · are at most · <=
>=is greater than or equal to · is at least · is no less than · is not less than · are at least · >=
<is less than · is smaller than · is fewer than · is below · is under · are less than · <
>is greater than · is more than · is larger than · is bigger than · is above · is over · exceeds · are greater than · are more than · >
==is equal to · is the same as · are the same as · equals · is · are · == · =
NOT INis / are not one of
NOT INis / are not in
NOT INis / are not a key of
NOT INis / are not a member of
NOT INis / are not among
INis / are one of
INis / are in
INis / are a key of
INis / are a member of
INis / are among

Questions the reader asks

Each is deterministic: the same sentence always raises the same question, with the readings as one-click rewrites.

IdWhen, and what it offersA sentence that raises it
range-ends"from 0 to the length of T" does not say whether the end is included. Offers "up to but not including" and "up to and including".
To count in T:
    Start with Count at 0.
    For each i from 0 to the length of T:
        Add 1 to Count.
    The answer is Count.
between"between 20 and 30" leaves both ends undecided. Offers the three readings.
To test Q:
    If Q is between 20 and 30, the answer is 1.
    The answer is 0.
answer-in-loop"the answer is i" inside a loop could stop now or keep looking. Offers "Stop and answer i" and "Set Best to i".
To find it in T:
    For each position i of T:
        If the letter of T at i is 'N', the answer is i.
    The answer is the length of T.
is-step"Count is 0" could set Count or claim it. As a step, say "Set Count to 0" or "Check that Count is 0".
To do it with T:
    Count is 0.
    The answer is Count.
and-or"A or B and C" does not say which binds. Parentheses do.
To test b and i:
    If b is 'A' or b is 'T' and i is 0, the answer is 1.
    The answer is 0.
not-or"is not 'G' or 'C'" has two readings; say "is neither 'G' nor 'C'" or "is not one of".
To test b:
    If b is not 'G' or 'C', the answer is 1.
    The answer is 0.
stop"Stop" inside a loop could end the loop or the routine.
To scan T:
    Start with Count at 0.
    For each letter b of T:
        If b is 'N', stop.
        Add 1 to Count.
    The answer is Count.
pronoun"it", "they", "them" could stand for several names. Name the thing you mean.
To scan T:
    Start with Count at 0.
    For each letter b of T:
        If it is 'G', add 1 to Count.
    The answer is Count.
used-before-setA name used before any step gives it a value: the set-up step is missing.
To scan T:
    For each letter b of T:
        Add 1 to Count.
    The answer is Count.
text-place"Add b to R" with R a text does not say where b goes; say "to the end of" or "to the front of".
To reverse T:
    Start with an empty text called R.
    For each letter b of T:
        Add b to R.
    The answer is R.

matho

Equations as a source language, written in LaTeX. Each equation becomes a FUNCTION in pseudo; sums become loops, subscripts become positions, cases become IF. Every decision the translation makes (which letters are whole numbers, which are lists, where a 1-based sum meets a 0-based list) is a note on the equation's line.

What it reads

WrittenBecomesExample
f(x) = …An equation with a function on the left defines FUNCTION F(X : FLOAT) RETURNS FLOAT. Names used on the right but not named on the left become extra parameters, with a note.
f(x) = a x^2 + b
name = …A plain name on the left names the function; its parameters are the free names on the right, in order of appearance. \bar{x} → X_BAR, E_k → E_K, \sigma^2 → SIGMA_SQUARED.
\bar{x} = \frac{1}{n} \sum_{i=0}^{n-1} x_i
x_iA subscript that is an index (bound by a sum, or free on the left side) makes the name a LIST OF FLOAT and the subscript a position. Any other subscript is part of the name: v_0 is V0, x_{max} is XMax.
h(t) = v_0 t - \frac{1}{2} g t^2
\sum_{i=a}^{b} …A FOR loop with an accumulator, Total. The upper bound is inclusive in mathematics and exclusive in pseudo, so n-1 becomes TO N. From i = 1, a subscript i becomes the position I - 1, with a note.
s = \sum_{i=1}^{n} x_i^2
\sum_i … \sum_{x \in S} …With no bounds, the loop runs over every position of the list the index walks. Over a set, it is FOR EACH.
m = \sum_{x \in S} x
\prod, n!A product loop with an accumulator starting at 1.0; n! is the same loop from 2 to n.
c = \frac{n!}{k! (n-k)!}
\frac{a}{b}, \sqrt{x}, x^k, e^xDivision, SQRT, ^ (x^{1/2} is SQRT too), and EXP. A plain e is a name; e^{…} is the exponential.
f(x) = \frac{1}{\sqrt{2\pi\sigma^2}} e^{-\frac{(x-\mu)^2}{2\sigma^2}}
|x|, \lfloor x \rfloor, \lceil x \rceil, \bmodABS, FLOOR, CEIL and MOD. MOD makes its operands INTEGER; FLOOR and CEIL give a whole number from any number.
r = \lfloor n / 2 \rfloor + a \bmod b
\sin \cos \tan \exp \ln \log \max \minThe built-ins of the same name. \log is LOG10; \log_2 is LOG2; \log_b x is LOG(x) / LOG(b). \sin^2 x is SIN(X) ^ 2.
y = \sin^2 \theta + \log_{10} n
\binom{n}{k}CHOOSE(N, K); both become INTEGER.
P(k) = \binom{n}{k} p^k (1-p)^{n-k}
\vec{a} \cdot \vec{b}, \|\vec{a}\|A \vec or \mathbf name is a LIST OF FLOAT; \cdot between two of them is DOT and the double bar is NORM_OF.
\cos\theta = \frac{\vec{a} \cdot \vec{b}}{\|\vec{a}\| \|\vec{b}\|}
A_{ij}Two index letters in one subscript: a LIST OF LIST OF FLOAT, indexed A[I][J].
y_i = \sum_{j=0}^{n-1} A_{ij} x_j
\begin{cases} … \end{cases}IF / ELSEIF / ELSE. Conditions use < \le > \ge = \ne, chains such as 0 \le x < 1, and \text{and} / \text{or}. The last case must be the one with no condition.
f(x) = \begin{cases} 0 & \text{if } x < 0 \\ x & \text{otherwise} \end{cases}
an earlier equation's nameA name defined by an equation higher up is a call to that function, with its parameters joining this one's. Inside a loop, a call whose arguments do not change is computed once, before the loop, as a local.
g(x) = x^2 + 1
h(x) = 2 g(x) + c
Greek letters, \text{…}, \bar \hat \tildeNames: \sigma is Sigma, \text{pH} is PH, \bar{x} is XBar. Two symbols that would be one pseudo name (p and P) are told apart with a suffix, and a note says so.
\text{pH} = -\log_{10} [H]

What it refuses, and what to write instead

Some mathematics has no finite procedure behind it. The reader says so, and says what the procedure would be.

WrittenWhy, and what to write
\intAn integral has no finite procedure behind it. Write the sum it approximates: \sum_{i=0}^{n-1} f(a + i h) h with a step h, which becomes a loop.
\inftyA program cannot run to infinity. Give the sum or product an upper bound, such as n, and make n a parameter.
\lim, \partial, \nabla, f'Limits and derivatives are not procedures. Write the difference quotient (f(x + h) - f(x)) / h for a step h, or pick the value of n you mean.
\forall, \existsA statement about all or some values is a specification, not a procedure: it belongs in the speco pane as an ENSURE, or becomes the loop that searches.
a = b = c, x < 0 on its own, \pm, \approx, \propto, \simStatements and relations rather than definitions: keep the two sides you want computed, split ± into two equations, name the constant a proportionality leaves out, write RANDN() or RAND(x) for a draw.

pseudo

The course notation: uppercase keywords, <- for assignment, half-open bounds everywhere, typed names, and claims the prover can check.

Keywords

Uppercase, always. Names are case-insensitive and may not reuse a keyword or a built-in.

KeywordMeaningGroup
DECLARECreates a name and fixes its type, with or without a starting value: DECLARE Counter : INTEGER, or DECLARE Counter : INTEGER <- 0Declarations
CONSTANTNames a value that never changes: CONSTANT BasesPerCodon = 3Declarations
DEFINEMakes one fixed set of a named set type: DEFINE Purines ('A', 'G') : BaseSetDeclarations
TYPEDefines a record (TYPE … ENDTYPE with one DECLARE per field) or names a set type (TYPE BaseSet = SET OF CHAR)Declarations
ENDTYPECloses a TYPE blockDeclarations
OFJoins a collection to its element type: LIST OF INTEGERDeclarations
USEBrings routines from the library into the program: USE stats (the whole module) or USE stats.Mean (one routine). USE IEEE lets NaN and infinities flow as IEEE 754 says instead of stopping the runLibraries
INTEGERA whole number; a run holds it exactly from -9,007,199,254,740,991 to 9,007,199,254,740,991 and stops past either (the prover treats it as a whole number of any size)Types
FLOATA number with a fractional part, in IEEE 754 double precision; / always produces oneTypes
CHARExactly one character, in single quotesTypes
STRINGAny number of characters, in double quotes; positions count from 0Types
BOOLTRUE or FALSETypes
BOOLEANAnother spelling of BOOLTypes
ARRAYA fixed number of values of one type, declared by length: ARRAY[4] OF INTEGER, or ARRAY[R, C] for two dimensionsTypes
LISTAny number of values of one type, in order; starts empty and grows with APPENDTypes
HASHMAPValues reached by key: HASHMAP OF STRING : CHARTypes
SETDistinct values in no order; ask INTypes
INT8A whole number from -128 to 127; a result outside that stops the runSized numbers
INT16A whole number from -32,768 to 32,767Sized numbers
INT32A whole number from -2,147,483,648 to 2,147,483,647Sized numbers
INT64A 64-bit whole number (held exactly in this lab to ±9,007,199,254,740,991)Sized numbers
UINT8A whole number from 0 to 255: a byteSized numbers
UINT16A whole number from 0 to 65,535Sized numbers
UINT32A whole number from 0 to 4,294,967,295Sized numbers
UINT64A 64-bit whole number of 0 or more (held exactly in this lab to 9,007,199,254,740,991)Sized numbers
FLOAT32A FLOAT in single precision (about 7 significant digits): every +, -, *, / and ^ of FLOAT32 values, and every value stored in one, is rounded to the nearest single; SQRT, EXP and the other functions give a FLOAT, converted with FLOAT32(...)Sized numbers
FLOAT64Another name for FLOAT: double precision, about 16 significant digitsSized numbers
IFRuns its body when the condition is TRUESelection
THENEnds the condition of an IFSelection
ELSEIFOne word: another condition under the same IF, tested only if the ones above failedSelection
ELSEThe body that runs when no condition above was TRUESelection
ENDIFCloses an IFSelection
CASECASE OF X: picks the first arm whose value, list of values, or half-open range matches XSelection
OTHERWISEThe arm of a CASE that runs when nothing else matched; must come lastSelection
ENDCASECloses a CASESelection
FORA counted loop: FOR I <- 0 TO N runs with I = 0, 1, …, N-1. The bound is not reached. FOR EACH X IN C visits every valueIteration
TOThe stop value of a FOR, which the counter never reaches (half-open), or the upper end of a CASE rangeIteration
STEPThe increment of a FOR counter; negative counts downIteration
NEXTCloses a FOR, naming its counter: NEXT IIteration
PARALLELPARALLEL FOR I <- 0 TO N: a counted loop whose passes are independent, as on a GPU where each runs on its own thread. The lab runs them and stops with a data race if one pass writes a location another pass touchesIteration
WHILETests before each pass; the body may run zero timesIteration
ENDWHILECloses a WHILEIteration
REPEATRuns the body, then tests; the body runs at least onceIteration
UNTILCloses a REPEAT with the condition that stops itIteration
BREAKLeaves the innermost loop at onceIteration
CONTINUESkips the rest of this pass and starts the nextIteration
FUNCTIONA subroutine that hands back one value: FUNCTION F(X : INTEGER) RETURNS INTEGERSubroutines
ENDFUNCTIONCloses a FUNCTIONSubroutines
PROCEDUREA subroutine that does something and returns nothing; called with CALLSubroutines
ENDPROCEDURECloses a PROCEDURESubroutines
RETURNSStates the type of a FUNCTION's answerSubroutines
RETURNHands back the answer and ends the subroutine at onceSubroutines
CALLRuns a PROCEDURE on a line of its own: CALL REPORT("ATT", Found)Subroutines
BYREFMarks a parameter the procedure may change in the caller; everything else is a copySubroutines
BYVALStates the default explicitly: the parameter is a copySubroutines
INPUTFills one variable from outside the programInput and output
OUTPUTShows any number of values, listed with commas and printed one after another with nothing between; text prints without its quotesInput and output
ANDTRUE when both sides are; the right side is skipped once the left is FALSE, so put the guard firstOperators
ORTRUE when either side is (or both)Operators
NOTTRUE when its operand is FALSE; binds looser than a comparison, so NOT A == B means NOT (A == B)Operators
DIVInteger division, rounded down (toward minus infinity): 7 DIV 2 is 3 and -7 DIV 2 is -4Operators
MODThe remainder after DIV, with the sign of the divisor: 7 MOD 2 is 1, -7 MOD 2 is 1 and 7 MOD -2 is -1Operators
INMembership: X IN S for a SET, a LIST, a STRING, or the keys of a HASHMAP; also joins a FOR EACH variable to its collectionOperators
TRUEThe BOOL value for yesValues
FALSEThe BOOL value for noValues
REQUIREWhat every caller promises about the arguments; sits directly under the FUNCTION or PROCEDURE lineReasoning
ENSUREWhat the subroutine promises about its answer, RESULT; sits under the FUNCTION line after any REQUIREReasoning
INVARIANTWhat is true at the top of every pass of a loop; the first line of the loop bodyReasoning
DECREASESA whole number that shrinks every pass (or every recursive call) and never goes below 0: why the loop endsReasoning
ASSERTWhat is true at this line; checked on every runReasoning
FORALLFORALL K IN [0, N) : P(K) is TRUE when P holds at every positionReasoning
EXISTSEXISTS K IN [0, N) : P(K) is TRUE when P holds at some positionReasoning
EACHFOR EACH X IN C visits every value of a collection (a keyword only after FOR, as in FOR EACH X IN Collection)Contextual
SUMSUM K IN [0, N) : Q[K] adds the values over the range (a keyword only before a name and IN, as in SUM I IN [0, N) : Q[I])Contextual
RESULTInside an ENSURE, the value the function returned (a keyword only inside an ENSURE, for the value the function returns)Contextual
OLDInside an ENSURE, OLD(X) is a BYREF parameter's value when the call began (a keyword only inside an ENSURE, for the value a BYREF parameter held on entry)Contextual

Literals

WrittenIs
42, -3an INTEGER
0.5, 2.0, 1.5e-3a FLOAT; a digit on each side of the point is required
1_000_000, 0xFF, 0b1010an INTEGER with underscores between digits, in hexadecimal, or in binary
0.1 next to a FLOAT32a literal takes the type of the sized value beside it: 0.1 becomes the nearest FLOAT32, and 1 next to an INT8 is an INT8
'A'a CHAR: exactly one character in single quotes
"GATTACA", ""a STRING in double quotes; \n, \t, \" and \\ are escapes
TRUE, FALSEa BOOL
[4, 17]a LIST
{'A', 'G'}a SET
{"ATG": 'M', "TAA": '*'}a HASHMAP
[0, N)a half-open range of positions, inside FORALL, EXISTS, SUM, and sets written by rule
{ K IN [0, N) : T[K] == B }a set written by rule: every K in the range for which the condition holds
← ≤ ≥ ≠accepted spellings of <-, <=, >=, !=

Operators, loosest first

Parenthesize wherever a reader might have to look this table up.

OperatorsAssociativity and notesLevel
ORleft: TRUE when either side is; the right side is skipped once the left is TRUElevel 1
ANDleft: TRUE when both sides are; the right side is skipped once the left is FALSElevel 2
NOTprefix: NOT A == B means NOT (A == B)level 3
== != < <= > >= INchains: 0 <= I < N means 0 <= I AND I < Nlevel 4
&left: joins STRING and CHAR values into a STRINGlevel 5
+ -leftlevel 6
* / DIV MODleft: / always gives a FLOATlevel 7
- (negation)prefixlevel 8
^right: -2 ^ 2 is -4; 2 ^ 3 ^ 2 is 2 ^ 9level 9
X[I] X.F F(X)postfix: indexing, fields, and calls bind tightestlevel 10

Statements

Every form, with a runnable example.

FormMeaningExample
DECLARE <name> : <type>Creates a name of that type with no value yet. Several names may share a line.
DECLARE Counter : INTEGER
DECLARE N, M : INTEGER
DECLARE <name> : <type> <- <expr>Creates a name and gives it its starting value on the same line, as Mojo's var total: Int = 0 does. One name per line in this form; the two-line form (DECLARE, then an assignment) means the same.
DECLARE T : STRING <- "GATTACA"
DECLARE N : INTEGER <- LENGTH(T)
DECLARE Total : INTEGER <- 0
OUTPUT N, " ", Total
USE <module> / USE <module>.<Routine>Brings verified routines from the library into the program, to be called like your own. A run does not step into them (open the routine in the library to do that); the prover uses their REQUIRE and ENSURE lines at each call. Lines go at the top of the program.
USE IEEE
DECLARE X : FLOAT
X <- 1.0 / 0.0
OUTPUT IS_INF(X)
DECLARE <name> : INT32 (or another sized type)A number of a fixed width. A whole-number result that does not fit stops the run rather than wrapping around; a FLOAT32 result is rounded to single precision. Two different sized types meet only through a conversion such as INT32(X) or FLOAT32(X), and a literal takes the type beside it.
DECLARE Count : UINT8 <- 250
Count <- Count + 5
OUTPUT Count, " ", WRAP(Count + 1, UINT8)
DECLARE X : FLOAT32 <- 0.1
OUTPUT X, " holds ", EXACT(X)
CONSTANT <name> = <value>A value fixed for the whole program, worked out once before it starts from literals, other constants and built-ins (2 + 3, LENGTH("ACGT")); a variable is refused. A random draw is drawn once and keeps its value.
CONSTANT BasesPerCodon = 3
<name> <- <expr>Assignment. The right side is worked out first, then stored.
DECLARE Counter : INTEGER
Counter <- 0
Counter <- Counter + 1
OUTPUT <expr>, <expr>, ...Shows values in order. A collection prints the way you would type it.
OUTPUT "Found ", 3, " matches"
INPUT <name>Fills a declared variable from outside the program.
DECLARE Threshold : INTEGER
INPUT Threshold
IF <cond> THEN ... ELSEIF <cond> THEN ... ELSE ... ENDIFThe first TRUE condition wins; ELSEIF and ELSE are optional; one ENDIF closes the lot.
DECLARE Q : FLOAT
Q <- 25.0
IF Q < 20 THEN
    OUTPUT "discard"
ELSEIF Q < 30 THEN
    OUTPUT "marginal"
ELSE
    OUTPUT "keep"
ENDIF
CASE OF <expr> ... <value> : ... <lo> TO <hi> : ... OTHERWISE : ... ENDCASEPicks the first arm whose value, comma-separated values, or half-open range matches. Ranges are [lo, hi).
DECLARE Base : CHAR
DECLARE Partner : CHAR
Base <- 'A'
CASE OF Base
    'A' : Partner <- 'T'
    'T' : Partner <- 'A'
    'G', 'C' : OUTPUT "strong"
    OTHERWISE : Partner <- 'N'
ENDCASE
FOR <i> <- <start> TO <stop> [STEP <k>] ... NEXT <i>Counts from start while the counter is strictly less than stop (strictly greater, with a negative STEP). The counter needs no DECLARE and has no value after the loop.
DECLARE T : STRING
T <- "GATTACA"
FOR I <- 0 TO LENGTH(T)
    OUTPUT T[I]
NEXT I
FOR J <- 10 TO 0 STEP -2
    OUTPUT J
NEXT J
PARALLEL FOR <i> <- <start> TO <stop> ... NEXT <i>A counted loop whose passes may run at the same time. Each pass may write only its own slots (indexed by the counter) and names it declares; writing a shared name, or reading a slot another pass writes, is a data race and stops the run naming both passes. This is the map step of GPU programming.
DECLARE Xs, Squares : LIST OF FLOAT
Xs <- [1.0, 2.0, 3.0]
Squares <- FILL(LENGTH(Xs), 0.0)
PARALLEL FOR I <- 0 TO LENGTH(Xs)
    Squares[I] <- Xs[I] * Xs[I]
NEXT I
OUTPUT SUM_OF(Squares)
FOR EACH <x> IN <collection> ... NEXT <x>Visits every character of a STRING, value of a LIST or ARRAY, member of a SET, or key of a HASHMAP.
DECLARE GC : INTEGER
GC <- 0
FOR EACH B IN "GATTACA"
    IF B == 'G' OR B == 'C' THEN
        GC <- GC + 1
    ENDIF
NEXT B
WHILE <cond> ... ENDWHILETests before each pass; may run zero times.
DECLARE I : INTEGER
DECLARE T : STRING
T <- "GATNACA"
I <- 0
WHILE I < LENGTH(T) AND T[I] != 'N'
    I <- I + 1
ENDWHILE
REPEAT ... UNTIL <cond>Runs the body, then tests; runs at least once; stops when the condition becomes TRUE.
DECLARE N : INTEGER
N <- 0
REPEAT
    N <- N + 1
UNTIL N >= 3
BREAK / CONTINUELeave the innermost loop at once / skip to the next pass.
FOR I <- 0 TO 10
    IF I == 2 THEN
        CONTINUE
    ENDIF
    IF I == 5 THEN
        BREAK
    ENDIF
    OUTPUT I
NEXT I
FUNCTION <name>(<p> : <type>, ...) RETURNS <type> ... RETURN <expr> ... ENDFUNCTIONA subroutine with one answer. Parameters are copies. A call stands where a value stands.
FUNCTION MAX_OF(A : INTEGER, B : INTEGER) RETURNS INTEGER
    IF A > B THEN
        RETURN A
    ENDIF
    RETURN B
ENDFUNCTION
OUTPUT MAX_OF(3, 7)
PROCEDURE <name>(BYREF <p> : <type>, ...) ... ENDPROCEDURE, and CALL <name>(...)A subroutine with no answer, run for its effect. BYREF lets it change the caller's variable.
PROCEDURE SWAP(BYREF X : INTEGER, BYREF Y : INTEGER)
    DECLARE Temp : INTEGER
    Temp <- X
    X <- Y
    Y <- Temp
ENDPROCEDURE
DECLARE A, B : INTEGER
A <- 1
B <- 2
CALL SWAP(A, B)
TYPE <name> ... DECLARE <field> : <type> ... ENDTYPEA record: several named fields that travel together. Reach a field with a dot.
TYPE Read
    DECLARE Name : STRING
    DECLARE Bases : STRING
ENDTYPE
DECLARE R : Read
R.Name <- "read_1"
R.Bases <- "GATTACA"
OUTPUT R.Name, LENGTH(R.Bases)
TYPE <name> = SET OF <type>, and DEFINE <set> (<v>, ...) : <name>Names a kind of set, then makes one fixed set of that kind. A growing set is DECLARE S : SET OF <type> plus ADD.
TYPE BaseSet = SET OF CHAR
DEFINE Purines ('A', 'G') : BaseSet
IF 'A' IN Purines THEN
    OUTPUT "purine"
ENDIF
REQUIRE / ENSURE / INVARIANT / DECREASES / ASSERT <cond>Claims the lab checks on every run and the prover tries to prove for every input. See the speco reference.
FUNCTION COUNT_BASE(B : CHAR, T : STRING) RETURNS INTEGER
    ENSURE RESULT == LENGTH({ K IN [0, LENGTH(T)) : T[K] == B })
    DECLARE Total : INTEGER
    Total <- 0
    FOR I <- 0 TO LENGTH(T)
        INVARIANT Total == LENGTH({ K IN [0, I) : T[K] == B })
        IF T[I] == B THEN
            Total <- Total + 1
        ENDIF
    NEXT I
    RETURN Total
ENDFUNCTION

Built-in functions

SignatureReturnsGroup
LENGTH(X)How many characters a STRING holds, or how many values a LIST, one-dimensional ARRAY, SET, or HASHMAP holds.Measuring
ROWS(A)The first length of a two-dimensional ARRAY.Measuring
COLUMNS(A)The second length of a two-dimensional ARRAY.Measuring
INT(X)The whole-number part of a FLOAT, dropping the fraction toward zero: INT(27.54) is 27 and INT(-2.5) is -2.Numbers
ROUND(X)The nearest whole number, with halves rounded away from zero: ROUND(2.5) is 3.Numbers
ABS(X)The size of a number, ignoring its sign.Numbers
MIN(A, B, ...)The smallest of two or more numbers, or of the values in one LIST. With USE IEEE, a NaN among them makes the answer NaN.Numbers
MAX(A, B, ...)The largest of two or more numbers, or of the values in one LIST. With USE IEEE, a NaN among them makes the answer NaN.Numbers
SQRT(X)The square root, as a FLOAT.Numbers
EXP(X)e raised to the power X, as a FLOAT.Numbers
LOG(X)The natural logarithm, as a FLOAT.Numbers
LOG2(X)The base-2 logarithm, as a FLOAT; information in bits.Numbers
RAND(X)A random FLOAT between 0 and X, never X itself: in [0, X) for X above 0, in (X, 0] for X below 0, and 0.0 for X = 0.Numbers
RANDINT(A, B)A random INTEGER in [A, B).Numbers
FLOOR(X)The largest whole number at or below X: FLOOR(2.7) is 2 and FLOOR(-2.3) is -3.Numbers
CEIL(X)The smallest whole number at or above X: CEIL(2.1) is 3.Numbers
LOG10(X)The base-10 logarithm, as a FLOAT; pH and decibels live here.Numbers
SIN(X)The sine of X radians, as a FLOAT.Numbers
COS(X)The cosine of X radians, as a FLOAT.Numbers
TAN(X)The tangent of X radians, as a FLOAT.Numbers
ATAN2(Y, X)The angle in radians of the point (X, Y) from the positive x axis, in [-PI(), PI()]: -PI() only when Y is -0.0 and X is negative.Numbers
PI()The number pi, 3.14159…, as a FLOAT.Numbers
CHOOSE(N, K)The binomial coefficient: how many ways to pick K of N things, and the counts behind the binomial distribution.Numbers
RANDN()A random FLOAT from the standard normal distribution (mean 0, standard deviation 1).Numbers
SUM_OF(L)The sum of the numbers in a LIST or ARRAY; 0 for an empty one. A FLOAT when any value is a FLOAT.Statistics
MEAN_OF(L)The arithmetic mean of the numbers in a LIST or ARRAY, as a FLOAT; stops on an empty one.Statistics
VARIANCE_OF(L)The sample variance (dividing by N - 1) of the numbers in a LIST or ARRAY, as a FLOAT; needs at least two values.Statistics
STDEV_OF(L)The sample standard deviation, SQRT(VARIANCE_OF(L)), as a FLOAT.Statistics
MEDIAN_OF(L)The middle value of the numbers in a LIST or ARRAY, as a FLOAT; the mean of the two middle values when there is an even number.Statistics
DOT(A, B)The dot product of two LISTs or ARRAYs of numbers of the same length: the sum of A[I] * B[I].Vectors
NORM_OF(A)The Euclidean length of a LIST or ARRAY of numbers, SQRT(DOT(A, A)), as a FLOAT.Vectors
FILL(N, V)A new LIST of N copies of the value V: FILL(3, 0.0) is [0.0, 0.0, 0.0]. The way to make a buffer before a loop fills it.Vectors
SLICE(X, A, B)The characters of a STRING, or the values of a LIST, at positions [A, B), as a new value of the same type.Text and lists
UPPER(X)A STRING or CHAR with every letter in capitals. A STRING can grow (UPPER("straße") is "STRASSE"); a CHAR whose capital is two characters, such as 'ß', stays as it is.Text and lists
LOWER(X)A STRING or CHAR with every letter in small letters. A STRING can grow; a CHAR whose small letter is two characters stays as it is.Text and lists
SPLIT(S, Sep)The pieces of the STRING S between occurrences of the STRING or CHAR Sep, as a LIST OF STRING. Empty pieces are kept, so SPLIT("a,,b", ",") is ["a", "", "b"]; split on a space and drop the empty pieces yourself for words.Text and lists
JOIN(L, Sep)One STRING made of the values of the LIST OF STRING L with Sep between each pair: JOIN(["a", "b"], ", ") is "a, b".Text and lists
INDEX_OF(X, Piece)The first position at which Piece (a STRING or CHAR) occurs in the STRING X, or at which the value Piece occurs in the LIST X; -1 when it does not occur.Text and lists
REPLACE(S, A, B)The STRING S with every occurrence of A replaced by B, left to right, without overlapping.Text and lists
ORD(C)The number Unicode gives a CHAR: ORD('A') is 65.Text and lists
CHR(N)The CHAR Unicode numbers N: CHR(65) is 'A'.Text and lists
TO_STRING(X)Any value written as a STRING, the way OUTPUT would print it.Converting
TO_INTEGER(S)The INTEGER a STRING of digits spells, or the digit a CHAR is: TO_INTEGER('7') is 7.Converting
TO_FLOAT(X)The FLOAT a STRING of decimal digits spells ("2.5", "-1e3"), or an INTEGER as a FLOAT.Converting
ASIN(X)The angle in radians whose sine is X, in [-PI()/2, PI()/2]; X must lie in [-1, 1].Numbers
ACOS(X)The angle in radians whose cosine is X, in [0, PI()]; X must lie in [-1, 1].Numbers
ATAN(X)The angle in radians whose tangent is X, in [-PI()/2, PI()/2] (the ends for the largest FLOATs, where the exact angle rounds to them).Numbers
SINH(X)The hyperbolic sine of X, as a FLOAT.Numbers
COSH(X)The hyperbolic cosine of X, as a FLOAT.Numbers
TANH(X)The hyperbolic tangent of X, as a FLOAT, in [-1, 1]: exactly 1.0 or -1.0 once X is past about 19 either way.Numbers
HYPOT(X, Y)SQRT(X * X + Y * Y), computed without overflowing on the way when X or Y is very large.Numbers
POW(X, Y)X raised to the power Y, as a FLOAT; X must not be negative unless Y is whole, nor 0 when Y is negative. With USE IEEE it follows IEEE 754 pow: POW(1.0, NAN()) is 1.0.Numbers
CBRT(X)The cube root of X, as a FLOAT; defined for negative X too.Numbers
EXPM1(X)EXP(X) - 1, accurate when X is close to 0, where the subtraction would lose every digit.Numbers
LOG1P(X)LOG(1 + X), accurate when X is close to 0; X must be above -1.Numbers
E()The number e, 2.71828…, as a FLOAT.Numbers
TRUNC(X)X with its fraction dropped toward zero, kept as a FLOAT: TRUNC(-2.7) is -2.0. INT does the same and gives an INTEGER.Numbers
SIGN(X)-1, 0 or 1, as X is negative, zero or positive, in the type of X.Numbers
COPYSIGN(X, Y)The size of X with the sign of Y, as a FLOAT.Numbers
CLAMP(X, Lo, Hi)X held inside [Lo, Hi]: Lo when X is below it, Hi when X is above it, X otherwise; Lo must not exceed Hi.Numbers
FMA(A, B, C)A * B + C with a single rounding at the end, as the processor's fused multiply-add computes it.Precision
IS_NAN(X)TRUE when X is not a number. Only a program that says USE IEEE can hold one.Precision
IS_INF(X)TRUE when X is infinity or minus infinity. Only a program that says USE IEEE can hold one.Precision
IS_FINITE(X)TRUE when X is an ordinary number, neither infinite nor not a number.Precision
INF()Positive infinity. A program has to say USE IEEE to hold it; otherwise the run stops.Precision
NAN()Not a number. A program has to say USE IEEE to hold it; otherwise the run stops.Precision
ULP(X)The gap between X and the next FLOAT away from zero: one unit in the last place, the size of X's rounding step. For a FLOAT32 X, the gap between singles. With USE IEEE, ULP of an infinity is infinity.Precision
NEXT_AFTER(X, Y)The FLOAT next to X in the direction of Y (a FLOAT32 next to X, for a FLOAT32 X).Precision
IS_CLOSE(A, B, RelTol, AbsTol)TRUE when ABS(A - B) <= MAX(RelTol * MAX(ABS(A), ABS(B)), AbsTol): equality for measured values, with the tolerance said out loud.Precision
EXACT(X)The exact decimal value a FLOAT holds, as a STRING: EXACT(0.1) is "0.1000000000000000055511151231257827021181583404541015625".Precision
MAX_VALUE(T)The largest value of the numeric type T: MAX_VALUE(INT8) is 127, MAX_VALUE(FLOAT64) about 1.8 × 10^308.Precision
MIN_VALUE(T)The lowest value of the numeric type T: MIN_VALUE(INT8) is -128, MIN_VALUE(FLOAT64) is -MAX_VALUE(FLOAT64).Precision
EPSILON(T)For FLOAT32 or FLOAT64, the gap between 1.0 and the next value above it: 2^-23 or 2^-52.Precision
GCD(A, B)The greatest common divisor of two whole numbers; GCD(0, 0) is 0.Whole numbers
LCM(A, B)The least common multiple of two whole numbers; 0 when either is 0.Whole numbers
BIT_AND(A, B)The bits set in both A and B (two's complement for negative values).Whole numbers
BIT_OR(A, B)The bits set in A or B or both.Whole numbers
BIT_XOR(A, B)The bits set in exactly one of A and B.Whole numbers
BIT_NOT(A)Every bit of A flipped, in A's type: BIT_NOT of a UINT8 0 is 255, of an INT8 or INTEGER 0 is -1.Whole numbers
SHIFT_LEFT(A, N)A times 2^N: the bits moved N places up. A result outside A's type stops the run, as any overflow does.Whole numbers
SHIFT_RIGHT(A, N)A divided by 2^N, rounded down: the bits moved N places down (the sign kept, for a negative A).Whole numbers
WRAP(A, T)The whole number A brought into the sized type T (up to 32 bits) by wrapping around, as hardware does: WRAP(300, UINT8) is 44. Arithmetic that is meant to wrap says so with WRAP.Whole numbers
KEYS(H)The keys of a HASHMAP as a LIST, smallest first.Collections
SORTED(X)The values of a LIST or SET as a new LIST, smallest first.Collections
APPEND(L, V)Adds V to the end of the LIST L.Collections
INSERT(L, I, V)Puts V at position I of the LIST L, moving every later value one place along.Collections
REMOVE(L, I)Takes the value at position I out of the LIST L, moving every later value one place back.Collections
ADD(S, V)Makes V a member of the SET S. Adding a member already there changes nothing.Collections
DELETE(X, K)Removes the key K from a HASHMAP, or the member K from a SET.Collections
SORT(L)Puts the values of the LIST L in order, smallest first. Equal values keep their order.Collections
INT8(X)X as INT8, from -128 to 127; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
INT16(X)X as INT16, from -32,768 to 32,767; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
INT32(X)X as INT32, from -2,147,483,648 to 2,147,483,647; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
INT64(X)X as INT64, from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807, held exactly in this lab only from -9,007,199,254,740,991 to 9,007,199,254,740,991; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
UINT8(X)X as UINT8, from 0 to 255; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
UINT16(X)X as UINT16, from 0 to 65,535; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
UINT32(X)X as UINT32, from 0 to 4,294,967,295; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
UINT64(X)X as UINT64, from 0 to 18,446,744,073,709,551,615, held exactly in this lab only from 0 to 9,007,199,254,740,991; a FLOAT loses its fraction toward zero first, and a value outside the range stops the run.Converting
FLOAT32(X)X rounded to the nearest FLOAT32 (single precision, about 7 significant digits).Converting
FLOAT64(X)X as a FLOAT64 (the same type as FLOAT).Converting

Idioms

Shapes worth learning once. Each example runs; the last column is what it prints.

IdiomWhy it is written this wayExample and output
Find the first, three waysA search can stop with RETURN inside a FUNCTION, with BREAK and a flag in a loop, or with a WHILE whose condition names what it is waiting for. All three agree on the answer: the position, or LENGTH when there is none. For a plain character or piece of text, INDEX_OF does the same search and answers -1 when absent; the three shapes are for searches with a condition of your own.
FUNCTION FIRST_N(T : STRING) RETURNS INTEGER
    FOR I <- 0 TO LENGTH(T)
        IF T[I] == 'N' THEN
            RETURN I
        ENDIF
    NEXT I
    RETURN LENGTH(T)
ENDFUNCTION
DECLARE T : STRING
T <- "GATNACA"
DECLARE Found, J : INTEGER
Found <- LENGTH(T)
FOR I <- 0 TO LENGTH(T)
    IF T[I] == 'N' THEN
        Found <- I
        BREAK
    ENDIF
NEXT I
J <- 0
WHILE J < LENGTH(T) AND T[J] != 'N'
    J <- J + 1
ENDWHILE
OUTPUT FIRST_N(T), " ", Found, " ", J, " ", INDEX_OF(T, 'N')
prints 3 3 3 3
Return two values: use a recordA FUNCTION hands back one value. When the answer has two parts, name a TYPE for the pair and return that; the reader sees what each part means instead of guessing which is which.
TYPE Extremes
    DECLARE Low : INTEGER
    DECLARE High : INTEGER
ENDTYPE
FUNCTION RANGE_OF(Xs : LIST OF INTEGER) RETURNS Extremes
    REQUIRE LENGTH(Xs) > 0
    DECLARE E : Extremes
    E.Low <- MIN(Xs)
    E.High <- MAX(Xs)
    RETURN E
ENDFUNCTION
DECLARE R : Extremes
R <- RANGE_OF([7, 2, 9, 4])
OUTPUT R.Low, " to ", R.High
prints 2 to 9
Memoize with a PROCEDURE and two BYREF parametersA FUNCTION is pure, so it cannot take a table BYREF. Memoized recursion is therefore a PROCEDURE: the table travels BYREF, and the answer comes back BYREF too. It is the heaviest idiom in the notation; it is also the one that makes "the table is shared" visible.
PROCEDURE FIB(N : INTEGER, BYREF Memo : HASHMAP OF INTEGER : INTEGER, BYREF Answer : INTEGER)
    IF N < 2 THEN
        Answer <- N
        RETURN
    ENDIF
    IF N IN Memo THEN
        Answer <- Memo[N]
        RETURN
    ENDIF
    DECLARE A, B : INTEGER
    CALL FIB(N - 1, Memo, A)
    CALL FIB(N - 2, Memo, B)
    Memo[N] <- A + B
    Answer <- A + B
ENDPROCEDURE
DECLARE Table : HASHMAP OF INTEGER : INTEGER
DECLARE F : INTEGER
CALL FIB(40, Table, F)
OUTPUT F
prints 102334155
Split text: SPLIT, and what it does by handSPLIT(S, " ") cuts a text at every space and keeps empty pieces, so two spaces give an empty word; drop those yourself when you want words. Writing the walk by hand once is still worth it: grow a word until a separator, APPEND it, start a new one, and append the last word after the loop; forgetting that last step is the classic mistake, and the trace shows it.
FUNCTION WORDS_OF(S : STRING) RETURNS LIST OF STRING
    DECLARE Out : LIST OF STRING
    DECLARE W : STRING
    W <- ""
    FOR EACH C IN S
        IF C == ' ' THEN
            IF LENGTH(W) > 0 THEN
                APPEND(Out, W)
            ENDIF
            W <- ""
        ELSE
            W <- W & C
        ENDIF
    NEXT C
    IF LENGTH(W) > 0 THEN
        APPEND(Out, W)
    ENDIF
    RETURN Out
ENDFUNCTION
OUTPUT WORDS_OF("the  cat sat"), " ", SPLIT("the  cat sat", " "), " ", JOIN(WORDS_OF("the  cat sat"), "_")
prints ["the", "cat", "sat"] ["the", "", "cat", "sat"] the_cat_sat
A stack from a LISTPush with APPEND; the top is the last position; pop with REMOVE of that position. A LIST already is a stack, so there is no stack type.
DECLARE Stack : LIST OF CHAR
APPEND(Stack, '(')
APPEND(Stack, '[')
DECLARE Top : CHAR
Top <- Stack[LENGTH(Stack) - 1]
REMOVE(Stack, LENGTH(Stack) - 1)
OUTPUT Top, " ", LENGTH(Stack)
prints [ 1
A queue from a LISTJoin at the end with APPEND; leave from the front with REMOVE(Q, 0). REMOVE at the front shifts every later value, so this costs LENGTH steps per leave; a lesson on cost measures exactly that.
DECLARE Q : LIST OF STRING
APPEND(Q, "read_1")
APPEND(Q, "read_2")
APPEND(Q, "read_3")
DECLARE Next_Up : STRING
Next_Up <- Q[0]
REMOVE(Q, 0)
OUTPUT Next_Up, " ", Q
prints read_1 ["read_2", "read_3"]
Count with a HASHMAPTest IN before reading a key: a missing key stops the run. "If seen, add one; else start at one" is the shape every tally takes, and the checker recognizes it.
DECLARE Tally : HASHMAP OF CHAR : INTEGER
FOR EACH B IN "GATTACA"
    IF B IN Tally THEN
        Tally[B] <- Tally[B] + 1
    ELSE
        Tally[B] <- 1
    ENDIF
NEXT B
OUTPUT Tally
prints {'A': 3, 'C': 1, 'G': 1, 'T': 2}
Swap through BYREFThe one place BYREF is the natural tool: a procedure that changes two of the caller's variables and has no answer of its own.
PROCEDURE SWAP(BYREF X : INTEGER, BYREF Y : INTEGER)
    DECLARE Temp : INTEGER
    Temp <- X
    X <- Y
    Y <- Temp
ENDPROCEDURE
DECLARE A, B : INTEGER
A <- 1
B <- 2
CALL SWAP(A, B)
OUTPUT A, " ", B
prints 2 1
ARRAY for fixed shapes, LIST for everything a subroutine takesAn ARRAY type always states its lengths, so a parameter of ARRAY type works for one size only. Anything a FUNCTION or PROCEDURE takes is a LIST; an ARRAY is for a table whose shape is part of the problem, such as a 3×3 grid.
FUNCTION TOTAL(Xs : LIST OF INTEGER) RETURNS INTEGER
    DECLARE S : INTEGER
    S <- 0
    FOR EACH X IN Xs
        S <- S + X
    NEXT X
    RETURN S
ENDFUNCTION
DECLARE Grid : ARRAY[2, 2] OF INTEGER
Grid[0, 0] <- 1
Grid[0, 1] <- 2
Grid[1, 0] <- 3
Grid[1, 1] <- 4
OUTPUT TOTAL([1, 2, 3, 4]), " ", ROWS(Grid) * COLUMNS(Grid)
prints 10 4

What stops a run

StopWhen
Position does not existan index outside [0, LENGTH), a SLICE outside [0, LENGTH], or a row or column outside an ARRAY
No value yetreading a name, a position, or a field before anything is stored in it, or a FOR counter after its loop
Missing keyreading H[K] when K is not a key of H; test with IN first
Division by zerodividing by 0 with /, DIV, or MOD (with USE IEEE, a FLOAT / gives an infinity or NaN instead; DIV and MOD still stop), or 0.0 raised to a negative power
No answera whole number to a negative power, a negative FLOAT to a power that is not whole, SQRT of a negative, LOG of a non-positive, LOG1P at or below -1, ASIN or ACOS outside [-1, 1], CLAMP with its low end above its high end, a shift by a negative count, FILL with a negative count, RANDINT from an empty range, MIN or MAX or MEAN_OF of an empty collection, text TO_INTEGER or TO_FLOAT cannot read (the FLOAT cases give NaN or an infinity instead when the program says USE IEEE)
Wrong lengtha store, an argument, or a RETURN that gives an ARRAY a LIST or ARRAY of another length than it was declared with (an error before the run when both lengths are written as numbers), or DOT of two collections of different lengths
STEP 0a FOR whose STEP is 0 when the loop starts (STEP 0 written as a number is an error before the run)
Too largea whole number beyond ±9,007,199,254,740,991 (a product or partial sum inside SUM_OF or DOT too), a result outside its sized type (an INT8 past 127, a FOR counter declared INT8 past 127), a conversion such as INT32(X) that does not fit, a FLOAT past about 1.8 × 10^308 or a FLOAT32 past about 3.4 × 10^38 (unless the program says USE IEEE)
Too much to holda collection of more than 2,000,000 values (an ARRAY, FILL, or a range FOR EACH or a quantifier walks), or a text of more than 10,000,000 characters
InputINPUT with nothing left, or input that does not convert (a FLOAT is read only from decimal text, such as 2.5 or -1e3)
A value from outsidea call from outside the program (the Run tab's call) whose argument does not fit its parameter: the wrong type, an ARRAY of another length, or NaN or an infinity for a FLOAT without USE IEEE
A broken promisea REQUIRE, ENSURE, INVARIANT, DECREASES, or ASSERT that is FALSE
No end in sightmore steps than the lab allows (20,000 here); the lab names the loop and says whether its condition has stopped changing. The positions FORALL, EXISTS, SUM and sets written by rule visit count too: 100 for every step allowed (2,000,000 here)
Too deeprecursion more than 400 calls deep, or fewer when the call sits inside many nested blocks and the lab cannot follow it that far
A data racein a PARALLEL FOR, one pass writes a location (a shared name, or a slot of a list) that another pass reads or writes; the message names the location and both passes

Limits

What the lab will read, run and record. Each limit is far above what the course's programs need.

LimitWhat happens
200 levels of nestinga line inside more than 200 blocks, or brackets, calls or types nested more than 200 deep, is the error too-deep before the run: give the inner part a FUNCTION of its own
400 operands in a chaina chain of more than 400 operands joined by +, AND, & or the like (1 + 1 + ... + 1) is the error too-deep; so are brackets that each hold a long chain, once they build a value more than 400 levels deep
2,000,000 valuesthe most one collection may hold; past it the run stops (Too much to hold)
10,000,000 charactersthe longest text a run holds; past it the run stops (Too much to hold)
20,000 stepsthe steps a run may take here, and 100 positions visited by quantifiers for each (No end in sight)
400 calls deepthe deepest recursion a run follows (Too deep)
10,000,000 recorded valueswhat the pictures of a recorded run may copy; past it the trace ends with a step that says so and the run goes on without recording, its output and how it ends shown at the end
3 seconds to prove, 3 per routine to trythe Prove tab gives the prover 3 seconds for each routine, then tries generated inputs on each routine for up to 3 seconds; what each found in that time stands, and an obligation the prover could not finish stays open. When the time ran out the tab says so, and its time limit can be raised: a slow or busy device proves less in 3 seconds, never anything wrong

Names you cannot use

Names ignore case, so Next, step, and Keys are refused just as NEXT, STEP, and KEYS would be. Pick a longer word: Neighbor, Generation, KeyList.

WordReserved asMeans
ANDkeywordTRUE when both sides are
ARRAYkeywordA fixed number of values of one type, declared by length
ASSERTkeywordWhat is true at this line
BOOLkeywordTRUE or FALSE
BOOLEANkeywordAnother spelling of BOOL
BREAKkeywordLeaves the innermost loop at once
BYREFkeywordMarks a parameter the procedure may change in the caller
BYVALkeywordStates the default explicitly
CALLkeywordRuns a PROCEDURE on a line of its own
CASEkeywordCASE OF X
CHARkeywordExactly one character, in single quotes
CONSTANTkeywordNames a value that never changes
CONTINUEkeywordSkips the rest of this pass and starts the next
DECLAREkeywordCreates a name and fixes its type, with or without a starting value
DECREASESkeywordA whole number that shrinks every pass (or every recursive call) and never goes below 0
DEFINEkeywordMakes one fixed set of a named set type
DIVkeywordInteger division, rounded down (toward minus infinity)
ELSEkeywordThe body that runs when no condition above was TRUE
ELSEIFkeywordOne word
ENDCASEkeywordCloses a CASE
ENDFUNCTIONkeywordCloses a FUNCTION
ENDIFkeywordCloses an IF
ENDPROCEDUREkeywordCloses a PROCEDURE
ENDTYPEkeywordCloses a TYPE block
ENDWHILEkeywordCloses a WHILE
ENSUREkeywordWhat the subroutine promises about its answer, RESULT
EXISTSkeywordEXISTS K IN [0, N)
FALSEkeywordThe BOOL value for no
FLOATkeywordA number with a fractional part, in IEEE 754 double precision
FLOAT32keywordA FLOAT in single precision (about 7 significant digits)
FLOAT64keywordAnother name for FLOAT
FORkeywordA counted loop
FORALLkeywordFORALL K IN [0, N)
FUNCTIONkeywordA subroutine that hands back one value
HASHMAPkeywordValues reached by key
IFkeywordRuns its body when the condition is TRUE
INkeywordMembership
INPUTkeywordFills one variable from outside the program
INT16keywordA whole number from -32,768 to 32,767
INT32keywordA whole number from -2,147,483,648 to 2,147,483,647
INT64keywordA 64-bit whole number (held exactly in this lab to ±9,007,199,254,740,991)
INT8keywordA whole number from -128 to 127
INTEGERkeywordA whole number
INVARIANTkeywordWhat is true at the top of every pass of a loop
LISTkeywordAny number of values of one type, in order
MODkeywordThe remainder after DIV, with the sign of the divisor
NEXTkeywordCloses a FOR, naming its counter
NOTkeywordTRUE when its operand is FALSE
OFkeywordJoins a collection to its element type
ORkeywordTRUE when either side is (or both)
OTHERWISEkeywordThe arm of a CASE that runs when nothing else matched
OUTPUTkeywordShows any number of values, listed with commas and printed one after another with nothing between
PARALLELkeywordPARALLEL FOR I <- 0 TO N
PROCEDUREkeywordA subroutine that does something and returns nothing
REPEATkeywordRuns the body, then tests
REQUIREkeywordWhat every caller promises about the arguments
RETURNkeywordHands back the answer and ends the subroutine at once
RETURNSkeywordStates the type of a FUNCTION's answer
SETkeywordDistinct values in no order
STEPkeywordThe increment of a FOR counter
STRINGkeywordAny number of characters, in double quotes
THENkeywordEnds the condition of an IF
TOkeywordThe stop value of a FOR, which the counter never reaches (half-open), or the upper end of a CASE range
TRUEkeywordThe BOOL value for yes
TYPEkeywordDefines a record (TYPE … ENDTYPE with one DECLARE per field) or names a set type (TYPE BaseSet = SET OF CHAR)
UINT16keywordA whole number from 0 to 65,535
UINT32keywordA whole number from 0 to 4,294,967,295
UINT64keywordA 64-bit whole number of 0 or more (held exactly in this lab to 9,007,199,254,740,991)
UINT8keywordA whole number from 0 to 255
UNTILkeywordCloses a REPEAT with the condition that stops it
USEkeywordBrings routines from the library into the program
WHILEkeywordTests before each pass
EACHcontextual keywordFOR EACH X IN C visits every value of a collection
OLDcontextual keywordInside an ENSURE, OLD(X) is a BYREF parameter's value when the call began
RESULTcontextual keywordInside an ENSURE, the value the function returned
SUMcontextual keywordSUM K IN [0, N)
ABSbuilt-in functionThe size of a number, ignoring its sign
ADDbuilt-in functionMakes V a member of the SET S
APPENDbuilt-in functionAdds V to the end of the LIST L
ATAN2built-in functionThe angle in radians of the point (X, Y) from the positive x axis, in [-PI(), PI()]
CEILbuilt-in functionThe smallest whole number at or above X
CHOOSEbuilt-in functionThe binomial coefficient
CHRbuilt-in functionThe CHAR Unicode numbers N
COLUMNSbuilt-in functionThe second length of a two-dimensional ARRAY
COSbuilt-in functionThe cosine of X radians, as a FLOAT
DELETEbuilt-in functionRemoves the key K from a HASHMAP, or the member K from a SET
DOTbuilt-in functionThe dot product of two LISTs or ARRAYs of numbers of the same length
EXPbuilt-in functione raised to the power X, as a FLOAT
FILLbuilt-in functionA new LIST of N copies of the value V
FLOORbuilt-in functionThe largest whole number at or below X
INDEX_OFbuilt-in functionThe first position at which Piece (a STRING or CHAR) occurs in the STRING X, or at which the value Piece occurs in the LIST X
INSERTbuilt-in functionPuts V at position I of the LIST L, moving every later value one place along
INTbuilt-in functionThe whole-number part of a FLOAT, dropping the fraction toward zero
JOINbuilt-in functionOne STRING made of the values of the LIST OF STRING L with Sep between each pair
KEYSbuilt-in functionThe keys of a HASHMAP as a LIST, smallest first
LENGTHbuilt-in functionHow many characters a STRING holds, or how many values a LIST, one-dimensional ARRAY, SET, or HASHMAP holds
LOGbuilt-in functionThe natural logarithm, as a FLOAT
LOG10built-in functionThe base-10 logarithm, as a FLOAT
LOG2built-in functionThe base-2 logarithm, as a FLOAT
LOWERbuilt-in functionA STRING or CHAR with every letter in small letters
MAXbuilt-in functionThe largest of two or more numbers, or of the values in one LIST
MEAN_OFbuilt-in functionThe arithmetic mean of the numbers in a LIST or ARRAY, as a FLOAT
MEDIAN_OFbuilt-in functionThe middle value of the numbers in a LIST or ARRAY, as a FLOAT
MINbuilt-in functionThe smallest of two or more numbers, or of the values in one LIST
NORM_OFbuilt-in functionThe Euclidean length of a LIST or ARRAY of numbers, SQRT(DOT(A, A)), as a FLOAT
ORDbuilt-in functionThe number Unicode gives a CHAR
PIbuilt-in functionThe number pi, 3
RANDbuilt-in functionA random FLOAT between 0 and X, never X itself
RANDINTbuilt-in functionA random INTEGER in [A, B)
RANDNbuilt-in functionA random FLOAT from the standard normal distribution (mean 0, standard deviation 1)
REMOVEbuilt-in functionTakes the value at position I out of the LIST L, moving every later value one place back
REPLACEbuilt-in functionThe STRING S with every occurrence of A replaced by B, left to right, without overlapping
ROUNDbuilt-in functionThe nearest whole number, with halves rounded away from zero
ROWSbuilt-in functionThe first length of a two-dimensional ARRAY
SINbuilt-in functionThe sine of X radians, as a FLOAT
SLICEbuilt-in functionThe characters of a STRING, or the values of a LIST, at positions [A, B), as a new value of the same type
SORTbuilt-in functionPuts the values of the LIST L in order, smallest first
SORTEDbuilt-in functionThe values of a LIST or SET as a new LIST, smallest first
SPLITbuilt-in functionThe pieces of the STRING S between occurrences of the STRING or CHAR Sep, as a LIST OF STRING
SQRTbuilt-in functionThe square root, as a FLOAT
STDEV_OFbuilt-in functionThe sample standard deviation, SQRT(VARIANCE_OF(L)), as a FLOAT
SUM_OFbuilt-in functionThe sum of the numbers in a LIST or ARRAY
TANbuilt-in functionThe tangent of X radians, as a FLOAT
TO_FLOATbuilt-in functionThe FLOAT a STRING of decimal digits spells ("2
TO_INTEGERbuilt-in functionThe INTEGER a STRING of digits spells, or the digit a CHAR is
TO_STRINGbuilt-in functionAny value written as a STRING, the way OUTPUT would print it
UPPERbuilt-in functionA STRING or CHAR with every letter in capitals
VARIANCE_OFbuilt-in functionThe sample variance (dividing by N - 1) of the numbers in a LIST or ARRAY, as a FLOAT

speco

Specifications as a document of their own, in mathematical notation. Programming+ weaves them into the pseudocode and the prover checks every claim for every input it can reason about.

Symbols

Type either column; the pane accepts the math and the notation's ASCII spelling alike.

MathMeaningNotation
∀for every position in a range: ∀ k ∈ [0, n) : P(k)FORALL
∃for some position in a rangeEXISTS
Σthe sum over a range: Σ k ∈ [0, n) : Q[k]SUM
∈membership, or the range a bound variable runs overIN
∧bothAND
∨eitherOR
¬notNOT
≤at most<=
≥at least>=
≠different!=
=equal (a claim, never an assignment)==
|X|the size of a text, list, set, or set written by ruleLENGTH(X)
resultthe value the function returnsRESULT
X₀a BYREF parameter's value when the call beganOLD(X)

Lines

FormMeaningExample
SPEC <name>(<params>)Opens the claims about one FUNCTION or PROCEDURE in the pseudocode pane. The parameter names are documentation; the pseudocode header is authoritative.
SPEC COUNT_BASE(B, T)
    ENSURE result = |{ K ∈ [0, |T|) : T[K] = B }|
REQUIRE <claim>What every caller promises about the arguments.
SPEC GC_FRACTION(T)
    REQUIRE |T| ≥ 1
ENSURE <claim>What the routine promises about result (and about BYREF parameters, with X₀ for the starting value).
SPEC MAX_OF(A, B)
    ENSURE result ≥ A ∧ result ≥ B
LOOP FOR <i> / LOOP FOR EACH <x> / LOOP WHILE / LOOP REPEAT / LOOP <n>Names the loop the lines under it describe: by its counter, by its kind, or by its position among the routine's loops.
SPEC COUNT_BASE(B, T)
    LOOP FOR I
        INVARIANT Total = |{ K ∈ [0, I) : T[K] = B }|
INVARIANT <claim>True at the top of every pass. Checked before the first pass and after every pass. When the loop ends normally it is checked once more, except in FOR EACH for a claim that names the loop's own variable, which is about the value a pass is about to visit; in a FOR, that last check sees the counter at the value that ended the loop.
SPEC CONTAINS_SORTED(L, X)
    LOOP WHILE
        INVARIANT 0 ≤ Lo ∧ Lo ≤ Hi ∧ Hi ≤ |L|
DECREASES <whole number>A measure that is at least 0 whenever the loop continues and shrinks every pass: why it ends. Under SPEC directly, it measures a recursive routine.
SPEC CONTAINS_SORTED(L, X)
    LOOP WHILE
        DECREASES Hi - Lo
{ k ∈ [lo, hi) : <condition> }A set written by rule; |…| around it counts its members.
SPEC COUNT_GC(T)
    ENSURE result = |{ k ∈ [0, |T|) : T[k] = 'G' ∨ T[k] = 'C' }|

What the prover reports

VerdictMeaning
provedon every path the checker examined, the claim follows from what is known; no input can break it
broken by a runthe checker could not prove it, and a generated input violates it; Programming+ shows the smallest it found
opennot proved and not broken by any input tried: usually a loop needs an invariant, or the claim needs reasoning the checker lacks (products of unknowns, facts about whole sets, exact FLOAT values)

x86-64

Intel syntax, destination first, the course's instruction subset. Every program also gets a 512-byte stack; an address outside every region is a page fault.

Registers

A 32-bit write zeroes the upper half; 8- and 16-bit writes leave the rest alone.

64-bit nameRole (System V convention)Narrower names
raxaccumulator; the answer of a procedure and the system-call numberrax, eax, ax, al / ah
rcx4th argument; loop counter by conventionrcx, ecx, cx, cl / ch
rdx3rd argument; high half of a 128-bit product or dividendrdx, edx, dx, dl / dh
rbxcallee-saved general registerrbx, ebx, bx, bl / bh
rspstack pointer: the address of the top of the stackrsp, esp, sp, spl
rbpframe pointer (callee-saved)rbp, ebp, bp, bpl
rsi2nd argument; source pointer by conventionrsi, esi, si, sil
rdi1st argument; destination pointer by conventionrdi, edi, di, dil
r85th argumentr8, r8d, r8w, r8b
r96th argumentr9, r9d, r9w, r9b
r10scratchr10, r10d, r10w, r10b
r11scratchr11, r11d, r11w, r11b
r12callee-savedr12, r12d, r12w, r12b
r13callee-savedr13, r13d, r13w, r13b
r14callee-savedr14, r14d, r14w, r14b
r15callee-savedr15, r15d, r15w, r15b

Instructions

MnemonicWhat it doesOperands
movcopy the second operand into the first2 operands
movzxcopy a smaller value into a larger register and fill the rest with zeros2 operands
movsxcopy a smaller value into a larger register and repeat its sign bit across the rest2 operands
movsxdcopy a 32-bit value into a 64-bit register, repeating its sign bit across the top half2 operands
leawork out an address and store the address itself, reading no memory at all2 operands
addadd the second operand into the first2 operands
subsubtract the second operand from the first2 operands
adcadd the second operand and the carry flag into the first2 operands
sbbsubtract the second operand and the carry flag from the first2 operands
incadd one, leaving the carry flag alone1 operand
decsubtract one, leaving the carry flag alone1 operand
imulmultiply, reading both values as signed1,3 operands
mulmultiply rax by the operand, unsigned, with the double-width answer landing in rdx:rax1 operand
divdivide rdx:rax by the operand, unsigned: quotient to rax, remainder to rdx1 operand
idivdivide rdx:rax by the operand, signed: quotient to rax, remainder to rdx1 operand
cqofill rdx with copies of the sign bit of rax, ready for a signed division0 operands
cdqfill edx with copies of the sign bit of eax, ready for a 32-bit signed division0 operands
cdqewiden eax to rax, repeating its sign bit0 operands
andkeep only the bits set in both operands2 operands
orset every bit that is set in either operand2 operands
xorset every bit that is set in exactly one operand; with the same register twice, this clears it2 operands
shlshift bits left, which doubles the value once per place; the last bit pushed out lands in CF1,2 operands
salanother name for shl1,2 operands
shrshift bits right, filling with zeros; the last bit pushed out lands in CF1,2 operands
sarshift bits right, repeating the sign bit, which halves a signed value1,2 operands
rolrotate bits left: whatever leaves the top comes back in at the bottom1,2 operands
rorrotate bits right: whatever leaves the bottom comes back in at the top1,2 operands
cmpsubtract, set the flags, and throw the answer away2 operands
testAND, set the flags, and throw the answer away2 operands
btcopy one chosen bit into the carry flag2 operands
stcset the carry flag0 operands
clcclear the carry flag0 operands
cmcflip the carry flag0 operands
pushmove the stack pointer down by eight and store a value there1 operand
popload a value from the stack pointer and move the pointer up by eight1 operand
leaveundo a stack frame: rsp takes rbp’s value, then rbp is popped0 operands
jmpcarry on from a different place, always1 operand
nopdo nothing0,3 operands
rethand the answer back to whoever called0 operands
callremember where to come back to, then carry on somewhere else1 operand
syscallask the operating system to do something: rax says what, rdi, rsi, and rdx carry the details0 operands
negreplace a value with zero minus that value1 operand
notflip every bit, leaving the flags alone1 operand
xchgswap two values2 operands
popcntcount how many bits are set2 operands
tzcntcount the zero bits below the lowest set bit, which gives its position2 operands
lzcntcount the zero bits above the highest set bit2 operands
bsffind the position of the lowest set bit; leaves the destination alone when there is none2 operands
bsrfind the position of the highest set bit; leaves the destination alone when there is none2 operands
movdqucopy sixteen bytes, from any address2 operands
movdqacopy sixteen bytes, from an address that must be a multiple of sixteen2 operands
movdcopy four bytes between a vector register and an ordinary one2 operands
movqcopy eight bytes between a vector register and an ordinary one2 operands
pcmpeqbcompare sixteen pairs of bytes at once, filling each lane with ones where they matched2 operands
pmovmskbcollect the top bit of each of sixteen lanes into a sixteen-bit number2 operands
pandbitwise AND across sixteen bytes2 operands
porbitwise OR across sixteen bytes2 operands
pxorbitwise exclusive OR across sixteen bytes; with the same register twice, this clears it2 operands
psubbsubtract sixteen pairs of bytes at once, each lane on its own2 operands
paddbadd sixteen pairs of bytes at once, each lane on its own2 operands
andnAND the third operand with the complement of the second: keep the bits set in one and clear in the other3 operands
mulxmultiply rdx (or edx) by the third operand, unsigned, without touching the flags: the high half lands in the first operand, the low half in the second3 operands
shlxshift the second operand left by the count in the third, into the first, leaving the flags alone3 operands
shrxshift the second operand right by the count in the third, into the first, leaving the flags alone3 operands
sarxshift the second operand right, keeping its sign, by the count in the third, into the first, leaving the flags alone3 operands
bzhicopy the second operand with every bit from the position in the third upward cleared3 operands
rorxrotate the second operand right by a constant, into the first, leaving the flags alone3 operands
bextrtake a field of bits out of the second operand: the third holds the start position in its low byte and the length in the next3 operands
blsrclear the lowest set bit2 operands
blsikeep only the lowest set bit2 operands
blsmska mask of ones from bit 0 up to and including the lowest set bit2 operands
xaddexchange and add: the first operand becomes the sum, the second receives what the first held (with lock, the atomic increment behind a reference count)2 operands
cmpxchgcompare the accumulator (rax, eax, ax, or al) with the first operand: when they are equal, store the second operand there and set ZF; otherwise load the first into the accumulator and clear ZF2 operands
btscopy a bit into CF, then set it2 operands
btrcopy a bit into CF, then clear it2 operands
btccopy a bit into CF, then flip it2 operands
bswapreverse the order of the bytes: little-endian to big-endian and back1 operand
cwdwiden ax into dx:ax, repeating its sign bit0 operands
cwdewiden ax to eax, repeating its sign bit0 operands
cbwwiden al to ax, repeating its sign bit0 operands
ud2an instruction that is defined to be undefined: the compiler plants it where a path must never be taken, so reaching it is a crash0 operands
vzeroupperclear the upper halves of the 256-bit registers; with only the 128-bit halves modeled, nothing changes0 operands
vmovdquthe AVX spelling of movdqu2 operands
vmovdqathe AVX spelling of movdqa2 operands
vmovupscopy sixteen bytes (four floats, to the compiler) from any address; the same bytes move either way2 operands
vmovapscopy sixteen bytes (four floats, to the compiler) from an address that is a multiple of sixteen2 operands
vmovdthe AVX spelling of movd2 operands
vmovqthe AVX spelling of movq2 operands
vpmovmskbthe AVX spelling of pmovmskb2 operands
vpxorexclusive OR of the second and third operands, sixteen bytes at once, into the first3 operands
vxorpsexclusive OR of sixteen bytes into the first operand; with one register three times, this clears it3 operands
vporOR of the second and third operands, sixteen bytes at once, into the first3 operands
vpandAND of the second and third operands, sixteen bytes at once, into the first3 operands
vpaddbadd the second and third operands lane by lane, sixteen bytes at once, into the first3 operands
vpsubbsubtract the third operand from the second lane by lane, sixteen bytes at once, into the first3 operands
vpcmpeqbcompare the second and third operands lane by lane, filling each lane of the first with ones where they matched3 operands
vpinsrbcopy the second operand into the first with one byte lane (the last operand says which) replaced by the third4 operands
vpinsrwcopy the second operand into the first with one word lane (the last operand says which) replaced by the third4 operands
vpinsrdcopy the second operand into the first with one dword lane (the last operand says which) replaced by the third4 operands
vpinsrqcopy the second operand into the first with one qword lane (the last operand says which) replaced by the third4 operands
vpextrbcopy one byte lane (the last operand says which) of the second operand into the first3 operands
vpextrwcopy one word lane (the last operand says which) of the second operand into the first3 operands
vpextrdcopy one dword lane (the last operand says which) of the second operand into the first3 operands
vpextrqcopy one qword lane (the last operand says which) of the second operand into the first3 operands
vpminubthe smaller of each pair of bytes, unsigned3 operands
vpmaxubthe larger of each pair of bytes, unsigned3 operands
vpminudthe smaller of each pair of dwords, unsigned3 operands
vpmaxudthe larger of each pair of dwords, unsigned3 operands
vpcmpeqdcompare four pairs of dwords, filling each lane with ones where they matched3 operands
vpcmpeqwcompare eight pairs of words, filling each lane with ones where they matched3 operands
vpcmpeqqcompare two pairs of qwords, filling each lane with ones where they matched3 operands
vpcmpgtbcompare sixteen pairs of signed bytes, filling each lane with ones where the first was greater3 operands
vpcmpgtwcompare eight pairs of signed words, filling each lane with ones where the first was greater3 operands
vpcmpgtdcompare four pairs of signed dwords, filling each lane with ones where the first was greater3 operands
vpcmpgtqcompare two pairs of signed qwords, filling each lane with ones where the first was greater3 operands
vpadddadd four pairs of dwords3 operands
vpsubdsubtract four pairs of dwords3 operands
vpaddwadd eight pairs of words3 operands
vpsubusbsubtract sixteen pairs of bytes, stopping at zero instead of wrapping3 operands
vpandnAND the third operand with the complement of the second, sixteen bytes at once3 operands
vpsrldshift each dword right by a constant3 operands
vpslldshift each dword left by a constant3 operands
vpsrlwshift each word right by a constant3 operands
vpsllwshift each word left by a constant3 operands
vpsrlqshift each qword right by a constant3 operands
vpsllqshift each qword left by a constant3 operands
vpshufdrearrange the four dwords of the second operand: each pair of bits of the constant picks the source dword for one lane3 operands
vpshufbrearrange the bytes of the second operand: each byte of the third names the source lane for that position, or clears it when its top bit is set3 operands
vpbroadcastdcopy one dword into all four lanes2 operands
vpbroadcastbcopy one byte into all sixteen lanes2 operands
addsdadd two doubles, on the low double of an xmm register; its upper eight bytes stay as they were2 operands
vaddsdadd two doubles, on the low double: the second operand's low double with the third's, the result in the first, whose upper eight bytes are copied from the second3 operands
subsdsubtract the second double from the first, on the low double of an xmm register; its upper eight bytes stay as they were2 operands
vsubsdsubtract the second double from the first, on the low double: the second operand's low double with the third's, the result in the first, whose upper eight bytes are copied from the second3 operands
mulsdmultiply two doubles, on the low double of an xmm register; its upper eight bytes stay as they were2 operands
vmulsdmultiply two doubles, on the low double: the second operand's low double with the third's, the result in the first, whose upper eight bytes are copied from the second3 operands
divsddivide the first double by the second (division by zero gives infinity, and 0/0 gives NaN, without stopping the run), on the low double of an xmm register; its upper eight bytes stay as they were2 operands
vdivsddivide the first double by the second (division by zero gives infinity, and 0/0 gives NaN, without stopping the run), on the low double: the second operand's low double with the third's, the result in the first, whose upper eight bytes are copied from the second3 operands
sqrtsdthe square root of a double: the low double of the second operand, into the low double of the first; the first's upper eight bytes stay2 operands
vsqrtsdthe square root of a double: the low double of the third operand, into the low double of the first; the first's upper eight bytes are copied from the second3 operands
movsdcopy one double: from memory into the low eight bytes of an xmm register (clearing the rest), from a register to memory, or between registers (the destination keeps its upper eight bytes)2 operands
vmovsdcopy one double: from memory into the low eight bytes of an xmm register (clearing the rest), from a register to memory, or, with three registers, the third one's double with the second one's upper eight bytes2,3 operands
cvtsi2sdconvert a signed integer (in a register or memory) to a double in the low eight bytes of the first operand; its upper eight bytes stay2 operands
vcvtsi2sdconvert a signed integer (in a register or memory) to a double in the low eight bytes of the first operand; its upper eight bytes are copied from the second3 operands
ucomisdcompare the low doubles of two operands and report the answer in the flags: unordered (a NaN) sets ZF, PF and CF; greater clears all three; less sets CF; equal sets ZF; then use ja, jb, je, or jp to act on it2 operands
vucomisdcompare the low doubles of two operands and report the answer in the flags: unordered (a NaN) sets ZF, PF and CF; greater clears all three; less sets CF; equal sets ZF; then use ja, jb, je, or jp to act on it2 operands
comisdcompare the low doubles of two operands and report the answer in the flags: unordered (a NaN) sets ZF, PF and CF; greater clears all three; less sets CF; equal sets ZF; then use ja, jb, je, or jp to act on it2 operands
vcomisdcompare the low doubles of two operands and report the answer in the flags: unordered (a NaN) sets ZF, PF and CF; greater clears all three; less sets CF; equal sets ZF; then use ja, jb, je, or jp to act on it2 operands
shldshift the first operand left by a count (a constant or cl), filling from the right with the top bits of the second operand, which does not change; CF takes the last bit pushed out. A count of zero changes nothing, flags included3 operands
shrdshift the first operand right by a count (a constant or cl), filling from the left with the bottom bits of the second operand, which does not change; CF takes the last bit pushed out. A count of zero changes nothing, flags included3 operands
movabscopy a full sixty-four-bit constant into a register2 operands
jejump when equal (ZF set)1 operand
cmovecopy the second operand into the first when equal (ZF set), and do nothing otherwise2 operands
setestore 1 when equal (ZF set), otherwise store 01 operand
jzjump when zero (ZF set)1 operand
cmovzcopy the second operand into the first when zero (ZF set), and do nothing otherwise2 operands
setzstore 1 when zero (ZF set), otherwise store 01 operand
jnejump when not equal (ZF clear)1 operand
cmovnecopy the second operand into the first when not equal (ZF clear), and do nothing otherwise2 operands
setnestore 1 when not equal (ZF clear), otherwise store 01 operand
jnzjump when not zero (ZF clear)1 operand
cmovnzcopy the second operand into the first when not zero (ZF clear), and do nothing otherwise2 operands
setnzstore 1 when not zero (ZF clear), otherwise store 01 operand
jbjump when below, unsigned (CF set)1 operand
cmovbcopy the second operand into the first when below, unsigned (CF set), and do nothing otherwise2 operands
setbstore 1 when below, unsigned (CF set), otherwise store 01 operand
jnaejump when below, unsigned (CF set)1 operand
cmovnaecopy the second operand into the first when below, unsigned (CF set), and do nothing otherwise2 operands
setnaestore 1 when below, unsigned (CF set), otherwise store 01 operand
jcjump when carry set1 operand
cmovccopy the second operand into the first when carry set, and do nothing otherwise2 operands
setcstore 1 when carry set, otherwise store 01 operand
jaejump when at or above, unsigned (CF clear)1 operand
cmovaecopy the second operand into the first when at or above, unsigned (CF clear), and do nothing otherwise2 operands
setaestore 1 when at or above, unsigned (CF clear), otherwise store 01 operand
jnbjump when at or above, unsigned (CF clear)1 operand
cmovnbcopy the second operand into the first when at or above, unsigned (CF clear), and do nothing otherwise2 operands
setnbstore 1 when at or above, unsigned (CF clear), otherwise store 01 operand
jncjump when carry clear1 operand
cmovnccopy the second operand into the first when carry clear, and do nothing otherwise2 operands
setncstore 1 when carry clear, otherwise store 01 operand
jbejump when below or equal, unsigned1 operand
cmovbecopy the second operand into the first when below or equal, unsigned, and do nothing otherwise2 operands
setbestore 1 when below or equal, unsigned, otherwise store 01 operand
jnajump when below or equal, unsigned1 operand
cmovnacopy the second operand into the first when below or equal, unsigned, and do nothing otherwise2 operands
setnastore 1 when below or equal, unsigned, otherwise store 01 operand
jajump when above, unsigned1 operand
cmovacopy the second operand into the first when above, unsigned, and do nothing otherwise2 operands
setastore 1 when above, unsigned, otherwise store 01 operand
jnbejump when above, unsigned1 operand
cmovnbecopy the second operand into the first when above, unsigned, and do nothing otherwise2 operands
setnbestore 1 when above, unsigned, otherwise store 01 operand
jljump when less, signed1 operand
cmovlcopy the second operand into the first when less, signed, and do nothing otherwise2 operands
setlstore 1 when less, signed, otherwise store 01 operand
jngejump when less, signed1 operand
cmovngecopy the second operand into the first when less, signed, and do nothing otherwise2 operands
setngestore 1 when less, signed, otherwise store 01 operand
jgejump when greater or equal, signed1 operand
cmovgecopy the second operand into the first when greater or equal, signed, and do nothing otherwise2 operands
setgestore 1 when greater or equal, signed, otherwise store 01 operand
jnljump when greater or equal, signed1 operand
cmovnlcopy the second operand into the first when greater or equal, signed, and do nothing otherwise2 operands
setnlstore 1 when greater or equal, signed, otherwise store 01 operand
jlejump when less or equal, signed1 operand
cmovlecopy the second operand into the first when less or equal, signed, and do nothing otherwise2 operands
setlestore 1 when less or equal, signed, otherwise store 01 operand
jngjump when less or equal, signed1 operand
cmovngcopy the second operand into the first when less or equal, signed, and do nothing otherwise2 operands
setngstore 1 when less or equal, signed, otherwise store 01 operand
jgjump when greater, signed1 operand
cmovgcopy the second operand into the first when greater, signed, and do nothing otherwise2 operands
setgstore 1 when greater, signed, otherwise store 01 operand
jnlejump when greater, signed1 operand
cmovnlecopy the second operand into the first when greater, signed, and do nothing otherwise2 operands
setnlestore 1 when greater, signed, otherwise store 01 operand
jsjump when negative (SF set)1 operand
cmovscopy the second operand into the first when negative (SF set), and do nothing otherwise2 operands
setsstore 1 when negative (SF set), otherwise store 01 operand
jnsjump when not negative (SF clear)1 operand
cmovnscopy the second operand into the first when not negative (SF clear), and do nothing otherwise2 operands
setnsstore 1 when not negative (SF clear), otherwise store 01 operand
jojump when overflowed (OF set)1 operand
cmovocopy the second operand into the first when overflowed (OF set), and do nothing otherwise2 operands
setostore 1 when overflowed (OF set), otherwise store 01 operand
jnojump when did not overflow (OF clear)1 operand
cmovnocopy the second operand into the first when did not overflow (OF clear), and do nothing otherwise2 operands
setnostore 1 when did not overflow (OF clear), otherwise store 01 operand
jpjump when parity even (PF set); after a floating-point compare, unordered: one side was NaN1 operand
cmovpcopy the second operand into the first when parity even (PF set); after a floating-point compare, unordered: one side was NaN, and do nothing otherwise2 operands
setpstore 1 when parity even (PF set); after a floating-point compare, unordered: one side was NaN, otherwise store 01 operand
jpejump when parity even (PF set); after a floating-point compare, unordered: one side was NaN1 operand
cmovpecopy the second operand into the first when parity even (PF set); after a floating-point compare, unordered: one side was NaN, and do nothing otherwise2 operands
setpestore 1 when parity even (PF set); after a floating-point compare, unordered: one side was NaN, otherwise store 01 operand
jnpjump when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN1 operand
cmovnpcopy the second operand into the first when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN, and do nothing otherwise2 operands
setnpstore 1 when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN, otherwise store 01 operand
jpojump when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN1 operand
cmovpocopy the second operand into the first when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN, and do nothing otherwise2 operands
setpostore 1 when parity odd (PF clear); after a floating-point compare, ordered: neither side was NaN, otherwise store 01 operand

Condition codes

Append to j, set, or cmov: je, setg, cmovae.

CodeMeaning
eequal (ZF set)
zzero (ZF set)
nenot equal (ZF clear)
nznot zero (ZF clear)
bbelow, unsigned (CF set)
naebelow, unsigned (CF set)
ccarry set
aeat or above, unsigned (CF clear)
nbat or above, unsigned (CF clear)
nccarry clear
bebelow or equal, unsigned
nabelow or equal, unsigned
aabove, unsigned
nbeabove, unsigned
lless, signed
ngeless, signed
gegreater or equal, signed
nlgreater or equal, signed
leless or equal, signed
ngless or equal, signed
ggreater, signed
nlegreater, signed
snegative (SF set)
nsnot negative (SF clear)
ooverflowed (OF set)
nodid not overflow (OF clear)
pparity even (PF set); after a floating-point compare, unordered: one side was NaN
peparity even (PF set); after a floating-point compare, unordered: one side was NaN
npparity odd (PF clear); after a floating-point compare, ordered: neither side was NaN
poparity odd (PF clear); after a floating-point compare, ordered: neither side was NaN

Flags

FlagSet when
ZFthe result was zero
SFthe result's top bit is set (negative when read as signed)
CFan unsigned carry out, or borrow in
OFsigned overflow: the sign of the result is wrong
PFthe low byte of the result has an even number of one bits; after ucomisd, set when either side was NaN

System calls

Number in rax, arguments in rdi, rsi, rdx; the answer returns in rax; rcx and r11 are clobbered.

raxCall
0read
1write
39getpid
60exit
231exit_group

The setup box

LineMeaning
rdi = 0x1000any register, at any width: rdi, edi, di, dil
dl = 'A'a character is its ASCII code
memory 0x1000 "GATTACA"text, one byte per letter; \n and \t work
memory 0x2000 bytes 1 2 3 255individual bytes
memory 0x3000 qwords 3 11 148-byte values, little-endian
memory 0x4000 zero 64a run of zeros, for output
stdin "what read returns"input for the read system call
flags CF ZFflags that start set

Machine presets

PresetDescriptionL1d
teachingcaches small enough to watch fill and overflow on the course’s dataL1d 256 B, 16-byte lines, 2-way, 4 cycles
realisticcache sizes and latencies shaped like a desktop coreL1d 32768 B, 64-byte lines, 8-way, 4 cycles
idealevery memory access in 1 cycle and no fetch stalls, to isolate dependencies and portsL1d 1048576 B, 64-byte lines, 16-way, 1 cycles