Formula

From Esolang
Jump to: navigation, search

Formula is an esoteric programming language created by User:ais523 in 2006 as an exploration of the boundaries of the wire-crossing problem.

Syntax

A Formula program consists of a mathematical formula in one or more unknowns that evaluates to a real number; for instance, xy is a valid Formula program. Subscripts can be used on variables so there is an infinite stock available. The following mathematical operations are supported:

  • Addition
  • Subtraction
  • Multiplication
  • Division
  • Exponentiation
  • Sin, cos, tan (in radians) and their inverses

Semantics

Each variable in the formula corresponds to a variable in the program; all variables initially start at 0. Although the output of the formula merely has to be a real number, the variables are always integers. The formula is evaluated, and the output interpreted as follows:

  • If the output is an integer + ½ exactly, a bit is read from input, and it is rounded up to the nearest integer if the bit is 1 or down to the nearest integer if the bit is 0; then one of the following actions is applied to the rounded result.
  • If the output is 0 exactly, the program ends.
  • If the output is in the range (-½,½), then a 0 bit is output (if the output was negative) or a 1 bit is output (if the output was positive), and the first variable name is decremented or incremented (according to the sign of the result).
  • If none of the above apply, the output is rounded to the nearest integer; if the result is a positive integer n, the nth variable is incremented, and if it's a negative integer -n, the nth variable is decremented.
  • It is an error if the result refers to a non-existent variable (otherwise, the program would simply go into a trivial infinite loop).

This evaluation and interpretation of the result is repeated until the program ends.

Interpretation of the language

There are two ways to interpret the language; either as a zero-dimensional language with the variables as data storage, or as a multidimensional language with each variable corresponding to a dimension. For instance, a two-variable program has no wire crossings in its state diagram, which is trivial to prove by plotting each possible state of the program at (x,y) for a program with variables x and y.

Computational class

With three variables Formula can reasonably simply simulate a Minsky machine, and so is Turing complete. The computational class with two variables is unknown. All one-variable programs cannot go into a non-infinite loop and so cannot even emulate a push-down automaton.