algorithm - online - funciones exponenciales

¿Por qué los evaluadores óptimos de cálculo λ pueden calcular grandes exponenciaciones modulares sin fórmulas?

Question

Los números de iglesia son una codificación de números naturales como funciones.

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

Claramente, puede exponer 2 números de iglesia simplemente aplicándolos. Es decir, si aplica 4 a 2, obtiene el número 16 la iglesia 16 , o 2^4 . Obviamente, eso es completamente poco práctico. Los números de la iglesia necesitan una cantidad lineal de memoria y son muy, muy lentos. Calcular algo así como 10^10 , que GHCI responde rápidamente correctamente, llevaría años y, de todos modos, no podría caber en la memoria de su computadora.

He estado experimentando con evaluadores λ óptimos últimamente. En mis pruebas, accidentalmente escribí lo siguiente en mi calculadora λ óptima:

10 ^ 10 % 13

Se suponía que era multiplicación, no exponenciación. Antes de que pudiera mover mis dedos para abortar el programa que se ejecuta para siempre con desesperación, respondió a mi solicitud:

3
{ iterations: 11523, applications: 5748, used_memory: 27729 }
real 0m0.104s
user 0m0.086s
sys 0m0.019s

Con mi "alerta de error" parpadeando, fui a Google y verifiqué, 10^10%13 == 3 hecho. Pero no se suponía que la calculadora λ encontrara ese resultado, apenas puede almacenar 10 ^ 10. Empecé a enfatizarlo, por la ciencia. Al instante me respondió 20^20%13 == 3 , 50^50%13 == 4 , 60^60%3 == 0 . Tuve que usar herramientas externas para verificar esos resultados, ya que el propio Haskell no pudo calcularlo (debido al desbordamiento de enteros) (¡por supuesto, si usa Integers not Ints!). Llevándolo a sus límites, esta fue la respuesta a 200^200%31 :

5
{ iterations: 10351327, applications: 5175644, used_memory: 23754870 }
real 0m4.025s
user 0m3.686s
sys 0m0.341s

Si tuviéramos una copia del universo para cada átomo en el universo, y tuviéramos una computadora para cada átomo que teníamos en total, no podríamos almacenar el número de iglesia 200^200 . Esto me llevó a preguntarme si mi Mac era realmente tan poderoso. Quizás el evaluador óptimo pudo saltarse las ramas innecesarias y llegar directamente a la respuesta de la misma manera que Haskell lo hace con la evaluación perezosa. Para probar esto, compilé el programa λ para 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)

Esto genera correctamente 1 ( 5 ^ 5 % 4 ), pero arroja algo por encima de 10^10 y se bloqueará, eliminando la hipótesis.

El evaluador óptimo que utilicé es un programa JavaScript no optimizado de 160 líneas de largo que no incluía ningún tipo de matemática de módulo exponencial, y la función de módulo de cálculo lambda que utilicé fue igualmente simple:

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

No utilicé ningún algoritmo o fórmula aritmética modular específica. Entonces, ¿cómo puede el evaluador óptimo llegar a las respuestas correctas?

Answer 1

El fenómeno proviene de la cantidad de pasos de reducción beta compartidos, que pueden ser dramáticamente diferentes en la evaluación perezosa al estilo Haskell (o la llamada habitual por valor, que no está tan lejos a este respecto) y en Vuillemin-Lévy-Lamping- Kathail-Asperti-Guerrini- (et al ...) evaluación "óptima". Esta es una característica general, que es completamente independiente de las fórmulas aritméticas que podría usar en este ejemplo en particular.

Compartir significa tener una representación de su término lambda en el que un "nodo" puede describir varias partes similares del término lambda real que representa. Por ejemplo, puedes representar el término

/x. x ((/y.y)a) ((/y.y)a)

usando un gráfico (acíclico dirigido) en el que solo hay una aparición del subgrafo que representa (/yy)a , y dos bordes que apuntan a ese subgrafo. En términos de Haskell, tiene un thunk, que evalúa solo una vez, y dos punteros a este thunk.

La memorización al estilo Haskell implementa el intercambio de subterms completos. Este nivel de uso compartido se puede representar mediante gráficos acíclicos dirigidos. El intercambio óptimo no tiene esta restricción: también puede compartir subterms "parciales", lo que puede implicar ciclos en la representación gráfica.

Para ver la diferencia entre estos dos niveles de compartir, considere el término

/x. (/z.z) ((/z.z) x)

Si su uso compartido está restringido a subterms completos, como es el caso en Haskell, es posible que solo tenga una aparición de /zz , pero las dos beta-redexes aquí serán distintas: una es (/zz) x y la otra es (/zz) ((/zz) x) , y dado que no son términos iguales, no se pueden compartir. Si se permite compartir subterráneos parciales, entonces es posible compartir el término parcial (/zz) [] (que no es solo la función /zz , sino "la función /zz aplicada a algo" ), que se evalúa en un paso a algo , cualquiera que sea este argumento. Por lo tanto, puede tener un gráfico en el que solo un nodo representa las dos aplicaciones de /zz en dos argumentos distintos, y en el que estas dos aplicaciones se pueden reducir en un solo paso. Observe que hay un ciclo en este nodo, ya que el argumento de la "primera aparición" es precisamente la "segunda aparición". Finalmente, con el uso compartido óptimo puede pasar de (un gráfico que representa) /x. (/zz) ((/zz) x)) a (un gráfico que representa) el resultado /xx en solo un paso de la reducción beta (más algo de contabilidad). Esto es básicamente lo que sucede en su evaluador óptimo (y la representación gráfica es también lo que evita la explosión del espacio).

Para explicaciones ligeramente extendidas, puede consultar el documento Optimización débil y el significado de compartir (lo que le interesa es la introducción y la sección 4.1, y quizás algunos de los punteros bibliográficos al final).

Volviendo a su ejemplo, la codificación de funciones aritméticas que trabajan en enteros de la Iglesia es una de las minas de ejemplos "bien conocidos" en los que los evaluadores óptimos pueden funcionar mejor que los idiomas convencionales (en esta oración, bien conocido significa que un puñado de los especialistas conocen estos ejemplos). Para ver más ejemplos de este tipo, eche un vistazo al documento Safe Operators: Brackets Closed Forever de Asperti y Chroboczek (y, por cierto, encontrará aquí términos lambda interesantes que no son de tipo EAL; así que le animo a que tome un vistazo a los oráculos, comenzando con este artículo de Asperti / Chroboczek).

Como usted mismo dijo, este tipo de codificación es completamente poco práctico, pero aún representan una buena forma de entender lo que está sucediendo. Y permítanme concluir con un desafío para una mayor investigación: ¿podrá encontrar un ejemplo en el que la evaluación óptima de estas codificaciones supuestamente malas esté realmente a la par con la evaluación tradicional en una representación de datos razonable? (Hasta donde yo sé, esta es una pregunta realmente abierta).

Answer 2

Esto no es una respuesta, pero es una sugerencia de dónde puede comenzar a buscar.

Hay una forma trivial de calcular exponenciaciones modulares en poco espacio, específicamente reescribiendo

(a * x ^ y) % z

como

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

Si un evaluador evalúa así y mantiene el parámetro de acumulación a en forma normal, entonces evitará usar demasiado espacio. Si su evaluador es óptimo, entonces presumiblemente no debe hacer más trabajo que este, por lo que, en particular, no puede usar más espacio que el tiempo que lleva evaluar.

No estoy realmente seguro de qué es realmente un evaluador óptimo, así que me temo que no puedo hacer esto más riguroso.