Java in C++ programmieren - Programmier- und Designunterschiede

[aha]

Schreiben sie eine Anwendung welche den Anwender nach der i-ten Fibonacci-Zahl fragt, berechnen sie diese und geben sie diese anschließend aus.

Wie mache ich das mit deiner Methode?

[ghorst]

schlagen sie einen nagel in die wand.
wie machen sie das, wenn sie nur einen schraubendreher habe?
ich besorge mir ein passendes werkzeug.

die funktionale programmierung in c++ ist nicht für benutzerinteraktion ausgelegt...

[Prokkrammierer]

@Shade, der naive Ansatz mit fib(n)=fib(n-1)+fib(n-2) versagt aber bereits bei 100mio bei 1,5Ghz und 768MB Ram (wird heftig geswappt, habe nach 3min abgebrochen).

Mit .filmors Variante (die aus der dynamischen Programmierung) versuche ich gerade mal 1mrd, aber dauert auch seine Zeit, aber die Speicherverbrauch steigt nur sehr sehr langsam an).

[.filmor]

@aha: Wow, herzlichen Glückwunsch, du hast festgestellt, dass das statisch ist? Ich werd bekloppt. Dafür hätte auch ein Posting gereicht. Aber bitte, hier eine Lösung deiner Aufgabe:

#!/bin/sh
VAL=$1
OUT=`mktemp -d -q`
cat > $OUT/src.cpp << __EOF__
#include <cstdio>
template<unsigned I> struct Fibonacci
{
    static const unsigned value = Fibonacci<I-1>::value + Fibonacci<I-2>::value;
};
template<> struct Fibonacci<1> { static const unsigned value = 1; }; 
template<> struct Fibonacci<0> { static const unsigned value = 1; }; 
int main() { std::printf ("%i\n", Fibonacci<$VAL>::value); }
__EOF__
pushd $OUT > /dev/null
g++ src.cpp 2>&1 > /dev/null
./a.out
popd > /dev/null
rm -rf $OUT

@Prokkrammierer Dynamische Programmierung?! Das ist ein ziemlich häufiges Muster in der funktionalen Programmierung…

[humm]

Als ursprünglicher C#ler hat sich bei mir die OOP auch stark eingeprägt und ich will nicht abstreiten, dass ich ein wenig C#/Java in C++ programmiere.
Zur OOP findet man auch viele Unterlagen, welche die Argumente und die Grundlagen erklären(Datenkapselung, Polymorphie etc.).
Gibt es solche Texte auch zur funktionalen Programmierung, wo?(ja ich habe bereits bei google gesucht, finde aber eher Definitionen, gedruckte Bücher und Vorlesungstermine).
Vl auch ein direkter Vergleich zu OOP, Vor- und Nachteile gegenüber OOP, wann man es einsetzen sollte und das ganze auf einer modernen Ebene(ich nehme an funktionale Programmierung gibt es schon länger als das Problem der paralellen Prozesse?)

[timesinmylife]

Shade Of Mine schrieb:

Prokkrammierer schrieb:

Wo du gerade Fibonacci-Zahlen ansprichst, hier verwendet man normalerweise ja dynamisches Programmieren um einen effizienten Algorithmus zu implementieren.

Wie würde man die Fibonacci-Zahl(en) in einer funktionalen Sprache berechnen?

das ist das tolle:

let fib 1 = 1
let fib 0 = 1
let fib n = fib(n-1) + fib(n-2);;

und das war es. denn fib(7) liefert immer das selbe ergebnis. man hat somit automatisch memoization als optimierung. und je nachdem wie gut die compiler optimieren kann ein fib(100) bereits zur compiletime gelöst werden. denn eine pure funktion liefert für den selben eingabwert immer den selben ausgabewert und hat keine seiteneffekte.

das interessante dabei:

let x=fib(100)
let y=fib(200)

das kann parallelisiert werden und auf einen gemeinsamen cache zurück greifen so dass fib(7) nur _einmal_ berechnet werden muss. die frage in wie weit das in der praxis umgesetzt ist, ist natürlich etwas anderes. aber pure funktionen bieten dir genau diese möglichkeit. (unabhängig von funktionaler programmierung oder nicht. es sind die pure funktionen die so wertvoll sind, nicht das funktionale paradigma)

Irgendwas vorher schon mal berechnen oder cachen hat aber nicht wirklich viel mit rekursive Algorithmen parallelisieren zu tun, dass ist nur ein spezialfall. Wenn du einen rekursiven Algo. hast, der für den nächsten Schritt etwas braucht, was du im ersten ermittelst, dann kannst du die rekursion nicht wirklich parallelisieren.

