Haskell

knivil

Das kann C++ nicht.

Doch, while (true) {} !

freakC++

was ist daran rekursiv?

SideWinder

freakC++ schrieb:

was ist daran rekursiv?

Ich möchte fast wetten, dass der Haskell-Code in nicht-rekursiven Maschinencode übersetzt wurde. Verwendet ihr ghc oder hugs?

MfG SideWinder

SideWinder schrieb:

freakC++ schrieb:

was ist daran rekursiv?

Ich möchte fast wetten, dass der Haskell-Code in nicht-rekursiven Maschinencode übersetzt wurde. Verwendet ihr ghc oder hugs?

MfG SideWinder

Wieso fast? Wenn tatsächlich rekursiv immer wieder ein Call auftauchen würde, dann gäbe es zu 100% einen Überlauf. Funktionale Programmierung ist schön und gut, aber es verwandelt den Rechner nicht magisch in eine unendlich große Maschine.

otze

Stak schrieb:

Wieso fast? Wenn tatsächlich rekursiv immer wieder ein Call auftauchen würde, dann gäbe es zu 100% einen Überlauf. Funktionale Programmierung ist schön und gut, aber es verwandelt den Rechner nicht magisch in eine unendlich große Maschine.

klar, tail recursion kannste primitiv in ne Schleife umfrickeln. Und sobald du ne Schleife hast, kannst du analysieren ob du wirklich jedes mal Dinge auf den Stack/Heap pushen musst, oder ob du die alten Variablen nicht verwenden kannst.

volkard

freakC++ schrieb:

Wir hatten heute eine rekursive Funktion ohne Abbruchbedingung und ich hatte plötzlich "Stack overflow" im Kopf. Mich hat es schon sehr gewundert, dass das Haskell wenig krazt. Das Programm terminiert zwar nicht, aber es stürzt auch nicht ab! Das kann C++ nicht.

Das ist einfach falsch.
Ich habe im Kopf, daß C++-Compiler das seit Jahren können.
Ich teste das doch mal.

#include <iostream>

void test(){
   std::cout<<"hallo\n";
   test();
}

int main(){
   test();
}

Und der Compiler macht daraus

.L5:
	movl	$6, %edx
	movl	$.LC0, %esi
	movl	$_ZSt4cout, %edi
	call	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	jmp	.L5   # <-- hier, unbedingte Schleife

Oder mal etwas, was nicht ganz so trivial ist:

#include <iostream>

int gcd(int a,int b){
   if(b!=0)
      return gcd(b,a%b);
   else
      return a;
}

int main(){
   std::cout<<gcd(1024,768)<<'\n';
}

wird zu

_Z3gcdii:
.LFB1003:
	.cfi_startproc
	testl	%esi, %esi
	movl	%edi, %eax
	jne	.L5
	jmp	.L8
	.p2align 4,,7
	.p2align 3
.L4:
	movl	%esi, %eax
	movl	%edx, %esi
.L5:
	cltd
	idivl	%esi
	testl	%edx, %edx
	jne	.L4        # <-- Bedinter Sprung nach .L4, eine Schleife!
	movl	%esi, %eax
	ret
.L8:
	rep
	ret
	.cfi_endproc

knivil

Stak schrieb:

Funktionale Programmierung ist schön und gut, aber es verwandelt den Rechner nicht magisch in eine unendlich große Maschine.

Das nicht, es kann aber das Programm verwandeln. Stichwort: Endrekursion. Das kann gcc im uebrigen auch und ich habe es auch hier im Forum oft genug mit Beispielen belegt.

klar, tail recursion kannste primitiv in ne Schleife umfrickeln.

Das hat nichts mit frickeln zu tun und man benoetigt auch keine Schleifen. Es ist ein bestens verstandenes Konzept in Theorie und Praxis. Waehrend volkards Beispiel eine tatsaechliche endrekursive Funktion ist, kann der Kompiler auch in bestimmten Faellen aus einer rekursiven in eine endrekursive verwandeln. Das Beispiel der Fakultaetsfunktion findest hier auch im Forum irgendwo.

maximAL

Stak schrieb:

Wieso fast? Wenn tatsächlich rekursiv immer wieder ein Call auftauchen würde, dann gäbe es zu 100% einen Überlauf. Funktionale Programmierung ist schön und gut, aber es verwandelt den Rechner nicht magisch in eine unendlich große Maschine.

Stichwort: Tail-Rekursion.

edit: nächste Seite übersehen

knivil

Ach uebrigens: Ich mag den Bergiff Tail-Rekursion nicht!

Wenn man Haskel mal für was anderes als Rechnen nimmt, ist es garnicht mehr toll.

otze

knivil schrieb:

klar, tail recursion kannste primitiv in ne Schleife umfrickeln.

Das hat nichts mit frickeln zu tun und man benoetigt auch keine Schleifen. Es ist ein bestens verstandenes Konzept in Theorie und Praxis.

Sogar Volkard schreibt in seinem Kommentar, dass der Compiler daraus ne unbedingte Schleife macht. Keine Ahnung was du mal wieder hast

