Haupt >> Computerprogrammierung >> Funktionale Programmierung

Funktionale Programmierung

Funktionale Programmierung ist ein Programmierparadigma, das Berechnungen als Auswertung mathematischer Funktionen versteht und Zustände und veränderliche Daten vermeidet. Im Gegensatz dazu betont die funktionale Programmierung die Anwendung von Funktionen zwingende Programmierung , die Zustandsänderungen und die Ausführung sequentieller Befehle hervorhebt.

Eine breitere Konzeption der funktionalen Programmierung definiert einfach eine Reihe gemeinsamer Anliegen und Themen und nicht eine Liste von Unterschieden zu anderen Paradigmen. Häufig als wichtig erachtet werden höherwertige und erstklassige Funktionen, Closures und Rekursion. Andere gemeinsame Merkmale von funktionalen Programmiersprachen sind Fortsetzungen, Inferenzsysteme vom Hindley-Milner-Typ, nicht strenge Auswertung (einschließlich, aber nicht beschränkt auf 'Faulheit') und Monaden.

Funktionale Programmiersprachen, insbesondere 'rein funktionale', wurden in der Wissenschaft eher als in der kommerziellen Softwareentwicklung betont. Zu den bemerkenswerten funktionalen Programmiersprachen, die in industriellen und kommerziellen Anwendungen verwendet werden, gehören jedoch Erlang (gleichzeitige Anwendungen), R (Statistik), Mathematica (symbolische Mathematik), J und K (Finanzanalyse) und domänenspezifische Programmiersprachen wie XSLT. Wichtige Einflüsse auf die funktionale Programmierung waren der Lambda-Kalkül, die Programmiersprache APL, die Programmiersprache Lisp und in jüngerer Zeit die Programmiersprache Haskell.



Geschichte

Die von Alonzo Church in den 1930er Jahren erfundene Lambda-Kalkül bietet einen theoretischen Rahmen für die Beschreibung von Funktionen und deren Bewertung. Obwohl es sich eher um eine mathematische Abstraktion als um eine Programmiersprache handelt, bildet der Lambda-Kalkül heute die Grundlage fast aller funktionalen Programmiersprachen.

Die kombinatorische Logik ist eine gleichwertige theoretische Grundlage, die von Moses Schönfinkel und Haskell Curry entwickelt wurde. Es wurde ursprünglich entwickelt, um ein größeres Ziel zu erreichen: eine klarere Herangehensweise an die Grundlagen der Mathematik. Die kombinatorische Logik, die gemeinhin als abstrakter als der Lambda-Kalkül wahrgenommen wird, ging dem Lambda-Kalkül in der Erfindung voraus.

Die erste computerbasierte funktionale Programmiersprache war die Information Processing Language (IPL), die Mitte der 1950er Jahre von Newell, Shaw und Simon bei der RAND Corporation für den JOHNNIAC-Computer entwickelt wurde. Eine frühe Programmiersprache mit funktionalem Geschmack war LISP (jetzt Mixed-Case 'Lisp'), das Ende der 1950er Jahre von John McCarthy am MIT für die wissenschaftlichen Computer der IBM 700/7000-Serie entwickelt wurde. LISP führte viele der Features ein, die heute in modernen funktionalen Programmiersprachen zu finden sind, obwohl LISP technisch gesehen eine Sprache mit mehreren Paradigmen ist. Planen und Dylan waren spätere Versuche, LISP zu vereinfachen und zu verbessern.

Kenneth E. Iverson entwickelte Anfang der 1960er Jahre die Programmiersprache APL, die in seinem 1962 erschienenen Buch „A Programming Language“ beschrieben wurde. APL war der Haupteinfluss auf die Programmiersprache FP von John Backus. In den frühen 1990er Jahren schufen Iverson und Roger Hui einen Nachfolger von APL, der Programmiersprache J. Mitte der 1990er Jahre schuf Arthur Whitney, der zuvor mit Iverson zusammengearbeitet hatte, die Programmiersprache K, die kommerziell in der Finanzbranche eingesetzt wird.

