De combien de façons puis-je écrire factorielle dans Scheme?

Les langages mauvais prétendent que les langages de programmation fonctionnels sont des «langages d'écriture factoriels». Ceci est le plus souvent défini comme le langage Haskell, mais nous commencerons par le langage fonctionnel qui a grandement influencé à la fois Haskell et un sous-ensemble des outils de programmation fonctionnelle pour de nombreux autres langages - Scheme. Au moins map et for-each , filter et reduce , ainsi eval et eval sont venus à nos langages de programmation préférés, sinon de Scheme, puis de là.

Examinez quelques façons possibles d'écrire des calculs factoriels. En même temps, vous obtenez une sorte d'ode au langage de programmation Scheme. Je pense que cette merveilleuse langue le mérite.

J'ai eu 10 options pour écrire des définitions de fonctions, qui peuvent être réduites à 3 méthodes de calcul principales: le processus de calcul récursif linéaire traditionnel, l'itération, la génération d'une séquence de nombres, suivie d'une multiplication par convolution. Je propose d'examiner ces options plus en détail. En cours de route, nous considérerons: l'optimisation de la récursivité de la queue, les fonctions et métaprogrammations d'ordre supérieur, les calculs différés, les listes sans fin, la mémorisation, un moyen de créer une variable statique dans Scheme et des macros d'hygiène.

Pour les expériences, nous avons utilisé le bon vieux dialecte Schéma R5RS et le principe populaire des beaux-arts «moyens minimaux - impressions maximales».

Tous les exemples de schéma ont été préparés dans DrRacket 6.2 en mode R5RS. Les mesures d'exécution ont été effectuées dans Guile 2.0 dans l'environnement OpenSUSE Leap 15 OS.

Pour commencer, vous pouvez prendre une définition récursive de factorielle et simplement réécrire la formule sur Scheme:

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

Le résultat a été une définition d'une fonction (en termes de Scheme - une procédure, bien qu'il s'agisse en fait d'une fonction) pour calculer la factorielle, qui peut être vue dans d'innombrables guides de programmation, à commencer par le livre immortel de H. Abelson et D. Sassman «Structure et interprétation des programmes informatiques» .

Vous pouvez lire et comprendre ce code comme ceci: factoriel $$$n$ est là $$$1$ si $$$n = 0$ sinon - $$$n \ cdot (n-1)!$ . Ainsi, ce code correspond à la définition récursive de factorielle, adoptée en mathématiques. La seule chose que nous ne vérifions pas l'affiliation $$$n$ nombres non négatifs.

Étant récursif, le code ci-dessus contient une restriction évidente sur la valeur $$$n$ : les données d'appel récursives s'accumuleront sur la pile jusqu'à $$$n$ n'atteindra pas 0. Cela peut entraîner un débordement de pile dans son ensemble $$$n$ .

