The CALC esoteric programming language
This blog post is a bit different from normal, and is instead a linkpost for this Esolang page. That page is more up to date than this one. This is the precursor to an upcoming blog post, [[FRACTRAN and theoretically cheating at your A-levels]]B.
Language overview
CALC is an esoteric programming language based on the kinds of expression which a simple scientific calculator with memory allows. It was designed to demonstrate that the Casio FX-991EX can do arbitrary computation, despite being “non-programmable”.
Format of a program
The following example demonstrates all of the language features.
10 -> maxiter
1 -> iter
? -> guess
:::
guess - (guess * guess - 2) / (2 * guess) -> guess
iter + 1 -> iter : sqrt(maxiter - iter) # exit if iter > 10
:::
P(guess)
This program computes an estimate of the square root of two via ten iterations of Newton’s method, starting from a user-specified initial guess. It prints the estimate once it has finished.
A program consists of three sections:
- The initialization section, in which the initial value of any number of variables is set and any number of expressions are executed,
- The loop section, in which a sequence of expressions and variable assignments are repeated until an error occurs, and
- The finalization section, in which again any number of variables can be set and any number of expressions are executed.
These sections are separated by a triple colon: :::. A loop or finalization section is not mandatory, so omitting ::: is still a valid program.
Comments
Comments are denoted by #. All text on the same line after a # is ignored. Extra whitespace between lines is also ignored.
Variable assignment
Variable assignment is performed like so:
<expr> -> variable
where <expr> is any “calculator expression”, built up from (, ), +, -, /, *, ^ and calling any number of built-in functions. Variables can only be set to real numbers, there are no strings or booleans.
Note that this means variable assignment is performed the opposite way around to most other programming languages. The -> symbol can be read as “is assigned to”.
Multiple statements can be put on the same line by separating them with a :, like so:
iter + 1 -> iter : sqrt(maxiter - iter)
Built-in functions
There are a few built-in functions:
| Name | Description |
|---|---|
P(x) |
Print the value of x and return it unmodified. |
delta(x, y) |
Kronecker delta. Returns 1 if x = y, otherwise returns 0. |
round(x) |
Returns the result of rounding x to the closest integer. Half is rounded away from 0. |
floor(x) |
Returns the result of rounding x down to the nearest integer. |
ceil(x) |
Returns the result of rounding x up to the nearest integer. |
random_int(x, y) |
Returns a random integer between x and y, inclusive. |
sqrt(x) |
Returns the principal square root of x. Throws an error if x < 0. |
User input
User input is possible like so:
? -> variable
This will prompt the user for a numerical value for variable. In the above example, this is used to accept an initial guess.
Loops
There is only one loop, which consists of all of expressions and assignments after the first triple colon :::.
This will repeat until an error occurs.
To exit when some when some condition is met, you can turn the condition into an expression which causes a math error when that condition is met. In the example, the final sqrt(maxiter - iter) means the loop exits when iter > maxiter (since there is no support for imaginary numbers).
Non-features
The following are not part of the language:
- Function definitions
- Non-number types, like strings or booleans
- Complex control flow: no jumps, or if/else
Computational class
CALC is Turing-complete. Arbitrary FRACTRAN programs can be simulated like so:
a_1/b_1 -> frac1
a_2/b_2 -> frac2
# ...
a_k/b_k -> fracK
<start_value> -> n
:::
P(n)
n -> start
# Multiply by first fraction a_i/b_i such that the result is an integer
n + (n * frac1 - n) * delta(n * frac1, floor(n * frac1)) * delta(start, n) -> n
n + (n * frac2 - n) * delta(n * frac2, floor(n * frac2)) * delta(start, n) -> n
# ...
n + (n * fracK - n) * delta(n * fracK, floor(n * fracK)) * delta(start, n) -> n
# Exit if n is unchanged, otherwise loop
sqrt(-delta(n, start))
In particular, adapting the “POLYGAME” FRACTRAN program yields the following universal machine:
583/559 -> frac1
629/551 -> frac2
437/527 -> frac3
82/517 -> frac4
615/329 -> frac5
371/129 -> frac6
1/115 -> frac7
53/86 -> frac8
43/53 -> frac9
23/47 -> frac10
341/46 -> frac11
41/43 -> frac12
47/41 -> frac13
29/37 -> frac14
37/31 -> frac15
299/29 -> frac16
47/23 -> frac17
161/15 -> frac18
527/19 -> frac19
159/7 -> frac20
1/17 -> frac21
1/13 -> frac22
1/3 -> frac23
? -> c
c * 2^(2^n) -> n
:::
P(n)
n -> start
n + (n * frac1 - n) * delta(n * frac1, floor(n * frac1)) * delta(start, n) -> n
n + (n * frac2 - n) * delta(n * frac2, floor(n * frac2)) * delta(start, n) -> n
n + (n * frac3 - n) * delta(n * frac3, floor(n * frac3)) * delta(start, n) -> n
n + (n * frac4 - n) * delta(n * frac4, floor(n * frac4)) * delta(start, n) -> n
n + (n * frac5 - n) * delta(n * frac5, floor(n * frac5)) * delta(start, n) -> n
n + (n * frac6 - n) * delta(n * frac6, floor(n * frac6)) * delta(start, n) -> n
n + (n * frac7 - n) * delta(n * frac7, floor(n * frac7)) * delta(start, n) -> n
n + (n * frac8 - n) * delta(n * frac8, floor(n * frac8)) * delta(start, n) -> n
n + (n * frac9 - n) * delta(n * frac9, floor(n * frac9)) * delta(start, n) -> n
n + (n * frac10 - n) * delta(n * frac10, floor(n * frac10)) * delta(start, n) -> n
n + (n * frac11 - n) * delta(n * frac11, floor(n * frac11)) * delta(start, n) -> n
n + (n * frac12 - n) * delta(n * frac12, floor(n * frac12)) * delta(start, n) -> n
n + (n * frac13 - n) * delta(n * frac13, floor(n * frac13)) * delta(start, n) -> n
n + (n * frac14 - n) * delta(n * frac14, floor(n * frac14)) * delta(start, n) -> n
n + (n * frac15 - n) * delta(n * frac15, floor(n * frac15)) * delta(start, n) -> n
n + (n * frac16 - n) * delta(n * frac16, floor(n * frac16)) * delta(start, n) -> n
n + (n * frac17 - n) * delta(n * frac17, floor(n * frac17)) * delta(start, n) -> n
n + (n * frac18 - n) * delta(n * frac18, floor(n * frac18)) * delta(start, n) -> n
n + (n * frac19 - n) * delta(n * frac19, floor(n * frac19)) * delta(start, n) -> n
n + (n * frac20 - n) * delta(n * frac20, floor(n * frac20)) * delta(start, n) -> n
n + (n * frac21 - n) * delta(n * frac21, floor(n * frac21)) * delta(start, n) -> n
n + (n * frac22 - n) * delta(n * frac22, floor(n * frac22)) * delta(start, n) -> n
n + (n * frac23 - n) * delta(n * frac23, floor(n * frac23)) * delta(start, n) -> n
sqrt(-delta(n, start))
The result of any computable function f applied to any integer k can be computed via an appropriate input integer c, and the final value of n will be 2^(2^f(k)).
Motivation
This language matches closely matches the kinds of expressions that the Casio FX-991EX scientific calculator accepts, which is described as “non-programmable”. Since CALC is Turing-complete, this means that (up to memory limitations) the calculator can actually do arbitrary computation. The key differences between CALC and the calculator are:
- There’s no way of specifying the three sections ahead of time. If you want to run a program with an initialization, loop and finalization section, you need to type in the initialization section, press equals, then type in the loop section, repeatedly press equals until an error occurs, and do the same for the finalization section.
- A few built-in functions don’t exist on the calculator. These include:
delta,P,floor,ceil. - Numbers are not represented as standard IEEE 754 floats. Instead, the range is from $\pm 10^{-99}$ to $\pm 9.999999999 \times 10^{99}$.
All the built-in functions in this specification can however be implemented on the calculator. P is unnecessary as the result of every calculation is displayed as output. delta can be implemented by making use of rounding rules:
delta(a, b) = (10^(-99))**abs(a, b)
This is an example of executing the Fibonacci example below on the calculator:
Examples
Truth machine
# Accept input
? -> input
:::
# Print input
P(input)
# If I = 0, exit (sqrt(-1) is undefined)
# If I = 1, there is no error, so repeat indefinitely
sqrt(input-1)
Cat program
? -> input
P(input)
A+B problem
? -> A
? -> B
P(A + B)
Calculating Fibonacci numbers
# Initialise A and B
1 -> A
1 -> B
:::
# Repeatedly compute the next two Fibonacci numbers
P(A)
P(B)
A + B -> A
A + B -> B
Calculating Fibonacci numbers up to a limit
# Initialise A and B
1 -> A
1 -> B
# Used to exit the loop by throwing an error
1 -> iter
? -> maxiter
:::
# Repeatedly compute the next two Fibonacci numbers
P(A)
P(B)
A + B -> A
A + B -> B
iter+1 -> iter
# Will cause MathERROR if iter > maxiter, and so will exit.
sqrt(maxiter - iter)
Listing primes less than a limit
2 -> A
0 -> B
A -> C
100 -> D
:::
P(A * delta(B, 0))
B + (1 - B) * delta(B, 0) -> B
A + delta(B, 1) -> A
C + (A-1 - C) * delta(B, 1) -> C
B + (2 - B) * delta(B, 1) -> B
B + (0 - B) * delta(C, 1) * delta(B, 2) -> B
B + (1 - B) * delta(A/C - floor(A/C), 0) * delta(B, 2) -> B
C - 1 * delta(B, 2) -> C
sqrt(D-A)
Or, more verbosely:
# starting prime number
2 -> num
100 -> limit
# mode is: 0 for printing primes, 1 for incrementing, 2 for checking divisibility
0 -> mode
num -> curr
0 -> divisible
1000 -> maxits
0 -> its
:::
# if in prime printing mode, print and then set to incrementing mode
P(num * delta(mode, 0))
mode + (1 - mode) * delta(mode, 0) -> mode
# if in incrementing mode, add 1 and then switch to divisibility checking mode
# this does nothing if not in incrementing mode
num + delta(mode, 1) -> num
curr + (num-1 - curr) * delta(mode, 1) -> curr
mode + (2 - mode) * delta(mode, 1) -> mode
# divisibility checking mode
# num holds the number we are currently checking divisibility for
# curr holds the candidate divisor
# if curr is 1, then this number is prime. So print this prime.
mode + (0 - mode) * delta(curr, 1) * delta(mode, 2) -> mode
# so now curr is non zero
# how can we tell if curr_ | num?
# if curr_ | num, then delta(num/curr_ - floor(num/curr_), 0) is 1, otherwise it is 0
divisible + (delta(num/curr - floor(num/curr), 0) - divisible) * delta(mode, 2) -> divisible
# if curr_ | num, then switch back to incrementing mode.
mode + (1 - mode) * divisible * delta(mode, 2) -> mode
# otherwise, remain in candidate testing mode but decrement current by one
curr - 1 * delta(mode, 2) -> curr
its+1 -> its
sqrt(maxits - its)
Implementations
go-calc
go-calc is a working CALC interpreter written in Go.