title: Why are λ-calculus optimal evaluators able to compute big modular exponentiations without formulas?
body: <p>Church numbers are an encoding of natural numbers as functions.</p>
  
  <pre><code>(\ f x → (f x))             -- church number 1
  (\ f x → (f (f (f x))))     -- church number 3
  (\ f x → (f (f (f (f x))))) -- church number 4
  </code></pre>
  
  <p>Neatly, you can exponentiate 2 church numbers by just applying them. That is, if you apply 4 to 2, you get the church number <code>16</code>, or <code>2^4</code>. Obviously,  that is utterly unpractical. Church numbers need a linear amount of memory and are really, really slow. Computing something like <code>10^10</code> - which GHCI quickly answers correctly - would take ages and couldn't fit the memory on your computer anyway. </p>
  
  <p>I've been experimenting with optimal λ evaluators lately. On my tests, I accidentally typed the following on my optimal λ-calculator:</p>
  
  <pre><code>10 ^ 10 % 13
  </code></pre>
  
  <p>It was supposed to be multiplication, not exponentiation. Before I could move my fingers to abort the forever-running program in despair, it answered my request:</p>
  
  <pre><code>3
  { iterations: 11523, applications: 5748, used_memory: 27729 }
  
  real    0m0.104s
  user    0m0.086s
  sys     0m0.019s
  </code></pre>
  
  <p>With my "bug alert" flashing, I went to Google and verified, <code>10^10%13 == 3</code> indeed. <strong>But the λ-calculator wasn't supposed to find that result, it can barely store 10^10.</strong> I started stressing it, for science. It instantly answered me <code>20^20%13 == 3</code>, <code>50^50%13 == 4</code>, <code>60^60%3 == 0</code>. I had to use <a href="https://www.mtholyoke.edu/courses/quenell/s2003/ma139/js/powermod.html" rel="noreferrer">external tools</a> to verify those results, since <s>Haskell itself wasn't able to compute it (due to integer overflow)</s> (it is if you use Integers not Ints, of course!). Pushing it to its limits, this was the answer to <code>200^200%31</code>:</p>
  
  <pre><code>5
  { iterations: 10351327, applications: 5175644, used_memory: 23754870 }
  
  real    0m4.025s
  user    0m3.686s
  sys 0m0.341s
  </code></pre>
  
  <p>If we had one copy of the universe for each atom on the universe, and we had a computer for each atom we had in total, we couldn't store the church number <code>200^200</code>. This prompted me to question if my mac was really that powerful. Maybe the optimal evaluator was able to skip the unnecessary branches and arrive right at the answer in the same fashion Haskell does with lazy evaluation. To test this, I compiled the λ program to Haskell:</p>
  
  <pre><code>data Term = F !(Term -&gt; Term) | N !Double
  instance Show Term where {
      show (N x) = "(N "++(if fromIntegral (floor x) == x then show (floor x) else show x)++")";
      show (F _) = "(λ...)"}
  infixl 0 #
  (F f) # x = f x
  churchNum = F(\(N n)-&gt;F(\f-&gt;F(\x-&gt;if n&lt;=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
  expMod    = (F(\v0-&gt;(F(\v1-&gt;(F(\v2-&gt;((((((churchNum # v2) # (F(\v3-&gt;(F(\v4-&gt;(v3 # (F(\v5-&gt;((v4 # (F(\v6-&gt;(F(\v7-&gt;(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3-&gt;(v3 # (F(\v4-&gt;(F(\v5-&gt;v5)))))))) # (F(\v3-&gt;((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4-&gt;(F(\v5-&gt;(F(\v6-&gt;(v4 # (F(\v7-&gt;((v5 # v7) # v6))))))))))) # (F(\v4-&gt;v4))) # (F(\v4-&gt;(F(\v5-&gt;(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4-&gt;(F(\v5-&gt;v4))))) # (F(\v4-&gt;v4))) # (F(\v4-&gt;v4))))))) # (F(\v3-&gt;(((F(\(N x)-&gt;F(\(N y)-&gt;N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
  main = print $ (expMod # N 5 # N 5 # N 4)
  </code></pre>
  
  <p>This correctly outputs <code>1</code> (<code>5 ^ 5 % 4</code>) - but throw anything above <code>10^10</code> and it will be stuck, eliminating the hypothesis. </p>
  
  <p>The <a href="https://github.com/SrVictorMaia/optlam" rel="noreferrer">optimal evaluator I used</a> is a 160-lines long, unoptimized JavaScript program that didn't include any sort of exponential modulus math - and the lambda-calculus modulus function I used was equally simple:</p>
  
  <pre><code>(λab.(b(λcd.(c(λe.(d(λfg.(f(efg)))e))))(λc.(c(λde.e)))(λc.(a(b(λdef.(d(λg.(egf))))(λd.d)(λde.(ed)))(b(λde.d)(λd.d)(λd.d))))))
  </code></pre>
  
  <p>I used no specific modular arithmetic algorithm or formula. <strong>So, how is the optimal evaluator able to arrive at the right answers?</strong></p>