Funktionale Programmierung - Functional programming

In der Informatik ist funktionale Programmierung ein Programmierparadigma, bei dem Programme durch Anwenden und Zusammensetzen von Funktionen konstruiert werden . Es ist ein deklaratives Programmierparadigma, bei dem Funktionsdefinitionen Bäume von Ausdrücken sind , die Werte auf andere Werte abbilden, und nicht eine Folge zwingender Anweisungen, die den Ausführungszustand des Programms aktualisieren .

In der funktionalen Programmierung werden Funktionen behandelt , als Bürger erster Klasse , was bedeutet , dass sie zu den Namen gebunden werden können (einschließlich der lokalen Kennungen ), als bestanden Argumente , und kehrte von anderen Funktionen, wie jede andere Datentyp kann. Dadurch können Programme in einem deklarativen und zusammensetzbaren Stil geschrieben werden, bei dem kleine Funktionen modular kombiniert werden.

Funktionale Programmierung wird manchmal gleichbedeutend mit rein funktionaler Programmierung behandelt , einer Untermenge der funktionalen Programmierung, die alle Funktionen als deterministische mathematische Funktionen oder reine Funktionen behandelt . Wenn eine reine Funktion mit einigen angegebenen Argumenten aufgerufen wird, gibt sie immer das gleiche Ergebnis zurück und kann nicht von einem veränderlichen Zustand oder anderen Nebenwirkungen beeinflusst werden . Dies steht im Gegensatz zu unreinen Prozeduren , die bei der imperativen Programmierung üblich sind und Nebenwirkungen haben können (z. B. das Ändern des Programmstatus oder das Annehmen von Eingaben von einem Benutzer). Befürworter einer rein funktionalen Programmierung behaupten, dass Programme durch die Einschränkung von Nebenwirkungen weniger Fehler aufweisen , einfacher zu debuggen und zu testen sind und besser für die formale Verifizierung geeignet sind .

Funktionale Programmierung hat ihre Wurzeln in der Wissenschaft und hat sich aus dem Lambda-Kalkül entwickelt , einem formalen Berechnungssystem, das nur auf Funktionen basiert. Funktionale Programmierung war in der Vergangenheit weniger beliebt als zwingende Programmierung, aber viele funktionale Sprachen werden heute in der Industrie und im Bildungswesen verwendet, darunter Common Lisp , Scheme , Clojure , Wolfram Language , Racket , Erlang , Elixir , OCaml , Haskell und F# . Funktionale Programmierung ist auch der Schlüssel zu einigen Sprachen, die in bestimmten Domänen erfolgreich waren, wie JavaScript im Web, R in der Statistik, J , K und Q in der Finanzanalyse und XQuery / XSLT für XML . Domänenspezifische deklarative Sprachen wie SQL und Lex / Yacc verwenden einige Elemente der funktionalen Programmierung, z. B. das Verhindern veränderlicher Werte . Darüber hinaus unterstützen viele andere Programmiersprachen die Programmierung in einem funktionalen Stil oder haben Funktionen aus der funktionalen Programmierung implementiert, wie z. B. C++11 , Kotlin , Perl , PHP , Python , Go , Rust , Raku , Scala und Java (seit Java 8 ) .

Geschichte

Das Lambda - Kalkül , indem sie in den 1930er Jahren entwickelt Alonzo Church , ist ein formales System von Berechnung aus dem eingebauten Funktionsanwendung . Im Jahr 1937 bewies Alan Turing , dass der Lambda-Kalkül und Turing-Maschinen äquivalente Berechnungsmodelle sind, und zeigte, dass der Lambda-Kalkül Turing-vollständig ist . Die Lambda-Kalküle bildet die Grundlage aller funktionalen Programmiersprachen. Eine äquivalente theoretische Formulierung, die kombinatorische Logik , wurde in den 1920er und 1930er Jahren von Moses Schönfinkel und Haskell Curry entwickelt .

Church entwickelte später ein schwächeres System, den einfach typisierten Lambda-Kalkül , der den Lambda-Kalkül erweiterte, indem er allen Begriffen einen Typ zuordnete . Dies bildet die Grundlage für die statisch typisierte funktionale Programmierung.

Die erste funktionale Programmiersprache, LISP , wurde in den späten 1950er Jahren von John McCarthy am Massachusetts Institute of Technology (MIT) für die IBM 700/7000-Serie wissenschaftlicher Computer entwickelt . LISP-Funktionen wurden mit der Lambda-Notation von Church definiert, die um ein Label-Konstrukt erweitert wurde, um rekursive Funktionen zu ermöglichen . Lisp führte zuerst viele paradigmatische Merkmale der funktionalen Programmierung ein, obwohl frühe Lisps Sprachen mit mehreren Paradigmen waren und Unterstützung für zahlreiche Programmierstile enthielt, als sich neue Paradigmen entwickelten. Spätere Dialekte wie Scheme und Clojure und Ableger wie Dylan und Julia versuchten, Lisp um einen sauber funktionalen Kern zu vereinfachen und zu rationalisieren, während Common Lisp entworfen wurde, um die paradigmatischen Merkmale der zahlreichen älteren Dialekte, die es ersetzte, zu erhalten und zu aktualisieren.

