Enigmatic Code

Programming Enigma Puzzles

Running the first program: Part 3

[ Part 1 | Part 2 | Part 3 ]

Following on from my previous articles on programming the Analytical Engine (see Part 1 and Part 2), in this post we will actually translate Ada Lovelace’s diagram that is considered to be the first published program into a directly executable program for the Analytical Engine emulator, where each row in the diagram corresponds directly to a statement in the assembly language program.

As suggested in Part 2, I have written a simple assembler to make it a bit easier to write programs for the Analytical Engine emulator. It allows you to specify the arithmetic operations for the Engine as a single statement (rather than the usual 4 cards), and it keeps track of symbolic labels and automatically computes branch offsets for you.

The assembler is implemented by the assemble() function, which I’ve included in the latest version of analytical_engine.py.

The assemble() function takes a multi-line string representing the program, and returns a list of cards suitable for use as a program in the AnalyticalEngine class. It also returns a map from the labels used in the assembler program to the index of the corresponding card in the program.

The factorial program from Part 2 would look like this using the assembler:

from analytical_engine import AnalyticalEngine, Column, assemble

n = 40

(program, _) = assemble("""
  :init
  SET 0 <- {n}
  SET 1 <- 1
  SET 2 <- 1
  :loop
  # operation 1: v[2] *= v[0]
  MUL 0 2 -> 2
  # operation 2: v[2] -= 1
  SUB 0 1 -> 0
  # branch if non-zero to operation 1
  BRN loop
  # end
  HALT
""".format(n=n))

# initialise the engine
p = AnalyticalEngine(vars=3, number=Column(digits=50), trace=1)

# load the program to compute factorial(n)
p.load_program(program)

# run the program
p.run()

# the result is in v[2]
print("factorial({n}) = {f}".format(n=n, f=p.v[2]))

[Program 6 - factorial3.py]

The embedded program for the Analytical Engine is highlighted.

Note that I have used Python’s format() function to interpolate the (Python) variable n into the string before it is passed to the assembler. So the assembler just sees “… SET 0 <- 40 …”.

By setting the trace=1 flag on the emulator the actual program cards loaded into the emulator are printed out before execution (as well as the trace of the execution itself).

The format that the assembler accepts should be fairly self-explanatory, from the example above, and from the implementation of Ada’s program given below, but the main points are:

  1. Comments (as in Perl and Python) are indicated by a # (hash) and continue to the end of the line.
  2. A line that starts with a : (colon) declares a label (which can be used as the target of a branch).
  3. Statements start with an op-code, followed by a number of space separated arguments.
  4. The multiple cards required for an arithmetical operation (ADD, SUB, MUL, DIV) are replaced by a single statement. Each takes two arguments to indicate the source of the operands: either the index of a variable in the store, or the special token DATA, which indicates that the value is loaded from the input data stack. Additional arguments are used to indicate indices in the store where the result is to be stored.
  5. The offset in branch statements can be specified using a symbolic label, by using a symbol that is declared as a label elsewhere in the program. (The label can appear either before or after the branch statement).
  6. The arrows (<- and ->) used in the SET statement to indicate the value being assigned to a variable in the store, and in arithmetic operations to indicate the variables in the store that the result of the operation is assigned to, are entirely optional. (They are removed during the parsing process, but I think it makes the program a little more readable).

So we can now write Ada’s program for Bernoulli Numbers like this:

from analytical_engine import AnalyticalEngine, Column, assemble
from enigma import raw_input, printf

# assemble the program
(program, labels) = assemble("""
  :init
  SET 0 <- 0
  SET 1 <- 1
  SET 2 <- 2
  SET 3 <- 1
  :start
  MUL 2 3 -> 4 5 6
  SUB 4 1 -> 4
  ADD 5 1 -> 5
  DIV 4 5 -> 11
  DIV 11 2 -> 11
  SUB 13 11 -> 13
  SUB 3 1 -> 10
  BRZ finish
  ADD 2 7 -> 7
  DIV 6 7 -> 11
  MUL DATA 11 -> 12
  ADD 12 13 -> 13
  SUB 10 1 -> 10
  BRZ finish
  :loop
  SUB 6 1 -> 6
  ADD 1 7 -> 7
  DIV 6 7 -> 8
  MUL 8 11 -> 11
  SUB 6 1 -> 6
  ADD 1 7 -> 7
  DIV 6 7 -> 9
  MUL 9 11 -> 11
  MUL DATA 11 -> 12
  ADD 12 13 -> 13
  SUB 10 1 -> 10
  BRN loop
  :finish
  SUB 0 13
  PRINT
  ADD 1 3 -> 3
  SET 7 <- 0
  SET 13 <- 0
  HALT
""")

# initialise the engine
p = AnalyticalEngine(vars=14, number=Column(digits=10, dp=40), trace=1)

# load the program
p.load_program(program)

# indices B[k]
k = 1
# input data, initially empty, but each result is added after computation
data = []
# instruction to start execution at
start = labels['init']
# run the program
while True:
  # load the data and run the program
  p.load_data(data)
  p.run(start)
  # get the computed result from the output transcript
  r = (p.output[-1] if p.output else None)

  # display the computed result
  printf("B[{k}] = {r}")

  # run the program again?
  try:
    raw_input('\n[paused] >>> ')
  except EOFError:
    printf()
    break

  # add the result to the data and run it again
  data.append(r)
  start = labels['start']
  k += 2

[Program 7 - ada6.py]

Again, the highlighted section is the embedded program for the Analytical Engine, and the¬†statements in the program correspond to the lines in Ada’s diagram, with extra statements for the initialisation, branching and output added. So the first row in Ada’s diagram corresponds to the “multiply” statement after the “:start” instruction (line 12 of the above Python program).

We can use the output of the assembler to provide the indices of the cards where we wish to start and subsequently re-start execution.

This, then, is a directly executable representation of the first published program.

Advertisements

Leave a Comment

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: