Talk:Fractran

From Esolang
Jump to navigation Jump to search

Programming Techniques

This section builds on the information found at Good Math, Bad Math. Read there first.

Fractran is a register machine with infinite registers that can take integer values from 0 to infinity. A Fractran program is equivalent to this: 

BEGIN:
Instruction 1
Instruction 2
Instruction 3
...
END

where the only instruction available is of the form: 

if R_A >= M [ and R_B >= N [ and ... ] ] then
  R_A -= M
  [ R_B -= N
    ... ]
  [ R_X += P
    ... ]
  goto BEGIN

This kind of instruction can be represented by a shorthand form like this: 

ABB;XXXY

which means "if (A>=1 and B>=2) then { A-=1; B-=2; X+=3; Y+=1; goto BEGIN }". If the register increments/decrements are large, an equivalent notation can be used like this: 

AB2;X3Y

which means the same thing.

Note that instructions where a register is on both sides of the semicolon won't work. 

AABB;BX

does not mean "if (A>=2 and B>=2) then { A-=2; B-=1; X+=1; goto BEGIN }". Instead, it means the same thing as 

AAB;X

In other words, the registers always cancel until they are only left on one (or neither) side of the semicolon. If you don't understand why, you don't understand Fractran well enough yet. Go read Good Math, Bad Math again. Don't forget to read the comments section.

So, a simple Fractran program which calculates B = floor(A/2) could look like this 

A;BC  # Put A's initial value in B and C
CCB;  # While C>=2 & B>=1, decrement C twice and B once
CB;   # If C>=1 & B>=1, decrement C once and B once

This program in Fractran format looks like 

(3*5)/2, 1/(3*3*5), 1/(3*5)
 =>
15/2, 1/45, 1/15

Let's try something harder. This modulo program calculates C=A%B for all A>0, B>0. Start on line 1 and follow the comments to follow the flow of the program. 

FCE;BG  #  4. lines 4 & 5 will toggle F & G while restoring B to
GCE;BF  #  5.    its original value and clearing C,E&E
F;A     #  6. only one of F & G is on, so either line 6 or 7 will restore the decrement that
G;A     #  7.    occurred to A on line 3. After line 6/7 we are back to line 1.
B;D     #  1. the first order of business is to move B into D and E
AD;CE   #  2. decrement A & D while A>0 & D>0. C keeps track of the decrements. E is a flag.
A;F     #  3. F is a flag to indicate that we aren't done because A>0. This takes us up to line 4.
HD;I    #  9. use H & I just like F & G in lines 4 & 5
ID;H    # 10.    to clear D.
HE;I    # 11. use H & I to clear E.
IE;H    # 12.
H;      # 13. clear H
I;      # 14. clear I
D;H     #  8. if D!=0, then we need to clear the E flag. Set the H flag
EC;     # 15. if E was not cleared by lines 8-14, then we want to return 0, not the original B.

This program in Fractran format looks like 

(3*19)/(17*5*11*13), (3*17)/(19*5*11*13), 2/17, 2/19, (7*11)/3, (5*13)/(2*7), 17/2, 1/11,
  29/(23*7), 23/(29*7), 29/(23*13), 23/(29*13), 1/23, 1/29, 23/7, 1/(13*5)
 =>
57/12155, 51/13585, 2/17, 2/19, 77/3, 65/14, 17/2, 1/11, 29/161, 23/203, 29/299, 23/377,
  1/23, 1/29, 23/7, 1/65

--Nthern 23:43, 27 June 2007 (UTC)

Hey, I already made a symbolic notation for Fractran, Bag. Although I suppose yours is more compact. --Ørjan 09:57, 28 June 2007 (UTC)
Yeah, good work on that. I developed the notation above for Fractran algorithms before I saw Bag and just continued with it here. The two notations are equivalent, it's just a matter of taste. With my limited brain power, I prefer to see each instruction on one line (which I agree is perfectly valid in Bag) and see the "trigger registers" first in the instruction. Bag, OTOH has more ways to create expressions. BTW, as long as you're paying attention to it, there appears to be a hanging sentence on your Bag page. The sentence starts "In this form, it is", and is never completed. --Nthern 15:03, 28 June 2007 (UTC)
Thanks, I don't remember what I was going to say so I just deleted it for now. I also found I had misspelled the entities for angle brackets. --Ørjan 17:34, 28 June 2007 (UTC)

This is pretty much the notation that I like to use. Although, if you write \ instead of ;, then your statements really are fractions. I have some experience of Fractran programming, here's my version of your modulo program :-) 

F\E     # restore flag
EE\B    # T2. Other part of T routine.
ED\BF   # S1. Move complement back into B.
E\A     # S2. Return from subroutine, correcting A.
AB\D    #  1. Subtract as much from A of B as possible, store complement of B in D.
A\E     #  2. If some of A left, call subroutine S, to restore B.
        #     at this point, A=0, D=a%b (or b), B=b-D, where a and b are the original values of A and B.