Information Processing Language (IPL), 1956, wird manchmal als die erste computerbasierte funktionale Programmiersprache bezeichnet. Es ist eine Sprache im Assembler-Stil zum Bearbeiten von Symbollisten. Es hat eine Vorstellung von generator , was auf eine Funktion hinausläuft, die eine Funktion als Argument akzeptiert, und da es sich um eine Sprache auf Assemblerebene handelt, kann Code Daten sein, sodass IPL als Funktionen höherer Ordnung angesehen werden kann. Es hängt jedoch stark von der mutierenden Listenstruktur und ähnlichen zwingenden Merkmalen ab.

Kenneth E. Iverson entwickelte APL in den frühen 1960er Jahren, beschrieben in seinem 1962 erschienenen Buch A Programming Language ( ISBN  9780471430148 ). APL war der Haupteinfluss auf John Backus ' FP . In den frühen 1990er Jahren, Iverson und Roger Hui erstellt J . Mitte der 1990er Jahre schuf Arthur Whitney , der zuvor mit Iverson zusammengearbeitet hatte, K , das zusammen mit seinem Nachkommen Q kommerziell in der Finanzindustrie verwendet wird .

John Backus präsentierte FP 1977 in seinem Turing Award Vortrag "Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs". Er definiert funktionale Programme als hierarchisch aufgebaut durch "Kombinationsformen", die eine "Algebra von Programmen" ermöglichen; in der modernen Sprache bedeutet dies, dass funktionale Programme dem Prinzip der Kompositionalität folgen . Das Papier von Backus machte die Forschung zur funktionalen Programmierung populär, obwohl es eher die Programmierung auf Funktionsebene als den Lambda-Kalkül-Stil betonte, der heute mit funktionaler Programmierung verbunden ist.

Die Sprache ML von 1973 wurde von Robin Milner an der University of Edinburgh entwickelt , und David Turner entwickelte die Sprache SASL an der University of St Andrews . Ebenfalls in den 1970er Jahren in Edinburgh entwickelten Burstall und Darlington die Funktionssprache NPL . NPL basierte auf Kleene-Rekursionsgleichungen und wurde erstmals in ihrer Arbeit zur Programmtransformation eingeführt. Burstall, MacQueen und Sannella haben dann die polymorphe Typprüfung von ML integriert, um die Sprache Hope zu produzieren . ML entwickelte sich schließlich zu mehreren Dialekten, von denen die häufigsten heute OCaml und Standard ML sind .

In den 1970er Jahren Guy L. Steele und Gerald Jay Sussman entwickelte Schema , wie in den beschriebenen Lambda - Papieren und 1985 Lehrbuch Struktur und Interpretation von Computerprogrammen . Scheme war der erste Dialekt von Lisp, der lexikalisches Scoping verwendet und Tail-Call-Optimierung erfordert , Funktionen, die funktionale Programmierung fördern.

In den 1980er Jahren entwickelte Per Martin-Löf die intuitionistische Typentheorie (auch als konstruktive Typentheorie bezeichnet), die funktionale Programme mit konstruktiven Beweisen, ausgedrückt als abhängige Typen, verband . Dies führte zu neuen Ansätzen zum interaktiven Theorembeweisen und hat die Entwicklung späterer funktionaler Programmiersprachen beeinflusst.

Die von David Turner entwickelte faule Funktionssprache Miranda erschien erstmals 1985 und hatte einen starken Einfluss auf Haskell . Da Miranda proprietär ist, begann Haskell 1987 mit einem Konsens, einen offenen Standard für die funktionale Programmierungsforschung zu bilden ; Implementierungsversionen laufen seit 1990.

In jüngerer Zeit hat es dank der OpenSCAD- Sprache, die auf dem CSG-Geometrie-Framework basiert, in Nischen wie parametrischem CAD Verwendung gefunden , obwohl seine Beschränkung der Neuzuweisung von Werten (alle Werte werden als Konstanten behandelt) zu Verwirrung bei Benutzern geführt hat, die mit funktionaler Programmierung nicht vertraut sind als Konzept.

Funktionale Programmierung wird weiterhin in kommerziellen Umgebungen verwendet.

Konzepte

Eine Reihe von Konzepten und Paradigmen sind spezifisch für die funktionale Programmierung und im Allgemeinen fremd für die imperative Programmierung (einschließlich der objektorientierten Programmierung ). Programmiersprachen bedienen jedoch oft mehrere Programmierparadigmen, so dass Programmierer, die "meist zwingende" Sprachen verwenden, einige dieser Konzepte verwendet haben.

Erstklassige und höherwertige Funktionen

Funktionen höherer Ordnung sind Funktionen, die andere Funktionen entweder als Argumente annehmen oder als Ergebnisse zurückgeben können. In der Analysis ist ein Beispiel für eine Funktion höherer Ordnung der Differentialoperator , der die Ableitung einer Funktion zurückgibt .

Funktionen höherer Ordnung sind eng mit Funktionen erster Klasse verwandt, da Funktionen höherer Ordnung und Funktionen erster Klasse Funktionen als Argumente und Ergebnisse anderer Funktionen zulassen. Der Unterschied zwischen den beiden ist subtil: "höherer Ordnung" beschreibt ein mathematisches Konzept von Funktionen, die auf andere Funktionen operieren, während "erstklassig" ein Informatikbegriff für Programmiersprachenentitäten ist, deren Verwendung keine Beschränkungen hat (also zuerst -Klassenfunktionen können überall im Programm erscheinen, die andere erstklassige Entitäten wie Zahlen können, einschließlich als Argumente für andere Funktionen und als deren Rückgabewerte).

Funktionen höherer Ordnung ermöglichen partielle Anwendung oder currying , eine Technik, die eine Funktion nacheinander auf ihre Argumente anwendet, wobei jede Anwendung eine neue Funktion zurückgibt, die das nächste Argument akzeptiert. Damit kann ein Programmierer beispielsweise die Nachfolgefunktion als Additionsoperator, der teilweise auf die natürliche Zahl Eins angewendet wird, prägnant ausdrücken .

Reine Funktionen

Reine Funktionen (oder Ausdrücke) haben keine Nebenwirkungen (Speicher oder I/O). Dies bedeutet, dass reine Funktionen mehrere nützliche Eigenschaften haben, von denen viele zur Optimierung des Codes verwendet werden können:

  • Wenn das Ergebnis eines reinen Ausdrucks nicht verwendet wird, kann es entfernt werden, ohne andere Ausdrücke zu beeinflussen.
  • Wenn eine reine Funktion mit Argumenten aufgerufen wird, die keine Nebenwirkungen verursachen, ist das Ergebnis in Bezug auf diese Argumentliste konstant (manchmal als referentielle Transparenz oder Idempotenz bezeichnet ), dh ein erneuter Aufruf der reinen Funktion mit denselben Argumenten liefert das gleiche Ergebnis. (Dies kann Caching-Optimierungen wie Memoization ermöglichen .)
  • Wenn keine Datenabhängigkeit zwischen zwei reinen Ausdrücken besteht, kann ihre Reihenfolge umgekehrt werden oder sie können parallel ausgeführt werden und können sich nicht gegenseitig stören (mit anderen Worten, die Auswertung eines reinen Ausdrucks ist thread-sicher ).
  • Lässt die gesamte Sprache keine Nebeneffekte zu, kann jede Bewertungsstrategie verwendet werden; dies gibt dem Compiler die Freiheit, die Auswertung von Ausdrücken in einem Programm neu anzuordnen oder zu kombinieren (z. B. mit deforestation ).

Während die meisten Compiler für imperative Programmiersprachen reine Funktionen erkennen und für reine Funktionsaufrufe die Eliminierung gemeinsamer Teilausdrücke durchführen, können sie dies nicht immer für vorkompilierte Bibliotheken tun, die diese Informationen im Allgemeinen nicht offenlegen, wodurch Optimierungen verhindert werden, die diese externen Funktionen einbeziehen. Einige Compiler, wie z. B. gcc , fügen einem Programmierer zusätzliche Schlüsselwörter hinzu, um externe Funktionen explizit als rein zu markieren, um solche Optimierungen zu ermöglichen. Fortran 95 lässt auch Funktionen als pure bezeichnen . C++11 hat ein constexprSchlüsselwort mit ähnlicher Semantik hinzugefügt .

Rekursion

Iteration (Schleifenbildung) in funktionalen Sprachen wird normalerweise durch Rekursion erreicht . Rekursive Funktionen rufen sich selbst auf und lassen eine Operation wiederholt werden, bis sie den Basisfall erreicht . Im Allgemeinen erfordert die Rekursion das Aufrechterhalten eines Stapels , der Platz in einem linearen Betrag zur Rekursionstiefe verbraucht. Dies könnte die Verwendung von Rekursionen anstelle von imperativen Schleifen unerschwinglich machen. Eine spezielle Form der Rekursion, die als Tail-Rekursion bekannt ist, kann jedoch von einem Compiler erkannt und in denselben Code optimiert werden, der zur Implementierung der Iteration in imperativen Sprachen verwendet wird. Tail-Rekursions-Optimierung kann unter anderem dadurch implementiert werden, dass das Programm während der Kompilierung in einen Fortsetzungs-Passing-Stil umgewandelt wird .

Der Scheme- Sprachstandard verlangt von Implementierungen, dass sie die richtige Tail-Rekursion unterstützen, was bedeutet, dass sie eine unbegrenzte Anzahl von aktiven Tail-Aufrufen zulassen müssen. Die richtige Tail-Rekursion ist nicht nur eine Optimierung; Es ist eine Sprachfunktion, die Benutzern versichert, dass sie Rekursion verwenden können, um eine Schleife auszudrücken, und dies wäre sicher für den Speicherplatz. Darüber hinaus berücksichtigt es im Gegensatz zu seinem Namen alle Tail-Calls, nicht nur Tail-Rekursionen. Während eine korrekte Tail-Rekursion normalerweise implementiert wird, indem Code in imperative Schleifen umgewandelt wird, können Implementierungen sie auf andere Weise implementieren. Zum Beispiel CHICKEN hält absichtlich einen Stapel und läßt den Stack - Überlauf . Wenn dies jedoch geschieht, beansprucht sein Garbage Collector Speicherplatz zurück und ermöglicht eine unbegrenzte Anzahl aktiver Tail-Aufrufe, obwohl er die Tail-Rekursion nicht in eine Schleife umwandelt.

Gängige Rekursionsmuster können mit Funktionen höherer Ordnung abstrahiert werden, wobei Katamorphismen und Anamorphismen (oder "Falten" und "Entfalten") die offensichtlichsten Beispiele sind. Solche Rekursionsschemata spielen analog zu eingebauten Kontrollstrukturen wie Schleifen in imperativen Sprachen eine Rolle .

Die meisten universellen funktionalen Programmiersprachen erlauben uneingeschränkte Rekursion und sind Turing-vollständig , was das Halteproblem unentscheidbar macht , zu Unzuverlässigkeit des Gleichungsschlusses führen kann und im Allgemeinen die Einführung von Inkonsistenzen in die durch das Typsystem der Sprache ausgedrückte Logik erfordert . Einige Spezialsprachen wie Coq erlauben nur eine fundierte Rekursion und sind stark normalisierend (nicht terminierende Berechnungen können nur mit unendlichen Werteströmen namens codata ausgedrückt werden ). Infolgedessen sind diese Sprachen nicht Turing-vollständig und es ist unmöglich, bestimmte Funktionen in ihnen auszudrücken, aber sie können immer noch eine breite Klasse interessanter Berechnungen ausdrücken und gleichzeitig die Probleme vermeiden, die durch die uneingeschränkte Rekursion eingeführt werden. Funktionale Programmierung, die auf eine fundierte Rekursion mit einigen anderen Einschränkungen beschränkt ist, wird als totale funktionale Programmierung bezeichnet .

Strenge versus nicht-strenge Bewertung

Funktionale Sprachen können danach kategorisiert werden, ob sie eine strenge (eifrige) oder nicht strenge (faule) Auswertung verwenden, Konzepte, die sich darauf beziehen, wie Funktionsargumente bei der Auswertung eines Ausdrucks verarbeitet werden. Der technische Unterschied liegt in der denotationalen Semantik von Ausdrücken, die fehlgeschlagene oder abweichende Berechnungen enthalten. Bei einer strengen Bewertung schlägt die Bewertung eines Begriffs fehl, der einen fehlgeschlagenen Unterbegriff enthält. Zum Beispiel der Ausdruck:

print length([2+1, 3*2, 1/0, 5-4])

scheitert bei strenger Auswertung an der Division durch Null im dritten Element der Liste. Bei der verzögerten Auswertung gibt die Längenfunktion den Wert 4 (dh die Anzahl der Elemente in der Liste) zurück, da die Auswertung nicht versucht, die Begriffe auszuwerten, aus denen die Liste besteht. Kurz gesagt wertet die strikte Auswertung Funktionsargumente immer vollständig aus, bevor die Funktion aufgerufen wird. Die verzögerte Auswertung wertet keine Funktionsargumente aus, es sei denn, ihre Werte sind erforderlich, um den Funktionsaufruf selbst auszuwerten.

Die übliche Implementierungsstrategie für Lazy Evaluation in funktionalen Sprachen ist die Graphreduktion . Lazy Evaluation wird standardmäßig in mehreren rein funktionalen Sprachen verwendet, darunter Miranda , Clean und Haskell .

