fracasm

fracasm is an esoteric programming language based on a counter machine.

A fracasm program is a sequence of statements that end in semicolons. Comments start with # and continue to the end of the line. The first statement should be preceded by @start:.

Contents

• Variables and values
  • Input and output
• Program flow
  • Alternatives
  • Gotos
  • Copy loops
• Threads
  • What threads and labels actually are
• Other statement types
  • @always
  • !unreachable
  • @start
  • @const
  • !anything
  • !trace
• Translation to FRACTRAN
• Translation from other languages
  • From FRACTRAN
  • From Brainfuck
• Changes to version 1.1
• Grammar of fracasm
• Download

Variables and values

Variables don't need to be (and can't be) declared. Variable names can contain letters, numbers, underscores, apostrophes, and periods, and they are case-sensitive. Numbers are valid variable names, since there is never any ambiguity whether the number is being used as a variable name or as a number. All variables contain non-negative integers, and there is no upper limit to the value that a variable can have. Unless otherwise specified, all variables start out with the value 0.

The two most basic statements are adding a number to a variable (syntax: variable + number ;, e.g., a+1;), and subtracting a number from a variable (syntax: variable - number ;). (Note that although these look like non-side-effecting expressions, they do actually change the value of the variable; there aren't any expressions, so there's no ambiguity.) If you're adding or subtracting 1, there's a shorter form: just put the + or - before the variable name; e.g., +a; means the same thing as a+1;.

If you subtract a value from the variable, and subtracting the value would result in a negative value, then the whole statement doesn't execute. For instance, if a has the value 2, then after the statement a-5;, a will still have the value 2, not -3 (since variables cannot have negative values) nor 0. You can put multiple variable modifications in a single statement to take advantage of this; for instance, the statement a-5 b+2; will only add 2 to b if a is at least 5. It does not matter which order the additions and subtractions are in the statement; if any subtraction anywhere fails, the whole statement, even parts before that subtraction, does not execute. You can change this behavior by putting a question mark after the subtraction; a-5? b+2; will always add 2 to b, regardless of whether 5 could be subtracted from a. Putting two question marks after a subtraction will also set the variable to 0 if it's too small for the subtraction to succeed normally.

If you want to test the value of a variable without changing it, you can use >=; a statement part like a>=2 is equivalent to a-2 a+2. (Note that this means that testing a variable twice in the same statement, or testing a variable and subtracting from it in the same statement, probably won't do what you expect; a>=2 a>=3 is actually equivalent to a>=5. Don't depend on this, though; it might change in future versions.) There are no other comparison operators.

Input and output

The main way to do input and output is using @in and @out directives. These have the syntax @in or @out space-separated list of variable names ; and can appear anywhere in the program (except in the middle of a statement). All variables in an @in directive will be read in when the program starts, and will have the value that was read instead of 0 at the beginning of the program. All variables in an @out directive will be displayed when the program finishes.

You can also use !desc (new in version 1.1) to print out some text at the beginning of the program before it asks for input. This is intended for things like explaining what the program does and what format it expects its input to be. The format is !desc tokens; tokens can include any token recognized, and can include double-quoted strings. In quoted strings, backslashes can be used to escape quotation marks and other backslashes. If you want multiple lines, use multiple !desc statements.

It's also possible to display output while the program is running, though this isn't guaranteed to work in all implementations of the language. At the end of a statement (before the semicolon) put !print tokens to print a constant message (same format as !desc) or !printvars space-separated variable names to print the value(s) of variable(s). (!printvars by itself will display the value of all variables.)

In the current interpreter, !print and !printvars don't work if they're the first thing in the statement.

Program flow

By default, statements are executed in order. However, like most programming languages, there are ways to change this.

Alternatives

A statement can have multiple alternatives, separated by vertical bars (|). If one alternative fails (due to a subtraction that would make the variable negative, or due to a comparison that fails), the next alternative is tried. When an alternative succeeds, the rest of the alternatives in the statement are ignored and the next statement starts.

It's possible to put multiple alternatives inside parentheses; (a-1 | b-1) c+1, for instance, is equivalent to a-1 c+1 | b-1 c+1. If there are multiple parenthesized alternatives in a statement, they're checked in order. Note that the translation to the non-parenthesized version is actually done at compile-time, so use these sparingly. Question-marks are also translated to alternatives at compile-time.

Gotos

A statement can have a label. Anything that can be used as a variable name can also be used as a label name, though a label cannot have the same name as a variable (well, it can, but it won't do what you expect). Label a statement by putting the label followed by a colon before the statement.

To go to a labelled statement, use the syntax > label as part of a statement (this can be used anywhere addition and subtraction can be used). You can also use @repeat to repeat the current statement; if the statement is labelled, @repeat is the same as > the-statement's-label.

With everything up to this point, the language is Turing-complete.

Copy loops

Sometimes you want to add a variable to another variable, or copy a variable into another variable, without setting the original variable to 0. It's possible to do this with two loops:

a-1 b+1 tmp+1 @repeat; # move a to both b and a temporary variable
tmp-1 a+1 @repeat; # restore a from the temporary variable

However, there's a shortcut for this particular set of loops: source-variable >> statement-parts. This will execute statement-parts source-variable times. If any of statement-parts fails, the result is undefined.

Copy loops can appear as part of a larger statement: other variable modifications can appear before the loop, and the loop can be inside an alternative. However, copy loops cannot appear inside parentheses, nor can multiple copy loops appear in the same alternative.

The source variable can be followed by / and a number to divide it by that number (rounding down).

Threads

fracasm has multi-threading, sort of. However:

• Thread switches always happen between statements (and never during a copy loop).
• The highest-priority thread (that's not waiting) always executes. Thread priority is determined by which statement the thread is currently on: statements that come later in the program have higher priority. (This can be changed by putting @priority -; at the top of the program.)
• Threads do not have any thread-local state other than the execution pointer. All variables are shared by all threads.

A simple use of threads is to simulate subroutines: put the subroutine at the end of the program and start a thread at the beginning of the subroutine to call it.

To start a thread, use + label-to-start-at. (You can also start multiple threads at the same line using label-to-start-at + number-of-threads.) To end the current thread, use @end as a part of a statement.

If a statement ends in | @wait;, then if none of the alternatives succeed, then other threads execute and the thread waits until one of them does. If all threads are waiting or have ended, the program ends.

What threads and labels actually are

You may have noticed that the syntax for starting threads is the same as the syntax for adding to a variable. That's because labels are variables; a label is a variable whose value is the number of threads currently at the label. (Unlabelled statements are given labels with names that can't be directly referenced by the program.) At each step of the program, the statement with the highest priority whose label has a positive value and that's not waiting executes, the label's value is decreased by 1, and unless the selected alternative has @end, the label of the next statement's value is increased by 1.

Also, >label is actually a shortcut for +label @end.

Other statement types

@always

If @always precedes a statement, then the statement will always execute if any of its alternatives succeed and there's no thread at a higher priority currently executing.

!unreachable

An alternative can include !unreachable or !error; if this alternative is executed, the behavior is undefined. !unreachable can be followed by an error message that the interpreter may optionally display.

@start

@start variable = value ; assigns a value to a variable (or starts some number of threads) before the program starts. If a variable appears both in a @start directive and an @in directive, the behavior is undefined.

@const

@const name = value ; defines a constant, which can be used anywhere a number can. Constant names can be anything that can be a variable name except for numbers. A constant can have the same name as a variable or label without causing a conflict.

!anything

Statements that start with ! are compiler-dependent. Unrecognized statement types starting with ! are ignored.

!trace

Put !trace; at the bottom of the program (or top if you're using @priority -;) to show all variables for each step of the program.

Translation to FRACTRAN

Perhaps you're wondering why I made some of the design decisions I did, or why I chose the name I did? Because it's intended to be an assembly language for FRACTRAN.

To translate to FRACTRAN, first replace anything that I showed an equivalence for (including making the labels be explicitly variables and turning copy loops into actual loops). Then for each alternative that both adds and subtracts from the same variable, change the additions to jumps to new high-priority statements that add to that variable (because FRACTRAN doesn't allow adding to and subtracting from the same variable in the same statement).

Each alternative becomes a fraction. Each variable is associated with a prime number. Each fraction's numerator is the product of the variables added in the statement, to the power of the number to add to the variable; and the fraction's denominator is the product of the variables subtracted from in the statement, to the power of the number to subtract from the variable. Within a statement, the fractions go in decreasing order; the fractions for higher-priority statements come first.

@start and @in directives specify the initial number, and @out directives indicate how to interpret the output.

The !prime directive (syntax: !prime variable = constant ... ;) can be used to specify which prime to associate with which variable. !print, !printvars, and !trace are ignored when translated to FRACTRAN.

Translation from other languages

From FRACTRAN

Make the whole thing an @always statement with an alternative for each fraction. For each fraction, factor it, and turn p₁^n₁p₂^n₂.../q₁^m₁q₂^m₂... into p1+n1 p2+n2 q1-m1 q2-m2

From Brainfuck

Use the following template:

@start:
# code goes here
@end;


l:
r7-1 tmp+1 @repeat; tmp-1 r7+2 @repeat; cur-128 r7+1;
r6-1 tmp+1 @repeat; tmp-1 r6+2 @repeat; cur- 64 r6+1;
r5-1 tmp+1 @repeat; tmp-1 r5+2 @repeat; cur- 32 r5+1;
r4-1 tmp+1 @repeat; tmp-1 r4+2 @repeat; cur- 16 r4+1;
r3-1 tmp+1 @repeat; tmp-1 r3+2 @repeat; cur-  8 r3+1;
r2-1 tmp+1 @repeat; tmp-1 r2+2 @repeat; cur-  4 r2+1;
r1-1 tmp+1 @repeat; tmp-1 r1+2 @repeat; cur-  2 r1+1;
r0-1 tmp+1 @repeat; tmp-1 r0+2 @repeat; cur-  1 r0+1;

l7-2 tmp+1 @repeat; l7-1 cur+128; tmp-1 l7+1 @repeat;
l6-2 tmp+1 @repeat; l6-1 cur+ 64; tmp-1 l6+1 @repeat;
l5-2 tmp+1 @repeat; l5-1 cur+ 32; tmp-1 l5+1 @repeat;
l4-2 tmp+1 @repeat; l4-1 cur+ 16; tmp-1 l4+1 @repeat;
l3-2 tmp+1 @repeat; l3-1 cur+  8; tmp-1 l3+1 @repeat;
l2-2 tmp+1 @repeat; l2-1 cur+  4; tmp-1 l2+1 @repeat;
l1-2 tmp+1 @repeat; l1-1 cur+  2; tmp-1 l1+1 @repeat;
l0-2 tmp+1 @repeat; l0-1 cur+  1; tmp-1 l0+1 @repeat;
@end;

...and translate each character as follows:

IO is a bit more tricky, since Brainfuck inputs and outputs an arbitrary number of characters, whereas fracasm inputs and outputs a fixed number of big integers. My translation of a hello world program just has a separate variable for each output statement, where . translates to cur >> outn;, but that won't work if a program outputs inside of a loop. (It is possible, but whatever you do will require some work interpreting the output.)

My initial implementation of a tape used one variable for each direction (left and right). Moving the tape right meant first pushing the current value onto the left variable by calculating 256left + value, then popped from right by dividing right by 256 and using the remainder as the current value. That turned out to be super slow, even for a hello world program that only uses a few cells. This implementation instead uses eight variables for each direction of the tape, one per bit, and only multiplies and divides by two. This will still be slow for programs that use lots of memory, though; unfortunately, I think any sort of memory access in FRACTRAN or fracasm is going to be exponential in the amount of memory you're using.

Changes to version 1.1

In fracasm:

• Made everything compatible with Python 3
• Added !desc pragma
• Fixed handling of string literals (escapes didn't work quite right in the first version)
• Changed !trace to only include nonzero variables
• -t/--trace command-line option, which acts like !trace

In the included FRACTRAN interpreter:

• -t/--trace command-line option, which shows each number
• Added an option to specify the input on the command line.
• Made the format more flexible; fractions can now be separated by spaces or commas, not just newlines.
• Added a feature where lines starting with ! are printed at the beginning of the program (like !desc); also use this feature in fracasm.
• Reduced fractions that weren't reduced, and added an option not to do that.

I also added a bunch of examples and added the Translation from other languages section to this documentation (along with some smaller edits).

Grammar of fracasm

In the following grammar, * indicates 0 or more of the previous thing, and ? indicates 0 or 1 of the previous thing.