Wo das lambda herkommt

Beim letzten Mal hatten wir uns schon über Funktionen als die Objekte der Funktionalen Programmierung unterhalten. Heute soll es darum gehen, warum Funktionen tatsächlich so cool sind.

My god, it’s full of functions

Vielleicht habt ihr schon einmal vom Lambda-Kalkül gehört. Historisch war das der Versuch alles aus Funktionen aufzubauen (also so im Sinne von den Grundlagen der Mathematik und so ..). Heutzutage ist das meistens wichtig, weil man Programmiersprachen gerne mit einer etwas erweiterten Version davon beschreibt – es ist sowas wie die Assemblersprache der theoretischen Informatik 😉

Aber eigentlich will ich mir hier nur die grundlegenden Ideen klauen:

Wir können Datentypen, Bedingungen, ja eine ganze Programmiersprache nur aus Funktionen und der Anwendung von Funktionen aufbauen.

Es gibt nur 10 Booleans

Fangen wir ganz einfach mit den Bool’schen Zuständen wahr und falsch an. Wir müssen diese als Funktionen darstellen und natürlich wollen wir später die üblichen Operatoren wie AND, OR, NOT, .. und natürlich so etwas wie if-Abfragen auf dieser Basis implementieren.

Interessanterweise stellt sich die Darstellung einer Sache im Lambda-Kalkül oft als deren Kern-Idee heraus (Begriff zum Angeben: Catamorphism). Bei Listen (später) wäre das zum Beispiel fold und bei den Boolschen Werten ist es die IF-Anweisung.

Wir implementieren also True und False als IF????

Naja so ähnlich – wir implementieren True als den Teil der IF-Anweisung, der Eintritt, wenn die Bedingung wahr ist und False sozusagen als den ELSE-Zweig.

In C# würde das so aussehen (ich will hier ja niemand mit dem formalen Kalkül vertreiben ;)):

static A True<A,B>(A t, B f)
{
    return t;
}

static B False<A,B>(A t, B f)
{
    return f;
}

(merkt ihr schon wie hässlich das wird?)

Die IF-Anweisung würde dann übrigens einfach so aussehen:

static A If<A>(Func<A, A, A> bed, A th, A el)
{
    return bed(th, el);
}

Für bed werden wir hier ja entweder True or False übergeben (also eine unserer boolschen Funktionen) – und es geschieht nichts anderes, als dass diese Funktion auf die beiden anderen Argumente angewendet wird – IF ist also im Prinzip nur diese Funktionenauswertung! Deswegen sind die True und False eigentlich schon ihre eigenen IF-Anweisungen (Funktionenauswertungen sind in der FP ja geschenkt).

Das schwierigste am obigen Beispiel ist übrigens die richtigen Typen zu finden! In der Tat wäre diese Einführung hier viel leichter, wenn ich Python, JavaScript oder sonst eine dynamische Sprache nehmen würde!

Das brauchen wir aber glücklicherweise gar nicht – F# schenkt uns die Typen…

Nochmal mit Steroiden …

Vergessen wir also C# und nehmen was Richtiges!
FSharp.org

Eine typische entsprechung von False und True in F# kann so aussehen:

let bTrue t f = t
let bFalse t f = f

Wir verwenden hier let um eine Funktion zu definieren. let ist prinzipiell das Selbe wie var in C#. Mit let werden Werte zu einem Namen gebunden, und weil wir in einer funktionalen Sprache schreiben geht das natürlich auch mit Funktionen (die sind auch nur Werte). Ok, ganz richtig ist das hier nicht – was ich beschrieben habe wäre

let bTrue = fun t f -> t

und ja das geht auch, aber in F# gibt es eben auch die gezeigte Form einer Funktionsdefinition ohne den Lambdaausdruck (fun t f -> ...) und für unseren Fall hier wollen wir das einfach mal als gleich ansehen (natürlich gibt es da kleine Unterschiede/Einschränkungen, aber wir wollen hier ja Laune machen und nicht verderben 😉 )

Jedenfalls definieren wir hier also zwei Funktionen bTrue und bFalse mit jeweils zwei Parametern/Argumenten. Der Body der Funktion ist einfach der Teil nach dem = und ähnlich wie bei Lambda-Ausdrücken in C# ist einfach der letzte Wert die Rückgabe (das return fällt weg) – in dem Fall also entweder der erste oder der zweite Parameter.