Zeus

knivil

Du kannst schon vorher analysieren, was alles auf den Heap landet, ohne eine Schleife draus zu machen.

mit welchem switch wandelt g++ tail-recursions nochmal in loops? Bei meinen Tests war kurz vor Tiefe 262000 Schicht im Schacht.

otze

knivil schrieb:

Du kannst schon vorher analysieren, was alles auf den Heap landet, ohne eine Schleife draus zu machen.

Was ändert das an meinem Punkt? Die Schleife brauchste am Ende sowieso, denn solange du die Rekursion hast, musst du dir die Stackframes merken. Und sobald du die stackframes rausoptimierst hast du eine Schleife.
War dein Post also einzig und allein der Tatsache geschuldet, dass man die beiden Dinge vertauschen kann?

!rr!rr_. schrieb:

mit welchem switch wandelt g++ tail-recursions nochmal in loops? Bei meinen Tests war kurz vor Tiefe 262000 Schicht im Schacht.

geklärt, -O1 tut schon

Mal an die ganzen Zweifler: Haskell schlägt C++ haushoch in praktisch jeder Hinsicht außer OOP, und die braucht man in Haskell nicht, und zwar gar nicht. Praktisches Beispiel: Es folgt ein vollwertiger, hochskalierbarer, von Haus aus threading-fähiger, epoll benutzender Echo-Server in Haskell:

module Main where

import Control.Concurrent
import Control.Exception (finally)
import Control.Monad
import Network
import System.IO
import Text.Printf

main :: IO ()
main = do
    -- Logger thread.
    logVar <- newEmptyMVar
    forkIO . forever $ takeMVar logVar >>= hPutStrLn stderr

    -- Echo server.
    socket <- listenOn (PortNumber 4000)
    forever $ do
        (handle, clientHost, clientPort) <- accept socket
        hSetBuffering handle NoBuffering
        putMVar logVar (printf "Connection from %s." clientHost)

        -- Client thread.
        forkIO $ do
            (hGetContents handle >>= hPutStr handle) `finally` hClose handle
            putMVar logVar (printf "Client %s disconnected." clientHost)

Wie bereits erwähnt: Dieser Echo-Server ist thread-fähig, und zwar nicht in dem Sinne, dass jeder Client einen eigenen Thread bekommt, sondern dass beim Programmstart per Kommandozeilenparamter eine feste Anzahl Threads festgelegt werden kann. Innerhalb der Threads wird epoll benutzt. Und ja, der Client-Thread braucht konstanten Speicher, unabhängig davon, wieviel der Client sendet.

Das Gleiche in C++, bitte. Und nein, ich habe keinerlei Netzwerkbibliotheken für Server oder sonstiges verwendet. Das sind alles ganz normale Socket/Handle-Funktionen.

Fairnesshalber möchte ich dazusagen, dass ich ein langjähriger Haskell-Programmierer bin, der viele "real world"-Anwendungen entwickelt. Dazu zählt auch die Erstellung von Server-Software und dynamischen Webseiten in einer Geschwindigkeit, von der C++- (aber auch PHP-) Programmierer nur träumen können.

volkard

ertes schrieb:

dynamischen Webseiten in einer Geschwindigkeit, von der C++- (aber auch PHP-) Programmierer nur träumen können.

Mit PHP und C++ hast Du zwei Enden der Skala genannt. Ich glaube Dir, daß Du in der schnelleren Hälfte bist. Viel mehr aber auch nicht.

volkard schrieb:

ertes schrieb:

dynamischen Webseiten in einer Geschwindigkeit, von der C++- (aber auch PHP-) Programmierer nur träumen können.

Mit PHP und C++ hast Du zwei Enden der Skala genannt. Ich glaube Dir, daß Du in der schnelleren Hälfte bist. Viel mehr aber auch nicht.

hahahahaha

ertes schrieb:

Mal an die ganzen Zweifler: Haskell schlägt C++ haushoch in praktisch jeder Hinsicht außer OOP, und die braucht man in Haskell nicht, und zwar gar nicht. Praktisches Beispiel: Es folgt ein vollwertiger, hochskalierbarer, von Haus aus threading-fähiger, epoll benutzender Echo-Server in Haskell:

module Main where

import Control.Concurrent
import Control.Exception (finally)
import Control.Monad
import Network
import System.IO
import Text.Printf

main :: IO ()
main = do
    -- Logger thread.
    logVar <- newEmptyMVar
    forkIO . forever $ takeMVar logVar >>= hPutStrLn stderr

    -- Echo server.
    socket <- listenOn (PortNumber 4000)
    forever $ do
        (handle, clientHost, clientPort) <- accept socket
        hSetBuffering handle NoBuffering
        putMVar logVar (printf "Connection from %s." clientHost)

        -- Client thread.
        forkIO $ do
            (hGetContents handle >>= hPutStr handle) `finally` hClose handle
            putMVar logVar (printf "Client %s disconnected." clientHost)

Sieht ja fast wie ein normales Programm aus. Wo ist jetzt das Haskel ist so komplett anders und man muss ganz neu lernen?