[hustbaer]

unabhängig von funktionaler programmierung oder nicht. es sind die pure funktionen die so wertvoll sind, nicht das funktionale paradigma

ACK
Man müsste mal fein C++ mit funktional verheiraten. Bzw. eben um "pure" Funktionen erweitern. Und gleich noch um "pure value types" zusätzlich - spricht ja nix dagegen dass eine "pure" Funktion einen "pure UDT" als Ergebnis hat.

[.filmor]

hustbaer schrieb:

unabhängig von funktionaler programmierung oder nicht. es sind die pure funktionen die so wertvoll sind, nicht das funktionale paradigma

ACK
Man müsste mal fein C++ mit funktional verheiraten. Bzw. eben um "pure" Funktionen erweitern. Und gleich noch um "pure value types" zusätzlich - spricht ja nix dagegen dass eine "pure" Funktion einen "pure UDT" als Ergebnis hat.

Aber wie will man das machen? Hat ja schon seine Gründe, dass constexpr-Funktionen (das ist ja ziemlich genau das) nur genau ein vergleichsweise trivialer Ausdruck sein dürfen.

[rüdiger]

!!! schrieb:

Ich dachte das ursprüngliche Konzept von C++ war, moderne Dinge wie OOP nach C zu bringen. Das C++ mehr als C mit Klassen ist, heißt nicht, dass C++ nicht OOP sein sollte.
C++ ist doch eben Multiparadigmisch, sodass jeder so programmieren kann, wie er es als am sinnvollsten betrachtet und das ist für mich der Kerngedanke vom modernen C++ und nicht, dass auf einmal alles so aufgebaut ist wie die funktionalgenerische Standardbibliothek.

Das man in C++ nicht so streng OOP programmiert wie in Java, ist klar, aber der funktionale Ansatz ist meines Erachtens veraltet und ein Schritt in die falsche Richtung(C++ funktional programmieren und C OOP scheint ja ein Trend zu sein).
Ebenso ist die Templatemetaprogrammierung Schwachsinnig, solche Optimierung braucht kein Mensch, wenn dadurch das Programm derart unleserlich wird.
Um auf deine Aussage zurückzukommen, effektiv ist anders.

Warum sollte funktionale Programmierung veraltet sein? Gerade im C++-Bereich (und in ähnlichen Programmiersprachen) werden doch funktionale Ansätze immer stärker gepflegt, während man von den fetten Klassenhierachien weg ist. Sicher programmiert man in C++ noch OO. Aber nicht ausschließlich und man verzichtet eben möglichst auf die klassischen OOP-Fehler, wie große Klassenhierachien uä.

Das funktionale Programmierung wieder "in" ist und als gut angesehen wird, sieht man ja daran, dass diese Programmierweise in C++ gestärkt wird im kommenden Standard und auch in anderen Programmiersprachen wie C# die Fähigkeiten in die Richtung verbessert wurden.

Templatemetaprogrammierung ist nur Schwachsinn, wenn man nicht über seinen Tellerrand hinaus schauen will. Ich arbeite zum Beispiel für eine Firma, die im Scientificcomputing Bereich stark auf Templatemetaprogrammierung und die Hybridtechniken setzt, weil man so einerseits eine schönere API anbieten kann (eben sehr nahe an den mathematischen Problemen) und andererseits sehr guten und optimierten Code bekommt.
(Andererseits ist Templatemetaprogrammierung auch nicht die ultimative Lösung).

[Christoph]

Shade Of Mine schrieb:

Prokkrammierer schrieb:

Wie würde man die Fibonacci-Zahl(en) in einer funktionalen Sprache berechnen?

das ist das tolle:

let fib 1 = 1
let fib 0 = 1
let fib n = fib(n-1) + fib(n-2);;

und das war es. denn fib(7) liefert immer das selbe ergebnis. man hat somit automatisch memoization als optimierung.

Mit derzeitigen Haskell-Compilern hat man hier (soweit ich weiß) leider keine memoization for free. AFAIK liegt da auch aus theoretischer Sicht ein gewisses Problem vor: Memoization gibt nur Sinn, wenn der Cache die richtige Struktur hat, er soll also im Kontext des gesamten Programms zu keinem Performance-Verlust führen. Bei allgemeineren Funktionen als fib hat man auch schnell nicht-sequenziellen Zugriff, wodurch man entweder eine Such-Struktur braucht oder ein sehr großes Array, bei dem fast alle Einträge ungenutzt bleiben. Wie die Parameter-Bereiche einer Funktion aussehen, kann der Compiler im allgemeinen aber unmöglich entscheiden, deshalb implementiert er bei Funktionen bisher gar keine memoization.

