Funktionale Programmierung und wissenschaftliches Rechnen

Ich entschuldige mich, wenn dies eine vage Frage ist, aber hier geht:

In den letzten Jahren hat die funktionale Programmierung in der Software-Engineering-Community große Beachtung gefunden. Viele haben angefangen, Sprachen wie Scala und Haskell zu verwenden, und behaupteten, Erfolg gegenüber anderen Programmiersprachen und Paradigmen zu haben. Meine Frage ist: Sollten wir als Experten für Hochleistungsrechnen / Wissenschaftliches Rechnen an funktionaler Programmierung interessiert sein? Sollen wir an dieser Mini-Revolution teilnehmen?

Was sind die Vor- und Nachteile der funktionalen Programmierung im Arbeitsbereich von SciComp?

Ich habe nur ein bisschen funktionale Programmierung gemacht, also nimm diese Antwort mit einem Körnchen Salz.

Vorteile:

• Funktionale Programmierung sieht sehr mathematisch aus; Es ist ein schönes Paradigma, um einige mathematische Konzepte auszudrücken
• Es gibt gute Bibliotheken für Dinge wie die formale Überprüfung von Programmen und den Beweis von Theoremen. Es ist also möglich, Programme zu schreiben, die sich auf Programme beziehen - dieser Aspekt ist gut für die Reproduzierbarkeit
• Sie können funktionale Programmierung in Python und C ++ über Lambda-Ausdrücke ausführen. Sie können auch funktionale Programmierung in Julia und Mathematica machen
• Nicht viele Leute benutzen es, also können Sie ein Pionier sein. Ähnlich wie es frühe Anwender von MATLAB, Python, R und jetzt Julia gab, muss es frühe Anwender von funktionaler Programmierung geben, damit es funktioniert

Nachteile:

• Sprachen, die normalerweise als funktionale Programmiersprachen betrachtet werden, wie Haskell, OCaml (und andere ML-Dialekte) und Lisp, gelten im Vergleich zu Sprachen, die für leistungskritisches wissenschaftliches Rechnen verwendet werden, im Allgemeinen als langsam. OCaml ist bestenfalls etwa halb so schnell wie C.
• Diesen Sprachen fehlt die Bibliotheksinfrastruktur im Vergleich zu den in der Computerwissenschaft üblichen Sprachen (Fortran, C, C ++, Python). Wenn Sie eine PDE lösen möchten, ist es viel einfacher, sie in einer Sprache durchzuführen, die in der Computerwissenschaft häufiger verwendet wird als in einer anderen.
• Es gibt nicht so viele Computerwissenschaftler, die funktionale Programmiersprachen verwenden, wie prozedurale Sprachen, was bedeutet, dass Sie nicht viel Hilfe beim Erlernen oder Debuggen dieser Sprache erhalten, und die Leute werden Ihnen wahrscheinlich die Qual der Wahl geben Verwenden Sie es (ob Sie es verdienen oder nicht)
• Der Stil der funktionalen Programmierung unterscheidet sich von dem Stil der prozeduralen Programmierung, der normalerweise in einführenden Informatikkursen und in Kursen vom Typ "MATLAB für Wissenschaftler und Ingenieure" unterrichtet wird

Ich denke, viele der Einwände im Abschnitt "Nachteile" könnten überwunden werden. Wie auf dieser Stack Exchange-Site häufig diskutiert wird, ist die Entwicklerzeit wichtiger als die Ausführungszeit. Selbst wenn funktionale Programmiersprachen langsam sind, wenn leistungskritische Teile an eine schnellere prozedurale Sprache delegiert werden können und wenn Produktivitätssteigerungen durch eine schnelle Anwendungsentwicklung demonstriert werden können, lohnt es sich möglicherweise, sie zu verwenden. An dieser Stelle ist anzumerken, dass in Pure Python, Pure MATLAB und Pure R implementierte Programme erheblich langsamer sind als die Implementierung derselben Programme in C, C ++ oder Fortran. Sprachen wie Python, MATLAB und R sind gerade deshalb beliebt, weil sie Ausführungsgeschwindigkeit gegen Produktivität eintauschen. Python und MATLAB verfügen beide über Funktionen zum Implementieren von Schnittstellen für kompilierten Code in C oder C ++, sodass leistungskritischer Code für eine schnelle Ausführung implementiert werden kann. Die meisten Sprachen haben eine Fremdfunktionsschnittstelle zu C, was ausreichen würde, um mit den meisten Bibliotheken zusammenzuarbeiten, die für Computerwissenschaftler von Interesse sind.

Sollten Sie sich für funktionale Programmierung interessieren?

Das hängt alles davon ab, was du für cool hältst. Wenn Sie die Art von Person sind, die bereit ist, sich gegen Konventionen zu wehren, und bereit sind, den Menschen die Tugenden dessen zu erklären, was Sie mit funktionaler Programmierung erreichen wollen, dann würde ich sagen, machen Sie es . Ich würde gerne Leute sehen, die coole Dinge mit funktionaler Programmierung in der Computerwissenschaft machen, wenn auch aus keinem anderen Grund als um zu beweisen, dass alle Neinsager falsch sind (und es wird eine Menge Neinsager geben). Wenn Sie nicht die Art von Person sind, die sich mit einer Gruppe von Leuten befassen möchte, die Sie fragen: "Warum zum Teufel verwenden Sie eine funktionale Programmiersprache anstelle von (fügen Sie hier ihre bevorzugte prozedurale Programmiersprache ein)?" stört mich nicht

Es wurden einige funktionale Programmiersprachen für simulationsintensives Arbeiten verwendet. Die quantitative Handelsfirma Jane Street verwendet OCaml zur Finanzmodellierung und Umsetzung ihrer Handelsstrategien. OCaml wurde auch in FFTW zum Generieren von in der Bibliothek verwendetem C-Code verwendet. Liszt ist eine in Stanford entwickelte und in Scala implementierte domänenspezifische Sprache, die zum Lösen von PDEs verwendet wird. Funktionale Programmierung wird definitiv in der Industrie verwendet (nicht unbedingt in der Computerwissenschaft); es bleibt abzuwarten, ob es in der rechnerwissenschaft abheben wird.

Ich habe vielleicht eine einzigartige Perspektive, weil ich ein HPC-Praktiker mit einem wissenschaftlichen Berechnungshintergrund und einem Benutzer einer funktionalen Programmiersprache bin. Ich möchte HPC nicht mit wissenschaftlicher Berechnung gleichsetzen, aber es gibt erhebliche Überschneidungen, und das ist der Standpunkt, den ich bei der Beantwortung dieser Frage einnehme.

Derzeit ist es unwahrscheinlich, dass funktionale Sprachen in HPC übernommen werden, vor allem, weil HPC-Benutzer und -Kunden wirklich Wert darauf legen, eine möglichst hohe Leistung zu erzielen. Es ist richtig, dass Code, der funktional geschrieben ist, auf natürliche Weise Parallelität aufweist, die ausgenutzt werden kann, in HPC jedoch nicht ausreicht. Parallelität ist nur ein Teil des Puzzles, um eine hohe Leistung zu erzielen. Sie müssen auch eine Vielzahl von Details der Mikroarchitektur berücksichtigen, und dies erfordert im Allgemeinen eine sehr genaue Kontrolle über die Ausführung von Code. Diese Kontrolle ist in keinem Fall verfügbar funktionale Sprachen, die ich kenne.

Trotzdem habe ich große Hoffnungen, dass sich dies ändern kann. Mir ist der Trend aufgefallen, dass Forscher langsam erkennen, dass viele dieser mikroarchitektonischen Optimierungen (bis zu einem gewissen Grad) automatisiert werden können. Dies hat einen Zoo von Source-to-Source-Compilertechnologie hervorgebracht, in dem ein Benutzer eine "Spezifikation" der gewünschten Berechnung eingibt und der Compiler C- oder Fortran-Code ausgibt, der diese Berechnung mit den für eine effiziente Ausführung erforderlichen Optimierungen und Parallelitäten realisiert Verwenden Sie die Zielarchitektur. Übrigens sind funktionale Sprachen dafür gut geeignet: Modellierung und Analyse von Programmiersprachen. Es ist kein Zufall, dass die ersten großen Anwender von funktionalen Sprachen Compiler-Entwickler waren. Mit ein paar bemerkenswerten Ausnahmen habe ich noch nicht gesehen, dass dies tatsächlich zutrifft, aber die Ideen sind da,

Ich möchte einen Aspekt zu den beiden anderen Antworten hinzufügen. Neben dem Ökosystem bietet die funktionale Programmierung eine großartige Möglichkeit für die parallele Ausführung wie Multithreading oder verteiltes Computing. Seine inhärenten Unveränderlichkeitseigenschaften machen es für Parallelität geeignet, was im Allgemeinen ein echtes Problem darstellt, wenn es um imperative Sprachen geht.

Da sich die Verbesserung der Hardwareleistung in den letzten Jahren darauf konzentriert hat, den Prozessoren Kerne hinzuzufügen, anstatt höhere Frequenzen zu verwenden, wird die parallele Berechnung immer beliebter (ich wette, Sie alle wissen das).

Eine andere Sache, die Geoff erwähnt, ist, dass die Entwicklerzeit oft wichtiger ist als die Ausführungszeit. Ich arbeite für ein Unternehmen, das ein rechenintensives SaaS erstellt, und wir haben zu Beginn einen ersten Leistungstest durchgeführt, bei dem C ++ gegen Java getestet wurde. Wir haben festgestellt, dass C ++ die Ausführungszeit gegenüber Java um ungefähr 50% verkürzt hat (dies war für die Berechnungsgeometrie und die Zahlen werden höchstwahrscheinlich je nach Anwendung variieren), aber wir haben uns trotzdem für Java entschieden, da die Entwicklerzeit wichtig ist, und hofften, dass dies so ist Optimierungen und zukünftige Verbesserungen der Hardwareleistung würden uns helfen, das Produkt auf den Markt zu bringen. Ich kann mit Zuversicht sagen, dass wir, wenn wir uns anders entschieden hätten, nicht mehr im Geschäft wären.

Ok, aber Java ist keine funktionierende Programmiersprache. Was hat es mit irgendetwas zu tun? Später, als wir mehr Befürworter des Funktionsparadigmas beschäftigten und über die Notwendigkeit der Parallelisierung stolperten, haben wir Teile unseres Systems schrittweise auf Scala migriert, das die positiven Aspekte der funktionalen Programmierung mit der Kraft des Imperativs kombiniert und gut mit diesem verschmilzt Java. Es hat uns enorm geholfen, die Leistung unseres Systems mit minimalem Kopfzerbrechen zu steigern, und wird wahrscheinlich weiterhin von weiteren Leistungssteigerungen im Hardware-Geschäft profitieren, wenn mehr Kerne in die Prozessoren von morgen gesteckt werden.

Beachten Sie, dass ich den in den anderen Antworten erwähnten Nachteilen voll und ganz zustimme, aber ich dachte, dass die Erleichterung der parallelen Ausführung ein so starker Vorteil ist, dass er nicht unerwähnt bleiben kann.

Geoff hat bereits einen guten Überblick über die Gründe gegeben, zu denen ich nur einen seiner Punkte hervorheben möchte: das Ökosystem. Unabhängig davon, ob Sie sich für funktionale Programmierung oder ein anderes Paradigma einsetzen, ist eine der wichtigsten Fragen, die Sie beantworten müssen, dass es eine unglaubliche Menge an Software gibt, auf der alle anderen aufbauen können, die Sie neu schreiben müssen. Beispiele sind MPI, PETSc oder Trilinos für lineare Algebra oder eine der Finite-Elemente-Bibliotheken - alle in C oder C ++ geschrieben. Das System weist eine enorme Trägheit auf, vielleicht nicht, weil jeder der Meinung ist, dass C / C ++ die beste Sprache zum Schreiben von Computersoftware ist, sondern weil viele Menschen Jahre ihres Lebens damit verbracht haben, etwas Nützliches zu entwickeln viele Leute.

Ich denke, die meisten Computer-Experten werden zustimmen, dass es sehr wertvoll ist, neue Programmiersprachen auszuprobieren und ihre Eignung für dieses Problem zu bewerten. Aber es wird eine schwierige und einsame Zeit, denn Sie werden nicht in der Lage sein, Ergebnisse zu erzielen, die mit dem konkurrieren, was alle anderen tun. Es kann Ihnen auch einen Ruf als jemand einbringen, der den nächsten Schritt zu einem anderen Programmierparadigma unternommen hat. Hey, es hat nur 15 Jahre gedauert, bis C ++ Fortran ersetzt hat!

Die kurze Zusammenfassung ist das

1. Numerisches Rechnen nutzt Mutabilität / Nebenwirkungen, um die meisten seiner Beschleunigungen zu erzielen und Zuordnungen zu reduzieren (viele funktionale Programmierstrukturen haben unveränderliche Daten).
2. Eine verzögerte Auswertung kann bei numerischen Codes grob sein.
3. Entweder entwickeln Sie ein Paket, bei dem es wirklich darauf ankommt, die Leistung auf die niedrigsten Stufen zu senken (C / Fortran oder jetzt Julia) (in diesem können Sie auch den Assembler-Code nach Bedarf bearbeiten), oder Sie schreiben ein Skript, das diese schnellen Bibliotheken verwendet Sie interessieren sich meistens für die Entwicklungszeit (und wählen daher Julia / MATLAB / Python / R). Funktionale Sprachen tendieren dazu, in einem seltsamen Mittelweg zu sitzen, der in anderen Disziplinen hilfreich ist, aber hier nicht so hilfreich.
4. Die meisten numerischen Algorithmen für Differentialgleichungen, Optimierung, numerische lineare Algebra usw. sind in Bezug auf Konvergenz geschrieben / entwickelt / bewiesen, dh Sie haben die Approximation und möchten . Der natürliche Stil zur Implementierung dieser Algorithmen ist eine Schleife. (Es gibt einige Algorithmen, die rekursiv geschrieben sind, wie einige Multigrid-Algorithmen, aber diese sind viel seltener.)x n + $x_n$$x_{n+1}$

Zusammengenommen machen diese Tatsachen eine funktionale Programmierung für die meisten Benutzer nicht notwendig.

Ich finde es interessant festzustellen, dass der Einsatz von funktionaler Programmierung in der Computerwissenschaft nicht neu ist. In diesem Artikel aus dem Jahr 1990 wurde zum Beispiel gezeigt, wie die Leistung von numerischen Programmen, die in Lisp (möglicherweise der frühesten funktionalen Programmiersprache) geschrieben wurden, durch partielle Evaluierung verbessert werden kann. Diese Arbeit war Teil einer Werkzeugkette, die in einem Artikel von GJ Sussman (von SICP ) und J Wisdom aus dem Jahr 1992 verwendet wurde und numerische Beweise für das chaotische Verhalten des Sonnensystems lieferte . Weitere Details zu der Hardware und Software, die an dieser Berechnung beteiligt sind, finden Sie hier .

R ist eine funktionale Sprache und auch eine Statistiksprache (und jetzt Maschinelles Lernen) und die Sprache Nummer 1 für Statistiken. Es ist jedoch keine HPC-Sprache: Sie wird nicht für herkömmliche "Zahlenkalkulationen" wie Physiksimulationen usw. verwendet. Sie kann jedoch für massive Statistiksimulationen (MCMC) des maschinellen Lernens auf massiven Clustern (z. B. über MPI) ausgeführt werden.

Mathematica ist auch eine funktionale Sprache, aber ihre Kerndomäne ist eher symbolisches als numerisches Rechnen.

In Julia können Sie auch einen funktionalen Stil programmieren (neben dem prozeduralen und dem OO-Stil (Multi-Dispatch)), aber er ist nicht rein (die Basisdatenstrukturen sind alle veränderlich (mit Ausnahme von Tupeln)), obwohl es einige Bibliotheken mit unveränderlichen Eigenschaften gibt Funktionale Datenstrukturen: Noch wichtiger ist, dass sie viel langsamer als der prozedurale Stil sind und daher nicht häufig verwendet werden.

Ich würde Scala nicht als funktionale Sprache bezeichnen, sondern als objektfunktionalen Hybrid. In Scala können Sie viele Funktionskonzepte verwenden. Scala ist wegen Spark ( https://spark.apache.org/ ) wichtig für Cloud Computing .

Beachten Sie, dass das moderne Fortran tatsächlich einige Elemente der funktionalen Programmierung aufweist: Es hat eine strikte Zeigersemantik (im Gegensatz zu C), Sie können reine Funktionen (ohne Nebeneffekte) haben (und als solche markieren) und Sie können Unveränderlichkeit haben. Es verfügt sogar über eine intelligente Indizierung, bei der Sie Bedingungen für Matrixindizes angeben können. Dies ist abfrageähnlich und normalerweise nur in Hochsprachen wie R von LINQ in C # oder über Filterfunktionen höherer Ordnung in funktionalen Sprachen zu finden. Fortran ist also gar nicht so schlecht, es hat sogar einige ziemlich moderne Funktionen (z. B. Co-Arrays), die in vielen Sprachen nicht zu finden sind. Tatsächlich würde ich in zukünftigen Versionen von Fortran eher mehr Funktionsmerkmale als OO-Merkmale (was heute normalerweise der Fall ist) sehen, da OO in Fortran wirklich umständlich und hässlich ist.

Die Profis sind die "Werkzeuge", die in jeder funktionalen Sprache enthalten sind: Es ist so einfach, Daten zu filtern, es ist so einfach, Daten zu durchlaufen und es ist so viel einfacher, eine klare und prägnante Lösung für Ihre Probleme zu finden.

Der einzige Nachteil ist, dass Sie sich mit dieser neuen Art des Denkens auseinandersetzen müssen: Es kann einige Zeit dauern, bis Sie gelernt haben, was Sie wissen müssen. Andere in der SciComp-Domäne verwenden diese Sprachen nicht wirklich, was bedeutet, dass Sie nicht so viel Unterstützung erhalten können :(

Wenn Sie sich für funktional-wissenschaftliche Sprachen interessieren, habe ich eine https://ac1235.github.io entwickelt

Hier sind meine Argumente, warum funktionale Programmierung für die Computerwissenschaft verwendet werden kann und sollte . Die Vorteile sind enorm und die Nachteile verschwinden schnell. In meinen Augen gibt es nur einen Nachteil:

Con : mangelnde Sprachunterstützung in C / C ++ / Fortran

Zumindest in C ++ verschwindet dieser Nachteil - da C ++ 14/17 leistungsstarke Funktionen zur Unterstützung der funktionalen Programmierung hinzugefügt hat. Möglicherweise müssen Sie selbst Bibliotheks- / Support-Code schreiben, aber die Sprache wird Ihr Freund sein. Als Beispiel sehen Sie hier eine (Warnung: Plug-) Bibliothek, die unveränderliche mehrdimensionale Arrays in C ++ ausführt : https://github.com/jzrake/ndarray-v2 .

Hier ist auch ein Link zu einem guten Buch über funktionale Programmierung in C ++, obwohl es nicht auf wissenschaftliche Anwendungen ausgerichtet ist.

Hier ist meine Zusammenfassung dessen, was ich für die Profis halte:

Vorteile :

• Richtigkeit
• Verständlichkeit
• Performance

In Bezug auf die Korrektheit sind Funktionsprogramme offensichtlich gut aufgestellt : Sie zwingen Sie dazu, den minimalen Zustand Ihrer physikalischen Variablen und die Funktion, die diesen Zustand zeitlich vorantreibt, richtig zu definieren:

int main()
{
    auto state = initial_condition();

    while (should_continue(state))
    {
        state = advance(state);
        side_effects(state);
    }
    return 0;
}

Das Lösen einer partiellen Differentialgleichung (oder ODE) ist perfekt für die funktionale Programmierung. Sie wenden lediglich eine pure function ( advance) auf die aktuelle Lösung an, um die nächste zu generieren.

Nach meiner Erfahrung ist Physiksimulationssoftware im Großen und Ganzen durch schlechtes Staatsmanagement belastet . Normalerweise arbeitet jede Stufe des Algorithmus mit einem Teil eines gemeinsam genutzten (effektiv globalen) Zustands. Dies macht es schwierig oder sogar unmöglich, die richtige Reihenfolge der Vorgänge zu gewährleisten, sodass die Software anfällig für Fehler ist, die sich als Seg-Fehler oder schlimmer als Fehlerausdrücke manifestieren können, die Ihren Code nicht zum Absturz bringen, aber die Integrität seiner Wissenschaft stillschweigend gefährden Ausgabe. Der Versuch, den gemeinsam genutzten Status in einer Physiksimulation zu verwalten, verhindert auch das Multithreading. Dies ist ein Problem für die Zukunft, da Supercomputer eine höhere Kernanzahl anstreben und die Skalierung mit MPI häufig bei ~ 100.000 Aufgaben an erster Stelle steht. Im Gegensatz dazu macht die funktionale Programmierung die Parallelität von gemeinsamem Speicher aufgrund der Unveränderlichkeit trivial.

Die Leistung der funktionalen Programmierung wird auch durch die verzögerte Auswertung von Algorithmen verbessert (in C ++ bedeutet dies, dass zur Kompilierungszeit viele Typen generiert werden - oft einer für jede Anwendung einer Funktion). Es reduziert jedoch den Aufwand für Speicherzugriffe und -zuweisungen und eliminiert den virtuellen Versand. Dadurch kann der Compiler einen gesamten Algorithmus optimieren, indem alle Funktionsobjekte, aus denen er besteht, auf einmal angezeigt werden. In der Praxis werden Sie mit verschiedenen Anordnungen der Auswertungspunkte experimentieren (wobei das Algorithmusergebnis in einem Speicherpuffer zwischengespeichert wird), um die Verwendung von CPU- und Speicherzuordnungen zu optimieren. Dies ist aufgrund der hohen Lokalität (siehe das folgende Beispiel) der Algorithmusstufen im Vergleich zu dem, was Sie normalerweise in einem Modul oder klassenbasiertem Code sehen, recht einfach.

Funktionsprogramme sind insofern leichter zu verstehen , als sie den Aggregatzustand trivialisieren. Das heißt nicht, dass ihre Syntax für alle Ihre Kollegen leicht verständlich ist! Autoren sollten darauf achten, gut benannte Funktionen zu verwenden, und Forscher sollten sich im Allgemeinen daran gewöhnen, Algorithmen eher funktional als prozedural auszudrücken. Ich gebe zu, dass das Fehlen von Kontrollstrukturen für einige abschreckend sein kann, aber ich denke nicht, dass dies uns davon abhalten sollte, in die Zukunft zu gehen, um bessere wissenschaftliche Ergebnisse auf Computern zu erzielen.

Unten finden Sie eine Beispielfunktion advance, die mithilfe des ndarray-v2Pakets aus einem Code mit endlichem Volumen angepasst wurde . Beachten Sie die to_sharedOperatoren - dies sind die Bewertungspunkte, auf die ich früher angespielt habe.

auto advance(const solution_state_t& state)
{
    auto dt = determine_time_step_size(state);
    auto du = state.u
    | divide(state.vertices | volume_from_vertices)
    | nd::map(recover_primitive)
    | extrapolate_boundary_on_axis(0)
    | nd::to_shared()
    | compute_intercell_flux(0)
    | nd::to_shared()
    | nd::difference_on_axis(0)
    | nd::multiply(-dt * mara::make_area(1.0));

    return solution_state_t {
        state.time + dt,
        state.iteration + 1,
        state.vertices,
        state.u + du | nd::to_shared() };
}