Hughes 1984 argumentiert für faule Evaluation als einen Mechanismus zur Verbesserung der Programmmodularität durch Trennung von Interessen , indem die unabhängige Implementierung von Produzenten und Konsumenten von Datenströmen erleichtert wird. Launchbury 1993 beschreibt einige Schwierigkeiten, die eine faule Evaluation mit sich bringt, insbesondere bei der Analyse der Speicheranforderungen eines Programms, und schlägt eine operative Semantik vor , um bei einer solchen Analyse zu helfen. Harper 2009 schlägt vor, sowohl die strenge als auch die faule Bewertung in derselben Sprache einzubeziehen, wobei das Typensystem der Sprache verwendet wird, um sie zu unterscheiden.

Typensysteme

Insbesondere seit der Entwicklung der Hindley-Milner-Typeninferenz in den 1970er Jahren neigen funktionale Programmiersprachen dazu, typisierte Lambda-Kalküle zu verwenden , alle ungültigen Programme zur Kompilierungszeit abzulehnen und falsch positive Fehler zu riskieren , im Gegensatz zum untypisierten Lambda-Kalkül , der alle gültigen . akzeptiert Programme zur Kompilierungszeit und riskiert falsch-negative Fehler , die in Lisp und seinen Varianten (wie Scheme ) verwendet werden, obwohl sie alle ungültigen Programme zur Laufzeit ablehnen, wenn die Informationen ausreichen, um keine gültigen Programme abzulehnen. Die Verwendung algebraischer Datentypen erleichtert die Manipulation komplexer Datenstrukturen; das Vorhandensein einer starken Typüberprüfung während der Kompilierung macht Programme zuverlässiger , wenn andere Zuverlässigkeitstechniken wie testgetriebene Entwicklung fehlen , während die Typinferenz den Programmierer in den meisten Fällen von der Notwendigkeit befreit, Typen manuell für den Compiler zu deklarieren.

Einige forschungsorientierte funktionale Sprachen wie Coq , Agda , Cayenne und Epigram basieren auf der intuitionistischen Typentheorie , die Typen von Begriffen abhängen lässt. Solche Typen werden abhängige Typen genannt . Diese Typsysteme haben keine entscheidbare Typinferenz und sind schwer zu verstehen und zu programmieren. Aber abhängige Typen können beliebige Aussagen in der Logik höherer Ordnung ausdrücken . Durch den Curry-Howard-Isomorphismus werden also gut typisierte Programme in diesen Sprachen zu einem Mittel, um formale mathematische Beweise zu schreiben, aus denen ein Compiler zertifizierten Code generieren kann . Während diese Sprachen hauptsächlich in der akademischen Forschung (einschließlich der formalisierten Mathematik ) von Interesse sind, werden sie auch in den Ingenieurwissenschaften verwendet. Compcert ist ein Compiler für eine Teilmenge der Programmiersprache C , die in Coq geschrieben und formal verifiziert ist.

Eine begrenzte Form abhängiger Typen, die als generalisierte algebraische Datentypen (GADTs) bezeichnet werden, kann auf eine Weise implementiert werden, die einige der Vorteile der abhängig typisierten Programmierung bietet, während die meisten Unannehmlichkeiten vermieden werden. GADTs sind im Glasgow Haskell Compiler , in OCaml und in Scala verfügbar und wurden als Ergänzungen zu anderen Sprachen einschließlich Java und C# vorgeschlagen.

Referenzielle Transparenz

Funktionale Programme haben keine Zuweisungsanweisungen, dh der Wert einer Variablen in einem funktionalen Programm ändert sich nie, wenn sie einmal definiert wurde. Dadurch werden mögliche Nebenwirkungen ausgeschlossen, da jede Variable zu jedem Zeitpunkt der Ausführung durch ihren tatsächlichen Wert ersetzt werden kann. Funktionale Programme sind also referenziell transparent.

Betrachten Sie die C- Zuweisungsanweisung x = x * 10, dies ändert den der Variablen zugewiesenen Wert x. Lassen Sie uns sagen , dass der Anfangswert xwar 1, dann zwei aufeinander folgenden Auswertungen der variablen xAusbeuten 10und 100jeweils. Es ist klar, dass das Ersetzen x = x * 10durch entweder 10oder 100einem Programm eine andere Bedeutung verleiht, und daher ist der Ausdruck nicht referenziell transparent. Tatsächlich sind Zuweisungsanweisungen nie referenziell transparent.

Betrachten Sie nun eine andere Funktion wie ist transparent, da sie die Eingabe x nicht implizit ändert und daher keine derartigen Nebenwirkungen hat . Funktionale Programme verwenden ausschließlich diese Art von Funktion und sind daher referenziell transparent. int plusone(int x) {return x+1;}