John Backus stellte die Programmiersprache FP 1977 in seinem Turing-Award-Vortrag Can Programming Be Liberated From the von Neumann Style? vor. Ein funktionaler Stil und seine Programmalgebra. 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. Backus 'Papier machte die Forschung zur funktionalen Programmierung populär, obwohl es eher die Programmierung auf Funktionsebene als den Lambda-Kalkül-Stil betonte, der mit der funktionalen Programmierung in Verbindung gebracht wird.

In den 1970er Jahren wurde die Programmiersprache ML von Robin Milner an der University of Edinburgh entwickelt, und David Turner entwickelte die Sprache Miranda an der University of Kent. ML entwickelte sich schließlich zu mehreren Dialekten, von denen die gebräuchlichsten heute Objective Caml und Standard ML sind. Die Programmiersprache Haskell wurde Ende der 1980er Jahre veröffentlicht, um viele Ideen in der funktionalen Programmierforschung zu sammeln.

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 sind jedoch häufig Hybride aus mehreren Programmierparadigmen, sodass Programmierer, die 'meistens imperative' Sprachen verwenden, möglicherweise einige dieser Konzepte verwendet haben.

Funktionen höherer Ordnung

Die funktionale Programmierung verwendet den Begriff der Funktionen höherer Ordnung. Funktionen sind von höherer Ordnung, wenn sie andere Funktionen als Argumente annehmen und/oder Funktionen als Ergebnisse zurückgeben können. (Die Ableitung und Stammfunktion in Infinitesimalrechnung sind mathematische Beispiele für Funktionen, die eine Funktion auf eine andere Funktion abbilden.)

Funktionen höherer Ordnung sind eng mit erstklassigen Funktionen verwandt, da sowohl Funktionen höherer Ordnung als auch erstklassige Funktionen Funktionen als Argumente und Ergebnisse anderer Funktionen zulassen. Die Unterscheidung zwischen den beiden ist subtil: „höherer Ordnung“ beschreibt ein mathematisches Konzept von Funktionen, die auf anderen Funktionen operieren, während „erstklassig“ ein Begriff aus der Informatik ist, der Entitäten in Programmiersprachen beschreibt, die keine Beschränkung für ihre Verwendung haben (also Erstklassige Funktionen können überall im Programm erscheinen, wo andere erstklassige Entitäten wie Zahlen vorkommen können, einschließlich als Argumente für andere Funktionen und als deren Rückgabewerte).

Funktionen höherer Ordnung ermöglichen Currying, eine Technik, bei der eine Funktion einzeln auf ihre Argumente angewendet wird, wobei jede Anwendung eine neue Funktion (höherer Ordnung) zurückgibt, die das nächste Argument akzeptiert.

Reine Funktionen

Rein funktionale Programme haben keine Seiteneffekte. Nicht alle funktionalen Programme oder funktionalen Programmiersprachen sind rein funktional. Da reine Funktionen den Zustand nicht verändern, dürfen keine Daten durch parallele Funktionsaufrufe verändert werden. Reine Funktionen sind daher Thread-sicher, wodurch Sprachen Call-by-Future-Auswertungen verwenden können. Das Fehlen von Nebenwirkungen ermöglicht es einigen Sprachen, wie z. B. Haskell, die Call-by-Needness-Evaluierung zu verwenden.

'Reine' funktionale Programmiersprachen erzwingen normalerweise referenzielle Transparenz, d. h. die Vorstellung, dass 'Gleiches durch Gleiches ersetzt werden kann': Wenn zwei Ausdrücke 'gleiche' Werte haben (für einen Begriff der Gleichheit), kann einer durch den anderen ersetzt werden in beliebiger größerer Ausdruck, ohne das Ergebnis der Berechnung zu beeinflussen. Zum Beispiel im

y = f(x) * f(x);    

Ein Compiler kann f(x) ausklammern, wenn es rein ist, und das Programm umwandeln

z = f(x);   
y = z * z;       

und Eliminieren der zweiten Auswertung des (möglicherweise kostspieligen) Aufrufs an f(x). Diese Optimierung wird als Eliminierung gemeinsamer Unterausdrücke bezeichnet.

Wenn eine Funktion jedoch Seiteneffekte hat, kann der Funktionsaufruf nicht eliminiert werden. Betrachten Sie das folgende Programmfragment:

y = random() * random();    

Der zweite Aufruf von random kann nicht eliminiert werden, da sein Rückgabewert vom ersten Aufruf abweichen kann. Ähnlich,

y = printf("x") * printf("x");      

kann nicht wegoptimiert werden; selbst wenn printf beide Male denselben Wert zurückgibt, würde ein Fehlschlagen des zweiten Aufrufs zu einer anderen Programmausgabe führen.

Die meisten Compiler für imperative Programmiersprachen führen bei Funktionsaufrufen keine allgemeine Unterausdruckseliminierung durch, da sie nicht nachverfolgen, ob eine Funktion rein ist. Es ist einem fortgeschrittenen Compiler möglich, abzuleiten, ob eine lokale Funktion Auswirkungen hat, und entsprechend zu optimieren; Die meisten vorkompilierten Bibliotheken stellen diese Informationen jedoch nicht bereit, wodurch verhindert wird, dass Aufrufe externer Funktionen wegoptimiert werden. Einige Compiler wie gcc fügen zusätzliche Schlüsselwörter für einen Programmierer hinzu, um reine Funktionen explizit zu markieren, damit diese Optimierung durchgeführt werden kann.

Rekursion

Iteration (Schleife) in funktionalen Sprachen wird normalerweise durch Rekursion erreicht. Rekursive Funktionen rufen sich selbst auf, wodurch eine Operation immer wieder ausgeführt werden kann. Die Rekursion erfordert möglicherweise die Verwaltung eines Stacks, aber die Schwanzrekursion kann von einem Compiler erkannt und in denselben Code optimiert werden, der zur Implementierung der Iteration in imperativen Sprachen verwendet wird. Das Scheme-Programmiersprache Standard erfordert Implementierungen zum Erkennen und Optimieren der Schwanzrekursion.

Übliche Rekursionsmuster können unter Verwendung von Funktionen höherer Ordnung ausgeklammert werden, wobei Katamorphismen und Anamorphismen (oder 'Falten' und 'Entfalten') die offensichtlichsten Beispiele sind. Solche Funktionen höherer Ordnung spielen analog zu eingebauten Kontrollstrukturen wie Schleifen in imperativen Sprachen eine Rolle.

Funktionale Programmierung in nichtfunktionalen Sprachen

Es ist möglich, einen funktionalen Programmierstil in Sprachen zu verwenden, die traditionell nicht als funktionale Sprachen gelten. Einige nicht-funktionale Sprachen haben Funktionen wie Lambda-Funktionen, Funktionen höherer Ordnung und Listenverständnisse von funktionalen Programmiersprachen entlehnt. Dies erleichtert es, bei der Verwendung dieser Sprachen einen funktionalen Stil zu übernehmen. Funktionale Konstrukte wie Funktionen höherer Ordnung und faule Listen können in C++ über Bibliotheken bezogen werden. In C kann man Funktionszeiger verwenden, um einige der Effekte von Funktionen höherer Ordnung zu erhalten, zum Beispiel kann man die allgemeine Funktionsabbildung mit Funktionszeigern implementieren. Weit verbreitete deklarative domänenspezifische Sprachen wie SQL und Lex/Yacc verwenden einige Elemente der funktionalen Programmierung, insbesondere beim Verzicht auf veränderliche Werte, obwohl sie nicht Turing-vollständig sind.

Vergleich von funktionaler und imperativer Programmierung

Funktionale Programmierung unterscheidet sich sehr von zwingende Programmierung . Die wichtigsten Unterschiede ergeben sich aus der Tatsache, dass die funktionale Programmierung Seiteneffekte vermeidet, die bei der imperativen Programmierung verwendet werden, um Zustand und E/A zu implementieren. Rein funktionale Programmierung verbietet Nebenwirkungen vollständig. Das Verbieten von Nebeneffekten sorgt für referenzielle Transparenz, die es einfacher macht, Programme zu verifizieren, zu optimieren und zu parallelisieren und automatisierte Tools zu schreiben, um diese Aufgaben auszuführen.

