Auf wie viele Arten kann ich Fakultät in Schema schreiben?

Böse Sprachen behaupten, dass funktionale Programmiersprachen „faktorielle Schreibsprachen“ sind. Dies wird am häufigsten als Haskell-Sprache definiert, aber wir beginnen mit der funktionalen Sprache, die sowohl Haskell als auch eine Teilmenge der funktionalen Programmierwerkzeuge für viele andere Sprachen stark beeinflusst hat - Schema. Zumindest kamen map und for-each , filter und reduce sowie apply und eval zu unseren bevorzugten Programmiersprachen, wenn nicht aus Schema, dann von dort.

Betrachten Sie einige Möglichkeiten, um faktorielle Berechnungen zu schreiben. Gleichzeitig erhalten Sie eine Art Ode an die Programmiersprache Scheme. Ich denke, diese wunderbare Sprache hat es verdient.

Ich habe 10 Optionen zum Schreiben von Funktionsdefinitionen, die auf drei Hauptberechnungsmethoden reduziert werden können: den traditionellen linearen rekursiven Berechnungsprozess, die Iteration, die Erzeugung einer Folge von Zahlen, gefolgt von der Faltungsmultiplikation. Ich schlage vor, diese Optionen genauer zu betrachten. Auf dem Weg werden wir uns mit folgenden Themen befassen: Optimierung der Schwanzrekursion, Funktionen höherer Ordnung und Metaprogrammierung, verzögerte Berechnungen, endlose Listen, Memoisierung, eine Möglichkeit zum Erstellen einer statischen Variablen im Schema und Hygienemakros.

Für Experimente verwendeten wir das gute alte Dialektschema R5RS und das populäre Prinzip der bildenden Kunst „minimale Mittel - maximale Eindrücke“.

Alle Schema-Beispiele wurden in DrRacket 6.2 im R5RS-Modus erstellt. Laufzeitmessungen wurden in Guile 2.0 in der OpenSUSE Leap 15-Betriebssystemumgebung durchgeführt.

Zu Beginn können Sie eine rekursive Definition von Fakultät verwenden und einfach die Formel für Schema neu schreiben:

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

Das Ergebnis war eine Definition einer Funktion (in Bezug auf das Schema - eine Prozedur, obwohl es tatsächlich eine Funktion ist) zur Berechnung der Fakultät, die in unzähligen Programmierhandbüchern zu sehen ist, beginnend mit dem unsterblichen Buch von H. Abelson und D. Sassman „Struktur und Interpretation von Computerprogrammen“. .

Sie können diesen Code folgendermaßen lesen und verstehen: Fakultät $$$n$ ist da $$$1$ wenn $$$n = 0$ sonst - $$$n \ cdot (n-1)!$ . Somit entspricht dieser Code der rekursiven Definition von Fakultät, die in der Mathematik übernommen wurde. Das einzige, was wir nicht überprüfen Zugehörigkeit $$$n$ nicht negative Zahlen.

Da der obige Code rekursiv ist, enthält er eine offensichtliche Einschränkung des Werts $$$n$ : rekursive Aufrufdaten werden bis auf dem Stapel gesammelt $$$n$ wird 0 nicht erreichen. Dies kann einen Stapelüberlauf im Allgemeinen verursachen $$$n$ .

Wie kann ich diese Einschränkung aufheben? Es ist notwendig, die Schwanzrekursion zu optimieren: Schreiben Sie den Code neu, so dass der rekursive Aufruf zum Schwanz wird (d. H. Der letzte in der Prozedur). Auf diese Weise kann der Scheme-Interpreter die Optimierung durchführen. Ersetzen Sie die rekursive Berechnung durch die iterative.

Wenn Sie die Empfehlungen der Autoren des obigen Buches verwenden, können Sie Folgendes erhalten:

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

Dieser Code ist ein gängiges Beispiel, und beginnend mit dem Buch „Struktur und Interpretation von Computerprogrammen“ wird in der Regel die Optimierung der Schwanzrekursion erläutert.

Es war ein Klassiker. Aber Schema ist Flexibilität selbst. Ist es möglich, dasselbe grundlegend anders zu schreiben? Und am liebsten noch kürzer? Zum Beispiel laut Eintrag $$$n! = 1 \ cdot 2 \ cdot 3 \ cdot ~ \ cdots ~ \ cdot n$ bilden eine Sequenz aus $$$1$ vorher $$$n$ (oder von $$$n$ vorher $$$1$ ) und dann durch Multiplikation kollabieren? Glücklicherweise ist dies in Schema dank der integrierten apply Prozedur, die eine Prozedur mit einer beliebigen Anzahl von Argumenten auf die Liste apply , recht einfach:

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

Das Schema ist berühmt für seine Bequemlichkeit für symbolische Berechnungen aufgrund der "Einheit von Code und Daten" (wie sie manchmal über die Sprachen der Lisp-Familie sagen). Wir verwenden diese Funktion: Wir bilden einen Ausdruck zur Berechnung der Fakultät einer Zahl $$$n$ und dann berechnen:

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

