### 5 releases

Uses old Rust 2015

0.1.5 | Mar 21, 2015 |
---|---|

0.1.4 | Jan 26, 2015 |

0.1.3 | Jan 4, 2015 |

0.1.1 | Nov 20, 2014 |

0.1.0 | Nov 14, 2014 |

#**208** in Programming languages

**25** downloads per month

**MIT/Apache**

15KB

260 lines

`fractran_macros`

`fractran_macros`

A Rust macro for compiling
FRACTRAN programs embedded
in a Rust program into efficient, allocation-less,
libcore-only^{1} code at compile time.

FRACTRAN is a very simple language; a program is an integer

along
with a list of positive fractions, executed by finding the first
fraction `n`

for which `f`

is an integer, replace `nf`

by `n`

and
repeating (execution halts when there is no such fraction). It turns
out that this is Turing complete, and people have even written
FRACTRAN interpreters in FRACTRAN! (See `nf`

.)`examples /fractran.rs`

^{1}That's right; you can now use FRACTRAN inside a kernel.

## Usage

The

macro takes a series of comma-separated arithmetic
expressions, representing the sequence of fractions. Supported
operations:`fractran`

,`*`

and parentheses for grouping; no risk of arithmetic overflow or loss of precision,`/`

; can overflow,`+`- integer powers via

; no overflow, but precedence is incorrect, so`^`

is`a``^`b`*`c

, rather than`a``^``(`b`*`c`)`

as it should be. Use parentheses to ensure correctness.`(`a`^`b`)``*`c

The macro returns a constructor function

, where
`fn``(``&``[``u32``]``)` `->` T

is the initial number (in the format
described below), and `&``[``u32``]`

is a type implementing
`T`

and `Iterator``<``(``)``>`

. Calling `fractran_support ::`Fractran

`next`

will
step the machine (i.e. finding the appropriate fraction as described
above), returning `None`

when the machine has halted.The

trait provides the `fractran_support ::`Fractran

`state`

method
(for viewing the current number, in exponent form) and the `run`

method for executing the state machine until it halts.### Example

`#!``[``feature``(``phase``)``]`
`#``[``phase``(``plugin``)``]` `extern` `crate` fractran_macros`;`
`fn` `main``(``)`` ``{`
`//` takes 2^a 3^b to 3^(a+b)
`let` add `=` `fractran!``(``3``/``2``)``;`
`println!``(``"``{}``"``,` `add``(``&``[``12``,` `34``]``)``.``run``(``)``)``;` `//` [0, 46]
`//` takes 2^a 3^b to 5^(ab)
`let` mult `=` `fractran!``(``455` `/` `33``,` `11``/``13``,` `1``/``11``,` `3``/``7``,` `11``/``2``,` `1``/``3``)``;`
`println!``(``"``{}``"``,` `mult``(``&``[``12``,` `34``]``)``.``run``(``)``)``;` `//` [0, 0, 408, 0, ...]
`}`

Remember to ensure the

has the appropriate dependencies:`Cargo .toml`

`[``dependencies.fractran_macros``]`
`git ``=` `"`https://github.com/huonw/fractran_macros`"`

## Representation

Numbers are represented in terms of the (32-bit) exponents of their
prime factors. The

th entry of `i`

values is the exponent of
the `[``u32``]`

th prime (zero-indexed), for example `i`

, `2` `==` `[``1``]`

,
`3` `==` `[``0``,` `1``]`

. This representation
allows the implementation to handle very large numbers, anything where
the largest exponent of any prime is less than 2`9438` `==` `2` `*` `3` `*` `11``^``2` `*` `13` `==` `[``1``,` `1``,` `0``,` `0``,` `2``,` `1``]`^{32}, so the
*smallest* non-representable number is 2^{232} =
2^{4294967296}.

This also allows the internal implementation to be highly efficient
with just (statically determined) array indexing and integer
comparisons & additions; there is no possibility of out-of-bounds
indexing (and thus no performance penalty from unwinding), nor is
there any division or remainder operations. As an example, the

program uses Conway's prime enumeration FRACTRAN
program to generate primes, it takes only 6 seconds to do 1 billion
steps (reaching the lofty heights of 887).`example /prime.rs`

Converting this representation to and from an actual number can be
achieved with your favourite prime-number crate (e.g. zipping with the
primes iterator from

).`slow_primes`

## Why?

Why not? Esolang-macros are fun, and so is the fundamental theorem of arithmetic.

#### Dependencies

~555KB

~11K SLoC