Datenstrukturen

Rein funktionale Datenstrukturen werden oft anders dargestellt als ihre zwingenden Gegenstücke. Das Array mit konstanten Zugriffs- und Aktualisierungszeiten ist beispielsweise eine grundlegende Komponente der meisten imperativen Sprachen, und viele imperative Datenstrukturen, wie die Hash-Tabelle und der Binärheap , basieren auf Arrays. Arrays können durch Maps oder Random Access Lists ersetzt werden, die eine rein funktionale Umsetzung zulassen, aber logarithmische Zugriffs- und Aktualisierungszeiten aufweisen. Rein funktionale Datenstrukturen haben Persistenz , eine Eigenschaft, frühere Versionen der Datenstruktur unverändert zu lassen. In Clojure werden persistente Datenstrukturen als funktionale Alternativen zu ihren zwingenden Gegenstücken verwendet. Persistente Vektoren verwenden beispielsweise Bäume zur teilweisen Aktualisierung. Das Aufrufen der Insert-Methode führt dazu, dass einige, aber nicht alle Knoten erstellt werden.

Vergleich zur imperativen Programmierung

Die funktionale Programmierung unterscheidet sich stark von der imperativen Programmierung . Die wichtigsten Unterschiede ergeben sich aus der Tatsache, dass die funktionale Programmierung Nebeneffekte vermeidet , die bei der imperativen Programmierung verwendet werden, um Zustand und E/A zu implementieren. Reine funktionale Programmierung verhindert vollständig Nebeneffekte und sorgt für referentielle Transparenz.

Funktionen höherer Ordnung werden in der älteren imperativen Programmierung selten verwendet. Ein traditionelles Imperativ-Programm könnte eine Schleife verwenden, um eine Liste zu durchlaufen und zu ändern. Ein funktionales Programm hingegen würde wahrscheinlich eine „Map“-Funktion höherer Ordnung verwenden, die eine Funktion und eine Liste aufnimmt und eine neue Liste erzeugt und zurückgibt, indem es die Funktion auf jedes Listenelement anwendet.

Imperative vs. funktionale Programmierung

Die folgenden beiden Beispiele (in JavaScript geschrieben ) erzielen den gleichen Effekt: Sie multiplizieren alle geraden Zahlen in einem Array mit 10 und addieren sie alle, wobei die Endsumme in der Variablen "result" gespeichert wird.

Traditionelle Imperativschleife:

const numList = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let result = 0;
for (let i = 0; i < numList.length; i++) {
  if (numList[i] % 2 === 0) {
    result += numList[i] * 10;
  }
}

Funktionale Programmierung mit übergeordneten Funktionen:

const result = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
               .filter(n => n % 2 === 0)
               .map(a => a * 10)
               .reduce((a, b) => a + b);

Simulieren des Zustands

Es gibt Aufgaben (zum Beispiel das Führen eines Bankkontostands), die oft am natürlichsten mit dem Staat umgesetzt werden. Reine funktionale Programmierung führt diese Aufgaben und I/O-Aufgaben wie das Akzeptieren von Benutzereingaben und Drucken auf dem Bildschirm auf andere Weise aus.

Die rein funktionale Programmiersprache Haskell implementiert sie mit Monaden , die aus der Kategorientheorie abgeleitet sind . Monaden bieten eine Möglichkeit, bestimmte Arten von Rechenmustern zu abstrahieren, einschließlich (aber nicht beschränkt auf) die Modellierung von Berechnungen mit veränderlichem Zustand (und anderen Nebeneffekten wie E/A) auf zwingende Weise, ohne an Reinheit zu verlieren. Während bestehende Monaden mit geeigneten Vorlagen und Beispielen leicht in einem Programm angewendet werden können, sind sie für viele Studierende konzeptionell schwer zu verstehen, z. B. wenn sie aufgefordert werden, neue Monaden zu definieren (was manchmal für bestimmte Arten von Bibliotheken erforderlich ist).

Funktionale Sprachen simulieren auch Zustände, indem sie unveränderliche Zustände umgehen. Dies kann erreicht werden, indem eine Funktion den Zustand als einen ihrer Parameter akzeptiert und zusammen mit dem Ergebnis einen neuen Zustand zurückgibt, wobei der alte Zustand unverändert bleibt.

Unreine funktionale Sprachen beinhalten normalerweise eine direktere Methode zur Verwaltung des veränderlichen Zustands. Clojure verwendet zum Beispiel verwaltete Referenzen, die aktualisiert werden können, indem reine Funktionen auf den aktuellen Zustand angewendet werden. Diese Art von Ansatz ermöglicht Veränderlichkeit und fördert gleichzeitig die Verwendung reiner Funktionen als bevorzugte Methode zum Ausdrücken von Berechnungen.

