Fractran++
Proposal of Standard for Fractran++ Language Specifications 1.0.
By DrK3055A.
ABSTRACT
This document describes briefly the specifications of Fractran programming language. Once the Fractran language is documented, there follows a definition of the upgraded Fractran language called Fractran++. There are described some aspects of this new language, as well as some suggestions for implementing Fractran++ compilers and interpreters. The target is to create a full functional language, by the use of just numeric notations and fractional symbols.
Overview of the Fractran Language
Semantics and notations
The fractran algorithm was created by J.H.Conway (1987) as a mathematical game that encodes a state machine model inside a list of fractions. The key is that every state present at the accumulator (N), often refered to as fractran set of variables, is encoded within the exponent of each of the prime factors in the number stored at N. The system consists of these elements:
- A variable N that acts like an accumulator where the state variables are stored as exponets
of prime factors.
- A list of fractions F[1,2,...,n] that represent the code to be executed.
- A separator that acts as the boundary for each fraction in the list, usually the "," (comma) and/or the space character.
When using the fraction form for rationals, numerator and denominator can be an expression of prime factors, or just a list of exponents. When choosing such representations, then numerators and denominators must be enclosed in parentheses and angle brackets, respectively.
Operation
The whole code consists of a list of numbers separated by a separator string. The Input is the initial value of N, and the Output is N when all the command have been processed.
Then a test procedure will begin in order to determine the next operation. One command that is represented by a rational number, is executed if and only if when N is multiplied by that rational, it result in an integer. In the case the rational number is represented like a fraction, it must be in the irreducible form. When searching for a command that pass the test, once this is found, then N is substituted by the result integer value, and then the seek will be set to the begining of the list. The program finalizes when there are no more fractions (commands) left to be executed.
Language considerations
At first place, one can see that the whole execution is a while loop and a switch/case statement. One case for each fraction. The default case will break the execution of the while loop. Also, the only choices for Input and Output are the initial and final states of N. This is a hard restriction for a flexible language capable of implementing any reasonable algorithm. Therefore we should extend this language in order to set more control and let some interaction with the user. Also there is a need for conditional jumps, that would be the equivalent of jumping among various switch statements.
Need for extensions to Fractran. The Fractran++ as a high level language
Special cases.
We have mentioned that a command execution is a multiplication of an integer and a rational. If the rational or the number N are 0 then the execution would enter into an infinite loop, because the consequent multiplications will result to 0. Therefore we need to set an exception to this case. We define any rational with the value of 0, as being a user Input, to set up the value of N. If the rational is in the form of a fraction, then the denominator will tell the format of the data entered. Proposed formats are:
- Input is the value of N.
- Input is a sequence defining the exponents of the prime factors that compose N.
- Input is a Character converted to the value of N.
- Input is a string where every char in the string is one of the prime factor exponents.
- [...]
Besides, there is a case where a rational represents an infinite value. This special case, as it won't give us a useful result, can be used to perform Output operation. If the rational is in the form of a fraction, then there is a 0 at the denominator, and the numerator will tell us the format for Output, in correspondence to the values above mentioned for Input.
Notice that as long as the Output command doesn't modify N, the seek for a valid command must be resumed from the next fraction to the Output command, and not resetted to the begining of the list.
Both examples of Input and Output are 0/3 and 1/0 respectively.
There is a case in Output, with format number 219. This translates to 0xDB in hexadecimal notation. This case is used for DeBugging the code. Whenever a 219/0 command is found. Then a set of useful information will be printed out, such as the current N, prime factors of N, next fraction to be executed, the function call stack, and the thread/object ID for the current execution instance.
There is another special case, when a rational represents a NaN value (0/0). This value is reserved for defining an entry point to a function.A function will enter based up on the count of NaN values that are present at the Fractran++ program, and it will return when the execution finds a subsequent NaN value. If a NaN is found at the execution flow of the main program, then it will be inmediately terminated. A NaN can be assumed to work as a separator for sublists of fractions inside the main list in a Fractran++ program.
The fraction set as a superset of reducible equivalent fractions
The specifications of Fractran state that every fraction must be in an irreducible form, because if some are reducible, the test criteria for executing might differ from each equivalent (i.e, reducible fraction sets that can be reduced to a same rational). For avoiding errors, a fractran interpreter should detect such a case and operate in order to reduce the fraction to an irreducible form. This is automatically acomplished by decomposing each numerator and denominator in the form of prime factors, and then perform a substraction of numerator and denominator. The result vector still represents the fractional (negative exponents represent the denominator) but common factors are cancelled because of the substraction, thus yielding a rational, which when converted to a fraction again, will render an irreducible equivalent.
Then, we can sumarise that every set of reducible fractions can be reduced to just an irreducible one (the canonical representation of the set). Then, those extra representations can be used to extend the Fractran language in order to add more power for processing.
In Fractran++, every fraction is reduced to the canonical representation. But whether a reducible fraction is detected, then the exponent of the common prime factor will be stored as a special case for selecting extended commands (however, the reduced fraction is executed as normal). Those cases can be, most of the times for a certain prime factor in N:
- The new exponent will be a user Input integer.
- The exponent is printed as an integer.
- The new exponent will be a user Input character.
- The exponent is printed as a character.
- Function number refered by the exponent is called. The return value will be passed through N. This is an indirect Call.
- The main sublist of fractions, and the one refered to as a function by the exponent, are swapped together. This is the effect of an indirect Jump command.
- This is a bifurcation (multithreading) of the execution flow. One of the N will keep the last value before execution of the fraction, and the other will follow the normal execution flow.The program will terminate when the last thread is terminated.
- This is both the combination of 6 and 7, thus creating a new thread that holds a copy of the whole program, treated as another main program (following the swapping rules of 6). This is called an Object. When the execution of the new thread is terminated, then the object is destroyed. A program is terminated when all the objects are destroyed (including the main object).
- ,...: to do in further revisions of the language.
Need for control at the execution flow. Conditional jumps.
We can define a special condition for performing direct conditional jumps. In a normal Fractran implementation, there is no special meaning for the sign of a fraction. Hence, we can use this to create a special definition for negative fractions. (A negative fraction is one where the numerator or the denominator, but not both, is a negative expression).
Whenever a negative fraction is encountered, if N can be divided by the denominator (but this division is not performed, this is just a check), then the main sublist of fractions, and the one refered to as a function by the numerator, are swapped together. This is a conditional Direct Jump.
Implementation proposals.
While: The main structure block of a Fractran++ program.
As there has been stated above, a Fractran program is contained inside a While loop. With the Extensions defined in Fractran++, we must consider an interpreter that can create many while loops (one for each function) and even create some of them dynamically, as soon as objects and threads are created.
Decoding fractions depending up on the action
This is the method for detecting special cases. A Fractran++ interpreter must be fully compatible with a normal Fractran program. However, some notation might be introduced for initializing the N variable. If there is a number that is not a fraction (i.e. an integer), inside the fraction list (or a sublist considering a list inside of a function or a subset), then it will be used to initialize N at the first run. If no integer value is found inside the main list, then the program must initialize N by requesting an Input from the user. When a minus sign is detected in the representation of a fraction, then this is proceeded like explained in 3.3 (But remember that a negative sign at both numerator and denominator are cancelled, so they represent a positive fraction).
If there is found a 0 at numerator or denominator, proceed like explained in 3.1.
An interpreter must check for common prime factors at both numerator and denominator. The multiplicity of such factors determine the extended command to execute. For example, by executing this fraction: <3 1>/<2 0> = (2^3*3^1)/(2^2) = 24/4, then the fraction will be reduced to 6/1 (this is a different representation than just 6, because 6/1 means that this is a fraction and not an initializer of N). But as we see there is a common factor of 2^2. Then the factor indicates the position of the exponent at N, and the exponent will indicate the command, in this case (2), once the fraction is executed, the exponent of the factor 2 at N (the first prime factor) is printed out as an integer.
Implementing fractions as factor decomposition to optimize the execution
A full analysis for a fractional notation can lead us to the followin structure for handling the commands:
- struct FppCmd {
- long exponents[];
- bool Jump, Input, Output;
- int ExtendedCmd;
- };
This structure stores the set of exponents to prime factors, representing the irreducible form of that fraction. Each of the boolean values indicate if there is a special case for a conditional jump or an Input/Output/Debug operation. The format for the I/O command or the relative offset of the Jump is stored at the ExtendedCmd field. If none of the boolean flags are set, but ExtendedCmd holds a value other than 0, then ExtendedCmd contains the multiplicity of the common factor in a reducible fraction, as stated at 3.2, then the procedure is applicable for each different command.
Example code
This is a Hello World written in Fractran++:
- 3,-1/2,(2*37)/3,0/0,<71 101 108 108 111 32 87 111 114 108 100 0>/37,4/0
References
The idea of Fractran++ was created by DrK3055A, and was originated from the discussion that derived from the comments of this article:
http://scienceblogs.com/goodmath/2006/10/28/more-fractran-a-trivial-interp-1/
Thanks to Xanthir for the idea, and special thanks to MarkCC, because none of this could be possible without his Fractran analisys at his blog.