LODA Language Specification

Overview

The LODA language is an assembly language with focus on arithmetic and number-theoretic operations. It supports an unbounded set of memory cells storing integer, arithmetic operations and a loop based on a lexicographical order descent on memory regions.

This document is organized as follows:

Example Programs

Here is a basic example of a LODA program:

; A002994: Initial digit of cubes: 0,1,8,2,6,1,2,3,5,7,1,1,1,2,2,3,...

pow $0,3     ; take cube of $0
lpb $0       ; loop as long as $0 decreases
  mov $1,$0  ; assign $1 := $0
  div $0,10  ; divide $0 by 10
lpe          ; end of loop
mov $0,$1    ; store result in $0

The first line is a comment and ignored during execution. LODA does not support named variables, but an unbounded set of memory cells denoted by $0,$1,$2,… each storing an integer. Programs that calculate integer sequences use the memory cell $0 to pass the argument and store the result. The main part of the program is a sequence of operations. This particular example program calculate an integer sequence for the initial digit of cubes (A002994 in the OEIS). The details of the language are explained in the following sections.

Language Overview

Basic Structure an Semantics

A program consists of a sequence of operations which are executed from top to bottom (exception for loops and conditionals). Line comments start with a semicolon.

Memory

Programs operate on memory consisting of an unbounded sequence of memory cells $0,$1,$2,… each storing an integer. There are three types of operands supported:

  1. Constants, for example 5.
  2. Direct memory access, for example $5. Reads or writes the value of the fifth memory cell.
  3. Indirect memory access, for example $$7. Reads the value at memory cell #7 and interprets it as an address. For instance, if the value of $7 is 13, then $$7 accesses the memory cell #13.

Programs are allowed to read uninitialized memory cells. Their value defaults to 0 (zero). There are no memory cells with negative indices. Using negative indices for direct memory access, e.g. $-1, yields parser/compile-time errors. Using negative indices for indirect memory access, e.g. $$3 when $3 = -1, causes runtime errors.

Operations

Operations have the following basic form: opcode target,source where target is a direct or indirect memory access, and source is a direct or indirect memory access or a constant. We use the Intel assembly syntax (target before source). The target memory cell may get updated by the operation. The source is read-only. For example, the operation add $3,5 adds 5 to the value stored in the memory cell $3. Detailed information can be found in the Operations Reference.

Integer Sequences

Programs operate on an unbounded set of memory cells. To compute integer sequences, we use the memory cell $0 both for the input and the output of the program. Thus, a sequence a(n) is generated by passing the parameter n as $0, executing the program and reading the output a(n) again from $0.

Operations Reference

mov (Assignment)

Assign the value of the source to the target operand.

An operation mov a,b corresponds to the assignment a := b.

Examples:

mov $0,26 ; $0 := 26
mov $1,$0 ; $1 := $0 = 26
mov $$1,7 ; $26 = $$1 := 7

add (Addition)

Add the value of the source to the target operand.

An operation add a,b corresponds to the assignment a := a+b.

Examples:

mov $0,2  ; $0 := 2
mov $1,3  ; $1 := 3
add $0,5  ; $0 := 2 + 5 = 7
add $0,$1 ; $0 := 7 + 3 = 10

sub (Subtraction)

Subtract the source from the target operand.

An operation sub a,b corresponds to the assignment a := a-b.

Examples:

mov $0,5  ; $0 := 5
mov $1,-3 ; $1 := -3
sub $0,7  ; $0 := 5 - 7 = -2
sub $0,$1 ; $0 := -2 - (-3) = 1

trn (Truncation)

Subtract the source from the target operand and ensure non-negative result.

An operation trn a,b corresponds to the assignment a := max(a-b,0).

Examples:

mov $0,9 ; $0 := 8
mov $1,3 ; $1 := 3
trn $0,5 ; $0 := 4
trn $1,5 ; $1 := 0

mul (Multiplication)

Multiply the target with the source value: a:=a*b.

An operation mul a,b corresponds to the assignment a := a*b.

Examples:

mov $0,5  ; $0 := 5
mov $1,-3 ; $1 := -3
mul $0,7  ; $0 := 5 * 7 = 35
mul $0,$1 ; $0 := 35 * (-3) = -105

div (Division)

Divide the target by the source value. This is the normal integer division where the fractional part is discarded.

An operation div a,b corresponds to the assignment a := floor(a/b). This operation yields a runtime error if b is zero.

Examples:

mov $0,26 ; $0 := 26
div $0,2  ; $0 := 13
div $0,-4 ; $0 := -3

dif (Conditional Division)

Divide the target by the source value if it is a divisor. If the source is not a divisor, the target is unchanged.

An operation dif a,b corresponds to the assignment a := a/b if b divides a. The target is unchanged if b does not divide a. It is also unchanged whenever b is zero.

Examples:

mov $0,26 ; $0 := 26
dif $0,2  ; $0 := 13
dif $0,4  ; $0 := 13
dif $0,0  ; $0 := 13

mod (Modulus)

Remainder of division of target by source.

An operation mod a,b corresponds to the assignment a := a % b. When using negative arguments, the sign of the result is the same as the sign of the dividend (target). This operation yields a runtime error if b is zero.

Examples:

mov $0,13  ;
mod $0,3   ; $0 := 1
mov $0,-13 ;
mod $0,3   ; $0 := -1
mov $0,13  ;
mod $0,-3  ; $0 := 1
mov $0,-13 ;
mod $0,-3  ; $0 := -1

pow (Power)

Raise target to the power of source.

An operation mod a,b corresponds to the assignment a := a ^ b. This operation yields a runtime error if b is negative.

Examples:

mov $0,3  ; $0 := 3
pow $0,3  ; $0 := 27

gcd (Greatest Common Divisor)

Greatest common divisor of target and source.

An operation gcd a,b assigns the greatest common divisor of a and b to a. The result is zero if a and b are both zero. Otherwise, the result is always positive (greater or equal to one).

Examples:

mov $0,20  ; $0 := 20
mov $1,16  ; $0 := 16
gcd $0,$1  ; $0 := 4
gcd $0,5   ; $0 := 1

lex (Largest Exponent)

Largest exponent of the source dividing the target.

An operation lex a,b computes the largest exponent of b that divides a, and assigns it to a. The result is always a non-negative number. If a is zero or b is zero or b is one, the result is always zero.

Examples:

mov $0,18  ; $0 := 9
lex $0,3   ; $0 := 2
mov $0,-8  ; $0 := 9
lex $0,2   ; $0 := 4

bin (Binomial Coefficient)

Binomial coefficient (source choose target).

An operation bin a,b corresponds to the assignment a := a! / (b! * (a-b)!) where the exclamation mark are the factorial numbers. For negative arguments, the semantics is defined as in M.J. Kronenburg: The Binomial Coefficient for Negative Arguments.

Examples:

mov $0,7 ; $0 := 7
bin $0,3 ; $0 := 35
mov $0,7 ; $0 := 7
bin $0,0 ; $0 := 1

log (Logarithm)

Discrete logarithm to a given base.

An operation log a,b computes the discrete logarithm of a to the base b. In other words, the largest non-negative integer c such that b^c <= a. The base b must be greater or equal to 2, and the argument a greater or equal to 1.

nrt (n-th Root)

Discrete n-th root.

An operation nrt a,n computes the discrete n-th root of a. In other words, the largest non-negative integer c such that c^n <= a. The argument n must be non-negative, and n greater or equal to 1.

dis (Digit Sum)

Digit sum to a given base.

An operation dis a,b computes the digit sum of a in base b, and assigns the result to a. The base must be greater or equal to two. If a is negative, the digit sum is computed as in the positive case, but the result is negative.

Examples:

mov $0,345 ; $0 := 345
dis $0,10 ; $0 := 12
mov $0,8 ; $0 := 8
dis $0,2 ; $0 := 3

dir (Digital Root)

Digital root to a given base.

An operation dis a,b computes the digital root of a in base b, and assigns the result to a. The digital root is defined by iteratively computing digital sums until the result is less than the base. The base must be greater or equal to two. If a is negative, the digital root is computed as in the positive case, but the result is negative.

Examples:

mov $0,345 ; $0 := 345
dir $0,10 ; $0 := 3
mov $0,8 ; $0 := 8
dir $0,2 ; $0 := 1

equ (Equal)

Check if target and source values are equal. The result is 1 if the target and source are equal. Otherwise, the result is 0.

An operation equ a,b assigns the value 1 to a if a is equal to b. Otherwise, it assigns a := 0;

Examples:

mov $0,7 ; $0 := 7
equ $0,7 ; $0 := 1
mov $0,7 ; $0 := 7
equ $0,8 ; $0 := 0

neq (Not Equal)

Check if target and source values are not equal. The result is 1 if the target and source are not equal. If they are equal, the result is 0.

