2. Programmieren mit Lisp¶
2.1. Einführung¶
„the greatest single programming language ever designed“ - Alan Kay
„Lisp is a programmable programming language.“ - John Foderaro
„Lisp is worth learning for the profound enlightenment experience you will have when you finally get it; that experience will make you a better programmer for the rest of your days, even if you never actually use Lisp itself a lot.“ - Eric Raymond
2.1.1. Definition¶
Lisp [List Processing] ist eine Familie von Programmiersprachen, deren Grundkonzept 1958 von John McCarthy entworfen wurde. Sie ist die weltweit erste funktionale und nach Fortan die älteste noch verbreitete Programmiersprache. Lisp basiert auf dem untypisierten Lambda Kalkül, was die theoretische Grundlage aller funktionalen Sprachen bildet. Aufgrund seiner Flexibilität und der Fähigkeit Quelltext zu generieren erlangte Lisp große Beliebtheit im Forschungsfeld der künstlichen Intelligenz. Wegen der ausufernden Klammersetzung wird sie auch gerne als „Lots of Irritating Superfluous Parentheses“ bezeichnet.
Bekannte Lisp-Dialekte sind:
Common Lisp (am weitesten verbreiteter Industriestandard)
Scheme (neben CLisp bekanntester Dialekt)
Clojure (wird in Bytecode für JVM kompiliert)
Racket (moderne Ableitung von Scheme - Sprache zur Erzeugung von Programmiersprachen)
2.1.2. Eigenschaften von Lisp¶
Funktionale Programmierung
Expression-orientiert
Metaprogrammierung
dynamisches Typsystem
Kompilieren & Interpretieren möglich
2.1.3. λ - Kalkül¶
1936 von Alonzo Church & Stephen Kleene entworfene formale Sprache zur Beschreibung des Funktionsbegriffes. Mit dieser minimalen, universellen & abstrakten Programmiersprache lässt sich alles ausdrücken, was sich mit einer modernen Programmiersprache ausdrücken lässt. Es bildet die theoretische Grundlage aller funktionalen Programmiersprachen. λ−Kalkül und Turingmaschine beschreiben äquivalente Klassen berechenbarer Funktionen. Damit sind funktionale und imperative Programmiersprachen gleichmächtig in Bezug auf Berechenbarkeit.
λ - Funktionsdarstellung:
Die Darstellung der Zahlen ist allerdings inkorrekt. Die korrekte Darstellung von Zahlen im Lambdakalkül erfolgt über verschachtelte Aufrufe der Identitätsfunktion ( λ x . x ), wobei die Anzahl der Verschachtelungen dem Wert der Zahl entspricht.
β-Reduktion:
2.2. Grundlagen¶
2.2.1. Syntax¶
Folgender Lisp Code filtert die ungeraden Elemente einer Liste heraus:
(defun even (x) (= (mod x 2) 0))
(remove-if-not #'even '(1 2 3 4 5))
Der äquivalente Java Code lautet:
public class PrintEvenNumbers{
public static void main(String []args){
int[] num = {1, 2, 3, 4, 5};
for (int i=0; i< num.length; i++) {
if ((num[i] % 2) == 0)
{
System.out.println(num[i]);
}
}
}
}
Im Beispiel ist ein Großteil der Lisp Syntax zu erkennen. Das Defun Makro wird verwendet, um die Funktion zu definieren. x ist der Parameter der Funktion und (= (mod x 2) 0) der Funktionskörper. In Lisp können Funktionen parametrisch übergeben aber auch zurückgeliefert werden. Beides führt zu weitreichenden Abstraktionsmöglichkeiten.
2.2.2. Typisierung¶
Lisp ist dynamisch typisiert - Typ-Prüfungen erfolgen also erst zur Laufzeit. Der Typ eines Ausdrucks wird nicht am Bezeichner, sondern am Wert festgemacht. Dadurch können sich die Typen von Variablen ändern, da sie lediglich als Verweis auf einen konkreten, typisierten Wert dienen. Dynamische Typisierung erhöht die Ausdrucksstärke von Lisp und erlaubt eine schnellere Entwicklung von Prototypen.
2.2.3. Datenstrukturen¶
Syntaktische Grundelemente von Lisp sind symbolische Ausdrücke. Da sowohl Quelltext als auch Daten als S-expressions dargestellt werden, unterscheidet Lisp nicht zwischen Code und Daten. Ein symbolischer Ausdruck kann entweder ein Atom oder eine Liste sein. Atome können eine Zeichenkette, eine Zahl oder ein Symbol sein. Listen werden intern als einfach verknüpfte Listen repräsentiert, wobei jeder Knoten in einer Liste als Cons-Zelle bezeichnet wird. Eine Cons-Zelle besteht aus zwei Teilen: CAR („First“) zeigt auf das Element, das der Knoten enthält. CDR („Rest“) zeigt auf die nächste Cons-Zelle in der Liste oder auf NIL, wenn das Ende der Liste erreicht ist. Listen können beliebig verschachtelt werden, woraus sich neue Strukturen bilden lassen, wie z.B. Queues.
(setf x (cons 'a (cons 'b nil))) ;; or (setf x '(a b))
(setf x '((r t) b nil))
(setf y (cons 'd x))
Folgende S-expression lässt sich als Baumstruktur im Speicher wie folgt repräsentieren:
(/ 6 (+ 3 3))
2.3. Funktionale Programmierung¶
2.3.1. Definition¶
Diese Expressionen können wir kombinieren,um noch komplexere Strukturen zu bilden. Um von bestimmten wiederkehrenden Mustern in diesen Expressionen zu abstrahieren, verwenden wir in Lisp Funktionen, im Gegensatz zur objektorientierten Programmierung bei der wir Objekte als einzelne Bausteine verwenden. Syntaktisch
(f o)
statt
o.f()
Wir haben Zugriff auf die ganzen Datenstruktur. In der objektorientierten Programmierung verwenden wir Datenkapselung, um Details zu verbergen. Ein Objekt verfügt über eine internen Zustand auf den nur das Objekt zugreifen k ann. Dies vereinfacht die Modularisierung und Wiederverwendbarkeit von Komponenten, da weniger Argumente übergeben werden müssen. Bei der Funktionalen Programmierung wird alles übergeben. Funktionale Programmierung bedeutet also Programme zu entwickeln, welche Seiteneffekte vermeiden und stattdessen Werte zurückgeben. Unter einem Seiteneffekt kann man sich die Zuweisung einer Variable vorstellen. Wir haben also keinen internen, veränderlichen Zustand der unsere Berechnung beinflussen könnte. Für eine bestimmte Eingabe erhalten wir immer die gleiche Ausgabe. Durch die Vermeidung von Seiteneffekten verbessert sich also die Verständlichkeit, Lesbarkeit, da der Code deklarativ geschrieben wird, Testbarkeit und das Debuggen von Programmen.
Dieses Beispiel aus On Lisp von Paul Graham vergleicht eine funktionale mit einer imperativen Implementierung
(defun fun (x)
(list 'a (expt (car x) 2)))
(defun imp (x)
(let (y sqr)
(setq y (car x))
(setq sqr (expt y 2))
(list 'a sqr)))
Ein funktionales Programm beschreibe in dem Fall was man möchte statt zu sagen wie man es bekommt.
2.3.2. Funktion höherer Ordnung / First-Class-Funktion¶
Lisp bietet uns noch mehr Möglichkeiten zur Abstraktion. Dazu zählen Funktionen höherer Ordnung. Diese können First-Class-Funktionen als Argumente erhalten, und zurückgeben. Zum Beispiel eine Funktion, die eine andere als Argument erhält.
(apply #'* '(2 2))
Oder als anonyme Funktion (Funktionsdefinition ohne Bezeichner)
(apply #'(lambda (x x) (* x x)) '(2 2))
Was den Effekt hat wie
(* 2 2)
Beispiel für eine Funktion, welche eine andere Funktion zurückgibt
(defun multiplizier (n)
(lambda (x) (* x n)))
(apply (multiplizier 5) 3)
Diese gibt eine Funktion zurück, welche eine Eingabe mit n multipliziert. So lässt sich auch das Konzept der Closure anwenden. Hier hat eine Funktion Zugriff auf ihren Erstellungskontext, welcher außerhalb der Funktion nicht sichtbar ist. Somit lässt sich Datenkapslung realisieren, ähnlich zu der aus der objektorientierten Programmierung. Man kann First-Class-Funktionen auch zur Laufzeit erzeugen oder diese in Datenstrukturen speichern. Design pattern aus OO Sprachen lassen sich so in funktionalen Programmiersprachen realisieren.
2.3.3. Polymorphie¶
Polymorphie gibt uns in der objektorientierten Programmierung die Möglichkeit einem Bezeichner Objekte mit verschiedenen Datentyp zuzuordnen. Somit lässt sich das Dependency-Inversion-Prinzip erfüllen und die Erweiterbarkeit unseres Programm verbessern. Nach dem Prinzip sollte man von Abstraktionen und nicht Konkretisierungen abhängen. Eine andere Form von Polymorphie existiert in dem Lisp Dialect Clojure. Dieser kommt vollkommen ohne Vererbung aus. Man definiert eine Methode, die basierend auf den Argumente zu anderen Methoden dispatched. Bei Java findet ein single-dispatch statt. Also es wird dispatched nach dem Typen des Empfängers. Clojure verallgemeinert dies zu mehreren. Beispiel:
(defmulti konsumiere (fn [x y] [(:Entity x) (:Entity y)]))
(defmethod konsumiere [:Entwickler :Kaffee] [e k] :Code)
(defmethod konsumiere [:Manager :Kaffee] [m k] :Talk)
Die Prämisse ist, dass wir unsere Domäne gut mit wenigen, abstrakten Typen ausdrücken können und dann kontinuerlich diese einfach mit neuen Operationen erweitern. Deshalb sind solche Funktionalen Programmiersprachen gut geeignet für Probleme, wo wir unsere Typen a priori kennen und horizontal erweitern möchten. Vererbung ist vertikales erweitern. Man definiert zu beginn abstrakte Operationen und erweitert die Typhierarchie. Hier wär eine horizontale Erweiterung problematisch, da wenn wir eine neue Operation in die abstrakte Klasse hinzufügen, muss man alle Unterklassen modifizieren, während man in Clojure einfach eine neue Multimethode erstellt.
2.3.4. Nebenläufigkeit und Moores Law¶
Es ist zudem einfacher Nebenläufige Programme zu konstruieren. Dies wird wichtiger in der Zukunft, wenn Moores Law nicht mehr gilt. Nach Moores Law verdoppelt sich die Zahl der Transistoren auf einem Mikroship alle zwei Jahre.
Daraus folgt, falls unsere Anwendung zu langsam ist, müsse man nur lang genug warten, um die nötige Performanz zu erreichen. In der Zukunft muss man nun aber nebenläufige Anwendungs konstruieren, um eine weitere Geschwindigkeitserhöhung zu erzielen. Dies ist ein schwieriges Problem für Programme mit veränderlichen Zustand. Es können data races, deadlocks auftreten, welche schwer zu debuggen sind. Eine Lösung bieten z.B. Locks. Diese können aber bei komplexeren Programmen schwer zu handhaben sein. In der funktionalen Programmierung können wir Probleme umgehen, da wir mit unverändlichen Zustand arbeiten, welcher sicher geteilt werden kann zwischen mehreren Threads.
2.4. Metaprogrammierung¶
„One can even conjecture that Lisp owes its survival specifically to the fact that its programs are lists, which everyone, including me, has regarded as a disadvantage.“ - John McCarthy, „Early History of Lisp“
2.4.1. Definition¶
Eine alternative Möglichkeit zur Abstraktion in Lisp sind Makros. Das Makrosystem ist ein Werkzeug für Metaprogrammierung. Metaprogrammierung meint das erstellen von Programmen durch andere Programme. Dies ist im Vergleich zu anderen Programmiersprachen in Lisp deutlich einfacher. Lisp ist nämlich homoikonisch. Homoikonizität ist die Eigenschaft von Programmiersprachen, dass Programmcode gleichzeitig Datenstrukturen der Programmiersprache sind. Somit kann die Erzeugung des Programms durch das Metaprogramm mithilfe Lisp selbst erfolgen
2.4.2. Domänenspezifische Sprachen¶
Mithilfe von Makros lassen sich dann Domänenspezifische Sprachen, also formale Sprachen für einen bestimmtes Problemfeld, erstellen. Der Vorteil von Domänenspezifischen Sprachen besteht in der deklarativen Beschreibung eines Sachverhaltes. Damit erhöht sich die Lesbarkeit aber auch die Erlernbarkeit für Domänenexperten aufgrund weniger technischen Code. Dies geht auch in anderen Programmiersprachen, wie das Fluent Interfaces Konzept beschreibt, jedoch ist noch immer die Syntax der jeweiligen Programmiersprache erkennbar.
2.4.3. Bottom-up design¶
Im traditionellen Sinne würde man ein Top-down Design anwenden. Man überlegt, was das zu lösende Problem ist, und teilt dieses in Teilprobleme auf. Lisp Programme lassen sich nach dem Prinzip des bottom-up Design entwickeln. Die Sprache wird an das jeweilige Problem angepasst. Programm und Sprache entwickeln sich somit gemeinsam. Entwickeln wir zum Beispiel einen Musikplayer, würden wir unser Programm in verschiedene Schichten (GUI, App, DSP) strukturieren. Für jede Schicht könnte man dann eine eigene DSL entwickeln. Bottom-up Design resultiert dann in ein kleineres Programm, da stattdessen die Sprache größer wird durch Erweiterung mit neuen, abstrakten Operatoren. Dieses Vorgehen eignet sich für kleine, agile Teams.
2.4.4. Macros¶
Macros sind unser Mittel für Metaprogrammierung in Lisp. Man sollte Macros nur dann nutzen, wenn man das Problem mit Funktionen nicht lösen kann. Das ist genau dann der Fall, wenn wir die Kontrolle über die Evaluation der Parameter haben müssen. Wenn wir eine Funktion aufrufen, werden die Argumente vor dem Funktionsaufruf bereits ausgewertet.
(write (* 2 2))
Bei dem Beispiel wird zuerst (* 2 2) ausgewertet, also erhalten wir 4 und dann erst wird write aufgrufen und die 4 ausgegeben. Also geben wir nicht die Expression (* 2 2) aus.
Ein Macro lässt sich wie folgt definieren
(defmacro while (test &body body)
'(do ()
((not ,test))
,@body))
2.4.5. Neue Sprachfeatures¶
Macros können auch verwendet werden, um neue Sprachfeatures zu implementieren z.b. neue Kontrollstrukturen hinzuzufügen oder ein OO System. Man muss also nicht auf das Sprachentwicklerteam warten. Dieses Beispiel zeigt List Comprehensions in Python.
divisibleByTwo = [x for x in range(10) if x % 2 == 0]
So sieht die Funktionalität mittels Macro in Lisp aus.
(lcomp x for x in (range 10) if (= (mod x 2) 0))
Hier sieht man die Implementierung des Macros
(defmacro lcomp (expression for var in list conditional conditional-test)
;; create a unique variable name for the result
(let ((result (gensym)))
;; the arguments are really code so we can substitute them
;; store nil in the unique variable name generated above
`(let ((,result nil))
;; var is a variable name
;; list is the list literal we are suppose to iterate over
(loop for ,var in ,list
;; conditional is if or unless
;; conditional-test is (= (mod x 2) 0) in our examples
,conditional ,conditional-test
;; and this is the action from the earlier lisp example
;; result = result + [x] in python
do (setq ,result (append ,result (list ,expression))))
;; return the result
,result)))
2.5. REPL getriebene Entwicklung¶
REPL steht für read-eval-print loop. Dies ist eine interaktive computer programmier Umgebung für LISP, ohne die Einschränkungen des Edit-Compile-Run-Debug Zyklus. Sie führt Nutzereingaben aus und gibt die Ergebnisse an den Nutzer zurück. Eine minimale REPL lässt sich wie folgt definieren
(define (REPL environment)
(print (eval environment (read)))
(REPL environment) )
Die read funktion nimmt s-expression entgegen. Diese wird in eine LinkedList geparsed, welche dann durch die eval Funktion evaluiert wird und mit print ausgegeben. Die REPL eignet sich gut für explorative Programmierung und Prototypen in Kombination mit Buttom-up design.
2.6. Zusammenfassung und Konklusion¶
Wir haben hier eine Einführung zu Lisp gegeben und die zugrunde liegenden Paradigmen und Prinzipien erläutert. Wir kamen zum Schluss, dass Lisp Dialekte, wie z.B. Clojure eine Alternative zu den bekannten, mainstream Sprachen ist. Die Erfahrung von Experten zeigt, dass es schwierig ist lesbare, korrekte, testbaren, nebenläufigen Code für Programme mit veränderlichen Zustand zu schreiben. Da Moores Law nicht ewig gilt und Programme schneller werden müssen, wird dies wahrscheinlich umso wichtiger. Funktionale Programmierung erleichtert dies. Wir denken auch das DSLs eine wichtige Rolle in der Entwicklung spielen werden, da sie bekanntlich die Kommunikation zum Domänen Experten verbessern können, was eines der härtesten Probleme in der Softwareentwicklung nach Martin Fowler ist. Die Metaprogrammierung in Lisp erleichtert genau das. Die Zeit wird zeigen, ob sich Test-driven-development bewährt und somit die Nachteile von dynamisch typisierten Sprachen, wie Lisp bei größeren Projekten entfallen.
Zu guter Letzt haben wir die Ki gefragt, warum wir Lisp hier überhaupt lernen
(import [transformers [pipeline set_seed]])
(setv generator (pipeline "text-generation" :model "gpt2"))
(set_seed 42)
(setv result (get (generator "We learned Lisp because it is" :max_length 30 :num_return_sequences 5) 3))
(setv text (get result "generated_text"))
(print "AI:" text)
(setv nlp (pipeline "sentiment-analysis"))
(setv label (get (get (nlp text) 0) "label"))
(if (= label "POSITIVE")
(do
(print "Result: AI likes Lisp, too"))
(do
(print "Result: AI does not like Lisp")))
Ihre Antwort:
