Der Stack ist eine rein funktionale Datenstruktur und daher unveränderlich. Der Stack ist als implementiert. Ein Tripel ist eine weitere rein funktionale Datenstruktur, die drei Werte hält. Über "getter"-Funktionen kann auf diese Werte des Tripels zugegriffen werden. Der erste Wert des Tripels stellt die Größe (Anzahl der Elemente) des Stacks dar. Gleichzeitig repräsentiert der erste Wert, den Index des Kopfes (oberster Wert), des Stacks. Die Grösse/der Index, des Stacks wird als angegeben. Der zweite Wert repräsentiert den Vorgänger-Stack. Der dritte Wert stellt den Kopf ( oberster Wert ) des Stacks dar.
Stack Implementation:
Empty-Stack
Zur späteren Verwendung von einem Stack wird der leere Stack als Grundbaustein benötigt. Der leere Stack hat die Grösse/ den Index Null. Der leere Stack hat keinen Vorgänger, stattdessen hat er die als Platzhalter. Ausserdem bestitzt der leere Stack keinen Kopf (oberster Wert), sondern hat als Platzhalter die Identitätsfunktion.
Implementation des leeren Stacks:
Aufbau
Ein kleines grafisches Beispiel wie ein Stack aussieht. In diesem Beispiel wird ein Stack mit Emoji's erstellt:
Der Stack s3 besteht nun aus den Elementen: 😎, 🤓, 👾 .
Element an Index 1:😎
Element an Index 2:🤓
Element an Index 3:👾
Verwendung
push
Um einen Stack zu erstellen fügt man Elemente, dem leeren Stack hinzu. Dafür gibt es die Push-Funktion. Die Push-Funktion nimmt einen Stack und einen Wert entgegen. Der übergebene Wert, wird auf den übergegebenen Stack hinzugefügt.
Beispiel:
Nun besitzt der Stack von oben den Wert 1.
pop
Um den obersten Wert vom Stack zu entfernen gibt es die pop-Funktion. Die pop-Funktion gibt ein zurück. Dieses Pair besteht aus dem vorgänger-Stack und dem Wert, der vom Stack entfernt wurde. Mit den "getter"-Funktionen für Pairs, kann auf die Werte zugegriffen werden.
Beispiel:
Weitere Funktionen
size
Um auf den auf die Grösse eines Stacks zuzugreifen gibt es die Funktion size. Diese Funktion nimmt einen Stack entgegen und gibt die Grösse, des Stacks als zurück.
Beispiel:
head
Um auf den Kopf (oberster Wert) des Stacks zuzugreifen gibt es die Funktion head. Diese Funktion nimmt ein Stack entgegen und gibt den Kopf des Stacks zurück.
Beispiel:
hasPre
Die Funktion hasPre nimmt einen Stack entgegen und gibt ein zurück, der aussagt ob der übergegebene Stack einen Vorgänger hat oder nicht.
Beispiel:
Element per Index holen
getElementByIndex
Die Funktion getElementByIndex nimmt einen Stack und eine oder JS-Zahl, die den Index des Elements repräsentiert, entgegen. Falls an diesem Index ein Element existiert, wird dieses zurückgegeben ansonsten wird auf der Console einer Error-Hinweis erscheinen.
Beispiel:
Stack zu einem Array konvertieren und umgekehrt
convertStackToArray
Die Funktion convertStackToArray nimmt einen Stack entgegen und gibt einen Array mit denselben Elementen zurück.
Beispiel:
convertArrayToStack
Die Funktion convertArrayToStack nimmt einen Array entgegen und gibt einen neuen Stack mit den Elementenn vom übergebenen Array zurück.
Beispiel:
Stack umkehren
reverseStack
Die Funktion reverseStack nimmt einen Stack entgegen und gibt einen neuen Stack zurück, bei diesem die Elemente in umgekehrter Reihenfolge sind.
Beispiel:
Stack - Reduce, Map und Filter
Die JavaScript Funktionen reduce, map und filter wurden auch für den Stack implementiert.
Reduce
Reduce nimmt einen Stack entgegen und ein Argument-. Das erste Argument des Paares muss eine reduce-Funktion(wie bei JavaScript reduce). Das zweite Argument muss ein Startwert sein. Die Funktion gibt den reduzierten Wert zurück.
Beispiel:
Map
Map nimmt einen Stack und eine map-Funktion (wie bei JavaScript Array map) entgegen. Zurück gibt die Funktion einen neuen Stack mit den "gemappten" Werten.
Beispiel:
Map with Reduce
Ausserdem gibt es noch eine MapWithReduce-Funktion die mittels der obenstehenden reduce-Funktion implementiert ist. Sie nimmt auch einen Stack und eine Map-Funktion entgegen. Diese Funktion kann genau gleich wie die Map Funktion verwendet werden.
Implementation:
Filter
Filter nimmt einen Stack und eine filter-Funktion (wie bei JavaScript Array filter) entgegen. Die Funktion gibt den gefilterten Stack zurück. Wenn keine Elemente dem Filter entsprechen wird der leere Stack zurückgegeben.
Beispiel:
Filter with Reduce
Ausserdem gibt es noch eine FilterWithReduce-Funktion die mittels der obenstehenden reduce-Funktion implementiert ist. Sie nimmt auch einen Stack und eine Filter-Funktion entgegen. Diese Funktion kann genau gleich wie die Filter Funktion verwendet werden.
Implementation:
ForEach-Loop
Die Funktion forEach nimmt einen Stack und eine Callback-Funktion entgegen. Die Funktion iteriert über den Stack und ruft in jeder Iteration die Callbackfunktion auf. Der Callbackfunktion werden zwei Argumente übergeben. Das erste Argument ist das Element von der aktuellen Iterationsrunde. Das zweite Argument ist der Index, des Elements.
Beispiel:
Bei der Implementierung von der forEach-Funktion wurde für die eigentliche Iteration verwendet.
Die forEach-Funktion für Stacks funktioniert gleich wie die JavaScript forEach Schlaufe.
Nützliche Helferfunktionen
Stack auf der Konsole ausgeben - logStackToConsole
Die Funktion logStackToConsole nimmt einen Stack entgegen und führt einen Seiteneffekt aus. Der Seiteneffekt loggt den Stack auf die JavaScript-Konsole.
Beispiel:
Stack erstellen mit Helferfunktion - startStack
Die pushToStack Funktion wird der startStack Funktion übergeben. Danach folgt der erste Wert, der hinzugefügt werden soll. Für weitere Werte kann nochmals die pushToStack Funktion und ein weiteres Element hinzugefügt werden. Dies kann solange gemacht werden, wie man möchte. Um das Erstellen abzuschliessen, wird am Schluss die übergeben.
Durch diese Helferfunktion lassen sich Stacks bequemer erstellen.
Eigenschaften der Funktionen vom Stack
Alle Funktionen sind rein (mit Ausnahme logStackToConsole).
In allen Funktionen gibt es keine Ausdrücke wie for, while oder doSchleifen.
Ein Einstieg-Projekt, um sich am beste mit den Kombinatoren und den Church-Zahlen auseinander zusetzen, ist Taschenrechner daraus zu bauen.
Link zum lambdafizierten Taschenrechner:
Kern des lambdafizierten Taschenrechner
Eine Verkettung der arithmetischen Zahlen und Operationen.
Als Helferfunktion gibt es einen sogenannter CalculatorHandler, mit dem solch eine Verkettung von Konstruktion ermöglichen.
Der calculatorHandler nimmt jeweils eine arithmetische Operation (Addition, Subtraktion, Multiplikation usw.), zwei Werte und zum Schluss eine Funktion entgegen.
Rechnen mit Zahlen
Um mit Zahlen zu rechnen reichen die Arithmetischen-Operatoren (+, -, * etc.) von JavaScript:
Mit dem CalculatorHandler und den Arithmetischen-Operatoren kombiniert, ist es möglich via Point-Freestyle aus den vorhing erstellten Operatoren neue Funktionen zur Berechnung zu erstellen:
Anwendung der Operator-Funktionen
Mit der (T = x => f => f(x) ) als den Taschenrechner-Starter und den neuen Operator-Funktionen, ist es mögliche eine unendliche Verkettungen von Zahlen und Operationen zu erstellen.
Um dieser Verkettung ein Ende zu setzen und das Resultat der Berechnung zu erhalten, benötigt es jeglich die als Letztes anzuwenden.
Um die Leserlichkeit des Code zu verbessern, wird für die Trush- und id-Funktion ein passender Variablename gewählt.
Implementation (Umbenennung):
Beispiel:
Rechnen mit Church Encodings-Zahlen
Das der Taschenrechner nicht nur mit JavaScript-Zahlen sondern auch mit rechnen kann, braucht es nur die mit dem CalculatorHandler zu kombinieren.
Mit diesen und den lässt sich der Taschenrechner gleich bequem bedienen.
Die Probleme mit den Church-Zahlen
Church-Zahlen encoden
Chuch-Zahlen sind Nested-Funktionen und es ist schwer mit blossem Auge zu entziffern welche Zahl sich hinter versteckt. Schon nur die Church-Zahl n7 gibt dir diese Funktion:
Die Hilfe zum die Zahl hinter einer Church-Zahl zu Entziffern ist die Funktion
Negative Zahle
Was der lambdafizierter Taschenrechner im vergleich zum JavaScript-Taschenrechner nicht kann sind mit negative Zahlen rechnen, da Church-Zahlen nur Werte der Natürlichen-Zahlen repräsentiert werden kann:
Division
Gleiches Problem wie mit den negativen Zahlen, können die Church-Zahlen keine Rationale-Zahlen repräsentiere. Deswegen gibt es keinen lambdafizierten Division-Operator.
Maximum call stack size exceeded
Bei Berechnung mit grösseren Church-Zahlen und längerer Verkettungen kann es zu einem Maximum call stack size exceeded - Error kommen:
Taschenrechner User-Interface
Um den lambdafizierten Taschenrechner, wie ein gewöhnter Taschenrechner auch visuell bedienen zu können, wurde eine statische HTML-Webseite, mit einem grafischen Taschenrechner und den von hier gezeigten Funktionen implementiert:
Link zum lambdafizierten Taschenrechner:
Eigenschaften des lambdafizierter Taschenrechner
Alle Funktionen sind rein
In allen Funktionen gibt es keine Ausdrücke wie for, while oder doSchleifen.
Immutable ListMap
Stack mit Schlüssel-Wert Paare
Beschreibung
Die Titel der Funktionen sind mit einem Link zur Implementation verknüpft.
ListMap ist eine weitere unveränderliche Datenstruktur, die auf dem Stack aufbaut. Im Kern ist die ListMap Datenstruktur gleich wie der , d.h. sie ist auch als implementiert. Der Unterschied zum Stack ist, dass in der ListMap die Einträge Schlüssel-Wert Paare sind (wie bei einer ). Alle Werte werden in dieser Datenstruktur mit einem dazugehörigen Schlüssel abgespeichert, somit kann der Anwender einen Wert abfragen mit Hilfe des dazugehörigen Schlüssels. Alle Funktionen vom Stack sind kompatibel mit der ListMap, zusätzlich gibt es noch weitere Funktionen, die nur mit einer ListMap verwendet werden können.
Die emptyListMap repräsentiert die leere ListMap. Anhand dieser Konstruktion ist zu sehen, dass sie sich nur in einem Punkt zum Stack unterscheidet. Der letzte Parameter, der ListMap ist nicht nur idwie beim Stack, sondern ein Paar mit id als Schlüssel und id als dazugehörigen Wert.
Verwendung
Alle Funktionen vom Stack können auch für die ListMap verwendet werden. Hier folgt die Auflistung der zusätzlichen Funktionalität, die nur mit der ListMap kompatibel ist.
In den folgenden Beispielen wird zur besseren Übersicht, die ListMap Datenstruktur wie folgt dargestellt: ``[ (key1, value1), (key2, value2), (key3, value3), ... ]
Bei der Verwendung von Funktionen, des Stacks mit der ListMap muss beachtet werden, dass die Elemente immer Schlüssel-Wert Paare sind und somit immer mit einem pair gearbeitet wird als Eintrag.
Mit der getElementByKey Funktion kann anhand eines Schlüssels auf den dazugehörigen Wert zugegriffen werden.
Mit der Funktion removeByKey kann ein Wert anhand des Schlüssel entfernt werden.
Mit der Funktion convertObjToListMap kann ein JavaScript Objekt zu einer ListMap konvertiert werden. JavaScript-Objekte sind Container für benannte Werte, die Properties oder Methoden genannt werden. In der Konvertierungsfunktion werden die Namen als String-Schlüssel verwendet.
Tuple-Konstruktor mit convertObjToListMap
Mit der Funktion convertObjToListMap kann eine Tuple-Artige Datenstruktur mit Zugriffsfunktionen erstellt werden.
Die Funktion personCtor bildet den Konstruktor für das Personen Tuple.
Die übergebenen Variablen im "Konstruktor" bilden später zusammen mit der Funktion getElementByKey die Zugriffsfunktionen für die Werte im Tuple.
Mit der Funktion convertListMapToArray kann eine ListMap in ein JavaScript-Array konvertiert werden. Dabei werden nur die Werte in der ListMap erfasst.
Higher Order Functions (HOF's) speziell für ListMap
Für die ListMap wurde eine spezifischere Variante für die HOF's map, filter und reduce implementiert. Dies um die Anwendung nochmals zu vereinfachen, weil sonst mit einem pair(key)(value) gearbeitet werden muss, obwohl der Anwender den Key dabei nicht benötigt bzw. verändern darf. Der Key wird in den HOF's für die ListMap weg abstrahiert, sodass sicher der Anwender auf das eigentliche Element konzentrieren kann.
Diese Funktion nimmt eine map-Funktion (wie bei JavaScript Array map) und eine ListMap entgegen. Zurück gibt die Funktion eine neue ListMap mit den "gemappten" Werten.
Beim Mapping des Wertes bleibt der dazugehörige Schlüssel unverändert.
Diese Funktion nimmt eine filter-Funktion (wie bei JavaScript Array filter) und eine ListMap __entgegen. Die Funktion gibt die gefilterte ListMap __zurück. Wenn keine Elemente dem Filter entsprechen wird die leere ListMap __() zurückgegeben.
Diese Funktion nimmt als ersten Parameter eine reduce-Funktion entgegen (wie bei JavaScript Array reduce), als zweites einen Startwert und als letzten Parameter eine ListMap. Die Funktion gibt den reduzierten Wert zurück.
Helferfunktion
Die Funktion logListMapToConsole nimmt eine ListMap entgegen und führt einen Seiteneffekt aus. Der Seiteneffekt gibt die ListMap mit dessen Schlüssel-Wert Paaren auf die JavaScript-Konsole aus.
Enstehung der ListMap
Beim ersten Entwurf des Observables wurde für die Verwaltung der Listener die Stack Datenstruktur verwendet. Bei der Implementierung für das abmelden/entfernen der Listener wurde klar das dies mit einem Stack nicht bzw. nicht elegant gelöst werden kann. Dabei kam die Idee einer HashMap auf um einen Listener per Schlüssel abzuspeichern und wieder zu entfernen. Das Problem einer HashMap ist das dies ein gute Hash-Funktion voraussetzt und die ist ein bekanntlich schweres Problem in der Informatik. Auch für den direkten Zugriff auf eine HashMap (in O(1) ) wussten wir nicht wie wir dies implementieren könnten. Da kam uns die Idee das wir eine Liste mit Schlüssel-Wert Paaren entwicklen können ohne diese zu Hashen und den Zugriff auf die Elemente mittels Iteration zum implementieren. Der Schlüssel sollte eindeutig und mit dem JavaScript === Operator auf Gleichheit verglichen werden können. Eine alternative Implementierung wäre eine Art Binär Baum, dies wäre aber sehr komplex und nicht nötig für unsere Einsatz Zwecke. Der Vorteil von unserer Implementierung ist, dass wir den bereits existierenden Stack verwenden und erweitern diesen.
Either
Entweder Erfolgsfall mit Resultat oder Fehlerfall mit Fehlermeldung
Beschreibung
Either Type
Der Either Type wird häufig in funktionalen Programmiersprachen wie zum Beispiel Haskell oder Scala eingesetzt für das Error Handling. Der Either Type ist ein polymorpher Typ, der zwei Zustände annehmen kann. Für diese zwei Zustände gibt es die Wert-Konstruktoren Left und Right. Somit ist ein Either entweder ein Left oder ein Right. Beide tragen einen Wert mit sich: Left wird verwendet um im Fehlerfall die Fehlermeldung zu kapseln; Right wird verwendet, um im Erfolgsfall den korrekten Wert zu kapseln. Durch den Either Type kann so in rein funktionalen Sprache elegant auf Fehler reagiert werden. Dabei gibt es keine Seiteneffekte, wie es ansonsten mit dem Statement in JavaScript geben würde.
Either Type Implementation:
Left und Right sind zwei Funktionen die jeweils einen Wert und zwei Funktionen entgegen nehmen. Beide Funktionen ignorieren eine der beiden übergebenen Funktionen.Left wendet die linke (erste übergebene) Funktion auf den Parameter x an und ignoriert die zweite. Right wendet die rechte (zweite übergebene) Funktion auf den Parameter x an und ignoriert die erste. Left und Right bilden die Basis für einen weiteren Typ, den .
Verwendung
Die Titel der Funktionen sind mit einem Link zur Implementation verknüpft.
Die folgenden Funktionen geben alle ein Either zurück und unterstützen so eine Fehlerbehandlung mit reinen Funktionen ohne Seiteneffekte. Somit können typische Fehler, die zum Beispiel auftreten wenn Werte null oder undefined sind, vermieden werden. Eine Funktion die ein Either zurück liefert hilft dem Anwender an den Fehlerfall zu denken und diesen zu behandeln.
Allgemeine Anwendung für Funktionen, die ein Either zurückgeben
Bei Funktionen, die ein Either zurückgeben können an den Funktionsaufruf zwei weitere Parameter übergeben werden. Der erste Parameter ist eine Funktion, die eine Fehlermeldung entgegen nimmt und dann eine Fehlerbehandlung durchführt. Der zweite Parameter ist eine Funktion für den Erfolgsfall, die das Resultat entgegen nimmt.
Allgemeines Schema:
Eine Either Funktion XYZ wird mit einem oder mehreren Parametern aufgerufen. Am Schluss vom Funktionsaufruf werden 2 Funktionen übergeben. Eine Funktion für den Fehlerfall (Left Case) und eine für den Erfolgsfall (Right Case).
Die eitherTruthy Funktion erwartet einen Wert und überprüft ob dieser 'truthy' ist. Im Erfolgsfall wird ein Right mit dem Element zurück gegeben und im Fehlerfall ein Left mit der entsprechenden Fehlermeldung.
.
Die eitherNotNullAndUndefined ****Funktion erwartet einen Wert und überprüft ob dieser nicht null oder undefined ist.
Die eitherElementOrCustomErrorMessage Funktion erwartet eine Fehlermeldung und ein Element. Die Funktion überprüft das Element auf null oder undefined und gibt entweder ein Right mit dem Wert oder ein Left mit der übergebenen Fehlermeldung zurück.
Die eitherDomElement Funktion nimmt eine Id für ein Dom-Element entgegen und gibt ein Either Type zurück. Im Erfolgsfall wird das HTML-Element zurückgegeben sonst eine Fehlermeldung, dass ein solches Element nicht existiert.
Die eitherNumber Funktion überprüft ob ein Wert vom Typ Integer ist.
Die eitherNaturalNumber Funktion überprüft ob der übergebene Wert eine natürliche JavaScript-Zahl ist.
Die eitherFunction Funktion überprüft ob ein Wert vom Typ function ist.
Die eitherTryCatch Funktion nimmt eine Funktion f entgegen, die schief gehen könnte. Diese Funktion wird in einem try-catch Block ausgeführt. Wenn ein Fehler auftritt während der Funktionsausführung wird dieser gefangen und es wird ein Left mit der Fehlermeldung zurückgegeben, ansonsten ein Right mit dem Resultat.
Diese Funktion hat den Zweck bestehende JavaScript Funktionen die noch auf die nicht funktionale Art Fehler mit throw werfen abzufangen und diese in die Welt der funktionalen Programmierung einzubetten. Somit fungiert diese Funktion als Brücke von der JavaScript Welt in die Welt der funktionalen Programmiersprachen.
Die Funktion eitherElementsOrErrorsByFunction nimmt als ersten Parameter eine Funktion und als zweiten Parameter einen Rest Parameter (). Die Funktion die übergeben wird sollte einen Wert entgegen nehmen und ein Either Type zurückgeben. Die Funktion eitherElementsOrErrorsByFunction wendet dann die übergebene Funktion auf jeden Wert an der durch den Rest Parameter übergeben wurde. Zurück kommt ein Either. Im Erfolgsfall (Right) bekommt der Anwender eine ListMap mit allen "Erfolgs" -Werten. Im Fehlerfall bekommt der Anwender ein Stack mit allen Fehlermeldungen die aufgetreten sind.
Sobald ein Funktionsaufruf schief geht, wird ein Left mit den Fehlermeldungen zurückgegeben.
In Haskell hätte diese Funktion folgenden Typ:
Beispiel
Observable
Wie lässt sich ein Wert nach dessen Änderung z.B. auf mehreren Textfeldern synchronisiert darstellen?
In vielen Programmiersprachen bietet sich hierfür das Entwurfsmuster 'Observer-Pattern' an, dass in verschiedenen Sprachen sehr unterschiedlich implementiert wurde. Das Prinzip gestaltet sich allerdings gleich: Der 'Erzähler' (Observable) hält Informationen bereit an die sich 'Zuhörer' (Listener) registrieren können. Sobald der 'Erzähler' neue Informationen bekommt, benachrichtigt er seine 'Zuhörer'.
Beispiel
Lambda Kalkül für praktisches JavaScript
Benjamin Brodwolf & Pascal Andermatt
Was ist Lambda Kalkül?
Lambda Kalkül ist ein formales System, in der mathematische Logik zur Berechnung und Untersuchung von Funktionen gilt. Es ist ein universelles Berechnungsmodel , mit dem jede Turing-Maschine simuliert werden kann. Es wurde von dem Mathematiker in den 1930er Jahren als Teil seiner Forschung zu den Grundlagen der Mathematik eingeführt.
Box
Verpacken -> Verarbeiten -> Auspacken
Beschreibung
Das Box Konstrukt erleichtert das Verarbeiten von beliebigen Werten. Die Werte werden in eine "Box" eingepackt und danach gemapped (weiterverarbeitet). Dabei entsteht eine Art linearer Datenfluss, der die Leserlichkeit des Codes erhöht. Ausserdem werden keine Variablen-Deklarationen für die Zwischenstände benötigt, weil das Resultat der Verarbeitung direkt in die nächste Funktion weitergeleitet wird.
Mit dem Box Konstrukt kann eine Art Pipeline aufgebaut werden, bei dem ein Wert durch diese Pipeline geschickt wird und bei jedem fmap wird der Wert weiter prozessiert. Um am Schluss an den verarbeiteten Wert zu kommen wird die letzte Prozessierung nicht mit
Church Encodings - Booleans und Zahlen
Beschreibung
Nebst den bekannten gibt es noch die Church-Booleans und Church-Zahlen. Mit den Church-Booleans werden boolesche Logik mit Funktionen ausgedrückt und die Church-Zahlen sind die bekannteste Form, mit welche die natürlichen Zahlen repräsentiert werden. Benannt sind sie nach , Mathematiker und einer der Begründer der theoretischen Informatik.
Die Funktion fmap wird verwendet um den Inhalt einer Box zu verarbeiten (mappen). Diese fmapFunktionsaufrufe können beliebig oft hintereinander angewendet werden (chainning von Funktionen). Durch das "chainning" wird eine Art Pipeline aufgebaut.
Die Funktion chain wird verwendet um ein flatMap durchzuführen. Wenn eine Map-Funktion eine Box erstellt, würde mit fmap eine Box in einer Box entstehen. Um diese extra Box zu entfernen bzw. das gemappte Ergebnis abzuflachen gibt es die Methode chain. Dadurch können auch geschachtelte Box Aufrufe stattfinden.
Die Funktion debug ist eine Helferfunktion, die für debug Zwecke da ist. Die Funktion hilft dem Anwender die Zwischenresultate zu untersuchen in einer Pipeline.
Wichtig bei der debug Funktion ist, das die Funktion fold am Schluss zwingend verwendet werden muss, um das letzte debug Statement auch auszuführen.
Um die die Box Konstruktion mit Maybe Werten zu verwenden, gibt es spezielle Funktion, die das verarbeiten von Maybe Types erleichtern. Somit wird das prozessieren mit dem Maybe Type vereinfacht und die Maybe Types können verknüpft werden.
Wenn irgendwo ein Nothing zurück geliefert wird, wird die Funktionskette abgebrochen und die restlichen Funktionen werden nicht ausgeführt.
Die Funktion liftA2Maybe entspricht der Funktion liftA2 für einen Maybe Type.
Falls ein Parameter (fx, fy oder beide) Nothing sind, ist das Gesamtergebnis der Funktion Nothing.
Church-Boolean
True & False
True kann durch die Funktion Kestrel ausgedrückt werden. False kann durch die Funktion Kite ausgedrückt werden.
Implementation
Not
Der boolesche not Operator kann mit der Funktion Cardinal ausgedrückt werden.
Implementation & Beispiele:
And
Die And-Funktion nimmt zwei Church-Booleans entgegen und liefert ein Church-Boolean zurück. Die Funktion funktioniert genau gleich wie der and-Operator in der mathematischen Logik.
Implementation:
Beispiele:
Or
Die Or-Funktion nimmt zwei Church-Booleans entgegen und liefert ein Church-Boolean zurück. Die Funktion funktioniert genau gleich wie der or-Operator in der mathematischen Logik.
Implementation:
Beispiele:
Boolean Equality
Diese Funktion nimmt zwei Church-Booleans entgegen und vergleicht diese miteinander. Nur wenn beide gleich sind, gibt die Funktion ein Church-True zurück, sonst ein Church-False.
Implementation:
Beispiele:
Show Boolean
Die Funktion showBoolean ist eine Helferfunktion um eine String Repräsentation, eines Church-Boolean zu erhalten. Die Funktion nimmt ein Church-Boolean entgegen und gibt die String Repräsentation davon zurück.
Implementation:
Beispiele:
Connvert to js Bool
Die Funktion convertToJsBool nimmt ein Church-Boolean entgegen und liefert die JavaScript Representation davon zurück.
Implementation:
Beispiele:
Church-Zahlen
Die Church-Zahlen sind keine "echte" Zahlen, sondern eine Funktionen wird n-Mal auf ein Argument angewendet. Um die Zahl Eins als eine Church-Zahl ( n1) zu repräsentieren muss es eine Funktion geben die einmal auf das Argument angewendet wird.
Implementation der Church-Zahl n1 (Eins):
Das gleiche mit den Zahlen von Zwei bis Neun, welche jeweils n-Mal auf ein Argument angewendet werden.
Die Zahl Null n0 wird in den Church-Zahlen als Funktion die keinmal auf das Argument angewendet wird. Somit wird die Funktion f ignoriert.
Implementation der Church-Zahl n0 (Null):
n0 nimmt zwei Parameter und gibt den zweiten zurück. Gleich wie die Funktion: Kite (n0 === KI).
jsNum
Um eine Church-Zahl in eine JavaScript-Zahl zu transferiere, evaluiert die Funktion jsNum die Church-Zahl n-Mal den Funktionsaufruf und zählt dabei die Aufrufe.
churchNum
Um aus einer JavaScript-Zahl eine Church-Zahl zu kreieren, wird mit der Funktion churchNum rekursiv n-Mal mit der Nachfolger-Funktion successor eine Church-Zahl gebaut.
Mathematische Operationen mit Church-Zahlen
Successor (Nachfolger)
Der Successor nimmt eine Church-Zahl und gibt dessen Nachfolger zurück.
Implementation:
Beispiel:
Phi (-Kombinator)
Der Phi-Kombinator nimmt eine Pair und gibt ein neues Pair zurück. Der erste Wert entspricht dem zweiten des alten Pairs. Der zweite Wert ist der Nachfolger des zweiten Wertes vom alten Pair.
Implementation:
Beispiel:
Predecessor (Vorgänger)
Der Predecessor nimmt eine Church-Zahl und gibt dessen Vorgänger zurück.
Der Phi-Kombinator ist dabei eine unterstützende Funktion um den Vorgänger der Church-Zahl zu definieren.
Implementation:
Beispiel:
Church-Addition (Addieren)
ChurchAddition nimmt zwei Church-Zahlen und gibt den addierten Wert als Church-Zahl zurück.
Der Successor ist dabei unterstützende Funktion. Die erste Church-Zahl ruft dabei n-Mal den successorauf und nimmt die zweite Church-Zahl als Summand.
Implementation:
Beispiel:
Church-Substraction (Substrahieren)
ChurchSubstraction nimmt zwei Church-Zahlen und gibt den subtrahierten Wert als Church-Zahl zurück.
Der Predecessor ist dabei eine unterstützende Funktion. Die zweite Church-Zahl ruft dabei n-Mal den pred als Subtrahend und nimmt die erste Church-Zahl als Minuend.
Implementation:
Beispiel:
Church-Multiplication (Multiplizieren)
ChurchMultiplication nimmt zwei Church-Zahlen und gibt den multiplizierten Wert als Church-Zahl zurück.
Die ChurchMultiplication entspricht exakt dem Bluebird !
Implementation:
Beispiel:
Church-Potency (Potenzieren)
ChurchPotency nimmt zwei Church-Zahlen und gibt den potenzierende Wert als Church-Zahl zurück.
isZero nimmt eine Church-Zahlen und gibt ein Church-Boolean zurück. Wenn die Church-Zahl n0 ist gibt die Funktion ein Church-Boolean True, ansonsten False zurück.
Beachte den Kestrel k in der Funktion, der nur zum Zug kommt, wenn die Church-Zahl nicht n0 ist und somit den ersten Wert bzw. False zurück gibt.
Implementation:
Beispiel:
leq (less-than-or-equal)
leq nimmt zwei Church-Zahlen und gibt ein Church-Boolean zurück. Wenn der erste Wert kleiner oder gleich dem zweiten Wert ist gibt die Funktion ein Church-Boolean True, ansonsten False zurück.
isZero und churchSubstraction sind dabei die benötigten Funktionen um Leq zu implementieren.
churchSubstraction substrahiert die erste Church-Zahl mit der zweiten Church-Zahl. Der substrahierte Wert ist n0 , wenn die zweite Church-Zahl grösser oder gleich der ersten Church-Zahl ist. Wenn dies stimmt, gibt isZero ein True zurück.
Implementation:
Beispiel:
eq (equality-to)
eq nimmt zwei Church-Zahlen und gibt ein Church-Boolean zurück. Wenn die beiden Church-Zahlen gleich sind, gibt die Funktion das Church-Boolean True, ansonsten False zurück.
And und Leq sind dabei die unterstützende Funktionen. Mit a_nd_ und leq werden die Church-Zahlen auf ihre Äquivalenz geprüft. Wenn dies Stimmt, erhält a_nd_ zwei True-Werte von leq zurück.
Implementation:
Beispiel:
gt (greater-than)
gt nimmt zwei Church-Zahlen und gibt ein Church-Boolean zurück. Wenn der erste Wert grösser als der zweite Wert ist, gibt die Funktion ein Church-Boolean True, ansonsten False zurück.
Blackbird, Not und Leq sind dabei die unterstützende Funktionen. Der Blackbird handelt die not und leq-Funktion (not(leq(n)(k) ). Dabei wird nichts andere als der Output bzw. die Church-Boolean der leq-Funktion von der not-Funktion negiert.
// Implementation n1
const n1 = f => a => f(a);
// Demonstration
n1(x => x + 1)(0) // 1
n1(x => x + '!')('λ') // 'λ!'
// Implementation n2...n9
const n2 = f => a => f(f(a));
const n3 = f => a => f(f(f(a)));
const n4 = f => a => f(f(f(f(a))));
const n5 = f => a => f(f(f(f(f(a)))));
const n6 = f => a => f(f(f(f(f(f(a))))));
const n7 = f => a => f(f(f(f(f(f(f(a)))))));
const n8 = f => a => f(f(f(f(f(f(f(f(a))))))));
const n9 = f => a => f(f(f(f(f(f(f(f(f(a)))))))));
// Demonstration
n2(x => x + 1)(0) // 2
n3(x => x + 1)(0) // 3
n4(x => x + 1)(0) // 4
n3(x => x + '!')('λ') // 'λ!!!'
// Implementation n0
const n0 = f => a => a;
// Demonstration
n0(x => x + 1)(0) // 0
n0(x => x + '!')('λ') // 'λ'
Als erstes wird ein Listener erstellt. Ein Listener ist ein Schlüssel-Wert Paar, dessen Wert eine Funktion ist, die bei einer Wertänderung auf dem Observable, aufgerufen wird. Somit kann mit dieser Funktion auf eine Wertänderung reagiert werden. Diese Funktion nimmt zwei Parameter entgegen, als erstes dennewValue und als zweites den oldValue.
In diesem Beispiel wird die Variable listenerVariable immer mit dem newValue-Wert überschrieben, wenn der Listener vom Observable über eine Wertänderung benachrichtigt wird. oldValue wird in diesem Beispiel nicht verwendet.
Observable erstellen und Listener registrieren
Nachdem ein 'Zuhörer' (Listener) erstellt wurde, braucht es noch den 'Erzähler' (Observable).
Dafür gibt es die Funktion Observable welche als ersten Parameter den initialen Wert entgegennimmt.
Mit der Funktion addListener wird der zuvor erstellte Listener registriert.
Nachdem einer Listener mit einem Observable verknüpft ist, erhält der Listener sofort den aktuellsten Stand (initialen Wert) vom Observable. In diesem Beispiel die Zahl '42'.
Aktueller Wert abfragen
Die Funktion getValue gibt den aktuellen Wert aus dem Observable zurück.
Wertänderung
Mit der Funktion setValue wird dem Observable ein neuer Wert mitgeteilt. Alle verbundene Listener werden benachrichtig und der neue Wert als newValue __mitgegeben. Der vorherige Wert als oldValue. Die Funktion setValue gibt ein neues Observable zurück.
Listener entfernen
Wenn ein Listener wieder von einem Observable entfernt werden soll, gibt es dafür die FunktionremoveListener. Diese Funktion gibt wieder ein Observable zurück.
Der zuvor entfernte Listener bekommt nun keine Wertänderungen mehr mit.
Zusammenfassung:
Observable Text-Input Beispiel
In diesem Beispiel-Projekt gibt es ein 'Observable', welches auf die Wertänderungen eines Text-Input-Feldes auf dem UI reagiert. Dabei werden alle 'Listener' mit dem neuen und alten Wert informiert.
In der Demo sind die Checkboxen neben den Labels zum entfernen und hinzufügen der Listener da.
Screenshot Text-Input Example
Demo
Es gibt vorgefertigte Listener-Funktionen, welche im Beispiel benutzt werden.
In diesem Beispiel-Projekt wird gezeigt wie ein Color-Picker mit dem Observable gebaut werden kann.
Es gibt ein Observable das die Farbe verwaltet, an welches sich Listener wie Background, Labels und Inputs registrieren können. Die Input-Felder (Text-Input und Slider) sind dabei nicht nur Listener sondern auch gleichzeitig dafür da, dem Observable neue Werte zu übermitteln. Die Elemente Text-Input und Slider-Input sind bidirektional mit dem Observerable verbunden. Um das zu demonstrieren wurden Buttons im UI hinzugefügt zum an- und abmelden der Listener.
Screenshot Color-Picker Example
Demo
Implementation
Der observierte Farbwert ist als Triple implementiert:triple(red, green, blue)
In diesem Beispiel-Projekt gibt es ein Observable das Witze verwaltet. Die Witze werden mit Klick auf den Button von einem REST-API abgefragt. Sobald ein neuer Witz veröffentlich wird, werden alle Listener informiert. Es existieren zwei Listener, der eine rendert die Witze auf dem UI und der andere löst ein Text-To-Speech-Skript aus.
Für dieses Beispiel wurde extra eine Funktionen erstellt um HTTP-Get anfragen zu tätigen. Sie bieten einen einfachen Weg, Daten von einer URL zu erhalten.
****(asynchron)
Mit der Funktion HttpGet wird asynchrone anfrage abgesetzt. Die Anfrage wird nach 30 Sekunden Time-out automatisch beendet, wenn vom Webserver bis dahin keine Antwort kommt. Die Funktion HttpGet erwartet als ersten Parameter eine URL und als zweiten Parameter eine Callback-Funktion __mit der Antwort vom Webserver.
Analog zu HttpGet gibt es die Synchrone-Variante: HttpGetSync.
Denn Callback braucht es nicht, da der Response direkt als Rückgabewert zurück gegeben werden kann.
Der observableBody wird bei diesen Funktion immer zurückgegeben. Es ermöglicht eine Verkettung der Funktionen mit einem Observable.
Nachdem anwenden einer Observable-Funktion ist es wichtig den Rückgabewert in einer Variablen zu speichern, weil dieser das aktuelle Observable enthält. Anschliessend kann darauf immer weitere Observable-Funktion angewandt werden.
Die Variable, die das Observable enthält, kann mit dem const Schlüsselwort deklariert werden und ist somit auch immutable. Dadurch kann diese Variable nicht überschrieben werden und es können dann keine Listener hinzugefügt werden oder entfernt werden.
Mit der Funktion addListener wird dem Observable ein neuer Listener hinzugefügt.
Der aktuelle Wert des Observables wird beim Registrieren sofort dem neuen Listener mitgeteilt.
Das Observable sollte nicht mit mehr als 5'000 Listener verbunden werden, weil ansonsten ein "Uncaught RangeError: Maximum call stack size exceeded" __auftretten könnte.
Mit bis zu 100 Listener und vielen Wertänderungen (zb. 100'000) auf einmal hat das Observable kein Problem.
Mit der Funktion newListenerWithCustomKey wir ein neuer Listener erstellt. Die Funktion nimmt als erstes den Schlüssel, als zweites die Funktion, die auf die Wertänderung reagiert, entgegen.
Der Schlüssel muss mit dem JavaScript "===" - Operator verglichen werden können.
Der Schlüssel von einem Listener muss eindeutig sein in einem Observable.
Mit der Funktion newListener wir ein neuer Listener erstell. Der Key muss im Vergleich zu newListenerWithCustomKey nicht angeben werden, weil dieser automatisch generiert wird.
Der generateRandomKey erzeugt einen String der Länge sechs mit zufälligen Buchstaben (Gross-/Kleinschreibung) & Zahlen. Siehe implementation: generateRandomKey
Mit der Funktion logListenersToConsole werden die Listener eines Observables auf der JavaScript Konsole ausgegeben.
Lambda-Kalkül hat im Grunde nichts in sich. Es hat nur drei Dinge: Variablenbindung, einen Weg, Funktionen zu bauen und einen Weg, Funktionen anzuwenden. Es hat keine anderen Kontrollstrukturen, keine anderen Datentypen, gar nichts.
Was ist JavaScript?
JavaScript ist die Programmiersprache die hauptsächlich im Web verwendet wird und durch den Browser ausgeführt wird. JavaScript integriert dabei viele funktionale Aspekte, stellt aber auch einiges an Funktionalität aus der objektorientierten Programmierung zur Verfügung. Es besteht also die Möglichkeit, in vielen verschiedenen Paradigmen zu programmieren.
Lambda Kalkül & JavaScript
JavaScript hat den Ruf, eine unsichere Programmiersprache zu sein. Man kann aber auch in JavaScript sichere und belastbare Konstruktionen mit Industriehärte bauen. Ein Weg dazu ist die Anwendung von Erkenntnissen aus den Grundlagen der Informatik, dem untypisierten Lambda-Kalkül. Das Konzept ist, Lambda Kalkül mit der Programmiersprache JavaScript zu verbinden. Das heisst, in nur rein funktionalen Paradigma Program-Codes zu schreiben (purely functional). JavaScript bietet dazu Sprachelemente wie Closures und Funktionen. Sie machen es möglich, dass in JavaScript funktional programmiert werden kann. Es gewährleistet die Konzepte der Seiteneffektfreiheit, Zustandslosigkeit, Variablenbindung statt Zuweisung, Funktionskomposition und Funktionen höherer Ordnung (high order functions) zu schreiben.
Forschungsarbeit
Ziel dieser Forschungsarbeit ist es, neue Konstruktionen aus dem untypisierten Lambda Kalkül, mit der Programmiersprache JavaScript zu entwerfen. Diese Konstruktionen haben das Ziel JavaScript Applikationen robuster, sicherer und wartbarer zu machen. Bei diesen Konstruktionen wird komplett auf die Werte der reinen funktionalen Programmierung gesetzt:
Reinheit (pure functions): Funktionen ohne Seiteneffekte (wie mathematische Funktionen)
-Konstrukt um Werte in einer Pipeline zu verarbeiten
Eignes mit einer Zeitmessung für die Methodenausführung ()
(Dokumentation und Typ-Unterstützung für Anwender)
Code Convention (Konzepte, Formatierung und Anwendungsbeispiele)
Classic JS vs Lambda JS
Property Value aus Objekt extrahieren (null-safe)
Gegeben: Ein verschachteltes User-Objekt mit Street-Property.
Ziel: Strassenname extrahieren
Eine mögliche Implementierung im klassischen JavaScript (ohne Optional Chaining) wäre:
Eine gleichwertige Implementierung mit Verwendung des Werkzeugkastens (Lambda JS):
Vergleich
Eigenschaften
Classic JS
Lambda JS
Variablen für Zwischenstände
wird benötigt
keine
Verschachtelung von If Statements
wird benötigt
Pure Lambda JS vs Lambda JS
Bereits eine kleine Funktion wie push , die ein Stack mit einem neuen Wert erstellt , besteht im Kern aus mehreren Funktionen.
Die Implementation der Funktion push sieht wie folgt aus:
Sie besteht aus folgenden Funktionen: stack, succ, stackIndex .Diese Funktionen können in der Funktion push durch ihre Implementation ersetzt werden:
const stack = triple
const triple = x => y => z => f => f(x)(y)(z);
const succ = n => f => x => (f)(n(f)(x));
const stackIndex = firstOfTriple;
const firstOfTriple = x => y => z => x;
Die Funktion push würde im reinen Lambda Kalkül (pure Lambda JS) wie folgt aussehen:
Nach der Eta-Reduktion:
Funktionen in JS im reinen Lambda Kalkül zu schreiben kann schnell unübersichtlich werden weil die Definitionen fehlen. Diese verschachtelten anonymen Funktion werden schnell zu komplex. Darum ist es besser dieses Funktionskonstrukt in mehreren Funktionen aufzuteilen und diesen einen sinnvollen Namen zu geben.
Beispiel an der grösseren Funktion reduce
Implementation von reduce in Lambda JS:
Implementation in pure Lambda JS (Funktionsdefinitionen ersetzt und ETA reduziert)
Die Performance leidet wenn eine grössere, komplexere Funktion in einer reinen Lambda Kalkül Schreibweise definiert ist. Da es keine Definitionen gibt die wiederverwendet werden können muss viel mehr evaluiert werden in JavaScript. Darum ist es für die Performance und für die Leserlichkeit besser die Funktionen nicht in der reinen Lambda Kalkül Schreibweise zu definieren.
Fazit / Erkenntnisse
Konzepte aus der funktionalen Programmierung
Die Konstruktionen beinhalten Ideen und Konzepte aus der funktionalen Programmierung. Mit dem Einsatz dieser Konstruktionen, können JavaScript Applikationen funktionaler implementiert werden. Die Konstruktionen sind so implementiert, dass sie leicht integrierbar und anwendbar sind. Ein JavaScript Programm muss dabei nicht komplett nur aus diesen Konstruktionen bestehen, sondern der Anwender kann hier und dort bestimme Konstrukte in sein Programm einfliessen lassen.
Nutzen & Vorteile
In mehreren kleinen Beispielen hat sich gezeigt, dass die Konstruktionen den Code leserlicher, wartbarer und sicherer machen. Ausserdem entstehen weniger typische Fehler, die bei der Programmierung mit JavaScript auftreten.
Da die Konstruktionen aus puren Funktionen bestehen, ist der Programmablauf klarer und Fehler können besser eingegrenzt werden. Bei veränderlichen Daten und Funktionen mit Seiteneffekten, leidet die Übersicht, man verliert die Kontrolle über den Programmablauf und den Abhängigkeiten innerhalb des Programmes. Schon durch einen kleinen Einsatz von diesen Konstruktionen wird diesem Problem entgegenwirkt und die Übersicht wird verbessert.
JS Doc Unterstützung - Fehlendes Typ System bei JavaScript
Ein wesentliches Ziel von Typisierung in Programmiersprachen ist die Vermeidung von Laufzeitfehlern. JavaScript ist eine schwach typisierte oder dynamische Programmiersprache. Datentypen werden bei einer Variable nicht explizit deklariert und jede Variable kann mit Werten jedes Typen initialisiert werden. Es gibt auch kein Compiler der die Typen überprüfen würde. Die JS Doc unterstützt den Anwender für die korrekte Verwendung der Funktionen. Mit der JS Doc bekommt der Anwender Hinweise auf die korrekten Typ-Parameter.
Für die unveränderlichen Datenstrukturen Stack und ListMap könnten zusätzliche Funktionen entwickelt werden, sodass ein noch grösseres Anwendungsgebiet entsteht.
Der Index bei einem Stack beginnt bei 1. Der Index 0 ist reserviert für den . Am Index 0 steht immer das Element id.
In den folgenden Beispielen wird zur besseren Übersicht, die Stack Datenstruktur wie folgt dargestellt:[ element1, element2, element3, ... ]
Erweiterungen
Die Titel der Funktionen sind mit einem Link zur Implementation verknüpft
Die Funktion concat nimmt zwei Stacks entgegen und konkateniert diese.
Die Funktion flatten nimmt einen Stack entgegen, dessen Einträge Stacks sind. Die Funktion verknüpft diese alle zusammen zu einem Stack. Das Tiefenlevel, bis zu welcher die Struktur abgeflacht wird ist 1.
Die zipWithFunktion nimmt eine Verknüpfungsfunktion und zwei Stacks entgegen. Anhand der Verknüpfungsfunktion werden die Elemente der beiden übergebenen Stacks paarweise miteinander verknüpft zu einem neuen Stack.
Wenn einer der beiden übergebenen Stacks kürzer ist wird nur bis zum letzten Element des kürzeren Stacks verknüpft.
Die zip Funktion nimmt zwei Stacks entgegen und verknüpft die beiden Stacks mit der Funktion pair.
Wenn einer der beiden übergebenen Stacks kürzer ist wird nur bis zum letzten Element des kürzeren Stacks verknüpft.
Die Funktion stackEquals nimmt zwei Stacks entgegen und vergleicht alle Elemente mit dem JavaScript === Operator auf Gleichheit. Wenn alle Vergleiche true ergeben, gibt die Funktion ein Church-Boolean True ansonsten ein Church-Boolean False zurück.
Die Funktion getElementByIndex nimmt einen Stack und eine oder JS-Zahl, die den Index des Elements repräsentiert, entgegen. Falls an diesem Index ein Element existiert, wird dieses zurückgegeben ansonsten wird auf der Console einer Error geloggt und der Rückgabewert ist undefined.
Anwendungs Beispiel:
Der Anwender muss nicht mehr entscheiden, welche Funktionen er braucht: getElementByChurchNumberIndex oder getElementByJsNumIndex.
Die Funktion getElementByIndexwurde erweitert, dass der Index auf den "Typ" kontrolliert wird mittels eitherFunction und eitherNaturalNumber. So kann der Anwender eine Church- oder JavaScript-Zahl angeben, die Funktion findet selber heraus, welche Methode er braucht. Bei ungültigen Parametern werden die passende Fehler-Meldungen geloggt.
Die spezifischeren Funktionen um ein Element zu erhalten sind weiterhin vorhanden:
````
Die Funktion removeByIndex nimmt einen Stack und eine oder JS-Zahl als Index entgegen. Die Funktion löscht das Element am übergebenen Index und gibt den neuen Stack zurück.
Bei einem nicht existierenden Index erhält man denselben Stack unverändert zurück.
Die Funktion getIndexOfElement nimmt einen Stack und ein Element entgegen und gibt den Index als JavaScript-Zahl von diesem Element zurück. Wenn das Element nicht existiert wird undefined zurückgegeben.
Die Funktion maybeIndexOfElement ist analog zur Funktion . Nur der Rückgabetyp ist ein .
Die Funktion containsElement nimmt einen Stack und ein Element entgegen. Gibt True (ChurchBoolean) zurück, wenn das Element im Stack vorhanden ist. Gibt False (ChurchBoolean) zurück, wenn das Element nicht im Stack vorhanden ist.
Die Funktion convertElementsToStack nimmt einen Rest Parameter () entgegen. Die übergebenen Elemente werden in ein Stack umgewandelt.
Test-Framework
Beschreibung
Um die Korrektheit unserer Konstruktionen zu verifizieren haben, wir ein eigenes Test Framework ohne externe Abhängikeiten geschrieben. Von der Architektur (Aufbau/Struktur & Konzept) haben wir uns vom Test Framework von Prof. Dierk König inspieren lassen. Ausserdem wurde der Immutable-Stack im Test-Framework eingebaut und verwendet. Zudem sind mehrere nützliche Funktionen vom Stack verwendet worden, wie z.b die Filter- & forEach-Funktion.
Ansicht aller Testergebnissen:
Aufbau
Zuerst ein paar wichtige Definition/Erklärungen zum Test-Framework.
Die kleinste Einheit unseres Test-Frameworks ist ein einzelner Aufruf der equals-Methode auf dem Assert Objekt.
Die equals-Methode nimmt zwei Parameter entgegen. Das erste Argument ist der tatsächliche Wert (z.b der Wert vom Aufruf, einer zu testenden Funktion). Der zweite Parameter ist der erwartete Wert. Nun vergleicht die equals-Funktion die beiden übergebenen Parameter auf Gleicheit. Wenn der erwartete Wert mit dem IST-Zustand übereinstimmt, so ist der Test erfolgreich.
Pro Konstruktion/Funktion gibt es mehrere solche Test's mit der equals-Methode. Diese werden dann zu einem Testfall für die Funktion zusammengefasst.
Beispiel eines Testfalles:
Bei diesem Testfall wird die getestet. Der Testfall besteht hier aus 5 Tests.
Mehrer zusammengehörende Testfälle werden einer Testsuite hinzugefügt. Dies dient dazu um mehrere Testfälle zu gruppieren. Zum Beispiel werden alle Testfälle vom Stack einer Testsuite hinzugefügt.
In der Testsuite befinden Testfälle von allen Funktionen des Gruppierten Thema's(Im Bild oben alle Testfälle von allen Stack-Konstruktionen). Dabei sieht man bei einem einzelnen Testfall einer Funktion, wie viele Test's erfolgreich waren.
Wenn in einem Testfall ein Test fehlschlägt, wird dies farblich angezeigt. Dabei wird die Nummer des Test's und was genau schiefgegangen ist angezeigt.
Die Testsuiten werden am Schluss auf einer Html Seite angezeigt, sodass man eine Übersicht von allen Test's hat. Auf dieser Übersicht werden alle Test's von allen Testfällen zusammengezählt und als Total angezeigt.
Benchmark und unsere Erkenntnisse
BenchmarkTest
Um Funktionen auf ihre Ausführungsgeschwindigkeit zu prüfen wurde die Funktion BenchmarkTest dem TestFramework hinzugefügt. Mit der Zeitstempel Methode performance.now() von JavaScript **** kann die Ausführungsdauer der Funktion methodUnderTest berechnet werden. Die Werte, die von Performance.now() zurückgegeben werden sind immer in einem konstanten Tempo, unabhängig von der Systemuhr.
Unsere Erkenntnisse mit der Funktion BenchmarkTest
forEach-Methode des
Bei der Anwendung des Observables ist uns aufgefallen, dass die Benachrichtigung der Listener viel zu lange ging. Wir haben uns danach gefragt, welcher Teil so viel Zeit in Anspruch nimmt für die Ausführung. Danach untersuchten wir die forEach Methode, die bei der Benachrichtigung der Listener eine zentrale Rolle spielt. Wir haben die Methode analysiert und festgestellt dass in jeder Iterationsrunde eine weitere Iteration gestartet wird (ähnlich wie eine for-Schleife in einer for-Schleife), die jedoch nicht benötigt wird.
Anstelle den Index in jeder Iterationsrunde aus dem Stack via jsnum zu berechnen, wurde der Index in jeder Iteration um eins erhöht und der nächsten Iterationsrunde mitgegeben. Das Problem bei der Funktion jsnum ist das diese mit einer rekursiven Implementation eine Church Zahl in eine JavaScript Zahl umwandelt.
Nach dem Refactoring war die forEach Methode massiv viel schneller (mehr als doppelt so schnell) . Wir haben einen kleinen Benchmark Test erstellt, der misst wie lange eine Ausführung dauert und konnten dadurch einen erheblichen Unterschied feststellen.
Implementation: forEachvor dem Refactoring
Implementation: forEach nach dem Refactoring
Einfache Kombinatoren
Beschreibung
Folgende Konstruktionen dienen als Grundbausteine für unsere späteren Implementationen. Diese Grundbausteine kommen zum Teil aus dem Lambda Kalkül.
Code Convention
Naming
Im allgemeinen wird auf sprechende Namen gesetzt, sodass die Funktionen selbsterklärend sind.
Bei Abfragefunktionen, mit welcher der Anwender einen Wert anfordert, gibt der jeweilige Präfix des Funktionsnamens Aufschluss, von welchem Typ der Rückgabewert sein wird.
let listenerVariable; // undefined
const listenerExample = newListener( nVal => oVal => listenerVariable = nVal );
// create observable and add listener
let obsExample = Observable(42)
(addListener)(listenerExample);
listenerVariable // 42 <- get the value from initialValue
// set new value and update listeners
obsExample = obsExample(setValue)(11);
// receive the update
listenerVariable // 11
// remove listener
obsExample = obsExample(removeListener)(lisExample);
// set new value and update listeners
obsExample = obsExample(setValue)(67);
// receive no updates anymore
listenerVariable // 11
// Get the elements from the Dom
const [inputText, newValue, oldValue, sizes] = getDomElements("inputText", "newValue", "oldValue", "sizes");
// Create Listener
const listenerNewValue = newListener( listenerNewValueToDomElementTextContent (newValue) );
const listenerOldValue = newListener( listenerOldValueToDomElementTextContent (oldValue) );
const listenerNewValueSize = newListener( listenerNewValueLengthToElementTextContent (sizes) );
const listenerConsoleLog = newListener( listenerLogToConsole );
// Create Observable-Object, define the Initial-Value and append the Listeners
let textInputObservables = Observable("")
(addListener)( listenerNewValue )
(addListener)( listenerOldValue )
(addListener)( listenerNewValueSize )
(addListener)( listenerConsoleLog );
// Connect the Observables with the Input-Text-Field.
// Every change in the Input-Field execute the 'setValue'-Function with the new value from Input-Field.
inputText.oninput = _ =>
textInputObservables = textInputObservables(setValue)(inputText.value);
// reduce in reinem Lambda Kalkül
const reduce = reduceFn => initialValue => s => s(x => _ => _ => x)(t => t(x => _ => _ => x)(x => _ => _ => x)(_ => (_ => y => y))(x => _ => x)(t)((t => f => f(t(x => _ => _ => x)(_ => y => _ => y))(t(_ => y => _ => y))(t(_ => y => _ => y)(t(_ => _ => z => z))((t(x => _ => _ => x))(_ => _ => z => z))))(t)))(f => f(s(x => _ => _ => x)(t => t(x => _ => _ => x)(x => _ => _ => x)(_ => (_ => y => y))(x => _ => x)(t)((t => f => f(t(x => _ => _ => x)(_ => y => _ => y))(t(_ => y => _ => y))(t(_ => y => _ => y)(t(_ => _ => z => z))((t(x => _ => _ => x))(_ => _ => z => z))))(t)))(f => f(s)(acc => curr => f => f( f => x => f(s(x => _ => _ => x)(f)(x)))(acc)(curr))(f => f(_ => a => a)(x => x)(x => x)))(_ => _ => z => z))(reduceFn)(initialValue))(_ => _ => z => z);
const calculatorHandler = op => n => k => f => f(op(n)(k));
const plus = n => k => n + k;
const multiplication = n => k => n * k;
const subtraction = n => k => n - k;
const exponentiation = n => k => n ** k;
const division = n => k => n / k;
// example
plus(1)(2) // 3
multiplication(2)(3) // 6
subtraction(5)(2) // 3
const add = calculatorHandler(plus);
const multi = calculatorHandler(multiplication);
const sub = calculatorHandler(subtraction);
const pow = calculatorHandler(exponentiation);
const div = calculatorHandler(division);
Die Identitätsfunktion nimmt einen Wert entgegen und gibt diesen wieder zurück.
Implementation:
Beispiele:
Kestrel - Die Konstante Funktion
Die Konstante Funktion nimmt zwei Paramter entgegen und gibt den ersten wieder zurück.
Implementation:
Beispiele:
Kite
Der Kite ist eine Funktion, die zwei Parameter entgegennimmt und den zweiten Parameter zurückgibt.
Implementation:
Beispiele:
Mockingbird
Der Mockingbird nimmt einen Funktion entgegen und wendet die Funktion auf sich selber an. (English: self-application)
Implementation:
Beispiele:
Cardinal (Flip) - Vertauschungsfunktion
Die Vertauschungsfunktion nimmt eine Funktion und zwei Argumente entgegen und wendet die Argumente in vertauschter Reihenfolge auf die übergebene Funktion an.
Implementation:
Beispiel:
Bluebird - Funktionskomposition
Der Bluebird nimmt zwei Funktionen und ein Argument entgegen. Zuerst wendet der Bluebird das Argument auf die zweite Funktion an und das Resultat wird auf die erste Funktion angewendet. Der Bluebird funktioniert gleich wie die Funktionskomposition in der Mathematik .
Implementation:
Beispiele:
Thrush
Der Thrush nimmt ein Argument und eine Funktion entgegen. Dieses Argument wendet der Thrush auf die übergebene Funktion an.
Implementation:
Beispiele:
Vireo
Der Vireo ist eine Funktion, die zwei Argumente und eine Funktion entgegen nimmt. Die Funktion wendet die zwei übergebenen Argumente auf die übergebene Funktion an. Der Vireo ist gleichzeitig eine unveränderliche Datenstruktur, siehe Pair.
Implementation:
Pair
Das Pair ist eine unveränderliche Datenstruktur bestehend aus zwei Elementen. Mit sogenannten "getter"-Funktionen kann auf diese Werte zugegriffen werden. Für beide Werte des Pairs gibt es eine "getter"-Funktion. Für den ersten Wert des Pairs gibt es die Funktion fst (first), für den zweiten Wert gibt es die Funktion snd (second). Für das Pair und die dazugehörigen getter muss nichts neues implementiert werden, sondern es können dafür bereits bestehende Funktionen (Grundbausteine) verwendet werden. Das Pair ist gerade der Vireo. Die fst-Funktion ist gerade die Konstante Funktion. Die snd-Funktion ist gerade der Kite.
Implementation :
Beispiele:
MapPair
Die Funktion mapPair nimmt eine map-Funktion und ein Pair entgegen. Die Funktion gibt ein neues Pair mit den gemappten Werten zurück.
Implementation:
Beispiele:
ShowPair
Die Funktion nimmt ein Pair entgegen und gibt die String Repräsentation des Pairs zurück.
Implementation:
Beispiele:
Triple
Das Triple ist eine unveränderliche Datenstruktur bestehend aus drei Elementen. Mit sogenannten "getter"-Funktionen kann auf diese Werte zugegriffen werden. Für alle Werte des Triple gibt es eine "getter"-Funktion. Ein Triple ist fast wie ein Pair, nur hat es einen Wert mehr.
Implementation:
Beispiele:
Blackbird
Der Blackbird ist eine Funktion, die zwei Funktionen und zwei Argumente entgegennimmt. Die zweite Funktion wird auf die zwei übergebenen Argumente angewendet, das Ergebnis wird auf auf die erste Funktion angewendet. Der Blackbird hat ähnlichkeiten mit dem Bluebird.
// getter functions of triple
const firstOfTriple = x => y => z => x;
const secondOfTriple = x => y => z => y;
const thirdOfTriple = x => y => z => z;
// triple with 3 numbers
const tripleOfNumbers = triple(1)(2)(3);
tripleOfNumbers( firstOfTriple ); // 1
tripleOfNumbers( secondOfTriple ); // 2
tripleOfNumbers( thirdOfTriple ); // 3
const Blackbird = f => g => x => y => f(g(x)(y));
const add = x => y => x + y;
const multiplyWithTwo = x => x * 2;
Blackbird(multiplyWithTwo)(add)(2)(3); // 10
Blackbird(multiplyWithTwo)(add)(10)(20); // 60
get-Präfix
Funktionen die mit einem get beginnen, geben wenn möglich den gewünschten Wert ansonsten ein undefined zurück.
Alle Konstruktionen sind mit dem Keyword const definiert. Somit können diese Variablen nicht überschrieben/verändert werden.
Konzepte
Konstante Konstrukte
Bei Konstruktionen soll darauf geachtet werden, dass diese aus reinen Funktionen bestehen.
Die Brücke zwischen λ und JS
Objekte und Arrays werden nicht verwendet. Ausnahme gibt es bei Funktionen, die als Brücke zwischen den Welten Lambda Kalkül und JavaScript dienen.
Das sind die Convert-Funktionen:
Bei den erstelleten Funktionen kommt es häufig vor, dass die Impementation aus einer einzigen Codezeile besteht. Die Leserlichkeit kann zum Teil darunter leiden weil die Zeile zu lang ist. Richtiges formatieren der Funktionen mit Zeilenumbrüchen, Einrückungen und Leerzeichen sind daher empfehlenswert und JavaScript ist dabei ziemlich unempfindlich. So darf der Code schön arrangiert werden, denn gut ausgerichteter Code fördert die Leserlichkeit immens.
Workflow-Beispiel
Gegeben ist ein nicht formatierter Code: Ein Observable mit ein paar Listener, die hinzugefügt werden. Es ist schwer auf einem Blick zu sehen wieviel und welche Listener es sind, da sie in einer Reihe aufgelistet sind.
Schritt 1: Zeilenumbrüche
Wir sind gewohnt das Code Zeilen linksbündig ausgerichtet sind. Diese Struktur wird hier neu definiert. Wenn bei einer Funktion es zu mehrere Funktionsverknüpfungen mit Wertübermittlung kommt, ist es empfehlenswert diese Aufrufe untereinander zu schreiben.
Schritt 2: Einrücken
Einrücken der Funktion unterhalb der Haupt-Funktion in einer Linie plus einem Leerzeichen, macht es erkennbarer, dass sie zueinander gehören und darauf aufbauen.
Schritt 3: Leerzeichen (Padding)
Es ist schöner und lesbarer, wenn es zwischen den Werten in den Klammern mindestens ein Leerzeichen gibt. Somit bekommen alle Werte dieselbe Präsenz. Es ist dabei empfehlenswert die Klammern auf einer Linie untereinander zu bringen.
Schritt 4: Semikolon
JavaScript versucht zwar selber eine Semikolon am Ende einer Anweisung einzufügen, wenn der Programmierer keine gesetzt hat. Hier ist aber nicht klar, ob die Anweisung für JavaScript fertig ist, denn es wäre mittels Funktionskomposition möglich immer weitere Funktionen anzufügen. Es ist darum besser immer ein Semikolon zu setzen, nicht nur um JavaScript zu signalisieren, dass es hier zu ende ist, sondern auch für die Leserlichkeit.
Vergleichsbeispiele
Listeners-Deklaration
ForEach
Box
JS Doc
Das Dokumentieren der Funktionen mit der JSDoc bringt einige Vorteile. In den ersten Zeilen steht ein Text mit zwei bis drei Sätze, der fachlich erklärt was die Funktion tut. Anschliessend wird mit den JSDoc-Tags die Dokumentation mit Hinweisen erweitert:
@haskell Typ deklaration in Haskell Notation
@sideffect wenn die Funktion einen Side-Effekt auslöst wie zum Beispiel ein Log auf die Konsole
@function markiert eine Funktion explizit als eine Funktion. Optional: Kann man der Funktion einen zweiten Name geben (Alias)
@param für das erste Argument (hilfreich für die Pop-Up Informationen)
@return wenn die Funktion mehrere Argumente/Funktionen erwartet (hilfreich für die Pop-Up Informationen)
@example Beispiele wie die Funktion angewendet wird
In der IDEA (hier Intellij) wird die Dokumentation dementsprechend angezeigt:.
Dokumentation in der IDEA
Ein sehr praktischer Vorteil, nebst der Dokumentation, sind die Pop-Up Informationen welche dem Anwender beim benutzen der Funktionen angezeigt werden. Der Anwender wird informiert, welcher Parameter als nächstes erwartet wird.
Ein fehlgeschlagener Test im Testfall, der Identitätsfunktion
Ausschnitt aus der Gesamtübersicht von allen Test's
Maybe
Villeicht ist ein Wert vorhanden
Beschreibung
Maybe Type
Der Maybe Type baut auf dem Either Type auf und kommt aus der Welt der funktionalen Programmiersprachen. Der Maybe Type ist ein polymorpher Typ, der auch (wie der Either Type) zwei Zustände annehmen kann. Die Zustände sind: Es existiert ein Wert, dass wird mit Just(value) ausgedrückt oder es existiert kein Wert, dass wird mit Nothing ausgedrückt.
Beispiel Szenario:
Wenn eine Funktion, in einer übergebenen Datenstruktur ein Element anhand einer bestimmten Eigenschaft sucht und ein solches Element existiert nicht, dann kann diese Funktion ein Nothing zurückgeben. Dies hat mehrere Vorteile: Der Anwender weiss zu Beginn, dass diese Funktion nur "vielleicht" einen Wert zurück liefert und ist somit auch gezwungen, den Fall zu berücksichtigen wenn kein Wert vorhanden ist.
Durch den Maybe Type kann eleganter auf fehlende, abwesende Werte reagiert werden und dies nur mit Hilfe von reinen Funktionen ohne Seiteneffekte.
Maybe Implementation:
Anhand der Implementation von Just und Nothing ist erkennbar, dass der Maybe Type auf dem Either Type basiert. Just ist der Fall bei dem ein Wert vorhanden ist. Dem Just "Konstruktor" kann ein Wert übergeben werden. Nothing ist der Fall bei dem kein Wert vorhanden ist.
Verwendung
Allgemeine Anwendung für Funktionen, die ein maybe zurückgeben
Bei Funktionen, die ein Maybe zurückgeben können an den Funktionsaufruf zwei weitere Parameter übergeben werden. Der erste Parameter ist eine Funktion, die keinen Parameter entgegen nimmt und den Nothing Fall behandelt. Der zweite Parameter ist eine Funktion für den Just Fall, die das Resultat entgegen nimmt.
Allgemeines Schema:
Eine Maybe Funktion XYZ wird mit einem oder mehreren Parametern aufgerufen. Am Schluss vom Funktionsaufruf werden zwei Funktionen übergeben. Eine Funktion für den Nothing Fall und eine für den Just Fall.
Die getOrDefault Funktion erwartet ein Maybe und einen Default-Wert. Der Default-Wert wird zurückgegeben falls maybe von Typ Nothing ist.
Die Funktion maybeDivision führt 'vielleicht' eine Division mit zwei übergeben Parametern durch. Falls die übergeben Zahlen vom Typ Integer sind und der Divisor nicht 0 ist, wird die Division durchgeführt und es wird Just mit dem Resultat zurückgegeben.
Demo maybeDivision Example
Diese Funktion nimmt einen Wert entgegen und überprüft ob dieser 'truthy' ist. Falls nicht wird ein Nothing zurückgegeben.
.
Die maybeNotNullAndUndefined ****Funktion erwartet einen Wert und überprüft ob dieser nicht null oder undefined ist.
Diese Funktion nimmt eine Id für ein Dom-Element entgegen. Wenn ein Element mit dieser Id im DOM existiert wird ein Just mit diesem HTML-Element zurückgegeben ansonsten Nothing.
Diese Funktion nimmt einen Wert entgegen und prüft ob dieser vom Typ Integer (JavaScript-Zahl) ist. Falls es sich nicht um ein Wert vom Typ Integer handelt wird ein Nothing zurückgegeben.
Die maybeFunction Funktion überprüft ob ein Wert vom Typ function ist.
Mapping von Maybe
Die Funktion mapMaybe wird verwendet um ein Maybe Type zu mappen. Die Funktion nimmt ein Maybe und eine mapping Funktion f entgegen. Die Funktion liefert das gemappte Maybe zurück.
Die Funktion flatMapMaybe wird verwendet um eine Maybe Type zu mappen und anschliessend das Resultat abzuflachen.
/**
* A function that takes a stack and an index (as Church- or JS-Number).
* The function returns the element at the passed index or undefined incl. a Error-Log to the Console
*
* @haskell getElementByIndex :: stack -> number -> a
* @sideeffect Logs a error if index is no Church- or JS-Number or valid number
* @function
* @param {stack} stack
* @return {function(index:churchNumber|number) : * } stack-value or undefined when not exist or invalid
* @example
* const stackWithNumbers = convertArrayToStack([0,1,2]);
*
* getElementByIndex( stackWithNumbers )( n0 ) === id
* getElementByIndex( stackWithNumbers )( n1 ) === 0
* getElementByIndex( stackWithNumbers )( n2 ) === 1
* getElementByIndex( stackWithNumbers )( n3 ) === 2
*
* getElementByIndex( stackWithNumbers )( 0 ) === id
* getElementByIndex( stackWithNumbers )( 1 ) === 0
* getElementByIndex( stackWithNumbers )( 2 ) === 1
* getElementByIndex( stackWithNumbers )( 3 ) === 2
*
* getElementByIndex( stackWithNumbers )( "im a string" ) === undefined // strings not allowed, throws a Console-Warning
*/
const getElementByIndex = stack => index =>
eitherElementByIndex(stack)(index)
(console.error)
(id);
