Pathological Programming with Primes (REPOST)

I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any pathological programming ’round these parts, so I’m going to repost some of my favorites.

Today’s pathological language is my personal all-time favorite pathological monstrosity. It’s an incredibly combination of perfect simplicity and complete incomprehensibility. It’s based on a piece of work called Fractran by John Conway of game theory fame. It’s a really fascinating bugger; absolutely insanely difficult to program in, but based on one of the most bizarrely elegant concepts of computation that I’ve ever seen. It’s amazing that this is Turing complete. It’s not a real programming language in the sense of being able to write practical programs; it’s more of a simple theoretical computational model which has been implemented as a
language.

It’s based on the idea of numbers as products of prime factors. As you should remember from elementary school, every number can be represented by a collection of prime numbers that, multiplied together, produce the number. For a few examples:

  • 24 = 2×2×2×3, or 23×31
  • 291 = 3×97
  • 1800 = 5×5×3×3×2×2×2=52×32×23

Conway figured out that using something based on that concept, you can express any computable function using nothing but a list of positive fractions.

Every computation takes a single integer I as input, and operates by repeatedly doing the following:

  1. Set f equal the first fraction in the list.
  2. Set p=f×I.
  3. If p is an integer, then set I=p, and go back to step 1.
  4. Otherwise, set f to the next fraction in the list, and go back to step 2.

When you get through the entire list without any of the multiplications producing an integer, then the computation halts.

That, my friends, is Turing complete.

Let’s look at an example. How would you implement basic multiplication in Fractran?

385/13, 13/21, 1/7, 3/11, 7/2, 1/3

To make it a tad easier to follow, let’s factorize the numbers that form the fractions:

(7×11×5)/13, 13/(3×7), 3/11, 7/2, 1/3

How is this a multiplication program? If you take any integer I which is the product of 2a and 3b, then running it through here will produce the number 5a×b.

Let’s try it: take 24×33=432. It’ll be easiest to follow if we use the prime factorings.

  1. I=24×33; f=385/13. That won’t be an integer; 13 isn’t a factor of I.
  2. f=13/(3×7). That won’t be an integer, because 7 isn’t a factor of I.
  3. f=3/11. That won’t be an integer, because 11 isn’t a factor of I.
  4. f=7/2. That will be an integer, 23×33×7.

  5. I=23×33×7; f=385/13. Not a prime, because 13 isn’t a factor of I.
  6. f=13/(3×7). That will be an integer; I=13×23×32… By now, you should have a basic feel for what’s going on, so I’m going to start skipping the steps where I×f is not an integer.
  7. f=385/13, I becomes 7×11×5×23×32
  8. f=13/(3×7), I becomes 13×11×5×23×3.
  9. f=(7×11×5)/13, I becomes 7×112×52×23×3.
  10. f=13/(3×7), I becomes 13×112×52×23.
  11. f=(7×11×5)/13, I becomes 7×113×53×23.

It keeps going like that. Let’s analyze it to see what’s really going on.

the 7/2 fraction swaps a factor of 2 for a factor of 7. That’s basically removing a factor of two, which means subtracting 1 from a; and then adding in the 7 is keeping track of the fact that we haven’t yet added b to the result to match the subtraction of 1 from a. the 13/(3×7) rule allows us to start the process of adding b to the result. It removes one three, and the placeholder that says we subtracted one from a; and adds in a placeholder to say that we’ve removed one three, but haven’t finished adding. the (7×11×5)/13 rule says that if we’ve removed a three, we can add one to the exponent of five; and then we also need to add placeholders to continue the addition: we’ve adding one to the result, but we need to add b to the result. So we’re effectively subtracting one from b in order to keep track of the fact that we’ve done that much of an addition of b to the result. 3/11 says that if the
first two rules didn’t work, then we’ve finished an addition, we we want to re-add 1 to b, in order to restore it to its original value. The other rules have added one 11 for each time we subtracted one from b, so this will restore b. Finally, if get get to the 1/3 rule, it means that we’ve removed all of the 2s, which means we’ve completed the multiplication. So we want to remove the b leaving the result. Why is this turing complete? It should be pretty easy to see, once you get a sense of what’s going on. Prime numbers are basically variables – each prime number holds an integer value (its exponent). The factors of the denominators do two things: subtract values from a variable, and operate as statement guards determining what statements are executable. In terms of control flow, the end result is something that’s actually quite similar to Version. The primes that aren’t really being used as variables are the complement of the “ignore” set.

Evil, huh?

While researching this post, I discovered (via mathworld) that Conway figured out a way of writing an astonishing prime number generator in Fractran. If you take the following sequence as a fractran program, in the numbers that it generates, the exponent on 2 in every number that it generates will always be prime.

17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13,
13/11, 15/2, 1/7, 55/1

Definitely the most incomprehensible prime number generator that I’ve ever seen.

For your further fun and edumication, following are two complete Fractran interpreters! The first is one that I wrote in Scheme, and the second is a Haskell implementation which was written by a commenter on the original version of this post under the name “Psuedonym”.

;; A Trivial Fractran Interpreter
;;
;; Copyright 2006 Mark C. Chu-Carroll
;; http://scienceblogs.com/goodmath
;;
;; You're welcome to do anything you want with this code as long
;; as you keep a copy of this header to identify the original source.
;;
;; This program runs a fractran program. A fractran program is a list
;; of fractions. The fractions are represented by a list of two integers:
;; the numerator, and the denominator. For example, the classic fractran
;; multiplication program could be written:
;;     ((385 13) (13 21) (1 7) (3 11) (7 2) (1 3))
;; or:
;;     (((* 7 11 5) 13) (13 (* 3 7)) (1 7) (3 11) (7 2) (1 3))
;;
;;
;; To run a program until it terminates, call (run-fractran program input).
;; This will return a list; the car of the list will be the result of
;; running the program, and the cdr will be a trace of the executions in the
;; form of a list of the fractions that ran at each step.
;;
;; To run a program for a specific maximum number of steps, call
;; (run-fractran-bounded program input maxsteps)
;;
(define (step-fractran fract int)
  (if (equal? fract ()) 
      int
    (let ((fr (car fract)))
      (if (= (remainder int (cadr fr)) 0)
      (cons (/ (* int (car fr)) (cadr fr))
        (list fr))
    (step-fractran (cdr fract) int)))))

