Unit 15 — Assembly Language

Lesson 1 — The accumulator and memory

Division: Intermediate and above.

A computer's processor understands only very simple instructions: "fetch this number", "add that number", "store the result here". Assembly language writes those instructions as short words, one per line. Real processors each have their own assembly language, so ACSL made up a small one of its own, with the ideas they all share.

An ACSL assembly program works with two things:

• the accumulator, ACC: one special place that holds one number, like the robot's pocket. Every calculation happens in ACC, and ACC starts at 0.

• memory: boxes that each hold one number, called locations. Each location has a name, its label, such as SUM, A or TEMP.

The program runs from the first line downwards, one line at a time, until it reaches END.

The shape of a line

Every line has up to three parts, called fields:

LABEL OPCODE LOC

• LABEL is optional. It names the line (and the location a DC line makes). A label starts with a letter and may go on with letters and digits. Labels are case-sensitive: Sum and SUM are different labels.

• OPCODE says what to do. Opcodes are always in capitals, and an opcode can never be used as a label.

• LOC says which location the instruction uses.

Programs are printed in columns, with the labels at the left and a blank where a line has no label:

SUM   DC    0
      LOAD  SUM

So you read a line like this: if its first word is an opcode, the line has no label; otherwise the first word is the label and the opcode comes next. DONE END is an END line with the label DONE; LOAD B is a LOAD line with no label.

The first opcodes

The arithmetic opcodes change only ACC; the location they read stays the same. Only STORE writes into memory.

In this book, every DC line sets its location before the program starts, wherever the line sits in the program; when the robot reaches a DC line it simply moves on. The programs here put their DC lines at the top.

Immediate data

Instead of a label, LOC can be a number written after =. This is called immediate data: the number itself is used, not a location.

• LOAD =123 puts 123 in ACC.

• SUB =1 takes 1 away from ACC.

• MULT =-3 multiplies ACC by −3.

Only LOAD, ADD, SUB, MULT and DIV may use immediate data, because they only read their LOC. STORE writes into its LOC, so STORE =5 makes no sense and is not allowed.

DIV rounds toward zero

ACSL says DIV keeps "the signed integer part of the quotient". That means: divide, then throw away everything after the decimal point, and keep the sign.

• 7 DIV 2: 7 ÷ 2 = 3.5, so the answer is 3.

• -7 DIV 2: −7 ÷ 2 = −3.5, so the answer is -3.

• -7 DIV -2: 3.5, so 3; and 7 DIV -2 is -3.

For a negative answer this is not the same as the int of ACSL's pseudocode or Python's //, which both round down (−3.5 becomes −4). DIV rounds toward zero: −3.5 becomes −3. This is the one place in ACSL where that happens, and it is the most common trap in this category.

Also watch the order. ACSL writes that LOC is "divided into" ACC, which means ACC ÷ LOC: ACC is the number being divided.

How big can a number be?

ACSL says ADD, SUB and MULT work modulo 1,000,000, and READ (Lesson 2) reads a number modulo 1,000,000. For a positive number that simply means keeping the last six digits: 999999 + 1 gives 0, and 1000 MULT =1000 gives 0.

ACSL gives no example for negative numbers. Book convention: this book keeps the sign and the last six digits, so -999999 - 2 gives -1. This is the book's own reading of the rule, not ACSL's. It never matters in this unit: in every exercise, every number stays between −999,999 and 999,999, and no program ever divides by zero.

Tracing a program

To trace a program, go down it line by line and write down ACC every time it changes. Here is the first sample program from ACSL's own page:

TEMP  DC    0
A     DC    8
B     DC    -2
C     DC    3
      LOAD  B
      MULT  C
      ADD   A
      DIV   B
      SUB   A
      STORE TEMP
      END

The DC lines set TEMP = 0, A = 8, B = −2 and C = 3.

So after the program runs, TEMP holds −9.

Example 2. What is in X and Y after this program?

X     DC    5
Y     DC    0
      LOAD  =20
      SUB   X
      STORE Y
      MULT  =-2
      DIV   =4
      STORE X
      END

So X holds −7 and Y holds 15. Notice that SUB X read the old X (5): a location only changes when a STORE writes into it.

Assembly in Python

Turning a short assembly program into Python is easy: each location becomes a variable, and ACC becomes a variable too. The only hard part is DIV. Python's // rounds down, so we need our own function that rounds toward zero:

• divide the sizes of the two numbers with // (for positive numbers, rounding down is rounding toward zero)

• if exactly one of the two numbers is negative, the answer is negative

Put it together: this program reads the three starting values of A, B and C, one per line, runs ACSL's sample program with them, and prints what ends up in TEMP. It is saved as assets/l1.py.

Run it from this unit's folder:

python assets/l1.py < assets/l1/1.in

With ACSL's values (8, −2 and 3) it prints -9. Try assets/l1/2.in, assets/l1/3.in and assets/l1/4.in, and check each answer by tracing the program by hand. assets/l1/4.in has a negative DIV: work out whether // would have given a different answer.

Lesson 2 — Jumps, loops, input and output

Division: Intermediate and above.

So far every program ran straight from top to bottom. Four branch opcodes let a program jump to another line. Their LOC is the label of the line to jump to, and three of them look at ACC to decide:

If a branch does not jump, the program simply goes on to the next line. A branch never changes ACC.

