LARSA

LARSA is a programming language created by User:Ian. LARSA stands for Logic ARray Stack Architecture. It is a concatenative language (except for assignments) that has a single-symbol state register, and two stacks: a data stack, which can hold an infinite number of bits (0 and 1), and a command stack, which holds single-symbol commands, that may include 0 and 1 and any user-defined commands. The data stack is assumed to contain infinite zeroes beyond the "end" of the stack. Even though it's infinite, the "end" marker can be tested for using the error handlers. Commands can contain various rules, which are executed depending on the state register. Each rule contains an input count, output count, a collection of logical tables, which can range from simple truth tables of 1's and 0's to complex structures with nops and recursions, and optional state transitions, which are in a similar table format. All data eventually evaluates into a collection of binary bits, or runs forever. "Symbol" is used instead of byte because the size of the symbol is implementation-dependent, as long as it is fixed-length. There are no explicit loops, so all looping is done by recursion. It has no input or output other than the stack and state and the assigned commands. The reference implementation is written in Perl and is available here.

Commands

Commands can be divided into different groups. Constants are commands that have no inputs and a fixed output (which may only be built-ins or other constants). Variables are commands that have no inputs, but return different values based on the state register. Operators are any non-recursive command that alters the stack, but not the state. Functions are commands that have a constant number of inputs and outputs for any given input. Functions can be recursive. Loops are recursive commands that may include state transitions. Conditionals are commands that call other commands depending on the state and/or input values. Subroutines are commands that are typically called from inside other commands or commands that do a utility-based function like clearing the stack or setting the state. Procedures are commands that have no inputs, but return a series of other commands.

These are defined mainly things like k (clear state) can be a "subroutine" or p and q (generic bit-size variables) "variables" or "&" (logical and) a "function" or "operator" instead of calling everything a command. These are not mutually exclusive, and not strict rules, just guidelines so people can better describe the types of commands they're defining.

Built-ins

0	pushes a 0 (false) onto the data stack
1	pushes a 1 (true) onto the data stack

An assignment is not a command, but a statement. It has no immediate effect on the stack or state, but defines new commands.

Assignment format

$var[state]=[in_count][[@err_state]|err_hand][,[out_count][,[truth_table][[,state_test_count],state_table]]]

A section inside square brackets ([ ]) means that it can be omitted.

• var is the command variable to assign this rule to.
• state is the (optional) state for that particular rule. If the state matches the value of the state register, that action is executed. If it is omitted, the default state is used, which makes it the rule that will be called when the state is empty, or the current state is undefined for that particular command.
• in_count is the number of bits that will be popped off of the data stack and used to determine which table entry will be pushed onto the command stack.
• out_count is the size of each table entry, in bits. If the table is too small for a particular entry, nothing will be pushed.
• err_state is the state to transition to when the stack is empty or there are less items on the stack than the value of in_count. If in_count is 0, and this is specified, it will be activated when there are no items on the stack.
• err_hand is the single-entry rule table to be called for the same conditions as err_state. If either err_state or err_hand execute, the command exits immediately after performing these error-handling functions. If either are omitted entirely (not empty: empty means that it will end with a NOP), the stack will be assumed to be filled with infinite zeroes beyond the end.
• truth_table is the main table that contains all symbols that a rule can push onto the command stack. The true values (1's) have a lower index on the table, and are the leftmost in the assignment statement. This follows the truth table convention:

P Q idx
T T  0
T F  1
F T  2
F F  3

• state_test_count is the number of bits to test (but not pop) for state transitions. It can be greater, less, or equal than the in_count. However, the error handler sections will not activate if this value falls off the end of the stack. It will just be filled with zeroes. This must be omitted if there is no state table. The comma is a prefix to this number, so if this is omitted, the comma must also be omitted.
• state_table is the table of state transitions. Like truth_table, it can contain empty entries (which will clear the state). To keep the state the same, this table must be omitted or explicitly contain transitions to that state. A completely empty (but included) table will clear the state unconditionally.

Control structures

The only way to make loops or other control structures is through recursion. Recursion is implemented by placing the command inside its own truth table. The command stack is a single level with no break functions. The only way to halt is after all remaining commands execute and the command stack is empty, even if they're treated as nops.

Examples

LARSA programs are composed of two types of statements: assignments and evaluations. Assignments begin with a dollar sign ($) and contain an equals sign in the third or fourth slot. Simple assignment:

$0=Definitions of common logic gates:
$|=2,,1110
$&=2,,1000
$~=1,,01
$==2,,1001
$>=2,,1011
$^=2,,0110

The > is implication, and = is equivalence. The rest are or, and, not, and xor, the same as in C, Perl, Java, etc. The $0= marks a comment. The 0 and 1 operators cannot be redefined in the default state, so they are ignored and can be used as comments.

Note: There are no syntax errors. If you type in a wrong assignment, it will be treated as an evaluation instead, and the $ and = will be processed as commands. Things like $=== are also valid assignments. This one defines the rule for the = sign when the state is an = sign to be a nop.

State machine:

$0=Clears the state:
$k=,,,
$0=Removes leading zeroes from the stack:
$Z=|,,Zk,p
$Zp=1@e|,,Z1ZZ0Z
$Ze=1,1,1,1e
$Z1=

In these assignments, the first character after the dollar sign is the variable, and the second one is the state. These assignments are the different rules of Z.

Arithmetic:

$0=Binary Successor and Predecessor functions:
$+=1,2,+01
$-=1|,2, 0-1

State as Variables:

$0=Logic variables (capital is set, lowercase is get):
$0=     01
$0=  Q P--
$0=0 |   A
$0=1 |  bB
$0=When both are 0, the empty state is used.

$P=1,,,A
$Pb=1,,,Bb
$PB=1,,,Bb
$Q=1,,,b
$QA=1,,,BA
$QB=1,,,BA
$p=,,0
$pA=,,1
$pB=,,1
$q=,,0
$qb=,,1
$qB=,,1

BCT in LARSA

Through recursion and state changes, it's possible to simulate Bitwise Cyclic Tag in LARSA. BCT programs in this emulator use i and j instead of 0 and 1, respectively. Data is still symbolized by 0 and 1.

$0=BCT (Bitwise Cyclic Tag) emulator:
$0=Command      Execution
$0=-------      ---------------------------------------------
$0=   0         delete the leftmost data-bit
$0= 
$0=   1         goto the next command (say x)
$0=             if the leftmost data-bit is 1:
$0=                copy x to the right end of the data-string

$0=In this implementation, command 0 is "i" and 1 is "j"
$0=A program is declared using $p=|,,[program]p (ex. $p=|,,iijjjp)
$0=and called using [data string]p (ex. 101p)
$0=The variable can be anything, not just p.
$0=The p at the end causes the program to loop.
$0=The | ensures that it halts when the data string is empty, as in a real BCT
$0=k (clear state) is defined above in the State Machine example.
$0=With this emulator, the example from the BCT article could be written:
$0=$p=|,,jijjjjijjjiijjjijjip
$0=And then executed as:
$0=1p

$0=Begin recursion and prepare to clear state at the end:
$i=1|,,i1iki0ik,0,p
$0=Recurse until end of stack:
$ip=1@e|,,i1ii0i
$0=Delete the bit:
$ie=1,,,0,n
$0=NOP the rest of the i commands:
$in=

$0=Begin recursion and prepare to set the "j" state at the end:
$j=1|,,j1jJj0jJ,0,p
$0=Recurse until end of stack:
$jp=1@e|,,j1jj0j
$0=Reached end of stack, *test* bit and set state:
$je=,,,1,10
$0=NOPs for the remaining j commands:
$j1=
$j0=
$0=Get the bit and set the state for the j command:
$J1=,,1,j
$J0=,,0,j
$Je=,,,j

$0=Result depends on following command (which clears the state):
$ij=1,1,0,
$jj=1,1,1,

This should prove that LARSA is Turing-complete, because it simulates the Turing-complete BCT language.