(define (run-fractran fract int)
  (let ((step-result (step-fractran fract int)))
    (if (list? step-result)`
    (let ((new-int (car step-result))
          (last-step (cadr step-result)))
      (cons step-result (run-fractran fract new-int)))
      (list int ))))

(define (run-fractran-bounded fract int bound)
  (if (> bound 0)
       (let ((step-result (step-fractran fract int)))
     (if (list? step-result)
         (let ((new-int (car step-result))
           (last-step (cadr step-result)))
           (cons step-result (run-fractran-bounded fract new-int (- bound 1))))
       (list int)))
       (list int)))

;; The mult program.
(define mult '((385 13) (13 21) (1 7) (3 11) (7 2) (1 3)))
;;
;; (run-fractran mult 432)
;; The primes program
(define primes
  '((17 91) (78 85) (19 51) (23 38) (29 33) (77 29) (95 23)
    (77 19) (1 17) (11 13) (13 11) (15 2) (1 7) (55 1)))
;; (run-fractran-bounded primes 2 1000)

And the Haskell:

module Fractran where
import Ratio
import Data.Maybe
import Control.Monad.Fix
type Program = [Rational]

runFractran :: [()] -> Program -> Integer -> [Integer]
runFractran bound prog l =
  step bound prog l
  where
    step _ [] l = []
    step [] (f:fs) l
      = []
    step (_:bound) (f:fs) l
      = let p = f * fromIntegral l
      in case denominator p of
      1 -> let pi = numerator p
        in pi : step bound prog pi
    _ -> step bound fs l

fractran :: Program -> Integer -> [Integer]
fractran prog l
  = runFractran (fix (():)) prog l

fractranBounded :: Int -> Program -> Integer -> [Integer]
fractranBounded b prog l
  = runFractran (take b $ fix (():)) prog l

mult = [385%13, 13%21, 1%7, 3%11, 7%2, 1%3]

primes = [17%91, 78%85, 19%51, 23%38, 29%33, 77%29, 95%23,
          77%19, 1%17, 11%13, 13%11, 15%2, 1%7, 55%1]
-- fractran mult (2^4 * 3^3)
-- fractranBounded 1000 primes 2

0 thoughts on “Pathological Programming with Primes (REPOST)

  1. Joshua Zelinsky

    Since Godel’s First Incompleteness Theorem is essentially a corollary to the statement that arithmetic can model Turing machines this gives an odd way of proving that result.

    Reply
  2. jefu

    Grin.
    I wrote a Fractran program in Haskell quite some time ago and this post reminded me of it, so here is my Fractran program. I never quite figured out how to build a nice way to generate Fractran programs to try more with this, so it probably needs more testing.

    Reply
  3. Bard

    *grin* I did something not all that different in what amounted to the theoretical macro language of a theoretical model of concurrency, back in grad school. Some theoreticians got (non-theoretically) upset about it.
    — Bard

    Reply
  4. Mark C. Chu-Carroll

    Re #3:
    Yeah, umm… Did you read the first paragraph of the post? Or the word “repost” in all capital letters in the title?

    Reply
  5. Znaika

    Neat language! I felt compelled to try my hand at writing a program. Here’s the result:
    11/13, 17/29, 203/85, 1/17, 19/31, 1085/57, 1/19, 23/37, 111/161, 1/23, 96577/22, 33/2, 1/11, 1/5
    Input: 2^n
    Output: 3^F(n), where F(n) is the n-th Fibonacci number.
    Also, a minor mistake in the post: when the multiplication program is given in its factored form, 1/7 disappears.

    Reply
  6. Ørjan Johansen

    I see you asked for links when you started running out of languages for this category.
    Perhaps my favorite “new” esolang this year is ///, an extremely simple rewriting language. It’s not my invention, but I’m still biased, since I was the one who found out how to write nontrivial programs in it. It’s actually from 2006 but it took until this year to “crack” it.

    Reply
  7. Nick Johnson

    And here’s an implementation in Python that I hope is fairly easy to understand:
    def fractran(program, input):
    “””Executes a fractran program with a given input.
    Args:
    program: A fractran program, as a list of (numerator, denominator) tuples.
    input: The program’s input, a single integer.
    Returns:
    The program’s output, if it terminates. Determining if it terminates is left
    as an exercise to the reader.
    “””
    pc = 0
    l = input
    while pc

    Reply
  8. Nick Johnson

    Bah, scienceblogs– for unquoting my < in preview. Try #2:
    def fractran(program, input):
    “””Executes a fractran program with a given input.
    Args:
    program: A fractran program, as a list of (numerator, denominator) tuples.
    input: The program’s input, a single integer.
    Returns:
    The program’s output, if it terminates. Determining if it terminates is left
    as an exercise to the reader.
    “””
    pc = 0
    l = input
    while pc < len(program):
    instr = program[pc]
    if (instr[0] * l) % instr[1] == 0:
    l = (instr[0] * l) / instr[1]
    pc = 0
    else:
    pc += 1
    return l

    Reply
  9. Nick Johnson

    And just to prove I’m totally insane, here’s a (129 character) Python one-liner (split up so I don’t kill the page):
    lambda a,b:(lambda q,p,i:q(q,p,0,i))
    (lambda q,p,x,i:(q(q,p,x+2,i)if p[x]*i%p[x+1]
    else q(q,p,0,p[x]*i/p[x+1]))if p[x:]else i,a,b)
    It expects to be called as fractan(program, input), where program is a flat list of pairs of integers; it’ll run out of stack on anything remotely complicated. I’d like to come up with one that doesn’t recurse on the stack, but I’m not sure if I can.

    Reply
  10. Nick Johnson

    One other consideration: Wouldn’t fractran be much more powerful if you were allowed to express fractions that aren’t in lowest terms? Then, you could have the same prime factors on both sides of a fraction, allowing you to test variables without decrementing them, and eliminating the need for the many placeholder variables.

    Reply
  11. Brian

    That won’t make it more powerful per se — just more efficient. And if you’re willing to forgo mathematical purity for the sake of efficiency, have you considered switching to a different language entirely?

    Reply
  12. Alex

    Hmm, Mark’s gone on “vacation”, and then he will be going on a “business trip”. Has Mark been kidnapped by aliens?
    Tell us what’s going on at Google!!!!!

    Reply
  13. Xanthir, FCD

    Fractran is pretty much my favorite esoteric language ever. I just can never get over the awesomeness of using lists of fractions for computation.
    Here’s my Common Lisp version; iirc it’s much better than the versions I provided the first time this lang was posted.

    (defun run-fractran (program initial &key (steps nil))
    (loop with i = initial
    with step = 0
    with trace = nil
    for (currfrac . x) = program then x
    for currval = (* currfrac i)
    if (integerp currval)
    do (setf x program i currval trace (cons currfrac trace) step (1+ step))
    until (or (null x) (and steps (= step steps)))
    finally (return (list i (nreverse trace)))))

    The LOOP macro is just amazing. ^_^
    I do love the Haskell implementation, though. I’ve even got a version of Fractran written using my full suite of utilities for Lisp, which does something very similar with a lazy list:

    (defun lazy-fractran (p i)
    (lazy (lambda (p i)
    (let ((frac (first-that p 'integerp :key (curry '* i))))
    (values-list (if frac
    (list i (list p (* i frac)))
    (list i nil t)))))
    (list p i)))
    (defparameter *mult* (list 385/13 13/21 1/7 3/11 7/2 1/3))
    (defparameter *primes* '(17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/2 1/7 55))
    (take-all (lazy-fractran *mult* 432))
    (take 10
    (map-lazy (filter-lazy (lazy-fractran *primes* 2)
    (_ (= 0 (nth-value 1 (floor (log _ 2))))))
    (curry* 'log 2)))

    (This is very far from Common Lisp at this point, of course, and many of my utilities are directly inspired by Haskell functionality.)
    @14: It generates all primes, but Mark’s description is slightly wrong. The power of 2 is not always prime. However, occasionally the number it generates will be *just* a power of 2, and each time this happens the power is the next prime.

    Reply
  14. Demur Rumed

    Here’s an improved PyFractran (Speedwise, YTMV):
    def fr(code,d):
     while 1:
      for b,c in code:
       if not b*d%c:
        d=(b*d)//c
        break
       else:return d

    Reply

Leave a Reply to Ørjan Johansen Cancel reply