FP welche Sprache?

Christoph

beginn92 schrieb:

Obwohl, wenn ich im Tut "do ..." und "{ .. ; .. }" sehe, ist das nicht auch wieder imperative/sequenzielle Programmierung, durch die Hintertür eben?

Wenn du es darauf anlegst, kannst du damit in einem imperativen Stil schreiben. Aber der Trick ist, dass man do {} fuer viele Funktionen ueberhaupt nicht braucht. Die do-Notation ist auch nur syntactic sugar fuer die Operatoren, die MrN bereits genannt hat.
Die do-Notation kann sogar verwendet werden um damit Assembler-Code zu schreiben. Fuer Spruenge vorwaerts, also an Labels die erst spaeter definiert werden, muss jedoch die Syntax ein kleines Stueck erweitert werden (ghc hat diese Erweiterung). ("The Monad Reader", Issue 6).

Mr. N schrieb:

.filmor schrieb:

rüdiger schrieb:

.filmor schrieb:

Haskell würd ich nicht nehmen. Das macht ganz ganz komische Sachen, nur weil man etwas Ein- oder Ausgeben will.

Die "komische Sache" nennt sich halt funktionale Programmierung

Nein, sie nennt sich Monade. Und ist einfach unglaublich blöd zu programmieren, wenn in anderen auch recht funktionalen Sprachen ein io:format("blabla_wn", ["bla"]) zur Ausgabe reicht und man mit getline einlesen kann.

Also zum Beispiel 'cat' ist in Haskell leicht zu implementieren:
main = getContents >>= putStr
Wo isn da das Problem?

Monaden koennen schon stoerend sein, wenn man z.B. mit Zufall hantiert und seine Werte immer in eine IO-Monade packen muss.

rüdiger schrieb:

Bashar schrieb:

Oder Scheme.

hat aber ein set! :p

Erlang unterhaelt zu jedem Prozess eine Hashmap. In dieser lassen sich nach Belieben Werte setzen und veraendern, wodurch wir bei der Existenz von set! bei Erlang waeren ;).

hustbaer

Mal eine GANZ doofe Frage bezüglich Funktionaler Programmierung und "Set" (Mutable State): wie verträgt sich das?
Bzw. wie handhaben das die Sprachen bzw. die Compiler/Interpreter?

Der grosse Vorteil von funktionalen Sprachen ist ja, wenn ich das richtig verstehe, dass Funktionen eben keine Seifenblasen machen, äh, Seiteneffekte haben. Das Programm wird dadurch von etwas Dynamischem zu etwas Statischem was nurmehr (mit einem bestimmten Input) "ausgewertet" wird um das Ergebnis zu bestimmen. Grob gesagt.

Ein grosser Vorteil für den Compiler/Interpreter ist doch hier dass er Funktionen beliebig "wegoptimieren" kann, oder die Auswertung "aufschieben" (lazy evaluation) bis der Wert wirklich gebraucht wird (falls er das jemals wird).
Bloss wenn man nun Mutable State einführt "bricht" doch das alles, d.h. wenn der Compiler Funktionen "wegoptimieren" würde die Mutable State angreifen könnte sich ja das Verhalten des Programmes verändern. Genauso wenn die Ausführung "aufgeschoben" wird.

Flaggt der Compiler/Interpreter einfach alle Funktionen die "Mutable State" ändern, bzw. Funktionen aufrufen die "Mutable State" ändern, und stellt dann sicher dass diese an den passenden Stellen noch "ausgeführt" werden, so dass man immer den erwarteten Output bekommt?

Und ist das nicht auch ein Nachteil für den Programmierer, dass Funktionen nun doch Seiteneffekte haben können? Schliesslich ist es für den Programmierer auch nett wenn er sich keine Gedanken über sowas (Seiteneffekte) machen muss. Oder muss man Funktionen die Seiteneffekte haben speziell als solche auszeichnen? Das würde zumindest verhindern dass man denkt man schreibt eine Funktion ohne Seiteneffekte, aber in wirklichkeine eine MIT Seiteneffekten schreibt, indem man andere Funktionen mit Seiteneffekten aufruft.