Das Symbol "einfaches Anführungszeichen" bedeutet Quasiquotation. Ohne Quasi-Zitierung könnte ein Ausdruck zur weiteren Berechnung unter Verwendung des Codes (cons '* (iota n)) . Ein einfaches Anführungszeichen (Zitat, Zitat) bedeutet, dass * genau als Name (Symbol) und nicht als entsprechender Wert (hier - die Prozedur) in den Ausdruck eingesetzt werden muss. Also mit $$$n = 3$ wir bekommen (* 3 2 1) . Diese Liste ist ein Ausdruck im Schema. Sein Wert kann in einer geeigneten Umgebung ausgeführt werden, am besten in einer Umgebung (interaction-environment) die die integrierten Prozeduren und die von uns im Programm definierten Prozeduren enthält. Tatsächlich ist es das, was wir im Körper der factorial-eval tun.

Das Schema unterstützt das verzögerte Rechnen. Haskell, der stark vom Schema beeinflusst wurde, verwendet ein faules Berechnungsmodell, d.h. berechnet den Wert des Ausdrucks erst, wenn das Ergebnis dieser Berechnungen beansprucht wird. Dies ermöglicht es Programmen, solche besonderen Datenstrukturen wie endlose Listen zu haben. Wenn ihnen nur der für weitere Berechnungen erforderliche Teil entnommen wird, läuft das Programm nicht in Zyklen ab:

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

Der Ausdruck [1 ..] erzeugt eine unendliche Liste von ganzen Zahlen. Der take 4 Ausdruck erhält die ersten 4 Elemente aus dieser Liste. Da nachfolgende Listenelemente nicht beansprucht werden, werden sie nicht berechnet.

Bei Haskell bekommen $$$n!$ Aus einer endlosen Liste können Sie folgendermaßen schreiben:

 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 

Versuchen wir mit ein paar Formen von Schema- delay / force etwas Ähnliches zu tun. Das Schlüsselwort delay erstellt ein Versprechen zur Bewertung des Werts eines Ausdrucks. Das Schlüsselwort force weist an, diese Berechnungen durchzuführen. Der resultierende Wert wird berechnet und gespeichert. Bei wiederholtem Zugriff werden keine neuen Berechnungen durchgeführt, aber der zuvor berechnete Wert wird zurückgegeben.

In den Sprachen der Lisp-Familie werden Listen aus Paaren erstellt. Um unendliche Listen zu erstellen, führen wir den Typ des „faulen Paares“ ein - ein Paar, bei dem das erste Element der berechnete Wert und das zweite das Versprechen ist, den Wert zu berechnen. Dazu müssen wir die „heilige Dreifaltigkeit“ der Sprachen der Familie Lisp ( cons , car , cdr ) durch ihre faulen Versionen ergänzen:

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

Der Konstruktor des Lazy- lazy-cons Paares ist als Makro implementiert. Dies geschieht, um zu vermeiden, dass der Wert des zweiten Elements des Paares beim Erstellen berechnet wird.

Die Idee ist, eine endlose Liste von Werten zu erstellen und daraus zu entnehmen, was Sie brauchen. Definieren Sie dazu die Lazy-Version der Prozedur zum Abrufen des Elements nach 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)) 

Hier n! und n+1 sind die Namen der Variablen. In Scheme gibt es im Vergleich zu anderen Sprachen nur sehr wenige Zeichen, die nicht in Bezeichnern verwendet werden können.

Beachten Sie, dass der Generator generate-factorials Generators für unendliche Listen keinen Ausweg aus der Rekursion enthält. Es wird jedoch keine Schleife ausgeführt, da beim Aufruf nur der Kopf der Liste berechnet wird, während der Schwanz durch ein Versprechen zur Berechnung des Werts dargestellt wird.

Jetzt können Sie definieren $$$n!$ wie man bekommt $$$n$ th Element der Liste der Fakultäten:

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

Es funktioniert. Wenn außerdem Fakultäten mit unterschiedlichen Zahlen in einer Sitzung des Interpreters berechnet werden, erfolgen die Berechnungen schneller als in strengen Versionen, da einige der Werte in der Lazy-Liste bereits berechnet wurden.

Übrigens ist der Code in Scheme dem in Haskell sehr ähnlich. Also, die Empfangsbestätigung !! entspricht ungefähr der lazy-list-ref Prozedur lazy-list-ref : entspricht lazy-cons . Dementsprechend erinnert sich Haskell, obwohl es sich zu einem faulen Berechnungsmodell bekennt, im Gegensatz zu delay / force im Schema nicht an die berechneten Werte.

Um die Produktivität zu steigern, können Sie übrigens das Speichern bereits berechneter Werte anwenden - das Speichern. Wir werden die berechneten Werte in einer assoziativen Liste speichern, in der die Schlüssel Zahlen und die Werte ihre Fakultäten sind. Beim Aufruf durchsuchen wir die Liste nach bereits berechneten Werten. Wenn der Wert in der Liste enthalten ist, geben wir diesen gespeicherten Wert zurück. Wenn der Wert nicht in der Liste enthalten ist, berechnen wir ihn, fügen ihn in die Liste ein und geben ihn erst dann zurück. Um sicherzustellen, dass diese Liste immer die aufgerufene Funktion enthält und nicht in der globalen Umgebung, platzieren wir sie in einer statischen Variablen:

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

