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:
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