¿De cuántas maneras puedo escribir factorial en Scheme?

Los lenguajes malvados afirman que los lenguajes de programación funcionales son "lenguajes de escritura factoriales". Esto se define con mayor frecuencia como el lenguaje Haskell, pero comenzaremos con el lenguaje funcional que influyó mucho tanto en Haskell como en un subconjunto de las herramientas de programación funcional para muchos otros idiomas: Scheme. Como mínimo, map y for-each , filter and reduce , así como apply y eval llegaron a nuestros lenguajes de programación favoritos, si no desde Scheme, desde allí.

Considere algunas formas posibles de escribir cálculos factoriales. Al mismo tiempo, obtienes una especie de oda al lenguaje de programación Scheme. Creo que este maravilloso lenguaje lo merece.

Tengo 10 opciones para escribir definiciones de funciones, que se pueden reducir a 3 métodos principales de cálculo: el proceso computacional recursivo lineal tradicional, la iteración, la generación de una secuencia de números, seguida de la multiplicación por convolución. Propongo considerar estas opciones con más detalle. En el camino, consideraremos: optimización de recursión de cola, funciones de orden superior y metaprogramación, cálculos diferidos, listas interminables, memorización, una forma de crear una variable estática en Scheme y macros de higiene.

Para los experimentos, utilizamos el antiguo y antiguo dialecto Scheme R5RS y el popular principio de las bellas artes "medios mínimos - impresiones máximas".

Todos los ejemplos de Esquema se prepararon en DrRacket 6.2 en modo R5RS. Las mediciones de tiempo de ejecución se realizaron en Guile 2.0 en el entorno del sistema operativo OpenSUSE Leap 15.

Para comenzar, puede tomar una definición recursiva de factorial y simplemente reescribir la fórmula en Scheme:

 (define (factorial-classic n) (if (zero? n) 1 (* n (factorial-classic (- n 1))))) 

El resultado fue una definición de una función (en términos de Esquema, un procedimiento, aunque de hecho es una función) para calcular el factorial, que se puede ver en innumerables guías de programación, comenzando con el libro inmortal de H. Abelson y D. Sassman "Estructura e interpretación de programas de computadora" .

Puede leer y comprender este código así: factorial $$$n$ esta ahi $$$1$ si $$$n = 0$ de lo contrario $$$n \ cdot (n-1)!$ . Por lo tanto, este código corresponde a la definición recursiva de factorial, adoptada en matemáticas. Lo único que no verificamos es la afiliación. $$$n$ Números no negativos.

Al ser recursivo, el código anterior contiene una restricción obvia en el valor $$$n$ : los datos de llamadas recursivas se acumularán en la pila hasta $$$n$ no llegará a 0. Esto puede causar un desbordamiento de pila en general $$$n$ .

¿Cómo puedo eliminar esta restricción? Es necesario optimizar la recursividad de cola: reescribe el código para que la llamada recursiva se convierta en cola (es decir, la última en el procedimiento). Esto permitirá que el intérprete de Scheme realice la optimización: reemplace el cálculo recursivo con el iterativo.

Si utiliza las recomendaciones de los autores del libro anterior, puede obtener lo siguiente:

 (define (factorial-classic-tco n) (define (iteration product counter) (if (> counter n) product (iteration (* product counter) (+ counter 1)))) (iteration 1 1)) 

Este código es un ejemplo común, y comenzando con el libro "La estructura e interpretación de los programas de computadora", es allí donde generalmente se explica la optimización de la recursividad de la cola.