Diese Implementierung verspricht auch Leistungssteigerungen durch wiederholte Berechnung von Fakultäten verschiedener Zahlen in einer Dolmetschersitzung.

Natürlich ist auch hier eine Optimierung der Schwanzrekursion möglich:

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

„Warum tanzen diese mit einem Tamburin?“, Kann der Leser sagen. In imperativen Programmiersprachen wird dasselbe einfach geschrieben - über eine Schleife funktioniert es schnell und ohne unnötige Speicherkosten. Das Schema hat eine Teilmenge für die imperative Programmierung, es hat auch ein Mittel zum Organisieren von Schleifen - eine spezielle Form von do . Das mit seiner Hilfe geschriebene Verfahren zur Berechnung der Fakultät kann folgendermaßen aussehen:

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

Das do Konstrukt ist ziemlich vielseitig und deshalb nicht zu lesbar. Ist es nicht besser, einen eigenen Zyklus in einem imperativen Stil zu organisieren? Makros helfen dabei:

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

Dank der Optimierung der Schwanzrekursion durch den Interpreter erhalten wir eine Schleife, die wir in imperativen Programmiersprachen gewohnt sind. Durch die Optimierung der Schwanzrekursion wächst der Stapel nicht.

Fakultät definieren mit:

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

Es gibt eine weitere Option, die dem Imperativ for Schleife ähnelt - mit der integrierten Prozedur for-each Prozedur:

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

Tolle und mächtige Schemasprache! Was ist mit Leistung?

Wir werden die GNU Guile verwenden , um die Leistung zu messen. In dieser Umgebung können Sie die Zeit messen, die erforderlich ist, um einen Ausdruck am einfachsten zu bewerten.

Guile funktioniert wie folgt: Kompiliert den Quellcode des Programms in Bytecode, der dann von der virtuellen Maschine ausgeführt wird. Dies ist nur eine der Implementierungen und eine von mehreren Möglichkeiten, ein Schema-Programm auszuführen. Es gibt andere: Racket (verwendet die JIT-Kompilierung), Chicken Scheme (verwendet eine „ehrliche“ Interpretation oder Kompilierung in eine Teilmenge von C) usw. Offensichtlich können sowohl die Einschränkungen als auch die Leistung von Programmen in diesen Umgebungen geringfügig variieren.

Wir werden Messungen bei einem bestimmten Wert durchführen $$$n$ . Was soll es sein? $$$n$ ? Also mit dem der Größte $$$n$ wird in der Lage sein, mit den vorgeschlagenen Optionen "fertig zu werden". Mit den Standardeinstellungen von Guile 2.0 auf einem PC mit Intel Core i5 und 4 GB RAM habe ich Folgendes erhalten:

Von hier aus wurden Leistungstests bei durchgeführt $$$n = 8 \, 000$ . Die Ergebnisse sind in der folgenden Tabelle dargestellt $$$t_ {run}$ - Vorlaufzeit $$$t_ {GC}$ - Garbage Collector-Laufzeit in Sekunden.
Für alle Prozeduren außer faul und gespeichert werden die kleinsten Werte der Laufzeit und die entsprechende Zeit des Garbage Collectors erhalten, die aus den Ergebnissen von drei Starts bei erhalten werden $$$n = 8 \, 000$ .
Bei gespeicherten und faulen Prozeduren wird die Ausführungszeit des ersten Aufrufs angezeigt, dann der kleinere der drei Aufrufe.

Wir haben 4 Optionen, die mit großen arbeiten können $$$n$ . Bei $$$n = 100 \, 000$ Sie haben die folgenden Berechnungs- und Speicherbereinigungszeiten:

Sie können das mit nicht zu groß sehen $$$n$ der schnellste und gleichzeitig der kürzeste ist der erste. Die gleiche Option stimmt am besten mit der mathematischen Definition von Fakultät überein. Die Option zur Optimierung der Schwanzrekursion ist der Leistung nicht viel unterlegen. Beide Optionen werden von den Autoren der Sprache idiomatisch empfohlen. Die Schlussfolgerung ist in vielerlei Hinsicht offensichtlich: Sofern nicht anders angegeben, wird der für die Sprache „typische“ Ansatz zumindest für die erste Implementierung eines Algorithmus oder einer Methode bevorzugt.

Gleichzeitig erlaubte uns die Schemasprache, viele Optionen für die Implementierung der Fakultätsberechnung zu schreiben, wobei eine sehr begrenzte Anzahl von Grundelementen verwendet wurde (das „minimale Mittel - maximale Eindrücke“). Trotz ihres ehrwürdigen Alters und nicht allzu weit verbreitet kann diese Sprache dennoch für die Forschungsprogrammierung empfohlen werden: Es scheint, dass Sie alles auf jede Art und Weise (und auf jede Art und Weise) bequem implementieren können.