Почему оптимизаторы λ-исчисления способны вычислять большие модульные экспоненции без формул?

Церковные числа - это кодирование натуральных чисел как функций.

(\ 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

Аккуратно, вы можете увеличить 2 номера церкви, просто применяя их. То есть, если вы применяете 4 к 2, вы получаете номер церкви 16 или 2^4. Очевидно, что это совершенно непрактично. Церковные числа нуждаются в линейном объеме памяти и действительно, очень медленны. Вычисляя что-то вроде 10^10, которое GHCI быстро отвечает правильно, потребует возраста и не сможет поместиться в памяти на вашем компьютере.

В последнее время я экспериментировал с оптимальными оценщиками λ. В моих тестах я случайно набрал следующее на моем оптимальном λ-калькуляторе:

10 ^ 10 % 13

Предполагалось, что это будет умножение, а не возведение в степень. Прежде чем я смог перенести мои пальцы, чтобы отменить бесконечную программу в отчаянии, она ответила на мою просьбу:

3
{ iterations: 11523, applications: 5748, used_memory: 27729 }

real    0m0.104s
user    0m0.086s
sys     0m0.019s

Когда мое "предупреждение об ошибке" мигает, я отправился в Google и подтвердил, 10^10%13 == 3 действительно. Но λ-калькулятор не должен был найти этот результат, он едва может хранить 10 ^ 10. Я начал подчеркивать это, для науки. Он мгновенно ответил мне 20^20%13 == 3, 50^50%13 == 4, 60^60%3 == 0. Мне пришлось использовать внешние инструменты, чтобы проверить эти результаты, так как ~~сам Haskell не смог вычислить его (из-за переполнения целого)~~ (это если вы используете целые числа, а не инты, конечно!). Подталкивая его к своим пределам, это был ответ на 200^200%31:

5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }

real    0m4.025s
user    0m3.686s
sys 0m0.341s

Если бы у нас была одна копия Вселенной для каждого атома на вселенной, и у нас был компьютер для каждого атома, который у нас был в общей сложности, мы не смогли сохранить номер церкви 200^200. Это побудило меня задать вопрос, действительно ли мой мак был настолько сильным. Может быть, оптимальный оценщик смог пропустить ненужные ветки и прийти прямо к ответу тем же способом, который Haskell делает с ленивой оценкой. Чтобы проверить это, я скомпилировал λ-программу для Haskell:

data Term = F !(Term -> 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)->F(\f->F(\x->if n<=0 then x else (f#(churchNum#(N(n-1))#f#x)))))
expMod    = (F(\v0->(F(\v1->(F(\v2->((((((churchNum # v2) # (F(\v3->(F(\v4->(v3 # (F(\v5->((v4 # (F(\v6->(F(\v7->(v6 # ((v5 # v6) # v7))))))) # v5))))))))) # (F(\v3->(v3 # (F(\v4->(F(\v5->v5)))))))) # (F(\v3->((((churchNum # v1) # (churchNum # v0)) # ((((churchNum # v2) # (F(\v4->(F(\v5->(F(\v6->(v4 # (F(\v7->((v5 # v7) # v6))))))))))) # (F(\v4->v4))) # (F(\v4->(F(\v5->(v5 # v4))))))) # ((((churchNum # v2) # (F(\v4->(F(\v5->v4))))) # (F(\v4->v4))) # (F(\v4->v4))))))) # (F(\v3->(((F(\(N x)->F(\(N y)->N(x+y)))) # v3) # (N 1))))) # (N 0))))))))
main = print $ (expMod # N 5 # N 5 # N 4)

Это правильно выводит 1 (5 ^ 5 % 4) - но выбросьте что-нибудь выше 10^10, и оно застрянет, исключив гипотезу.

Оптимизатор который я использовал, представляет собой неоптимизированную программу JavaScript на 160 строк, которая не включала в себя какой-либо математический показатель экспоненциального модуля используемая нами функция модуля лямбда-исчисления была одинаковой:

(λ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))))))

Я не использовал никакого специального модульного арифметического алгоритма или формулы. Итак, как оптимальный оценщик может прийти к правильным ответам?

Ответ 1

Явление исходит из количества общих этапов бета-восстановления, которые могут быть резко различны в ленивой оценке в стиле Хаскелла (или обычном call-by-value, что не так уж и далеко в этом отношении) и в Vuillemin-Lévy -Lamping-Kathail-Asperti-Guerrini- (и др.) "Оптимальная" оценка. Это общая функция, полностью независимая от арифметических формул, которые вы можете использовать в этом конкретном примере.

Обмен означает наличие вашего лямбда-термина, в котором один "node" может описывать несколько аналогичных частей фактического лямбда-термина, который вы представляете. Например, вы можете представить термин

\x. x ((\y.y)a) ((\y.y)a)

с использованием (направленного ациклического) графа, в котором есть только одно вхождение подграфа, представляющего (\y.y)a, и два ребра, нацеленные на этот подграф. В терминах Haskell у вас есть один thunk, который вы оцениваете только один раз и два указателя на этот thunk.

Мемонирование в стиле Хаскеля реализует совместное использование полных субтерм. Этот уровень обмена может быть представлен направленными ациклическими графами. Оптимальное разделение не имеет этого ограничения: оно также может делиться "частичными" подтермиями, что может означать циклы в представлении графика.

Чтобы увидеть разницу между этими двумя уровнями совместного использования, рассмотрите термин

\x. (\z.z) ((\z.z) x)

Если ваш общий доступ ограничен полными субтерминами, как это имеет место в Haskell, у вас может быть только одно вхождение \z.z, но два бета-редекса здесь будут отличаться: один - (\z.z) x, а другой (\z.z) ((\z.z) x), и поскольку они не равны, они не могут быть разделены. Если разрешено разделение частичных субтерм, тогда становится возможным разделять частичный термин (\z.z) [] (это не просто функция \z.z, а "функция \z.z, примененная к чему-то), которая оценивается за один шаг до просто что-то, независимо от этого аргумента. Следовательно, вы можете иметь график, в котором только один node представляет два приложения \z.z для двух различных аргументов и в которых эти два приложения могут быть уменьшены всего за один шаг. на этом node есть цикл, поскольку аргумент" первого вхождения "является именно" вторым вхождением". Наконец, при оптимальном совместном использовании вы можете перейти от (графика, представляющего) \x. (\z.z) ((\z.z) x)) к (графику, представляющему) результат \x.x всего за один шаг бета-редукции (плюс некоторый бухгалтерский учет). Это в основном то, что происходит в вашем оптимальном оценщике (и представление графика также предотвращает взрыв пространства).

Для слегка расширенных объяснений вы можете посмотреть на бумагу "Слабая оптимизация" и "Значение общего доступа" (вас интересует введение и раздел 4.1, а может быть, некоторые из библиографических указателей в конце).

Возвращаясь к вашему примеру, кодирование арифметических функций, работающих с целыми числами Церкви, является одной из "хорошо известных" шахт примеров, где оптимальные оценщики могут работать лучше, чем обычные языки (в этом предложении хорошо известно, что это означает, что некоторые специалисты знают об этих примерах). Для более таких примеров взгляните на статью Безопасные операторы: скобки закрыты навсегда от Asperti и Chroboczek (и, кстати, вы найдете здесь интересные лямбда-термины, которые не являются EAL-типами, поэтому Im поощряю вас взглянуть на оракулы, начиная с этой работы Asperti/Chroboczek).

Как вы сами сказали, такая кодировка совершенно непрактична, но они по-прежнему представляют собой хороший способ понять, что происходит. И позвольте мне завершить вызов для дальнейшего расследования: сможете ли вы найти пример, на котором оптимальная оценка этих якобы плохих кодировок на самом деле совпадает с традиционной оценкой на разумном представлении данных? (насколько я знаю, это настоящий открытый вопрос).

Ответ 2

Это не anwser, но это предложение о том, где вы можете начать искать.

Существует тривиальный способ вычисления модульных выражений в небольшом пространстве, в частности, путем перезаписи

(a * x ^ y) % z

(((a * x) % z) * x ^ (y - 1)) % z

Если оценщик оценивает это так и сохраняет накопленный параметр a в нормальной форме, вы избежите использования слишком большого количества пространства. Если действительно ваш оценщик оптимален, то, по-видимому, он не должен делать больше работы, чем этот, поэтому, в частности, не может использовать больше места, чем время, которое требуется для оценки.

Я не уверен, что такое оптимальный оценщик, поэтому я боюсь, что не могу сделать это более строгим.