Fue un clásico. Pero Scheme es flexibilidad en sí misma, ¿es posible escribir lo mismo de una manera fundamentalmente diferente? ¿Y preferiblemente incluso más corto? Por ejemplo, de acuerdo con la entrada $$$n! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$ formar una secuencia de $$$1$ antes $$$n$ (o de $$$n$ antes $$$1$ ) y luego colapsarlo por multiplicación? Afortunadamente, en Scheme esto es bastante simple gracias al procedimiento de apply incorporado, que aplica un procedimiento con un número arbitrario de argumentos a la lista:

 (define (iota n) (define (iteration sequence i) (if (> in) sequence (iteration (cons i sequence) (+ i 1)))) (iteration '() 1)) (define (factorial-fold n) (apply * (iota n))) 

Scheme es famoso por su conveniencia para los cálculos simbólicos debido a la "unidad de código y datos" (como a veces dicen sobre los idiomas de la familia Lisp). Usamos esta característica: formamos una expresión para calcular el factorial de un número $$$n$ y luego calcularlo:

 (define (factorial-eval n) (define expression `(* ,@(iota n))) (eval expression (interaction-environment))) 

El símbolo "entre comillas simples" significa cuasiquotación. Sin cuasi-cita, se puede obtener una expresión para el cálculo adicional utilizando el código (cons '* (iota n)) . Una comilla simple (cita, cita) significa que * debe sustituirse en la expresión exactamente como un nombre (símbolo), y no el valor correspondiente (aquí, el procedimiento). Entonces, con $$$n = 3$ obtenemos (* 3 2 1) . Esta lista es una expresión en Scheme. Su valor se puede realizar en un entorno adecuado, lo mejor de todo: en un entorno (interaction-environment) entorno de (interaction-environment) contiene los procedimientos integrados y los procedimientos definidos por nosotros en el programa. En realidad, esto es lo que hacemos en el cuerpo de factorial-eval .

El esquema admite computación diferida. Haskell, quien fue fuertemente influenciado por Scheme, usa un modelo de cálculo perezoso, es decir no calcula el valor de la expresión hasta que se reclame el resultado de estos cálculos. Esto permite que los programas tengan estructuras de datos tan peculiares como listas interminables. Si solo se les toma la parte necesaria para realizar más cálculos, el programa no irá en ciclos:

 ghci> take 4 [1 ..] [1,2,3,4] 

La expresión [1 ..] genera una lista infinita de enteros. La expresión take 4 obtiene los primeros 4 elementos de esta lista. Como los elementos de la lista subsiguientes no se reclaman, no se calculan.

En Haskell obteniendo $$$n!$ de una lista interminable puedes escribir así:

 factorials :: [Integer] factorials = next 0 1 where next n fact = let n' = n + 1 in fact : next n' (fact * n') factorial :: Integer -> Integer factorial n = factorials !! fromIntegral n 

 ghci> take 7 $ factorials [1,1,2,6,24,120,720] ghci> factorial 6 720 

Usando un par de formas de Scheme delay / force intentemos hacer algo similar. La palabra clave delay crea una promesa para evaluar el valor de una expresión. La palabra clave force indica que realice estos cálculos, el valor resultante se calcula y almacena. Tras el acceso repetido, no se realizan nuevos cálculos, pero se devuelve el valor calculado anteriormente.

En los idiomas de la familia Lisp, las listas se construyen a partir de pares. Para construir listas infinitas, presentamos el tipo de "par perezoso": un par en el que el primer elemento es el valor calculado y el segundo es la promesa de calcular el valor. Para hacer esto, necesitamos complementar la "santa trinidad" de los idiomas de la familia Lisp ( cons , car , cdr ) con sus versiones perezosas:

 (define-syntax lazy-cons (syntax-rules () ((_ first second) (cons first (delay second))))) (define lazy-car car) (define (lazy-cdr lazy-pair) (force (cdr lazy-pair))) 

El constructor del par lazy-cons se implementa como una macro. Esto se hace para evitar calcular el valor del segundo elemento del par cuando se crea.

La idea es crear una lista interminable de valores y luego tomar de ella lo que necesita. Para hacer esto, defina la versión perezosa del procedimiento para obtener el elemento por índice:

 (define (lazy-list-ref lazy-list index) (if (zero? index) (lazy-car lazy-list) (lazy-list-ref (lazy-cdr lazy-list) (- index 1)))) (define (generate-factorials) (define (next nn!) (define n+1 (+ n 1)) (lazy-cons n! (next n+1 (* n! n+1)))) (next 0 1)) 

Aquí n! y n+1 son los nombres de las variables. En Scheme, en comparación con otros idiomas, hay muy pocos caracteres que no se pueden usar en identificadores.

Tenga en cuenta que el generador de listas infinitas generate-factorials no contiene una salida a la recursividad. Sin embargo, no se realizará un bucle, ya que cuando se llama, solo se calculará el encabezado de la lista, mientras que la cola estará representada por una promesa de calcular el valor.

Ahora puedes definir $$$n!$ como llegar $$$n$ Elemento de la lista de factoriales:

 (define lazy-factorials (generate-factorials)) (define (factorial-lazy n) (lazy-list-ref lazy-factorials n)) 

Funciona Al mismo tiempo, si se calculan factores de diferentes números en una sesión del intérprete, los cálculos se realizarán más rápido que en las versiones estrictas, porque algunos de los valores de la lista diferida ya se calcularán.

Por cierto, el código en Scheme es muy similar al de Haskell. ¡Entonces, la declaración de recepción !! corresponde aproximadamente al procedimiento lazy-list-ref constructor de lazy-list-ref : corresponde a lazy-cons . Correspondientemente, porque Haskell, aunque profesa un modelo de cálculo vago, sin embargo, a diferencia del delay / force en Scheme, no recuerda los valores calculados.

Por cierto, para aumentar la productividad, puede aplicar la memorización de valores ya calculados: la memorización. Almacenaremos los valores calculados en una lista asociativa, en la que las claves son números y los valores son sus factores. Cuando se le llame, veremos en la lista los valores ya calculados. Si el valor está en la lista, devolveremos este valor almacenado. Si el valor no está en la lista, lo calcularemos, lo pondremos en la lista y solo luego lo devolveremos. Para garantizar que esta lista siempre esté con la función llamada, y no en el entorno global, la colocamos en una variable estática:

 (define factorial-memoized (let ((memo '())) (lambda (n) (let ((memoized (assq n memo))) (if memoized (cadr memoized) (if (zero? n) 1 (let ((computed (* n (factorial-memoized (- n 1))))) (set! memo (cons (list n computed) memo)) computed))))))) 

 (define proc (let ((static-var initial-value)) (lambda args ...))) 

 (define count (let ((n 0)) (lambda () (set! n (+ n 1)) n))) 

 (define count ((lambda (n) (lambda () (set! n (+ n 1)) n)) 0)) 

Esta implementación también promete ganancias de rendimiento al calcular repetidamente factoriales de varios números en una sesión de intérprete.

Por supuesto, la optimización de recursión de cola también es posible aquí:

 (define factorial-memoized-tco (let ((memo '())) (lambda (n) (define (iteration product counter) (cond ((> counter n) product) (else (set! memo (cons (list counter product) memo)) (iteration (* product counter) (+ counter 1))))) (iteration 1 1)))) 

“¿Por qué hacen estos bailes con una pandereta?”, Puede decir el lector. En los lenguajes de programación imperativos, lo mismo se escribe simplemente: a través de un bucle, funciona rápidamente y sin costos de memoria innecesarios. Scheme tiene un subconjunto para la programación imperativa, también tiene un medio para organizar bucles, una forma especial de do . El procedimiento para calcular el factorial, escrito con su ayuda, puede verse así:

 (define (factorial-do n) (define product 1) (do ((i 1 (+ i 1))) ((> in) product) (set! product (* product i)))) 

La construcción do es bastante versátil, y es por eso que no es muy legible. ¿No es mejor organizar tu propio ciclo en un estilo imperativo? Las macros ayudarán con esto:

 (define-syntax for (syntax-rules () ((_ (variable init test step) . body) (let loop ((variable init)) (if test (begin (begin . body) (loop step))))))) 

Gracias a la optimización de la recursividad de cola por parte del intérprete, obtenemos un bucle al que estamos acostumbrados en los lenguajes de programación imperativos. Al optimizar la recursividad de la cola, la pila no crecerá.

Definición de factorial utilizando for :

 (define (factorial-for n) (define product 1) (for (i 1 (<= in) (+ i 1)) (set! product (* product i))) product) 

 for → _ i → variable 1 → init (<= in) → test (+ i 1) → step (set! product (* product i)) → body 

 (define (factorial-for n) (define product 1) (let loop ((i 1)) ;   (if (<= in) ;  (begin (begin (set! product (* product i))) ;  (loop (+ i 1))))) ;  for product) 

Hay otra opción que se parece al imperativo for bucle: con el procedimiento incorporado for-each :

 (define (factorial-for-each n) (define product 1) (for-each (lambda (i) (set! product (* product i))) (iota n)) product) 

¡Excelente y poderoso lenguaje Scheme! ¿Qué pasa con el rendimiento?

Utilizaremos el GNU Guile para medir el rendimiento: en este entorno puede medir el tiempo que lleva evaluar una expresión de la manera más simple.

Guile funciona de la siguiente manera: compila el código fuente del programa en código de bytes, que luego es ejecutado por la máquina virtual. Esta es solo una de las implementaciones y una de varias formas posibles de ejecutar un programa Scheme, hay otras: Racket (usa la compilación JIT), Chicken Scheme (usa una interpretación o compilación "honesta" en un subconjunto de C), etc. Obviamente, tanto las limitaciones como el rendimiento de los programas en estos entornos pueden variar ligeramente.

Tomaremos medidas a un cierto valor. $$$n$ . Que debe ser $$$n$ ? Entonces con el cual el más grande $$$n$ podrá "hacer frente" a las opciones propuestas. Con la configuración predeterminada de Guile 2.0, en una PC con Intel Core i5 y 4 GB de RAM, obtuve lo siguiente:

A partir de aquí, las pruebas de rendimiento se realizaron a $$$n = 8 \, 000$ . Los resultados se presentan en la tabla a continuación, donde $$$t_ {run}$ - plazo de entrega $$$t_ {GC}$ - Tiempo de ejecución del recolector de basura en segundos.
Para todos los procedimientos, excepto perezoso y memorizado, se obtienen los valores más pequeños del tiempo de ejecución y el tiempo correspondiente del recolector de basura, obtenido de los resultados de tres inicios en $$$n = 8 \, 000$ .
Para procedimientos memorables y perezosos, se indica el tiempo de ejecución de la primera llamada, luego la menor de las tres llamadas.

Tenemos 4 opciones que pueden funcionar con grandes $$$n$ . En $$$n = 100 \, 000$ tienen los siguientes tiempos de cálculo y recolección de basura:

Puedes ver eso con no demasiado grande $$$n$ el más rápido y, al mismo tiempo, el más corto es el primero. La misma opción es más consistente con la definición matemática de factorial. La opción de optimización de recursión de cola no es muy inferior en rendimiento. Ambas opciones son idiomáticas recomendadas por los autores del lenguaje. La conclusión es obvia en muchos sentidos: a menos que se especifique lo contrario, se prefiere el enfoque, que es "típico" para el lenguaje, al menos para la primera implementación de un algoritmo o método.

Al mismo tiempo, el lenguaje Scheme nos permitió escribir muchas opciones para implementar el cálculo factorial, utilizando un conjunto muy limitado de primitivas (los mismos "medios mínimos - impresiones máximas"). Por lo tanto, a pesar de su edad venerable y no demasiado extendida, este lenguaje aún se puede recomendar para la programación de investigación: parece que puede implementar cualquier cosa en él de cualquier manera (y de cualquier manera) conveniente .