CALC

== 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 </code>#</code> 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)
(whitespace is not important here)
=== 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 up to 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.
Category:Languages Category:Turing complete Category:Implemented