Comment puis-je supprimer cette restriction? Il est nécessaire d'optimiser la récursivité de la queue: réécrivez le code afin que l'appel récursif devienne la queue (c'est-à-dire le dernier de la procédure). Cela permettra à l'interpréteur Scheme d'effectuer l'optimisation - remplacer le calcul récursif par le calcul itératif.

Si vous utilisez les recommandations des auteurs du livre ci-dessus, vous pouvez obtenir les éléments suivants:

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

Ce code est un exemple courant, et à partir du livre «La structure et l'interprétation des programmes informatiques», c'est sur lui que l'on explique généralement l'optimisation de la récursivité de la queue.

C'était un classique. Mais le schéma est la flexibilité elle-même, est-il possible d'écrire la même chose d'une manière fondamentalement différente? Et de préférence encore plus court? Par exemple, selon l'entrée $$$n! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$ former une séquence à partir de $$$1$ avant $$$n$ (ou de $$$n$ avant $$$1$ ) puis l'effondrer par multiplication? Heureusement, dans Scheme, c'est assez simple grâce à la procédure d' apply intégrée, qui applique une procédure avec un nombre arbitraire d'arguments à la liste:

 (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 est célèbre pour sa commodité pour les calculs symboliques en raison de «l'unité de code et de données» (comme on dit parfois sur les langages de la famille Lisp). Nous utilisons cette fonctionnalité: nous formons une expression pour calculer la factorielle d'un nombre $$$n$ puis calculez-le:

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

Le symbole «retour guillemet simple» signifie quasiquotation. Sans quasi-citation, l'obtention d'une expression pour un calcul ultérieur pourrait être obtenue en utilisant le code (cons '* (iota n)) . Une citation simple (citation, citation) signifie que * doit être substitué dans l'expression exactement comme un nom (symbole), et non la valeur correspondante (ici - la procédure). Donc, avec $$$n = 3$ nous obtenons (* 3 2 1) . Cette liste est une expression dans Scheme. Sa valeur peut être réalisée dans un environnement approprié, le meilleur de tous - dans un environnement (interaction-environment) contenant les procédures intégrées et les procédures définies par nous dans le programme. En fait, c'est ce que nous faisons dans le corps de l' factorial-eval .

Le schéma prend en charge l'informatique différée. Haskell, qui a été fortement influencé par Scheme, utilise un modèle de calcul paresseux, c'est-à-dire ne calcule pas la valeur de l'expression tant que le résultat de ces calculs n'est pas revendiqué. Cela permet aux programmes d'avoir des structures de données particulières comme des listes sans fin. Si seule la partie nécessaire à d'autres calculs leur est prélevée, le programme ne se déroulera pas en cycles:

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

L'expression [1 ..] génère une liste infinie d'entiers. L'expression take 4 obtient les 4 premiers éléments de cette liste. Étant donné que les éléments de liste suivants ne sont pas réclamés, ils ne sont pas calculés.

Chez Haskell, $$$n!$ à partir d'une liste sans fin, vous pouvez écrire comme ceci:

 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 

En utilisant quelques formes de delay / force du schéma force essayons de faire quelque chose de similaire. Le mot clé delay crée une promesse pour évaluer la valeur d'une expression. Le mot force clé force demande d'effectuer ces calculs, la valeur résultante est calculée et stockée. Lors d'un accès répété, de nouveaux calculs ne sont pas effectués, mais la valeur calculée précédemment est renvoyée.

Dans les langages de la famille Lisp, les listes sont construites à partir de paires. Afin de construire des listes infinies, nous introduisons le type de «paire paresseuse» - une paire dans laquelle le premier élément est la valeur calculée, et le second est la promesse de calculer la valeur. Pour ce faire, nous devons compléter la «sainte trinité» des langages de la famille Lisp ( cons , car , cdr ) avec leurs versions paresseuses:

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

Le constructeur de la paire lazy lazy-cons est implémenté sous forme de macro. Ceci est fait afin d'éviter de calculer la valeur du deuxième élément de la paire lors de sa création.

L'idée est de créer une liste infinie de valeurs, puis d'en tirer ce dont vous avez besoin. Pour ce faire, définissez la version paresseuse de la procédure d'obtention de l'élément par index:

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

Ici n! et n+1 sont les noms des variables. Dans Scheme, par rapport à d'autres langues, il y a très peu de caractères qui ne peuvent pas être utilisés dans les identificateurs.

Notez que le générateur de listes infinies generate-factorials ne contient aucun moyen de sortir de la récursivité. Cependant, il ne sera pas bouclé, car lors de son appel, seule la tête de liste sera calculée, tandis que la queue sera représentée par une promesse de calculer la valeur.

Vous pouvez maintenant définir $$$n!$ comment arriver $$$n$ e élément de la liste des factorielles:

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

Ça marche. Dans le même temps, si des factorielles de nombres différents sont calculées en une seule session de l'interpréteur, les calculs se produiront plus rapidement que dans les versions strictes, car certaines des valeurs de la liste paresseuse seront déjà calculées.

Soit dit en passant, le code sur Scheme est très proche de celui sur Haskell. Donc, la déclaration de réception !! correspond approximativement à la procédure lazy-list-ref constructeur de lazy-list-ref : correspond à lazy-cons . En conséquence, parce que Haskell, bien qu'il professe un modèle de calcul paresseux, cependant, contrairement au delay / force dans Scheme, il ne se souvient pas des valeurs calculées.

Par ailleurs, pour augmenter la productivité, vous pouvez appliquer la mémorisation de valeurs déjà calculées - mémorisation. Nous allons stocker les valeurs calculées dans une liste associative, dans laquelle les clés sont des nombres et les valeurs sont leurs factorielles. Une fois appelé, nous allons parcourir la liste pour les valeurs déjà calculées. Si la valeur est dans la liste, nous retournerons cette valeur stockée. Si la valeur n'est pas dans la liste, nous la calculerons, la mettrons dans la liste et la renverrons ensuite. Pour nous assurer que cette liste est toujours avec la fonction appelée, et non dans l'environnement global, nous la plaçons dans une variable statique:

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

Cette implémentation promet également des gains de performances en calculant à plusieurs reprises les factorielles de divers nombres dans une même session d'interpréteur.

Bien sûr, l'optimisation de la récursivité de queue est également possible ici:

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

«Pourquoi ces danses au tambourin?», Dira le lecteur. Dans les langages de programmation impératifs, la même chose est écrite simplement - à travers une boucle, cela fonctionne rapidement et sans coûts de mémoire inutiles. Le schéma a un sous-ensemble pour la programmation impérative, il a également un moyen d'organiser les boucles - une forme spéciale de do . La procédure de calcul de la factorielle, écrite avec son aide, peut ressembler à ceci:

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

La construction do est assez polyvalente, et c'est pourquoi elle n'est pas trop lisible. N'est-il pas préférable d'organiser son propre cycle dans un style impératif? Les macros aideront à cela:

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

Grâce à l'optimisation de la récursivité de queue par l'interpréteur, nous obtenons une boucle à laquelle nous sommes habitués dans les langages de programmation impératifs. En optimisant la récursivité de la queue, la pile ne se développera pas.

Définition de la factorielle à l'aide 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) 

Il existe une autre option qui ressemble à l'impératif for loop - avec la procédure for-each intégrée:

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

Langage Scheme grand et puissant! Et la performance?

Nous utiliserons GNU Guile pour mesurer les performances - dans cet environnement, vous pouvez mesurer le temps nécessaire pour évaluer une expression le plus simplement possible.

Guile fonctionne comme suit: compile le code source du programme en bytecode, qui est ensuite exécuté par la machine virtuelle. Ce n'est qu'une des implémentations et l'une des nombreuses façons possibles d'exécuter un programme Scheme, il y en a d'autres: Racket (utilise la compilation JIT), Chicken Scheme (utilise une interprétation ou compilation «honnête» dans un sous-ensemble de C), etc. De toute évidence, les limitations et les performances des programmes dans ces environnements peuvent varier légèrement.

Nous prendrons des mesures à une certaine valeur $$$n$ . Que devrait-il être $$$n$ ? Alors avec qui le plus grand $$$n$ sera en mesure de "faire face" aux options proposées. Avec les paramètres par défaut de Guile 2.0, sur un PC avec Intel Core i5 et 4 Go de RAM, j'ai obtenu ce qui suit:

De là, des tests de performance ont été effectués à $$$n = 8 \, 000$ . Les résultats sont présentés dans le tableau ci-dessous, où $$$t_ {run}$ - délai $$$t_ {GC}$ - durée d'exécution du ramasse-miettes en secondes.
Pour toutes les procédures, sauf paresseux et mémorisés, les plus petites valeurs de l'exécution et l'heure correspondante du garbage collector sont obtenues, obtenues à partir des résultats de trois démarrages à $$$n = 8 \, 000$ .
Pour les procédures mémorisées et paresseuses, le temps d'exécution du premier appel est indiqué, puis le plus petit des trois appels.

Nous avons 4 options qui peuvent fonctionner avec de grandes $$$n$ . À $$$n = 100 \, 000$ ils ont les temps de calcul et de récupération de place suivants:

Vous pouvez voir qu'avec pas trop grand $$$n$ le plus rapide et, en même temps, le plus court est le premier. La même option correspond le mieux à la définition mathématique de factorielle. L'option d'optimisation de la récursivité de queue ne lui est pas très inférieure en termes de performances. Ces deux options sont idiomatiques recommandées par les auteurs de la langue. La conclusion est à bien des égards évidente: sauf indication contraire, l'approche, qui est «typique» du langage, est préférée, au moins pour la première implémentation d'un algorithme ou d'une méthode.

Dans le même temps, le langage Scheme nous a permis d'écrire de nombreuses options pour implémenter le calcul factoriel, en utilisant un ensemble très limité de primitives (les très «moyennes minimales - impressions maximales»). Par conséquent, malgré son âge vénérable et pas trop répandu, ce langage peut toujours être recommandé pour la programmation de recherche: il semble que vous pouvez implémenter n'importe quoi dessus de n'importe quelle manière (et de n'importe quelle manière).