4 ms·

John Conway's FRACTRAN, a ridiculous, yet surprisingly deep language (2020)

144 points by warrenm 3y ago

dang 3y ago
Related: Building Fizzbuzz in Fractran from the Bottom Up (2016) - https://news.ycombinator.com/item?id=28448283 https://news.ycombinator.com/item?id=28448283 - Sept 2021 (5 comments) Open Problems in Communication and Computation (1987) [pdf] - https://news.ycombinator.com/item?id=26074413 https://news.ycombinator.com/item?id=26074413 - Feb 2021 (2 comments) Remembering John Conway's FRACTRAN - https://news.ycombinator.com/item?id=23142232 https://news.ycombinator.com/item?id=23142232 - May 2020 (14 comments) Building FizzBuzz in Fractran from the Bottom Up - https://news.ycombinator.com/item?id=22866303 https://news.ycombinator.com/item?id=22866303 - April 2020 (1 comment) FRACTRAN - https://news.ycombinator.com/item?id=14202367 https://news.ycombinator.com/item?id=14202367 - April 2017 (8 comments) Building Fizzbuzz in Fractran from the bottom up - https://news.ycombinator.com/item?id=11894141 https://news.ycombinator.com/item?id=11894141 - June 2016 (3 comments) In FRACTRAN, every program is a list of functions - https://news.ycombinator.com/item?id=10091053 https://news.ycombinator.com/item?id=10091053 - Aug 2015 (1 comment) FRACTRAN - the esoteric programming language invented by John H Conway - https://news.ycombinator.com/item?id=3119937 https://news.ycombinator.com/item?id=3119937 - Oct 2011 (1 comment)
gfody 3y ago
I think the world has yet to feel the weight of this great man's contributions. the monstrous moonshines and the freewill theorem seem mind blowing and not very well known at all.
jonahx 3y ago
A FRACTRAN interpreter in FRACTRAN, in 24 fractions: https://codegolf.stackexchange.com/a/246682/15469 https://codegolf.stackexchange.com/a/246682/15469
- VHRanger 3y ago
  Thanks, the fact that FRACTRAN didnt bootstrap its own interpreter was the reason I didnt use the language seriously for programming!
- boothby 3y ago
  related: FRACTRAN to brainfuck translator https://codegolf.stackexchange.com/questions/5210/convert-fractran-into-brainfuck https://codegolf.stackexchange.com/questions/5210/convert-fr...
peterderivaz 3y ago
Project Euler challenge involving Fractran: https://projecteuler.net/problem=308 https://projecteuler.net/problem=308
deleted 3y ago
[deleted]
nerpderp82 3y ago
I miss raganwald, I loved it when their posts and comments were blowing up HN.
- warrenm 3y ago
  I only discovered the site recently, but it seems he still posts: raganwald.com
optimalsolver 3y ago
See also: "Building Fizzbuzz in Fractran from the Bottom Up (2016)" [0] I'll repost my comment from that thread: >For some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... [0] https://news.ycombinator.com/item?id=28448283 https://news.ycombinator.com/item?id=28448283
- jfoutz 3y ago
  I played a lot of the original civ as a kid. I'd be super disappointed if I didn't get railroads before 0. rush pyramids, democracy, tons of tiny self supporting towns. That game didn't really offer a way to convert other cities and towns sort of invasion. so I'd inevitably turn evil and conquer the world. Good times.
- jameshart 3y ago
  In principle Minsky Machines are very similar to abacus algorithms. They do seem in the reach of ancient mathematics. Reducing them to FRACTRAN requires dealing with some VERY big numbers for not a lot of benefit. You’re probably dealing with those on an abacus anyway…
- tourgen 3y ago
  Who really knows what was in the Library of Alexandria before it was burned for the 6th or 7th time.
  - warrenm 3y ago
    Probably a bunch of recipes But you could only read them after you unscrolled 50 feet of story about how much they enjoyed the buffet platters at Bel's temple as a kid before watching the sacrifices
oh_sigh 3y ago
Has anyone made attempts at writing FRACTRAN programs which would calculate `78 * 5^(x - 1)` and `2^x`?
- ravenhappy 3y ago
  Why?
  - oh_sigh 3y ago
    Those are the necessary pre and post processing steps that you need to compute outside of the FRACTRAN system for the fibonacci example from the article. If you could do those steps the entire process would be self contained, which you should be able to if the claim of yielding all possible computations is correct. (actually, it is log2(x) that would need to be implemented and not 2^x, but my point remains).
    - anonymoushn 3y ago
      One reasonable design equivalent to FRACTRAN is to do away with the divisibility checks and store an array of counts of prime factors. Then you could put the input in the 5s slot and read the output from the 2s slot without computing the values of these expressions.
