Funktionale Programmierung: Simulation imperativer Programmierung und IO

Aufgaben
Schleifen	durch Rekursion ersetzen
Zuweisungen	eliminieren und durch Zwischenergebnisse mit let oder where ersetzen
Globale Variablen	zusammenfassen zu einem einzigen Record und als expliziten Parameter oder 2. Resultat durch die Funktionen schleifen

C Fragment
Globaler Zustand	typedef struct { S1 v1; S2 v2; ... Sn vn; } State; State s;
Prozedur	void f0(void) { ... s.vi ...; s.vj = ...; }
Funktion ohne Parameter	T1 f1(void) { ... s.vi ...; s.vj = ...; return e; }
Funktion mit Parameter	T2 f2(T0 x) { ... s.vi ...; s.vj = ...; return e(x); }

Haskell Fragment	Die C Teile systematisch nach Haskell transformiert
Globaler Zustand	data State = S { v1 :: S1 , v2 :: S2 , ... , vn :: Sn }
Prozedur	f0 :: State -> State f0 s0 = let s1 = ... vi s0 ... ... s0 { vj = ... } in s1
oder	zu Vereinheitlichung mit den folgenden Funktionen
	f0 :: State -> ((), State) f0 s0 = let s1 = ... in ((), s1)
Funktion ohne Parameter	f1 :: State -> (T1, State) f1 s0 = let s1 = ... res = ... in (res, s1)
Funktion mit Parameter	f2 :: T0 -> State -> (T2, State) f2 x s0 = let s1 = ... res = ... in (res, s1)

	Die Typen der Funktionen können kürzer formuliert werden
Aktionen	type Action t = State -> (t, State) f0 :: Action () f1 :: Action T1 f2 :: T0 -> Action T2

Eine C Anwendung	void run(void) { fn(...(f2(f1()))); } // oder void run(void) { T1 r1 = f1(); T2 r2 = f2(r1); ...; fn(...); }
transformiert nach Haskell	run :: State -> State run s0 = let (r1, s1) = f1 s0 (r2, s2) = f2 r1 s1 ... (rn, sn) = fn ... sn-1 in sn
	Der Zustand wird durch die Berechnungen hindurch gefädelt

Notwendig	für diese zustandsbehafteten Berechnungen
.1	reine Berechnungen in Aktionen nutzen, zu Aktionen machen
.2	Aktionen sequenziell zusammensetzen: Aktionskomposition
.3	Lesenden und schreibenden Zugriff auf den Zustand: Spezialaktionen

.1	Liften von Werten (Berechnungen) zu Aktionen
gegeben	v :: T v = f x
gesucht	a :: State -> (T, State) a s0 = (v, s0) -- oder a :: Action T
Lösung	return :: t -> (State -> (t, State)) return v = \ s -> (v, s) -- oder return :: t -> Action t return v s = (v, s)
	a = return v

.2	Aktionskomposition
in C	ausprogrammieren
	T1 f1(T0 x1); T2 f2(T1 x2); T2 f(T0 x) { T1 r1 = f1(x); T2 r2 = f2(r1); return r2; }
in Haskell	f1 :: T0 -> Action T1 f2 :: T1 -> Action T2 f :: T0 -> Action T2 f x0 = \s0 -> let (r1, s1) = f1 x0 s0 (r2, s2) = f2 r1 s1 in (r2, s2)
?	Gesucht: Ein Kombinator, der beliebige f1 und f2 zusammensetzt
Vereinfachung	Der Parameter vom Typ T0 spielt für die Kombination keine Rolle
	a1 :: Action T1 f2 :: T1 -> Action T2 a :: Action T2 a = \s0 -> let (r1, s1) = a1 s0 (r2, s2) = (f2 r1) s1 in (r2, s2)
?	Wie sieht ein Kombinator xxx aus, so dass a1 `xxx` f2 == a?
Kombinatorname	bind oder >>=
	(>>=) :: Action t1 -> (t1 -> Action t2) -> Action t2 a1 >>= f2 = \ s0 -> let (r1, s1) = a1 s0 (r2, s2) = (f2 r1) s1 in (r2, s2)
	a = a1 >>= f2