Oder mache ich hier einen Denkfehler und das alles ist viel einfacher? Oder viel komplizierter?

Christoph

hustbaer schrieb:

Oder mache ich hier einen Denkfehler und das alles ist viel einfacher? Oder viel komplizierter?

Du siehst das schon richtig. Funktionale Sprachen, bei denen man jederzeit ein set! und damit mutable state verwenden kann, sind nicht das, was man unter "rein funktional" versteht. Lisp wird allgemein als funktionale Sprache angesehen, die Funktionen koennen aber beliebige Seiteneffekte haben. Daher kann Lisp nicht das Feature "referentielle Transparenz" bieten, das du in deinem Posting umschrieben hast.
Andere Sprachen wie Haskell oder Clean bieten dieses Feature, allerdings auf Kosten der Seiteneffekte an beliebigen Stellen. In beiden Sprachen muessen Funktionen gekennzeichnet werden, die Seiteneffekte haben. Dieses Kennzeichnen laeuft in Haskell ueber den Rueckgabewert und damit ueber das Typsystem. In Clean ist es AFAIK auch der Rueckgabewert, aber Clean benutzt dafuer eine etwas andere Theorie als Haskell.

In Haskell steht im Rueckgabewert z.B. IO, wenn die Funktion I/O-Operationen macht. Eine Funktion wie das Sieb des Eratosthenes benoetigt (wenn sie effizient sein soll) auch mutable state, allerdings nicht IO im Rueckgabetyp. Hier koennte man sinngemaess "State BoolArray" waehlen. Damit wird zum einen festgelegt, dass diese Funktion mutable state hat, zum anderen wird aber garantiert, dass diese Funktion keine I/O-Operationen macht. Der mutable state, den diese Funktion verwendet, bricht sogar nicht einmal die referentielle Transparenz. Das funktioniert dank der Monaden.

In Lisp ist es mit der Optimierung soweit ich weiss wie in C++: Der Compiler kann Funktionsaufrufe deren Rueckgabewert nicht benoetigt wird nur dann weglassen, wenn er den Code der aufgerufenen Funktion kennt und feststellt, dass dieser seiteneffektfrei ist.

hustbaer

Erstmal danke für die Erklärung!
Aber noch eine Frage: kann man denn in z.B. Haskell oder Clean dem Compiler/Interpreter mitteilen dass z.B. so eine Funktion wie das Sieb des Dingsbums zwar mutable State verwendet, der Aufruf aber trotzdem wegoptimiert werden darf? Und/oder dem Compiler/Interpreter mitteilen dass SiebVomDingsBums(N) immer das gleiche Resultat liefern wird wenn N gleich ist, egal wie oft und wann man es aufruft?

EDIT: oder geht's hier nur um "lokalen" State (das was bei anderen Sprachen halt "Stack Variablen" sind)? Der ist ja unproblematisch, d.h. der kann eine Funktion auch nich nicht-deterministisch machen, da er ja nicht von Aufruf zu Aufruf erhalten bleibt, und auch nie Seiteneffekte verursachen, da er ja lokal ist. -- "Problematisch" sind halt Funktionen die globalen State verwenden... /EDIT

----

Weil du C++ erwähnt hast: ich wünsche mir das schon länger für C++ als Erweiterung, also dass man dem Compiler durch irgendein Keyword sagen kann dass eine Funktion "deterministisch" ist (also das Ergebnis nur vom Input abhängt), und dass sie keine (wichtigen) Seiteneffekte hat.
Weiters wäre es natürlich nett wenn man solche "deterministischen" Funktionen dann auch in Template-Metaprogrammierung verwenden könnte, bzw. der Compiler sie an den passenden Stellen einfach beim Compilieren "ausrechnen" und durch Konstanten ersetzen könnte.

Christoph

hustbaer schrieb:

Erstmal danke für die Erklärung!
Aber noch eine Frage: kann man denn in z.B. Haskell oder Clean dem Compiler/Interpreter mitteilen dass z.B. so eine Funktion wie das Sieb des Dingsbums zwar mutable State verwendet, der Aufruf aber trotzdem wegoptimiert werden darf? Und/oder dem Compiler/Interpreter mitteilen dass SiebVomDingsBums(N) immer das gleiche Resultat liefern wird wenn N gleich ist, egal wie oft und wann man es aufruft?

EDIT: oder geht's hier nur um "lokalen" State (das was bei anderen Sprachen halt "Stack Variablen" sind)? Der ist ja unproblematisch, d.h. der kann eine Funktion auch nich nicht-deterministisch machen, da er ja nicht von Aufruf zu Aufruf erhalten bleibt, und auch nie Seiteneffekte verursachen, da er ja lokal ist. -- "Problematisch" sind halt Funktionen die globalen State verwenden... /EDIT

Ja, beim Sieb geht es um lokalen Status, der nach Funktionsende verschwindet. Will man auf globalen Status zugreifen fuehrt nichts daran vorbei der Funktion "IO irgendwas" als Rueckgabewert zu geben (wobei globaler Status in Haskell zur Zeit eher ein Hack ist).

dann stelle ich mir die ganz prinzipielle Frage:
ist es überhaupt erstrebenswert, zur Programmierung von Computern (funktionale) Sprachen zu verwenden, bei denen zeitabhängige Zustände eigentlich nicht ins Konzept passen und schwierig zu rechtfertigen sind.?

Schließlich besteht eine Turing maschine wesentlich aus dem Bandspeicher zum Speichern des zeitabhängigen globalen zustands, oder?

Um die natürlichen Zahlen, Bäume oder andere zeitunabhängige Strukturen zu beschreiben, mag Haskell ja gut geeignet sein.

Christoph

beginn92 schrieb:

dann stelle ich mir die ganz prinzipielle Frage:
ist es überhaupt erstrebenswert, zur Programmierung von Computern (funktionale) Sprachen zu verwenden, bei denen zeitabhängige Zustände eigentlich nicht ins Konzept passen und schwierig zu rechtfertigen sind.?

Schließlich besteht eine Turing maschine wesentlich aus dem Bandspeicher zum Speichern des zeitabhängigen globalen zustands, oder?

Diese Frage laesst sich IMHO nur durch Praxis beantworten.

Meine Meinung ist, dass diese Entwicklung auf keinen Fall ignoriert werden sollte. Denn die heutigen PCs entfernen sich immer mehr vom einfach sequentiellen Turing-aehnlichen Modell und gehen mehr in die Richtung Parallel-Rechner. Uebliche Sprachen wie C++ sind fuer Multithreading nicht gut geruestet. Wie es Simon Peyton Jones (IIRC) bei einer Praesentation sehr schoen gesagt hat: In der Thread-Synchronisation befinden wir uns immer noch auf Assembler-Ebene.
Er bezog diese Aussage darauf, dass man auch heute im Jahr 2007 noch manuell mit Locks und Semaphores arbeiten muss, und zwar auf einem so niedrigen Level wie Assembler. Seit vielen Jahrzehnten gibt es auf diesem Gebiet keine Innovation, die die inzwischen steinalten Semaphores verdraengt haette.

Hier kommen die rein funktionalen Sprachen ins Spiel. Haskell kann Funktionen auf Typsystem-Level als atomare Bloecke markieren. Mehrere atomare Bloecke lassen sich mit den ueblichen Verkettungs-Operatoren zu einem einzigen verbinden. Das wichtigste ist aber die Semantik: Atomare Bloecke werden entweder ganz oder gar nicht ausgefuehrt. Kein Thread wird jemals einen zur Haelfte ausgefuehrten Block sehen.
Diese Bloecke werden aber parallel ausgefuehrt, wie sie gerade angetroffen werden. Lese-Zugriffe auf shared memory werden voellig ohne Locking ausgefuehrt und protokolliert, die Schreib-Zugriffe werden nur protokolliert. Am Ende eines Blocks werden die geloggten Schreib-Zugriffe in den richtigen Speicher uebernommen. Das ist die einzige Stelle, an der Locking und Sequenzierung stattfinden muss; und diese Stelle liegt in einer fertig implementierten Lib. Damit muss man sich nicht mehr selber mit dieser Art Korrektheitsproblemen herumschlagen.