Funktionen höherer Ordnung werden in der älteren imperativen Programmierung selten verwendet. Wo ein traditionelles imperatives Programm eine Schleife verwenden könnte, um eine Liste zu durchlaufen, würde ein funktionaler Stil oft eine Funktion höherer Ordnung verwenden, map, die als Argument eine Funktion und eine Liste nimmt, die Funktion auf jedes Element der Liste anwendet und zurückkehrt eine Ergebnisliste.

Zustand simulieren

Es gibt Aufgaben – zum Beispiel die Führung eines Kontostands – die oft am natürlichsten mit dem Staat umgesetzt zu werden scheinen. Die reine funktionale Programmierung führt diese Aufgaben und E/A-Aufgaben wie das Akzeptieren von Benutzereingaben und das Drucken auf dem Bildschirm auf andere Weise aus.

Die reine funktionale Programmiersprache Haskell implementiert sie mit Hilfe von Monaden, abgeleitet aus der Kategorientheorie der Mathematik. Monaden sind extrem leistungsfähig und bieten eine intuitive Möglichkeit, den Zustand (und andere Nebeneffekte wie IO) auf zwingende Weise zu modellieren, ohne die Reinheit zu verlieren. Während vorhandene Monaden einfach zu verwenden sind, finden es viele schwierig zu verstehen, wie neue Monaden definiert werden (was manchmal für bestimmte Arten von Bibliotheken erforderlich ist).

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

Effizienzprobleme

Funktionale Programmiersprachen haben eine automatische Speicherverwaltung mit Garbage Collection, im Gegensatz zu älteren imperativen Sprachen wie C und Pascal, die eine explizite Speicherverwaltung verwenden. Funktionale Programmiersprachen wurden als weniger effizient in ihrer Nutzung von CPU und Speicher als diese Sprachen wahrgenommen. Viele moderne imperative Sprachen wie Java, Perl, Python und Ruby führen jedoch auch eine automatische Speicherverwaltung durch.

Funktionale Programmiersprachen sind im Laufe der Jahre effizienter geworden. Für Programme, die intensive numerische Berechnungen durchführen, sind funktionale Sprachen wie OCaml und Clean ähnlich schnell wie C. Für Programme, die mit großen Matrizen und mehrdimensionalen Datenbanken umgehen, wurden Array-Funktionssprachen (wie J und K) im Hinblick auf die Geschwindigkeitsoptimierung entwickelt. Obwohl rein funktionale Sprachen den Ruf haben, langsamer zu sein, ist jeder imperative Algorithmus in diesen Sprachen im schlimmsten Fall mit einer logarithmischen Verlangsamung ausdrückbar. Darüber hinaus kann die Unveränderlichkeit von Daten in vielen Fällen zu einer höheren Ausführungseffizienz führen, da der Compiler Annahmen trifft, die in einer imperativen Sprache unsicher sind.

Codierungsstile

Imperative Programme neigen dazu, die Reihe von Schritten zu betonen, die ein Programm bei der Ausführung einer Aktion unternimmt, während funktionale Programme dazu neigen, die Zusammensetzung und Anordnung von Funktionen zu betonen, oft ohne es explizit anzugeben Schritte . Ein einfaches Beispiel von zwei Lösungen für dasselbe Programmierziel (unter Verwendung derselben Multi-Paradigma-Sprache Python) veranschaulicht dies.

# imperative style
target = []               # create empty list
for item in source_list:  # iterate over each thing in source
    trans1 = G(item)      # transform the item with the G() function
    trans2 = F(trans1)    # second transform with the F() function
    target.append(trans2) # add transformed item to target

Eine funktionale Version fühlt sich anders an:

# functional style
def compose2(F, G):       # FP-oriented languages often have standard compose()
    def C(item):          # here we create utility-function for composition
        return F(G(item))
    return C
target = map(compose2(F,G), source_list)
# More compact examples of the functional paradigm in Python:
target =  map(lambda x: F(G(x)), source_list) # uses a lambda form with map
# or:
target = [F(G(item)) for item in source_list] # a list comprehension

Im Gegensatz zum imperativen Stil, der die Schritte zum Erstellen von target beschreibt, beschreibt der funktionale Stil die mathematische Beziehung zwischen source_list und 45A20E8B5621751283C56E051.323D51E51E56E051.