Vereinfachung	von run
	run :: State -> State run s0 = let (r1, s1) = f1 s0 (r2, s2) = f2 r1 s1 ... (rn, sn) = fn ... sn-1 in sn
	run :: State -> State run s0 = let (rn, sn) = a s0 in sn where a = f1 >>= \ r1 -> f2 r1 >>= \ r2 -> ... fn ...
	In der Aktion wird der Zustand nicht mehr explizit benötigt.
	Der Zustand kann also ohne Änderungen in den Aktionen beliebig modifiziert und erweitert werden.

.3	Zugriff auf den Zustand
	getState :: Action State getState = \ s -> (s, s) putState :: State -> Action () putState s = \ olds -> ((), s)
	Andere Zugriffsfunktionen können aus diesen beiden abgeleitet werden.
Variante	Minimale Schnittstelle für Zugriff auf den Zustand
	swapState :: State -> Action State swapState new = \ old -> (old, new) getState = swapState xxx >>= \ old -> swapState old >>= \ new -> return old where xxx = undefined putState new = swapState new >>= \ old -> return ()
	Die Notation mit >>= und λ-Funktionen ist immer noch zu umständlich.

	do-Notation
Beispiel	run :: State -> State run s0 = let (rn, sn) = a s0 in sn where a = do r1 <- f1 r2 <- f2 r1 .... fn ...
Beispiel	getState = do old <- swapState undefined new <- swapState old return old putState new = do old <- swapState new return ()
	Diese Notation ist nur syntaktischer Zucker, sie wird intern in return und >>= transformiert
	Wird der Wert einer Aktion nicht verwendet, so kann der Bezeichner und der Pfeil weggelassen werden.
Beispiel	getState = do old <- swapState undefined swapState old return old putState new = do swapState new return ()

Monade	ist eine mathematische Struktur, in der es die beiden Operatoren return und >>= (bind) gibt. Es müssen allerdings noch ein paar Gesetze erfüllt sein.
	Für sehr viele Strukturen (Maybe, Listen, Zustände, Fehlerbehandlung, ...) sind diese Kombinatoren definierbar und sinnvoll einsetzbar.

Ein- und Ausgabe
Im Beispiel	eine einzige große globale Variable für den Programmzustand.
	Konzeptionell ist diese Transformation für jedes C-Programm möglich.
?	Was sind die in C vordefinierten Größen stdin, stdout, stderr, ...?
?	Was ist konzeptionell der Hauptspeicher in einem Rechner?
?	Was sind konzeptionell die externen Speicher und Geräte?

Weltzustand	data World = ... -- ??? type IO a = World -> (a, World)
	Der Typ IO entspricht genau dem Datentyp Action, nur für den Weltzustand.
	Der Weltzustand ist nie direkt zugreifbar, sondern nur durch eingebaute Systemfunktionen.
	getState und putState sind für World nicht möglich.
	Aber eine Reihe anderer Aktionen, die Teile des Weltzustandes lesen oder verändern.

Hauptprogramm	main :: IO ()
	main ist eine Zustandstransformation des Weltzustands

Ein- und Ausgabe	von einzelnen Zeichen
	getChar :: IO Char putChar :: Char -> IO ()
Ausgabe	einer Zeile
	putStrLn :: String -> IO () putStrLn "" = do putChar '\n' return () putStrLn (x:xs) = do putChar x putStrLn xs
Eingabe	einer Zeile
	getStrLn :: IO String getStrLn = do c <- getChar if c == '\n' then return "" else do s <- getStrLn return (c : s)
	Viele vordefinierte IO Aktionen in den Standardbibliotheken.

	Systementwurf:
?	Welche Systemteile werden rein funktional entwickelt?
?	Wo ist Ein- und Ausgabe notwendig?
?	Wie wird das System so strukturiert, das der Teil mit Ein- und Ausgabe möglichst gering ist?

Simulation imperativer Programmierung und IO

Übersetzung von C nach Haskell