A FRACTRAN interpreter in Hoon

fractran.hoon

|=  n=@
=<
|^
(fib-dec (interp fib-prog (fib-enc n)))
++  fib-prog
  :~  17^65
      133^34
      17^19
      23^17
      2.233^69
      23^29
      31^23
      74^341
      31^37
      41^31
      129^287
      41^43
      13^41
      1^13
      1^3
  ==
++  fib-enc
  |=  n=@
  (mul 78 (pow 5 (dec n)))
++  fib-dec
  |=  n=@
  (dec (xeb n))
--
|%
::
+$  frac  [n=@ d=@]
::
++  reduce-frac
  |=  x=frac
  ^-  frac
  =/  f  d:(egcd x)
  (div n.x f)^(div d.x f)
::
++  mul-frac
  |=  [x=frac y=frac]
  ^-  frac
  %-  reduce-frac
  (mul n.x n.y)^(mul d.x d.y)
::
++  first-div
  |=  [prog=(list frac) n=@]
  ^-  (unit @)
  ?~  prog  ~
  =/  m  (mul-frac n^1 i.prog)
  ?:  =(d.m 1)  `n.m
  $(prog t.prog)
::
++  interp
  |=  [prog=(list frac) n=@]
  ^-  @
  =/  d  (first-div prog n)
  ?~  d  n
  $(n u.d)
--