Programming Praxis – Fractran

In today’s Programming Praxis exercise, our goal is to write an interpreter for the esotreric programming language Fractran and use it to execute a program that generates prime numbers. Let’s get started, shall we?

A quick import:

import Data.List

The fractran interpreter itself is pretty simple. We use tuples to represent the fractions rather than Ratios since this made for slightly more elegant code. Unfortunately the Prelude doesn’t have a function to swap the values of a tuple, or I could’ve use divMod rather than having to repeat the multiplication.

fractran :: [(Integer, Integer)] -> Integer -> [Integer]
fractran xs = unfoldr (\m -> fmap ((,) m) . lookup 0 $
    map (\(n,d) -> (mod (m*n) d, div (m*n) d)) xs)

Since we’re using tuples, we represent the primegame program as a zip.

primegame :: [(Integer, Integer)]
primegame = zip [17,78,19,23,29,77,95,77, 1,11,13,15,15,55]
                [91,85,51,38,33,29,23,19,17,13,11,14, 2, 1]

Finding the primes is a matter of finding the terms in the output of fractran primegame 2 that are powers of two.

primes :: [(Integer, Integer)]
primes = [(i,e) | (i,n) <- zip [1..] $ fractran primegame 2
                , let e = round $ log (fromIntegral n) / log 2, 2^e == n]

A test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ take 26 primes

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: