Was bringen funktionale Programmiersprachen bei der Parallelisierung?

Wenn mam ein etwas aufwendigeres Problem als eine Schleife parallelisieren hat, was bringen dann funktionale Programmiersprachen für einen Vorteil? Wenn ich z.B. eine baumartige Struktur (XML oder ähnliches) parallel parsen will, wo hilft mir da eine funktionale Programmiersprache?

otze

Parser sind im Allgemeinen nicht parallelisierbar. Da können auch funktionale Sprachen nichts ändern. Wenn, dann bringt das höchstens beim branchen was.

Wenn also eine grammatische Regel in EBNF Syntax so lautet:

A:=B|C dann kann die funktionale Sprache den B/C parser parallel laufen lassen. Aber XML ist da noch nicht komplex genug um das wirklich ausnutzen zu können, im Allgemeinen ist ja relativ schnell klar in welchem Ableitungsbaum sich der Parser befindet.

Shade Of Mine

Funktionale Sprachen sind nicht deswegen gut parallelisierbar weil sie funktional sind, sondern weil Funktionen dort idR "pure" sind. Das bedeutet Funktionen haben keine Seiteneffekte und sind nicht von Funktions-externen Resourcen (wie zB einer globalen Variablen) abhaengig..

So eine Funktion ist nun recht leicht parallelisierbar. Das ist natuerlich nicht alles was funktionale Sprachen leichter parallelisierbar macht (zB kein shared state) aber es ist ein essentieller Punkt.

Aber Funktionen die keine Seiteneffekte kann ich doch auch mit imperativen Sprachen schreiben. Was unterscheidet da die Funktionen von funktionale Sprachen?

ipsec

bei funktionalen Sprachen hat der Interpreter die Garantie, dass Funktionen keine Seiteneffekte haben, weswegen er sie automatisch parallelisieren kann. Bei imperativen Sprachen gibt es diese Garantie nicht, also muss man die Parallelisierung manuell machen.

ipsec schrieb:

bei funktionalen Sprachen hat der Interpreter die Garantie, dass Funktionen keine Seiteneffekte haben, weswegen er sie automatisch parallelisieren kann. Bei imperativen Sprachen gibt es diese Garantie nicht, also muss man die Parallelisierung manuell machen.

Das kommt auf die Sprache an, D (imperativ) zum Beispiel hat afair das Schluesselwort "pure", womit die Garantie gegeben ist. Bei funktionalen Sprachen ist die Garantie eben idR implizit, bei imperativen idR explizit (falls ueberhaupt verwirklichbar).

knivil

Ohne Seiteneffekte ist nur ein Aspekt. Es erlaubt Datenparallelitaet a la mapReduce von google. Die andere Seite ist Taskparallelitaet. Mittels (Software) Transactional Memory kann die Synchronisation stark vereinfacht werden. Die Implementation in Haskell skaliert sehr gut mit der Anzahl der Kerne. Auch bietet Haskell insgesamt gute high level Ansaetze fuer Parallelisierung. Das Hauptproblem ist, dass die meisten imperativen Sprachen rein sequentiell orientiert sind.

Ansonsten: Liess einfach die Paper. Hier eine Auswahl: http://donsbot.wordpress.com/2009/09/03/parallel-programming-in-haskell-a-reading-list/

ipsec schrieb:

bei funktionalen Sprachen hat der Interpreter die Garantie, dass Funktionen keine Seiteneffekte haben, weswegen er sie automatisch parallelisieren kann. Bei imperativen Sprachen gibt es diese Garantie nicht, also muss man die Parallelisierung manuell machen.

Muss der Programmierer dafür sorgen, dass die Funktionen keine Seiteneffekte haben oder geht das bei funktionalen Sprachen garnicht anders? Wie würde man z.B. eine Liste parallel sortieren? Sobald ich da ein Element wo anders einhänge hat das ja einen Effekt auf einen anderen Thread der auch an der anderen Stelle arbeiten könnte.

knivil

Haskell trennt ueber das Typsystem "reine" von "unreinem" Funktionen. Es geht also nicht anders. Zur Datenparalleliteat, Suchen und Sortieren gibt es hier etwas und die Folien sind hier.

Sobald ich da ein Element wo anders ..

Vergiss einfach alles, was du bisher weisst. Es funktioniert anders.

Shade Of Mine

Soetwas wie automatische Parallelisierung gibt es nicht.
Funktionale Sprachen erleichtern nur das parallelisieren, aber magie ist da keine dabei.

Du musst schon selber die Liste ein Teile zerlegen und diese Teile koennen dann parallel sortiert werden. Wenn du dir aber mal zB mergesort oder quicksort ansiehst, wirst du sehr schnell erkennen wie man hier recht einfach parallelisieren kann.

knivil

Soetwas wie automatische Parallelisierung gibt es nicht. Funktionale Sprachen erleichtern nur das parallelisieren, aber magie ist da keine dabei.

Fuer mich grenzt die Einfachheit von

a `par` b

schon an Magie.

Also muss man sich genauso wie bei jeder anderen Sprache Algorithmen ausdenken die parallel ausgeführt werden können. Mergesort ist ja praktisch das was raus kommt, wenn man Bubblesort parallelisiert und die Daten auf mehrere Threads aufteilt und darum lässt es sich dann so einfach parallelisieren. Sieht für mich überhaupt nicht anders aus als alles was ich bisher kenne, nur die Schreibweise ist anders.

knivil

Also muss man sich genauso wie bei jeder anderen Sprache Algorithmen ausdenken die parallel ausgeführt werden können.

Ja, aber es ist schwieriger fuer sequentiell orientierte Sprachen, als fuer parallel/funktional orientierte Sprachen.

Mergesort ist ja praktisch das was raus kommt, wenn man Bubblesort parallelisiert

Nein, das sehe ich nicht so.

Sieht für mich überhaupt nicht anders aus als alles was ich bisher kenne, nur die Schreibweise ist anders.

Ich habe keine Ahnung, was du bisher kennst. Aber du kannst gerne Parallel-Quicksort in C implementieren und vom Entwicklngsaufwand, Codeumfang, Bugs und Performance mit Implementationen in anderen Sprachen vergleichen.

volkard

knivil schrieb:

Ich habe keine Ahnung, was du bisher kennst. Aber du kannst gerne Parallel-Quicksort in C implementieren und vom Entwicklngsaufwand, Codeumfang, Bugs und Performance mit Implementationen in anderen Sprachen vergleichen.

Achtung, gleich sind wir wieder dabei, Ökosysteme zu vergleichen und zu schauen, ob die IDE "Refactoring" im Menu hat.

Shade Of Mine

backdoorman schrieb:

Also muss man sich genauso wie bei jeder anderen Sprache Algorithmen ausdenken die parallel ausgeführt werden können.

Was hast du denn gedacht? Dass du funktional alle Probleme der Welt automatisch geloest bekommst?

Die Arbeit ist immer beim Programmierer - Tools helfen dir dabei und machen die Arbeit leichter. Aber am Ende des Tages zaehlt der Programmierer, nicht die Sprache.

knivil

volkard schrieb:

Achtung, gleich sind wir wieder dabei, Ökosysteme zu vergleichen und zu schauen, ob die IDE "Refactoring" im Menu hat.

Das stimmt, da vieles als Bibliothek implementiert werden kann. Aber ich wehre mich gegen die Aussage, alles sei Einheitsbrei. Es gibt gravierende Unterschiede.

Shade Of Mine schrieb:

backdoorman schrieb:

Also muss man sich genauso wie bei jeder anderen Sprache Algorithmen ausdenken die parallel ausgeführt werden können.

Was hast du denn gedacht? Dass du funktional alle Probleme der Welt automatisch geloest bekommst?

Wenn man Leute wie knivil so hört, könnte man schon meinen, das man mit funktionalen Programmiersprachen alles ganz einfach parallelisieren kann, aber geglaubt hab ich es nicht.

knivil

Was meinst du denn mit einfach? Vergleicht man die parallele Implementation von Quicksort in Haskell mit der sequentiellen in Haskell, so fallen recht wenig Unterschiede auf. Unteranderem entfaellt der Code fuer Erzeugen von Threads, Verteilen der Daten, etc. Der Aufwand verringert sich, die Implementation ist einfach. Wenn du aber mit einfach meinst, dir keine Gedanken mehr machen zu muessen, dann muss ich dich enttaeuschen.

Es ging nie um Sprachfeatures die einem beim Erzeugen von Threads usw. helfen.

knivil

backdoorman schrieb:

Es ging nie um Sprachfeatures die einem beim Erzeugen von Threads usw. helfen.

Es wurden Links zu allen Aspekten der parallelen Programmierung gegeben. Und ja, es ist einfacher dank rein funktional.

Wenn man Leute wie knivil so hört .. alles ganz einfach .. geglaubt hab ich es nicht.

Wenn man keine Ahnung vom Problem hat, ist es egal, welches Werkzeug man benutzt. Und wenn man keine Ahnung vom Werkzeug hat, hilft es einem wohl auch nicht viel. Wieviel Erfahrung hast du denn mit paralleler Algorithmen oder funktionalen Sprachen?