Die Seiteneffekt-Freiheit von Haskell wird im Falle eines Konflikts benoetigt: Falls am Ende eines atomaren Blocks festgestellt wird, dass es einen Zugriff auf inkonsistente Daten gab, werden die Protokolleintraege einfach verworfen und der ganze atomare Block noch einmal ausgefuehrt. Das ist so einfach moeglich, weil Haskell garantiert, dass der atomare Block ausschliesslich auf shared memory zugreifen kann, aber zum Beispiel keine Datei verarbeiten oder globalen Status veraendern darf. Das Konzept heisst Software Transactional Memory.

Bashar

beginn92 schrieb:

dann stelle ich mir die ganz prinzipielle Frage:
ist es überhaupt erstrebenswert, zur Programmierung von Computern (funktionale) Sprachen zu verwenden, bei denen zeitabhängige Zustände eigentlich nicht ins Konzept passen und schwierig zu rechtfertigen sind.?

"Programmierung von Computern" klingt wie "Programmierung von Videorecordern". Funktionale Programmierung ist in der Tat nicht dazu da, Computer dazu zu bringen, irgendwas bestimmtes zu tun, sondern dazu, die Lösung eines Problems in einer abstrakten Art und Weise zu beschreiben, die zufällig (naja nicht ganz) auch auf Computern ausführbar ist. Das heißt natürlich, dass alles, was tatsächlich eher "Programmierung von Computern" ist, also z.B. Hardwareansteuerung, Systemutilities und dergleichen, in funktionalen Sprachen zwangsläufig einige unnatürliche Elemente enthalten muss. Die Domäne von FP sehe ich eher im Bereich KI, Compiler, automatisches Theorembeweisen, Optimierung usw.

Schließlich besteht eine Turing maschine wesentlich aus dem Bandspeicher zum Speichern des zeitabhängigen globalen zustands, oder?

Das der funktionalen Programmierung unterliegende Berechnungsmodell ist eigentlich nicht die Turingmaschine, sondern der Lambdakalkül.

Christoph schrieb:

Meine Meinung ist, dass diese Entwicklung auf keinen Fall ignoriert werden sollte. Denn die heutigen PCs entfernen sich immer mehr vom einfach sequentiellen Turing-aehnlichen Modell

sehr interessant, das mit der Parallelisierung und dem Stillstand auf dem Gebiet.
Wann schätzt Du denn, daß es soweit ist, dass die vorteile beim Multi threading dazu führen, da0ß eine Sprache wie haskell in den Mainstream durchbricht?

D.h. macht es Sinn, sich jetzt schon so etwas wie Haskell anzutun: ist ja eine Menge Lernarbeit, wie es scheint. oder hat Haskell seinen Zenith schon überschritten, und das "next big thing" ist etwas ganz anderes als funktionale Programmierung?

Helium

Seit vielen Jahrzehnten gibt es auf diesem Gebiet keine Innovation, die die inzwischen steinalten Semaphores verdraengt haette.

Objektorientierung gibt es seit den späten 60ern, wirklich verbreitet hat es sich in den 90ern. Jetzt gerade fangen die Mainstreamsprachen erst Closures aufzunehmen. Der Mainstream hängt in der Entwicklung einfach unheimlich weit zurück. Bis die Highlevel-Threading-Konstrukte in den Mainstream kommen wird noch unheimlich viel Zeit vergehen. Es ist ja nicht so, das entsprechendes nicht schon existieren würde.

---

Mutable State ist erst dann schlecht, wenn das veränderliche Objekt geteilt wird, denn erst dann verursacht es Seiteneffekte.