An operation neq a,b assigns the value 1 to a if a is not equal to b. Otherwise, it assigns a := 0;

Examples:

mov $0,7 ; $0 := 7
neq $0,6 ; $0 := 1
mov $0,7 ; $0 := 7
neq $0,7 ; $0 := 0

leq (Less or Equal)

Check if target is less than or equal to the source value. The result is 1 if the target is less than or equal to the source value. Otherwise, the result is 0.

An operation leq a,b assigns the value 1 to a if a is less or equal to b. Otherwise, it assigns a := 0;

Examples:

mov $0,7 ; $0 := 7
leq $0,8 ; $0 := 1
mov $0,7 ; $0 := 7
leq $0,6 ; $0 := 0

geq (Greater or Equal)

Check if target is greater than or equal to the source value. The result is 1 if the target is less than or equal to the source value. Otherwise, the result is 0.

An operation geq a,b assigns the value 1 to a if a is greater or equal to b. Otherwise, it assigns a := 0;

Examples:

mov $0,7 ; $0 := 7
geq $0,6 ; $0 := 1
mov $0,7 ; $0 := 7
geq $0,8 ; $0 := 0

min (Minimum)

Minimum of the target and source values.

An operation min a,b corresponds to the assignment a := min(a,b).

Examples:

mov $0,7 ; $0 := 7
min $0,5 ; $0 := 5
min $0,6 ; $0 := 5

max (Maximum)

Maximum of the target and source values.

An operation max a,b corresponds to the assignment a := max(a,b).

Examples:

mov $0,7 ; $0 := 7
max $0,5 ; $0 := 7
max $0,8 ; $0 := 8

ban (Bitwise And)

Bitwise “and” of the target and source values. The result is negative, if and only if both the source and the target are negative.

bor (Bitwise Or)

Bitwise “or” of the target and source values. The result is negative, if and only if the source or the target is negative.

bxo (Bitwise Xor)

Bitwise “xor” of the target and source values. The result is negative, if and only if either the source or the target is negative (exclusive).

lpb..lpe (Loop / Conditional)

Loops are implemented as code blocks between lpb and lpe operations. The block is executed as long as a variable is decreasing and non-negative. For example, consider the following program:

mov $1,1
lpb $0
  mul $1,5
  sub $0,1
lpe

It first assigns 1 to the memory cell $1. Inside the loop, the memory cell $0 is counted down to zero and in every step $1 is multiplied by 5. Note that this could be also achieved without loops using the pow operation. If the loop counter is not decreasing or becomes negative, the side effects of this last iteration are rolled back. This also enables the usage of this concept as conditional. For example, the following code multiplies $1 by 5 if $0 is greater than 17.

lpb $0
  mul $1,5
  mov $0,17
lpe

The lpb can also have a second (optional) argument. In that case, the loop counter is not a single variable, but a finite memory region, which must strictly decreases in every iteration of the loop. The loop counter cell marks the start of that memory region, whereas the second argument is interpreted as a number and defines the length of this region. For example, lpb $4,3 … lpe is executed as long as the vector (or polynomial) $4,$5,$6 is non-negative and strictly decreasing in every iteration according to the lexicographical ordering. If y is not a constant and evaluates to different values in subsequent iterations, the minimum length is used to compare the memory regions.

clr (Clear)

The clr (clear) operation resets a memory region to zero. The target operand marks the start of the memory region. The second argument is the length of the memory region. For example clr $2,3 sets the memory cells $2,$3$4 to zero. If the length is negative, the memory region is reset to the left-hand side of the target operand.

sor (Sort)

The sor operation sorts a memory region. The target operand marks the start of the memory region. The second argument is the length of the memory region. For example sor $2,3 sorts the memory cells $2,$3$4 in ascending order. If the length is negative, the memory region is reset to the left-hand side of the target operand. This can be used to sort a region in descending order.

seq (Sequence)

Calling another LODA program for an OEIS sequence is supported using the seq operation. This assumes you are evaluating the program as a sequence (see below). This operation takes two arguments. The first one is the parameter of the called program. The second argument is the number of the OEIS program to be called (see below). The result is stored in the first argument. For example, the operation seq $2,45 evaluates the program A000045 (Fibonacci numbers) using the argument value in $2 and overrides it with the result.

Termination

All LODA programs are guaranteed to halt on every input. Recursive calls are not allowed. An infinite loop also cannot occur, because the values of the memory region strictly decrease in every iteration and can at most reach the region consisting only of zeros. Hence, all loops therefore also all LODA programs eventually terminate.