Alternative Methoden wie Hoare-Logik und Einzigartigkeit wurden entwickelt, um Nebenwirkungen in Programmen zu verfolgen. Einige moderne Forschungssprachen verwenden Effektsysteme , um das Vorhandensein von Nebenwirkungen explizit zu machen.

Effizienzprobleme

Funktionale Programmiersprachen sind bei der Nutzung von CPU und Speicher in der Regel weniger effizient als zwingende Sprachen wie C und Pascal . Dies hängt mit der Tatsache zusammen, dass einige veränderliche Datenstrukturen wie Arrays eine sehr einfache Implementierung unter Verwendung der gegenwärtigen Hardware haben. Auf flache Arrays kann mit Deep-Pipeline-CPUs sehr effizient zugegriffen, effizient durch Caches (ohne komplexes Pointer-Chasing ) vorabgerufen oder mit SIMD-Befehlen gehandhabt werden. Es ist auch nicht einfach, ihre ebenso effizienten, unveränderlichen Gegenstücke für allgemeine Zwecke zu erstellen. Für rein funktionale Sprachen ist die Verlangsamung im schlimmsten Fall logarithmisch in der Anzahl der verwendeten Speicherzellen, da veränderlicher Speicher durch eine rein funktionale Datenstruktur mit logarithmischer Zugriffszeit (wie einen ausgeglichenen Baum) repräsentiert werden kann. Solche Verlangsamungen sind jedoch nicht universell. Für Programme , die intensive numerische Berechnungen, funktionale Sprachen wie ausführen OCaml und reinigen sind nur etwas langsamer als C nach dem Computer Language Benchmarks Spiel . Für Programme, die mit großen Matrizen und mehrdimensionalen Datenbanken umgehen , wurden Array- Funktionssprachen (wie J und K ) mit Geschwindigkeitsoptimierungen entworfen.

Die Unveränderlichkeit von Daten kann in vielen Fällen zu einer Effizienz bei der Ausführung führen, da der Compiler Annahmen treffen kann, die in einer imperativen Sprache unsicher sind, wodurch die Möglichkeiten für eine Inline-Erweiterung erhöht werden .

Lazy Evaluation kann auch das Programm beschleunigen, sogar asymptotisch, während es es höchstens um einen konstanten Faktor verlangsamen kann (allerdings kann es bei unsachgemäßer Verwendung zu Speicherverlusten führen ). Launchbury 1993 diskutiert theoretische Probleme im Zusammenhang mit Speicherlecks aus fauler Auswertung, und O'Sullivan et al. 2008 geben einige praktische Ratschläge, um sie zu analysieren und zu beheben. Die allgemeinsten Implementierungen der Lazy-Evaluation, die ausgiebigen Gebrauch von dereferenziertem Code und Daten machen, funktionieren jedoch auf modernen Prozessoren mit tiefen Pipelines und Caches mit mehreren Ebenen (wo ein Cache-Miss Hunderte von Zyklen kosten kann) schlecht.

Funktionale Programmierung in nicht-funktionalen Sprachen

Es ist möglich, einen funktionalen Programmierstil in Sprachen zu verwenden, die traditionell nicht als funktionale Sprachen gelten. Sowohl D als auch Fortran 95 unterstützen beispielsweise explizit reine Funktionen.

JavaScript , Lua , Python und Go hatten von Anfang an erstklassige Funktionen . Python hatte 1994 Unterstützung für " Lambda ", " Map ", " Reduce " und " Filter " sowie Closures in Python 2.2, obwohl Python 3 "Reduce" in das functoolsStandardbibliotheksmodul verbannte . Erstklassige Funktionen wurden in andere Mainstream-Sprachen wie PHP 5.3, Visual Basic 9 , C# 3.0, C++11 und Kotlin eingeführt .

In PHP werden anonyme Klassen , Closures und Lambdas vollständig unterstützt. Zur Unterstützung der Programmierung im funktionalen Stil werden Bibliotheken und Spracherweiterungen für unveränderliche Datenstrukturen entwickelt.

In Java , anonyme Klassen können manchmal simuliert werden Verschlüsse ; Anonyme Klassen sind jedoch nicht immer ein geeigneter Ersatz für Closures, da sie über eingeschränktere Fähigkeiten verfügen. Java 8 unterstützt Lambda-Ausdrücke als Ersatz für einige anonyme Klassen.

In C # , anonymen Klassen sind nicht erforderlich, da Verschlüsse und Lambda - Ausdrücke voll unterstützt werden. Bibliotheken und Spracherweiterungen für unveränderliche Datenstrukturen werden entwickelt, um die Programmierung im funktionalen Stil in C# zu unterstützen.

Viele objektorientierte Entwurfsmuster lassen sich in Begriffen der funktionalen Programmierung ausdrücken: Zum Beispiel schreibt das Strategiemuster einfach die Verwendung einer Funktion höherer Ordnung vor, und das Besuchermuster entspricht ungefähr einem Katamorphismus oder fold .

In ähnlicher Weise ist die Idee unveränderlicher Daten aus der funktionalen Programmierung oft in imperativen Programmiersprachen enthalten, beispielsweise dem Tupel in Python, das ein unveränderliches Array ist, und Object.freeze() in JavaScript.

Anwendungen

Tabellenkalkulationen

Tabellenkalkulationen können als eine Form eines reinen funktionalen Programmiersystems nullter Ordnung mit strikter Bewertung angesehen werden. Tabellenkalkulationen fehlen jedoch im Allgemeinen Funktionen höherer Ordnung sowie die Wiederverwendung von Code, und in einigen Implementierungen fehlt auch die Rekursion. Für Tabellenkalkulationsprogramme wurden mehrere Erweiterungen entwickelt, um Funktionen höherer Ordnung und wiederverwendbare Funktionen zu ermöglichen, die jedoch bisher hauptsächlich akademischer Natur sind.

Wissenschaft

Funktionale Programmierung ist ein aktives Forschungsgebiet im Bereich der Programmiersprachentheorie . Es gibt mehrere von Experten begutachtete Publikationsorte, die sich auf funktionale Programmierung konzentrieren, darunter die International Conference on Functional Programming , das Journal of Functional Programming und das Symposium on Trends in Functional Programming .

Industrie

Funktionale Programmierung hat in einer Vielzahl von industriellen Anwendungen Verwendung gefunden. Beispielsweise wurde Erlang , das Ende der 1980er Jahre von der schwedischen Firma Ericsson entwickelt wurde, ursprünglich verwendet, um fehlertolerante Telekommunikationssysteme zu implementieren, ist aber seitdem für den Aufbau einer Reihe von Anwendungen bei Unternehmen wie Nortel , Facebook , Électricité de . populär geworden Frankreich und WhatsApp . Scheme , ein Dialekt von Lisp , wurde als Grundlage für mehrere Anwendungen , die auf frühen verwendet Apple Macintosh - Computer und hat zu Problemen wie Ausbildung angewandt Simulationssoftware und Teleskop - Steuerung. OCaml , die in der Mitte der 1990er Jahre eingeführt wurde, hat sich in Bereichen wie Finanzanalyse, kommerzielle Nutzung gesehen Fahrerprüfung, Industrieroboterprogrammierung und statische Analyse von Embedded - Software . Haskell , obwohl ursprünglich als Forschungssprache gedacht, wurde auch von einer Reihe von Unternehmen in Bereichen wie Luft- und Raumfahrtsystemen, Hardwaredesign und Webprogrammierung angewendet.

Andere funktionale Programmiersprachen, die in der Industrie Verwendung gefunden haben, sind Scala , F# , Wolfram Language , Lisp , Standard ML und Clojure .

Funktionale „Plattformen“ sind im Finanzbereich zur Risikoanalyse beliebt (insbesondere bei den größeren Investmentbanken). Risikofaktoren werden als Funktionen kodiert, die voneinander abhängige Graphen (Kategorien) bilden, um Korrelationen in Marktverschiebungen zu messen, ähnlich wie bei Gröbner- Basisoptimierungen, aber auch für die Einhaltung gesetzlicher Vorschriften wie Comprehensive Capital Analysis and Review . Angesichts der Verwendung von OCAML- oder CAML- Variationen im Finanzwesen werden diese Systeme manchmal als mit einer kategorischen abstrakten Maschine oder CAM in Verbindung gebracht. Tatsächlich wird die funktionale Programmierung stark von der Kategorientheorie beeinflusst .

Ausbildung

Viele Universitäten lehren oder haben funktionale Programmierung als Teil ihres gelehrt Bachelor Informatik Grad. Einige verwenden es als Einführung in die Programmierung, während andere es unterrichten, nachdem sie das Imperative Programmieren unterrichtet haben.

Außerhalb der Informatik wird die funktionale Programmierung als Methode verwendet, um Problemlösungen, Algebra und geometrische Konzepte zu lehren. Es wurde auch als Werkzeug verwendet, um klassische Mechanik in Struktur und Interpretation der klassischen Mechanik zu lehren .

Siehe auch

Verweise

Weiterlesen

Externe Links

Diesen Artikel anhören ( 28 Minuten )
Gesprochenes Wikipedia-Symbol
Diese Audiodatei wurde aus einer Überarbeitung dieses Artikels vom 25. August 2011 erstellt und spiegelt keine späteren Bearbeitungen wider. ( 2011-08-25 )