Den Typ der Funktionen meldet jetzt F# als 'a -> 'b -> 'a bzw 'a -> 'b -> 'b. Der Backtick (`) steht dabei immer generischen Parametern voran.

Hmm… Curry

Schaut euch nochmal den Typ der beiden Funktionen an – sind die vielen -> nicht etwas seltsam? Stimmt! Ich war nämlich (schon wieder) nicht ganz ehrlich: Die Funktionen haben nicht wirklich zwei Parameter – sie haben nur einen. Dafür geben sie aber auch keinen Wert zurück sondern wieder eine Funktion … uff! Im Typ wird nämlich nach-rechts geklammert:

'a -> 'b -> 'a 
= 'a -> ('b -> 'a)` 

und so haben wir eine Funktion, die ein 'a erwartet und dann eine Funktion zurückgibt, die wiederum ein 'b erwartet und dann ein 'a zurückgibt.

Im Prinzip brauchen wir niemals mehr als einen Parameter für eine Funktion – wir können das immer auf Funktionen zurückführen, die nur einen Parameter erwarten und die dann eine Funktion zurückgeben, die auf die restlichen Parameter wartet (ergänzt euch den Rest rekursiv 😉 ).

Diesen Vorgang bzw. diese Operation nennt man Currying (nach Haskell Curry – ratet mal wo der Name der Programmiersprache herkommt) – was auch nicht so wirklich richtig ist, weil das Prinzip wohl schon eher von Schönfinkel beschrieben wurde, aber lassen wir das.

Eine Funktion so zu schreiben hat viele Vorteile und wir werden hier noch viele sehen – jedenfalls sollte man das einmal gehört haben, Funktionen dieser Form kommen praktisch überall in der FP vor.

In C# müssten wir unsere Funktionen hierfür so umschreiben:

static Func<B, A> True<A,B>(A t)
{
    return _ => t;
}

Ich denke wir sollten das an dieser Stelle lassen – C# wird einfach immer hässlicher ^^

eine kleine Meta-Funktion

Um unsere Experimente jetzt auswerten zu können, nehmen wir gleich noch eine Meta-Funktion dazu (die hat nichts mehr mit unserer Spielerei zu tun, die hilft uns nur Menschlich-interpretierbaren Output zu bekommen):

let eval f = f true false

Damit können wir jetzt boolsche Ausdrücke innerhalb unseres Spielsystems auswerten – zum Beispiel:

> eval bTrue;;
val it : bool = true
> eval bFalse;;
val it : bool = false

UND …

Um UND jetzt entsprechend zu implementieren missbrauchen wir die bekannte Tautologie

A && B = if A then B else False

Wie schon bemerkt ist ja A in gewisser Weise sein eigenes if und damit können wird das so schreiben:

let bAnd a b = a b bFalse

Hier der Beweis das die Funktion so stimmt:

> eval (bAnd bTrue bTrue);;
val it : bool = true
> eval (bAnd bTrue bFalse);;
val it : bool = false
> eval (bAnd bFalse bTrue);;
val it : bool = false
> eval (bAnd bFalse bFalse);;
val it : bool = false

(der Beweis ist offensichtlich einfach die bekannte Wahrheitstabelle für UND 😉 )

Schlussbemerkung

Das war natürlich nur die Spitze des Eisbergs (und eigentlich auch eine maskierte Werbung für F# ;)) – aber ich denke als Appetitanreger soll das hier reichen.

Ihr seid dran!

Wenn ihr Lust habt versucht doch mal schnell ODER, NOT, … zu implementieren und schreibt eure Lösungen in die Kommentare.
Außerdem könnt Ihr euch die Typen der Funktionen (bAnd, …) ansehen (entweder in F#-Interactive eingeben oder in VisualStudio/Monodevelop den Tooltip über der Funktion ansehen) und versuchen euch einen Reim darauf zu machen.

Weiterführende Links

Ich habe zum Lambda-Kalkül hier schon einiges geschrieben – am interessantesten dürften folgende Sachen sein:

Allerdings geht das Typentechnisch etwas tiefer – bei Problemen: Kommentar unten und ich helfe 😉