siraben 3y ago
A few years ago, I wrote a compiler for FRACTRAN written in Haskell[0] (translated from Common Lisp) with an associated blog post[1]. Using the tagless-final style you can write a simple program like this: sumTo :: FracComp repr => Integer -> [repr [Rational]] sumTo n = [addi "c" 0, addi "n" n, while (jge "n" 0) [adds "c" "n", subi "n" 1]] And the compiler would output this: λ> runAssembler (sumTo 10) -- Program length: 31 Right [847425747 % 2,13 % 3,19 % 13,11 % 3,11 % 29,31 % 11,41 % 31,23 % 11,23 % 47,2279 % 23,59 % 301,59 % 41,67 % 413,329 % 67,61 % 59,73 % 61,83 % 73,71 % 61,71 % 97,445 % 71,707 % 89,103 % 5353,103 % 83,109 % 5459,5141 % 109,107 % 103,113 % 749,113 % 19,131 % 113,29 % 131,127 % 113] λ> runAsm (sumTo 10) [(Prime 97,55),(Prime 107,1)] [0] https://github.com/siraben/hasktran https://github.com/siraben/hasktran [1] https://siraben.dev/2020/02/26/translating_cl.html https://siraben.dev/2020/02/26/translating_cl.html
marcodiego 3y ago
TIL John Conway died during the COVID pandemic. I'm as shocked as someone who just discovered John Lennon was killed. :(
- alanbernstein 3y ago
  Probably the biggest celebrity death of the pandemic, IMO. I believe it was on the nyt front page.
breck 3y ago
He mentions a CD-ROM version of Society of Mind (https://web.media.mit.edu/~minsky/Voyager.html https://web.media.mit.edu/~minsky/Voyager.html). I had never heard of it. Does anyone know if the video content from that CD-ROM is available online?
- rootbear 3y ago
  There is a link what appears to be part one in the article. https://www.youtube.com/watch?v=-Hx8RixhoOM
  - breck 3y ago
    Oh I missed that. Thank you so much!
bmacho 3y ago
Very long article, and IMO it doesn't justify the "surprisingly deep" claim. Disappointing. Can I have my time back? tl;dr: a 'usage' of fractran is that fratcran programs are collatz-like sequences, thus, the behaviour of collatz-like sequences is undecidable.

144 points by warrenm 3y ago

dang 3y ago

Related: Building Fizzbuzz in Fractran from the Bottom Up (2016) - https://news.ycombinator.com/item?id=28448283 https://news.ycombinator.com/item?id=28448283 - Sept 2021 (5 comments) Open Problems in Communication and Computation (1987) [pdf] - https://news.ycombinator.com/item?id=26074413 https://news.ycombinator.com/item?id=26074413 - Feb 2021 (2 comments) Remembering John Conway's FRACTRAN - https://news.ycombinator.com/item?id=23142232 https://news.ycombinator.com/item?id=23142232 - May 2020 (14 comments) Building FizzBuzz in Fractran from the Bottom Up - https://news.ycombinator.com/item?id=22866303 https://news.ycombinator.com/item?id=22866303 - April 2020 (1 comment) FRACTRAN - https://news.ycombinator.com/item?id=14202367 https://news.ycombinator.com/item?id=14202367 - April 2017 (8 comments) Building Fizzbuzz in Fractran from the bottom up - https://news.ycombinator.com/item?id=11894141 https://news.ycombinator.com/item?id=11894141 - June 2016 (3 comments) In FRACTRAN, every program is a list of functions - https://news.ycombinator.com/item?id=10091053 https://news.ycombinator.com/item?id=10091053 - Aug 2015 (1 comment) FRACTRAN - the esoteric programming language invented by John H Conway - https://news.ycombinator.com/item?id=3119937 https://news.ycombinator.com/item?id=3119937 - Oct 2011 (1 comment)

gfody 3y ago

I think the world has yet to feel the weight of this great man's contributions. the monstrous moonshines and the freewill theorem seem mind blowing and not very well known at all.

jonahx 3y ago

A FRACTRAN interpreter in FRACTRAN, in 24 fractions: https://codegolf.stackexchange.com/a/246682/15469 https://codegolf.stackexchange.com/a/246682/15469

VHRanger 3y ago
Thanks, the fact that FRACTRAN didnt bootstrap its own interpreter was the reason I didnt use the language seriously for programming!
boothby 3y ago
related: FRACTRAN to brainfuck translator https://codegolf.stackexchange.com/questions/5210/convert-fractran-into-brainfuck https://codegolf.stackexchange.com/questions/5210/convert-fr...

peterderivaz 3y ago

Project Euler challenge involving Fractran: https://projecteuler.net/problem=308 https://projecteuler.net/problem=308

deleted 3y ago

[deleted]

nerpderp82 3y ago

I miss raganwald, I loved it when their posts and comments were blowing up HN.

warrenm 3y ago
I only discovered the site recently, but it seems he still posts: raganwald.com

optimalsolver 3y ago

See also: "Building Fizzbuzz in Fractran from the Bottom Up (2016)" [0] I'll repost my comment from that thread: >For some reason this makes me imagine an alternate history sci-fi universe where Pythagoras (famous for his love of fractions) invents FRACTRAN. Then Archimedes builds a mechanical computer to execute those programs, and one of the successors of Alexander The Great puts the computer to use in warfare and conquers the world. Science is accelerated so that nuclear physics are invented by the time Jesus is born... [0] https://news.ycombinator.com/item?id=28448283 https://news.ycombinator.com/item?id=28448283

jfoutz 3y ago
I played a lot of the original civ as a kid. I'd be super disappointed if I didn't get railroads before 0. rush pyramids, democracy, tons of tiny self supporting towns. That game didn't really offer a way to convert other cities and towns sort of invasion. so I'd inevitably turn evil and conquer the world. Good times.
jameshart 3y ago
In principle Minsky Machines are very similar to abacus algorithms. They do seem in the reach of ancient mathematics. Reducing them to FRACTRAN requires dealing with some VERY big numbers for not a lot of benefit. You’re probably dealing with those on an abacus anyway…
tourgen 3y ago
Who really knows what was in the Library of Alexandria before it was burned for the 6th or 7th time.
- warrenm 3y ago
  Probably a bunch of recipes But you could only read them after you unscrolled 50 feet of story about how much they enjoyed the buffet platters at Bel's temple as a kid before watching the sacrifices

oh_sigh 3y ago

Has anyone made attempts at writing FRACTRAN programs which would calculate `78 * 5^(x - 1)` and `2^x`?

ravenhappy 3y ago
Why?
- oh_sigh 3y ago
  Those are the necessary pre and post processing steps that you need to compute outside of the FRACTRAN system for the fibonacci example from the article. If you could do those steps the entire process would be self contained, which you should be able to if the claim of yielding all possible computations is correct. (actually, it is log2(x) that would need to be implemented and not 2^x, but my point remains).
  - anonymoushn 3y ago
    One reasonable design equivalent to FRACTRAN is to do away with the divisibility checks and store an array of counts of prime factors. Then you could put the input in the 5s slot and read the output from the 2s slot without computing the values of these expressions.

siraben 3y ago

A few years ago, I wrote a compiler for FRACTRAN written in Haskell[0] (translated from Common Lisp) with an associated blog post[1]. Using the tagless-final style you can write a simple program like this: sumTo :: FracComp repr => Integer -> [repr [Rational]] sumTo n = [addi "c" 0, addi "n" n, while (jge "n" 0) [adds "c" "n", subi "n" 1]] And the compiler would output this: λ> runAssembler (sumTo 10) -- Program length: 31 Right [847425747 % 2,13 % 3,19 % 13,11 % 3,11 % 29,31 % 11,41 % 31,23 % 11,23 % 47,2279 % 23,59 % 301,59 % 41,67 % 413,329 % 67,61 % 59,73 % 61,83 % 73,71 % 61,71 % 97,445 % 71,707 % 89,103 % 5353,103 % 83,109 % 5459,5141 % 109,107 % 103,113 % 749,113 % 19,131 % 113,29 % 131,127 % 113] λ> runAsm (sumTo 10) [(Prime 97,55),(Prime 107,1)] [0] https://github.com/siraben/hasktran https://github.com/siraben/hasktran [1] https://siraben.dev/2020/02/26/translating_cl.html https://siraben.dev/2020/02/26/translating_cl.html

marcodiego 3y ago

TIL John Conway died during the COVID pandemic. I'm as shocked as someone who just discovered John Lennon was killed. :(

alanbernstein 3y ago
Probably the biggest celebrity death of the pandemic, IMO. I believe it was on the nyt front page.

breck 3y ago

He mentions a CD-ROM version of Society of Mind (https://web.media.mit.edu/~minsky/Voyager.html https://web.media.mit.edu/~minsky/Voyager.html). I had never heard of it. Does anyone know if the video content from that CD-ROM is available online?

rootbear 3y ago
There is a link what appears to be part one in the article. https://www.youtube.com/watch?v=-Hx8RixhoOM
- breck 3y ago
  Oh I missed that. Thank you so much!

bmacho 3y ago

Very long article, and IMO it doesn't justify the "surprisingly deep" claim. Disappointing. Can I have my time back? tl;dr: a 'usage' of fractran is that fratcran programs are collatz-like sequences, thus, the behaviour of collatz-like sequences is undecidable.