In diesem kurzen Hinweis werden wir uns ansehen, wie Sie in Lisp derzeit sehr beliebte Softwaremechanismen wie die teilweise Anwendung und das Currying von Funktionen implementieren können. Dabei verwende ich meine Homelisp- Implementierung (dies ist ein reiner Lisp-Interpreter mit einigen zusätzlichen Funktionen).
Die Verwendung einer Teilanwendung in Common Lisp ist wahrscheinlich etwas schwierig (da funcall / apply zum Aufrufen eines berechneten Funktionsobjekts verwendet werden muss). im Schema sollte es einfacher sein. Ich plane, bald eine neue Version von HomeLisp zu veröffentlichen, für die kein funcall / apply erforderlich ist, um ein berechnetes Funktionsobjekt aufzurufen. In Fällen, in denen das Verhalten des Codes unterschiedlich ist, werde ich dies betonen.
Teilanwendung und Currying sind strenge mathematische Operationen. Aber wir werden sie "an den Fingern" betrachten, ohne auf Lambda-Kalkül und kombinatorische Logik zurückzugreifen.
Eine teilweise Anwendung der Funktion f besteht darin, von der Funktion f eine neue Funktion f 'zu erhalten, die die angegebenen Argumente bereits übernommen hat und bereit ist, den Rest zu akzeptieren. Wofür ist eine Teilanmeldung? Zum Beispiel, damit ein Funktionswert von einer Funktion zurückgegeben werden kann.
Betrachten wir eine Teilanwendung anhand eines einfachen Beispiels. Die Funktion f sei gegeben durch die Formel:
f (x, y, z) = x + y ** 2 + z ** 3,
dann sollte die teilweise Anwendung dieser Funktion mit den Argumenten x = 1 und y = 2 die Funktion erzeugen:
f '(z) = 1 + 4 + z ** 3 = 5 + z ** 3
In Haskell kostet eine teilweise Anwendung den Programmierer nichts:
Prelude> f x y z = x+y**2+z**3 --
f :: Floating a => a -> a -> a -> a
Prelude> f 1 2 3 -- ...
32.0 -- !
it :: Floating a => a
Prelude> f' = f 1 2 -- x=1 y=2 f'
f' :: Floating a => a -> a
Prelude> f' 3 -- f'
32.0 --
it :: Floating a => a
In Lisp schlägt dieser Versuch jedoch fehl:
(defun f (x y z) (+ x (* y y) (* z z z))) ;;
==> F
(f 1 2 3) ;;
==> 32 ;;
(f 1 2) ;; ...
PairLis:
: F
: (X Y Z)
: (1 2)
==> ERRSTATE
Natürlich hat Lisp einen Mechanismus zum Erstellen von Funktionen mit einer beliebigen Anzahl von Argumenten (das & rest-Konstrukt); Sie können eine Funktion erstellen, die zwei oder drei (oder zehn) Parameter akzeptiert:
(defun s (&rest x) ;; - x
(apply '+ x)) ;;
==> S
(s 1 2) ;;
==> 3
(s 1 2 3) ;;
==> 6
Es ist jedoch wichtig, den Unterschied zu verstehen: Diese Funktion verarbeitet alle Parameter und gibt das Ergebnis der Berechnung zurück, während die teilweise Anwendung zu einer neuen Funktion führt, die „bereit ist, die Berechnung fortzusetzen“.
Mal sehen, wie wir einen Teilfunktionsanwendungsmechanismus in Lisp implementieren können. Und es wird uns dabei helfen ... ja, der Apparat anonymer Funktionen (Lambda). Einige Programmierer denken, dass anonyme Funktionen nur zum Speichern von Namen benötigt werden (sie sagen, ihr Platz in einem Stream-Map-Filter-Reduce, um eine kurze Aktion für ein Sequenzelement auszuführen). In der Tat können anonyme Funktionen viel mehr, was wir jetzt sehen werden.
Lassen Sie uns zunächst untersuchen, wie eine Funktion als Ergebnis eine andere Funktion zurückgeben kann. In Lisp ist es sehr einfach:
(defun func-gen (x)
(lambda (y) (+ x (* y y))))
==> FUNC-GEN
(func-gen 5)
==> (CLOSURE (Y) ((+ X (* Y Y))) ((X 5)))
Wie Sie sehen können, gibt die Funktion einen Abschluss zurück, in dem der Wert der freien Variablen x fest ist (gleich 5). Das Ergebnis einer Funktion kann als Funktion aufgerufen werden. Dazu müssen Sie in Common Lisp und HomeLisp (mit Kernel-Revision <= 13.53) funcall verwenden:
(funcall (func-gen 5) 7)
==> 54
Nun ist klar, wie wir vorgehen können, wenn wir eine Funktion f aus n Argumenten und einem Wert von x nehmen und als Ergebnis eine Funktion aus (n-1) Argumenten erhalten wollen. Bezeichnen wir die Liste der formalen Parameter unserer Funktion mit plist. Dann müssen Sie nur noch einen Lambda-Ausdruck wie folgt erstellen:
(lambda (-plist) (apply f (cons x -plist)))
Die Idee ist sehr einfach: Wir erstellen einen Lambda-Ausdruck, in dessen Körper wir einfach die ursprüngliche Funktion in der Parameterliste aufrufen, in der der Kopf durch den Wert von x ersetzt wird.
Dies bedeutet, dass Sie für die teilweise Anwendung der Funktion einen Lambda-Ausdruck erstellen müssen, der auf dieser Funktion basiert und ein Argument weniger enthält. Das während der teilweisen Anwendung angegebene Argument wird beim internen Aufruf unserer Funktion im Hauptteil des Lambda-Ausdrucks "berücksichtigt".
Wie implementiere ich das? Einfach ... HomeLisp verfügt über eine getd-Funktion, die den Zugriff auf den definierenden Ausdruck oder das Makro einer Funktion ermöglicht:
(defun g (x y z) (+ x (* x y) (* x y z)))
==> G
(getd 'g)
==> (EXPR (X Y Z) (+ X (* X Y) (* X Y Z)))
Wie Sie sehen können, gibt getd den definierenden Ausdruck der Funktion zurück, in der "anstelle" des Lambda ein spezielles EXPR-Atom vorhanden ist. Wir können die Parameterliste unserer Funktion (das zweite Element des Ergebnisses) nehmen und einen Lambda-Ausdruck konstruieren, dessen Parameter das Ende der ursprünglichen Parameterliste bilden, und im Hauptteil des Lambda-Ausdrucks werden wir die ursprüngliche Funktion mit der vollständigen Liste der Parameter aufrufen.
(defun part-apply (f a)
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
Aus dem obigen Code ist leicht zu verstehen, dass plist die ursprüngliche Liste der Funktion f ist, die wir teilweise anwenden möchten. rlist ist die ursprüngliche Liste ohne das erste Element, und clist ist die vollständige Liste der Parameter, wobei das erste Element durch x ersetzt wird. Insbesondere für die obige Funktion g gilt plist = (xyz), rlist = (yz) und clist = (ayz). Lassen Sie uns nun überprüfen, wie eine Teilanwendung funktioniert:
(part-apply 'g 111)
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
Sie können sicherstellen, dass genau dies geplant ist: part-apply hat eine neue Funktion mit einer geringeren Anzahl von Argumenten zurückgegeben. Wenn diese neue Funktion mit den Parametern y und z aufgerufen wird, entspricht das Ergebnis genau dem Aufruf der ursprünglichen Funktion g mit drei Argumenten: 111 y und z:
(g 111 1 2)
==> 444 ;;
(funcall (part-apply 'g 111) 1 2) ;; "--"
==> 444
((part-apply 'g 111) 1 2) ;; "-"
==> 444
Im Folgenden werde ich (der Kürze halber) keinen Funcall angeben. Im nächsten Kern von HomeLisp wird das Schema zur Berechnung von Funktionen geändert - die "Schema" -Syntax wird verfügbar.
Gehen wir weiter. Es wird nun einen natürlichen Drang geben, das Ergebnis der erneuten Anwendung erneut anzuwenden. Dies stellt sich als sehr einfache Angelegenheit heraus - schließlich ist das Ergebnis einer teilweisen Anwendung ein Lambda-Ausdruck und hat fast die gleiche Struktur wie das von getd zurückgegebene Ergebnis. Die Parameterliste des Lambda-Ausdrucks ist das zweite Element in der Liste. All diese Überlegungen ermöglichen es uns, die endgültige Lösung für das Problem zu finden:
(defun part-apply (f a)
(cond ((and (atom f) (member 'expr (proplist f))) ;; *** ***
(let* ((plist (cadr (getd f))) ;;
(rlist (cdr plist)) ;;
(clist (cons a rlist))) ;; a
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
((eq 'lambda (car f)) ;; *** - ***
(let* ((plist (cadr f)) ;;
(rlist (cdr plist)) ;;
(clist (cons x rlist))) ;; x
`(lambda ,rlist (apply (quote ,f) (list ,@clist)))))
(t (raiseerror "part-apply: "))))
Hier wird die Analyse des ersten Parameters hinzugefügt: Wenn es sich um ein Atom handelt, muss es eine Funktion (vom Typ EXPR) "darstellen"; Wenn der erste Parameter weder ein "gültiges" Atom noch ein Lambda-Ausdruck ist, wird eine Fehlerbedingung ausgelöst. Der Code könnte natürlich weiter verkürzt werden, zwei fast identische Zweige bleiben zur Klarheit übrig. Nun wollen wir sehen, wozu diese Funktion fähig ist:
(part-apply (part-apply 'g 1) 2) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
((part-apply (part-apply 'g 1) 2) 3) ;;
==> 9
(part-apply (part-apply (part-apply 'g 111) 1) 2) ;;
==> (LAMBDA NIL (APPLY (QUOTE (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))) (LIST 2)))
((part-apply (part-apply (part-apply 'g 111) 1) 2)) ;; ...
==> 444
(setq u (part-apply 'g 111)) ;;
==> (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))
;; U
(part-apply u 1) ;;
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 111 Y Z)))) (LIST 1 Z)))
((part-apply u 1) 2) ;;
==> 444
Jetzt lass uns Curry machen. Eine Curry-Funktion, die eine unzureichende Anzahl von Argumenten akzeptiert, gibt eine Funktion zurück, die den Rest verarbeiten kann. Der Hauptzweck des Curry ist die teilweise Anwendung. Wir gingen vom anderen Ende aus: Schauen wir uns nun an, wie Currying implementiert werden kann, wenn es eine Teilanwendung gibt.
Es sei eine Funktion g mehrerer Argumente gegeben. Wir werden eine Curry-Version davon unter einem anderen Namen erstellen! G. Das Wesen der Konstruktion ist wie folgt: Die Funktion! G akzeptiert eine unbestimmte Anzahl von Argumenten. Nach dem Aufruf muss die Anzahl der übergebenen Argumente überprüft werden. Wenn diese Zahl gleich der Anzahl der Argumente der ursprünglichen Funktion g ist, sollte from an die Eingabe g übergeben werden. Wenn es mehr Argumente gibt, als g akzeptieren kann, sollte eine Fehlerbedingung ausgelöst werden. Wenn die Anzahl der Argumente jedoch geringer ist als die der Funktion g, dann ... ja, ja - Sie müssen eine sequentielle Teilanwendung ausführen. Geben Sie das Ergebnis dieser Anwendung zurück.
In diesem Fall ist es zweckmäßig, ein Makro zu verwenden. Der Code mit Kommentaren ist unten:
(defmacro curry (f)
(let* ((parmlist (cadr (getd f))) ;; f
(body (cddr (getd f))) ;; f
(lp (length parmlist)) ;; f
(cf (implode (cons '! (explode f))))) ;;
`(defun ,cf (&rest x)
(let ((lx (length x))) ;;
(cond ((= lx ,lp) ;;
(let ((e `(lambda ,parmlist ,@body)))
(apply e x)))
((> lx ,lp) ;;
(raiseerror "curry: "))
(t (let ((tmp nil)) ;;
(iter (for a in x) ;;
(setq tmp (if (null tmp) (part-apply (quote ,f) a) (part-apply tmp a))))
tmp)))))))
Es lohnt sich, hier die Konstruktion des neuen Funktionsnamens zu kommentieren. Verwenden Sie dazu die Explosionsfunktionen von HomeLisp, mit denen eine Liste der konstituierenden Symbole aus einem Atom erstellt wird, und implodieren Sie, um die Listensymbole zu einem zu komprimieren und ein neues Atom zu generieren.
Lassen Sie uns nun unser Makro in Aktion überprüfen:
(curry g) ;; g
==> !G ;;
(!g 1 2 3) ;;
==> 9 ;; g
(!g 1 2) ;; -
==> (LAMBDA (Z) (APPLY (QUOTE (LAMBDA (Y Z) (APPLY (QUOTE G) (LIST 1 Y Z)))) (LIST 2 Z)))
;; :
((!g 1 2) 3) ;;
==> 9
((!g 1) 2 3) ;;
==> 9
(!g 1 2 3 4) ;;
curry:
==> ERRSTATE
Das Currying wurde ohne zusätzliche Kontrolle durchgeführt. Und wir haben keinen Curry-Lambda-Ausdruck implementiert. Sie können alles tun, wenn Sie möchten ...
So können Sie die Anwendung von Teilfunktionen und das Currying in Lisp ohne großen Aufwand implementieren. Lisp ist eine wunderbare Sprache!
Vielen Dank für Ihre Aufmerksamkeit.