Schreibt man die Funktion aber um, bekommt man memoization:
let fibs = 1 : 1 : zipWith (+) fibs (tail fibs)
let fib n = fibs !! n
Hier ist fibs eine Liste der Fibonacci-Zahlen, und Listen sind Konstanten und keine Funktionen, deswegen werden diese gecached. Man muss dem Compiler praktisch die gewünschte Cache-Struktur explizit mitteilen.

Compiler können heute viel Arbeit übernehmen, aber die Wahl der entscheidenden Algorithmen, z.B. die Wahl einer passenden Cache-Struktur oder passender Parallelisierungs-Strategien, bleibt in den meisten Fällen noch am Programmierer hängen.

[is klar]

.filmor schrieb:

is klar schrieb:

Es gibt ne Menge Anwendungen, die verteilen nicht nur auf die Cores eines PCs, sondern sogar noch auf mehrere PCs. Und das geht auch mit ganz normaler OOP, wenn man Aufgaben hat die man gut verteilen kann. Da braucht man kein parallel.for.

Sowas geht meines Erachtens wenn überhaupt nur mit einem Objektmodell, wie Objective C es benutzt halbwegs problemlos.

Warum sträubst du dich so gegen funktionale Programmierung? Die ist wirklich unfassbar elegant (bis auf E/A-Operationen, wie hustbaer schon sagte) und die Programme sehr gut parallelisierbar (/ohne/ fehleranfälliges Zutun des Programmierers). Schau dir einfach mal Erlang an.

Was hier immer in Aussagen rein interpretiert wird. Ich hab garnichts gegen funktionale Programmierung, aber man braucht sie nicht um zu parallelisieren. Parallelisierbarkeit hat einfach garnichts mit irgendwelchen Sprachen, Objektmodellen oder Paradigmen zu tun. Und es wurde auch schon Parallelisiert, vor es Multi Core PCs für den Heimanwender gab und auch oft um andere Hardwarebeschränkungen als die CPU zu umgehen und bei sowas bringt ein simples parallel.for garnichts.

[.filmor]

Naja, schon. Wie Shade glaub ich vorher schon sagte sind geteilte Daten das größte Übel in der parallelen Programmierung. Sowas gibt's aber in rein funktionalen Programmen schlichtweg nicht, nicht mal in den kleinsten Einheiten des Programmes.
Genauso ist das Objektmodell in C++ meines Erachtens relativ ungeeignet, weil du es quasi permanent mit geteilten Daten (den Objekten) zu tun hast und du tatsächlich auf diesen operierst (da Methoden einen this-Zeiger nehmen und nur normale Prozeduren sind). Im Objective-C-Modell reicht es vielleicht eine Warteschlange für die Nachrichten an ein Objekt einzurichten, damit ist das Problem denk' ich erledigt.

Du bist nicht !!!? Dann zieh' ich das mit dem sträuben zurück.

[hustbaer]

.filmor schrieb:

hustbaer schrieb:

unabhängig von funktionaler programmierung oder nicht. es sind die pure funktionen die so wertvoll sind, nicht das funktionale paradigma

ACK
Man müsste mal fein C++ mit funktional verheiraten. Bzw. eben um "pure" Funktionen erweitern. Und gleich noch um "pure value types" zusätzlich - spricht ja nix dagegen dass eine "pure" Funktion einen "pure UDT" als Ergebnis hat.

Aber wie will man das machen? Hat ja schon seine Gründe, dass constexpr-Funktionen (das ist ja ziemlich genau das) nur genau ein vergleichsweise trivialer Ausdruck sein dürfen.

Und welche Gründe wären das?
Mir fällt auf jeden Fall nix ein was es verhindern würde da mehr zu erlauben.
Natürlich würden die Compiler entsprechend komplizierter, aber ... das ist mir ja egal so lange ich so einen Compiler nicht schreiben muss

[.filmor]