There is no "compare" opcode. To compare two numbers X and Y, work out X − Y in ACC and branch on its sign: it is greater than 0 when X > Y, 0 when they are equal, and less than 0 when X < Y.

Two more opcodes: READ and PRINT

A STORE or a READ into a label that has no DC line simply makes that location. A question tells you the input numbers in the order the program reads them.

When a question asks what a program prints, this book writes the printed numbers in order, on one line, separated by single spaces: 13 8 3.

Example 3. A jump forward. What does this program print?

X     DC    15
Y     DC    22
      LOAD  X
      SUB   Y
      BL    YBIG
      PRINT X
      BU    DONE
YBIG  PRINT Y
DONE  END

ACC becomes 15 − 22 = −7, which is less than 0, so BL YBIG jumps to the line labelled YBIG, which prints Y. Then the program reaches DONE END and stops. It prints 22: the program prints the larger of X and Y.

If X were bigger, BL would not jump: the program would print X, and then BU DONE would jump over the PRINT Y line. A jump forward over some lines works like an if … else in Python.

Example 4. A jump backward makes a loop. What does this program print?

N     DC    13
LOOP  PRINT N
      LOAD  N
      SUB   =5
      STORE N
      BG    LOOP
      END

So it prints 13 8 3. Notice that the test comes at the bottom of the loop, so the body always runs at least once, and that N still gets the value −2 before the loop stops.

Example 5. Here is ACSL's second sample program. If the input is a whole number N, what is the final value of X?

      READ  X
      LOAD  X
TOP   SUB   =1
      BE    DONE
      STORE A
      MULT  X
      STORE X
      LOAD  A
      BU    TOP
DONE  END

Trace it for N = 4. READ X makes X = 4, and LOAD X puts 4 in ACC.

So X ends as 24 = 4 × 3 × 2 × 1. In general X = N × (N − 1) × … × 1, which is written N! ("N factorial"). This is how ACSL answers the sample: X = N!. (The program needs N ≥ 1. For N = 0, ACC goes to −1, −2, … and never reaches 0, so the program never stops.)

Loops in Python

A jump forward is an if … else. A jump backward is a loop, and because the test is at the bottom, the loop body runs before the first test. One way to write that in Python is a while loop controlled by a variable going, which starts as True and is set by the test at the bottom. Here is Example 4:

Put it together: this program reads N and prints the final value of X in ACSL's sample program. In that program the test (BE DONE) comes straight after SUB =1, at the top of the loop, so here an ordinary while loop fits. It is saved as assets/l2.py.

Run it from this unit's folder:

python assets/l2.py < assets/l2/1.in

For N = 1 it prints 1: ACC becomes 0 straight away, so the loop never runs. Try assets/l2/2.in, assets/l2/3.in and assets/l2/4.in too. Line by line, match each Python line to the assembly line it comes from.

Lesson 3 — What does the program compute?

Division: Intermediate and above.

Some questions ask not "what is printed?" but "what does this program do?", as in ACSL's N! sample. The method is always the same:

1. Trace the program for a few small inputs, and put the results in a table.

2. Look for the pattern.

3. Check the pattern on one more input, and check the edge cases (0, 1, negative numbers) too: a program often behaves differently there.

Example 6. This program reads A and then B. What does it print?

      READ  A
      READ  B
      LOAD  =0
      STORE P
LOOP  LOAD  P
      ADD   A
      STORE P
      LOAD  B
      SUB   =1
      STORE B
      BG    LOOP
      PRINT P
      END

The loop adds A to P once for each pass, and B counts the passes down, so it prints A × B. But try B = 0: the body runs once before the test, B becomes −1, and the program prints A, not 0. So the honest answer is: "it prints A × B whenever B ≥ 1". Contest options are often built on exactly this kind of edge case.

An assembly interpreter in Python

Division: Senior and above.

An interpreter is a program that reads another program and runs it. Here is a plan for an interpreter for ACSL assembly.

First pass: read the program. Split each line into words. If the first word is not an opcode, it is a label: remember in a dict where which line number it is on, and move on to the next word. Keep the opcodes and the LOCs in two lists, ops and locs, so line k is ops[k] and locs[k]. For a DC line, also set its location in a second dict, memory, which maps each label to its number.

Second pass: run it. Keep acc and line, the number of the line to run next. Run the line, and move line on by one, unless a branch jumps, when line becomes where[loc]. Stop at END.

Here is the first pass on some sample lines:

Run it from this unit's folder:

python assets/l3.py < assets/l3/1.in

assets/l3/1.in is the robot's program. Try assets/l3/2.in (the robot with N DC 100), assets/l3/3.in and assets/l3/4.in too, and trace each program by hand to check. The Challenge exercise at the end of this unit asks you to add the missing opcodes.

Back to the robot

Trace the robot's program with N = 4:

1. The robot prints 10: 4 + 3 + 2 + 1 tins, the triangle with 4 tins on the bottom row.

2. For any N ≥ 1, it prints 1 + 2 + … + N, the number of tins in the whole triangle. For N = 100 that is 5050, which is what assets/l3.py prints for assets/l3/2.in. (There is a shortcut: 1 + 2 + … + N = N × (N + 1) ÷ 2, and 100 × 101 ÷ 2 = 5050.)