BD\EEC  # T1. So, if B is not zero, D=a%b, and we want to move this to C, otherwise, C=0 already, which is what we want.
B\      #  3. And finally clear B,
D\      #  4. and D.

--Devin 15:39, 30 June 2007 (UTC)

Very cool. I never thought of the "\", but I like it. After I posted my mod routine, I later shaved it down to 10 instructions (My E flag above is completely useless). But you best me with 8 instructions :-).--Nthern 22:49, 10 July 2007 (UTC)
9 instructions, not 8, so your 10 is not far off. My prime program is 9 instructions too --- maybe you need 9 instructions to do anything interesting in FRACTRAN :-) --Devin 10:29, 12 July 2007 (UTC)

A Fractran I/O Protocol

Lazy K inspired these thoughts. The way I see it, Lazy K is a protocol for achieving I/O when using Combinatory logic as a program engine. The input and output are lists of Church numerals representing character bytes. Input may be incomplete as the program is running; when the program asks for more input the implementation will block until more input (if any) is available.

The way Combinatory logic works, part of the output list may be complete while its tail is still under construction. As the output list is built by the program, the implementation spits out the characters as soon as possible. Thus, synchronized I/O is achieved. End of input is represented by endless 256's in the input list, and the program is terminated by the first 256 in the output list.

I believe a similar protocol can be devised using Fractran as a program engine. In this protocol, the input to the Fractran program is always 2*3^X where X is ((byte 1) + 256*(byte 2) + 256^2 * (byte 3) + ...). The "2" is there in the "2*3^X" because otherwise a program without any I/O input would never run. The implementation keeps track of the calculations that have been done so far (naturally), and if the program encounters a fraction with more 3's in the denominator than there are in the current state then the implementation blocks while getting more input. If there is no more input, the program state is unmodified and the program continues.

Output is similar, but in powers of 5. If the implementation blocks while waiting for more input, any powers of 5 in the current state will be output first, and the implementation will keep track of the output performed so far. This achieves synchronous I/O.

Using the above protocol, here is cat: 

5/3

And here is "Hello, world!\n": 

5^205469705004861725972941750691144/2

(e.g. 5^(72*256^0 + 101*256^1 + 108*256^2 + 108*256^3 + 111*256^4 + 44*256^5 + 32*256^6 + 87*256^7
         + 111*256^8 + 114*256^9 + 108*256^10 + 100*256^11 + 33*256^12 + 10*256^13)/2)

This program prints "Hi", waits for a keypress, and prints "!\n": 

7*5^(72+256*105)/2 11/21 5^(33*256^2+10*256^3)/11

There is a problem with the above protocol: Output can be forced by a block while waiting for input, and the final program state can have a different byte(s) in the output. Consider this program which prints an "A", inputs a byte, and prints a "C": 

7*5^65/2 11/21 5^(1+67*256)/11

The final state is 5^(66+67*256), or "BC", but an "A" was output instead of a "B". This may be more of an "inelegance" than a problem, but it bugs me. At this time, the only solution I can think of is to zero any powers of 5 in the current state any time output is printed, but that seems highly problematic (and inelegant) in itself.

--Nthern 22:49, 10 July 2007 (UTC)

I/O encoding for FRACTRAN as a computational model

For computing partial functions f: N -> N in FRACTRAN, the simplest generally applicable i/o encoding scheme that I've found in the literature is to encode the argument x as the initial value 2^(x+1) and to encode f(x) as the final value 3^(f(x)+1) upon halting (the function being undefined at x if the program does not halt with a final value of this form). This extends to n-ary functions by using the first n primes to encode the arguments, and the (n+1)th prime to encode the function value. NB: The "+1" in each exponent is to properly encode 0.
-- r.e.s. 15:07, 26 December 2009 (UTC)

JavaScript implementation

This is a implementation in JavaScript: 

(n,p,f=_=>p.some(([x,y])=>n*x%y?0:n=n*x/y)?f():n)=>f()

The first argument is the initial number, and the second argument is a list of fractions, with each fraction being given as a list consisting of the numerator and then the denominator. I started with the one given on Stack Overflow, and then shortened it. (If you can shorten it more, then, to do so.) --Zzo38 (talk) 06:54, 22 October 2017 (UTC)

Python Interpreter

 
Program = [455/33, 11/13, 1/11, 3/7, 11/2, 1/3] # This is the list of fractions in the program.
Input = 36 # This is the input


def Fractran(list, input):
	index = 0
	while index < len(list):
		if ((input * list[index])==(int(input * list[index]))):
			return int(Fractran(list, (input * list[index])))
		else:
			index = index + 1
	return input


Output = Fractran(Program, Input)

print(Output)

Jan Gamecuber (talk) 15:09, 28 April 2022 (UTC)

Retrieved from "https://esolangs.org/w/index.php?title=Talk:Fractran&oldid=95246"