Naja, wie willst du Wirkungen im Programm verhindern, wenn beliebige Ausdrücke zugelassen werden? Alles mit Zeigern ist schonmal tabu, Objekte erstellen könnte auch kompliziert werden (eben weil da vermutlich irgendwo in den Untiefen des Codes Zeiger verwendet werden, was man aber nur herausfinden kann, wenn man den gesamten Code sieht). Entsprechendes gilt für andere Funktionen.
Dann ist natürlich static auch noch nicht möglich und dann bist du schon so weit, dass du eigentlich alles in einen Ausdruck schreiben könntest. Nur Schleifen (bzw. Rekursionen) gingen noch, aber dann sind wir denke ich schon beim Halteproblem. Ich will schon, dass mein Compiler terminiert

/edit: Hmm, wobei, while-Schleifen sind eh sinnlos und bei for-Schleifen könnte man verbieten, die Laufvariable innerhalb der Schleife zu ändern. Endlosrekursionen abzufangen ist auch möglich. Da geht schon noch was

[Erlang-Progger]

.filmor schrieb:

Naja, wie willst du Wirkungen im Programm verhindern, wenn beliebige Ausdrücke zugelassen werden? Alles mit Zeigern ist schonmal tabu, Objekte erstellen könnte auch kompliziert werden (eben weil da vermutlich irgendwo in den Untiefen des Codes Zeiger verwendet werden, was man aber nur herausfinden kann, wenn man den gesamten Code sieht). Entsprechendes gilt für andere Funktionen.
Dann ist natürlich static auch noch nicht möglich und dann bist du schon so weit, dass du eigentlich alles in einen Ausdruck schreiben könntest. Nur Schleifen (bzw. Rekursionen) gingen noch, aber dann sind wir denke ich schon beim Halteproblem. Ich will schon, dass mein Compiler terminiert

/edit: Hmm, wobei, while-Schleifen sind eh sinnlos und bei for-Schleifen könnte man verbieten, die Laufvariable innerhalb der Schleife zu ändern. Endlosrekursionen abzufangen ist auch möglich. Da geht schon noch was

Schaut euch doch mal das Buch "Programming Erlang" an, da wird auch genau diese Problematik angesprochen (in den ersten 1 oder 2 Kapitel) und auch immer mal wieder darauf hingewiesen, wenn man an bestimmten Stellen nur auf Built-in Funktionen zugreifen darf um eben genau das garantieren zu können.

[Christoph]

.filmor schrieb:

Endlosrekursionen abzufangen ist auch möglich. Da geht schon noch was

Endlosrekursion abfangen geht im allgemeinen nicht. Normalerweise setzt man einfach ein Limit auf die maximale Rekursionstiefe, aber damit unterbindet man eben auch korrekte, aber sehr tiefe, Rekursion.

Dass der Compiler nicht immer in akzeptabler Zeit terminiert, ist heute auch schon der Fall bei template meta programming: Das ist turing-complete, im Extremfall (manche Limits außen vor gelassen) ist die Frage, ob ein gegebener C++-Quellcode fehlerhaft ist, also äquivalent zum Halteproblem.

[.filmor]

Christoph schrieb:

.filmor schrieb:

Endlosrekursionen abzufangen ist auch möglich. Da geht schon noch was

Endlosrekursion abfangen geht im allgemeinen nicht. Normalerweise setzt man einfach ein Limit auf die maximale Rekursionstiefe, aber damit unterbindet man eben auch korrekte, aber sehr tiefe, Rekursion.

Okay, im Allgemeinen kann man es vielleicht nicht abfangen. Aber Rekursionstiefe könnte man auch per Compilerschalter modifizierbar machen (wie es auch heutezutage bei Templates ist).

[hustbaer]

@.filmor:
Dass C++ templates bereits turing complete sind wurde ja schon erwähnt, d.h. hier ändert sich nix.

Das Thema ist sicherlich nicht trivial, aber ich bin überzeugt davon dass es möglich wäre da *wesentlich* mehr zu machen als im neuen Standard vorgesehen ist.

[.filmor]

Naja, Templates sind aber von sich aus wirkungsfrei (hab mir mal die Freiheit genommen, side effect halbwegs sinnvoll zu übersetzen ;)), normaler C++-Code nicht. Um Turingvollständigkeit geht's ja eigentlich gar nicht, das hab ich vorhin etwas vermischt. (Wobei es natürlich trotzdem ganz angenehm ist, einen deterministischen Compiler zu haben ;))

[*john 0]

.filmor schrieb:

Sowas gibt's aber in rein funktionalen Programmen schlichtweg nicht, nicht mal in den kleinsten Einheiten des Programmes.

Das ist nicht zutreffend. Das IO-Problem funktionaler Programmierung ist genau das Shared Data Problem aus anderen Programmiersprachen. Ohne Shared Data kommt man nun einmal nicht aus.