Currying

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Currying (vor allem in der Linguistik auch Schönfinkeln) ist die Umwandlung einer Funktion mit mehreren Argumenten in eine Funktion mit einem Argument. Obwohl das Verfahren von Moses Schönfinkel[1] erfunden und von Gottlob Frege[2] vorausgedacht wurde, wird es oft nach Haskell Brooks Curry benannt, der das Verfahren letztlich umfangreich theoretisch ausgearbeitet hat.[3]

Verfahren[Bearbeiten | Quelltext bearbeiten]

Es sei eine Funktion gegeben, die n Argumente erfordert. Wird diese auf ein Argument angewendet, so konsumiert sie nur genau dieses und liefert als Funktionswert eine weitere Funktion, die noch n-1 Argumente verlangt. Die zurückgegebene Funktion wird anschließend auf alle weiteren Argumente angewendet.

In Typen ausgedrückt, handelt es sich um die Umrechnung einer Funktion zu einer modifizierten Funktion .[4]

Eine alternative Schreibweise ist , wobei als ein Operator verstanden wird, der n-stellige Abbildungen (für n>1) modifiziert zu einer einstelligen Abbildung, deren Bildwerte einstellige Abbildungen sind, usw., wobei der Reihe nach alle Argumente der ursprünglichen Abbildung durchlaufen werden; formal:

.

Das Konzept des Currying ist verwandt, aber (für n>2) verschieden, von dem der partiellen Anwendung wie etwa:

,
.

Im einstelligen Fall (n=1) hat Currying keine Auswirkung:

,

im zweistelligen Fall (n=2) besteht der Zusammenhang

, d. h. für alle :
,

im dreistelligen Fall (n=3) gilt für :

, und mit zusätzlich :
, d. h. ,

allgemein:

,
.[5]

Im Allgemeinen kommt es häufig vor, dass eine mehrstellige Abbildung nicht für alle Wertekombinationen aus den Trägermengen definiert ist, also nur auf einer Teilmenge des kartesischen Produkts , d. h. auf (dem Graph einer) Relation.[6] Man kann diese Situation behandeln, in dem man entweder grundsätzlich partielle Abbildungen zulässt und die obigen Definitionen formal übernimmt. Hält man dagegen am Konzept totaler Abbildungen fest, werden die Definitionsbereiche der beteiligten Abbildungen von der Wahl bereits festgelegter Parameter abhängig, wie das Beispiel zweistelliger Abbildungen zeigt:

;

der Definitionsbereich dieser Abbildung ist von abhängig:

,

also die Urbildfaser von bezüglich des als Relation aufgefassten Definitionsbereichs .[7]

Da für n=1 gilt , kann für dasselbe Symbol verwendet werden wie für . Man nennt dies Überladung (siehe auch Signatur (Modelltheorie) §Anmerkungen).[8]

Beispiele[Bearbeiten | Quelltext bearbeiten]

Lambda-Notation[Bearbeiten | Quelltext bearbeiten]

Ein Beispiel in Lambda-Notation soll das Verfahren verdeutlichen, wobei die Funktion konkret folgendermaßen definiert sei:

Die Funktion verlangt also 3 Argumente und gibt diese zurück. Die Definition ist äquivalent zu:

Bei der Anwendung der Funktion auf die Argumente a, b und c geschieht Folgendes:

Nach erstmaliger Anwendung der Funktion auf a, b und c wird x im Funktionskörper durch das erste Argument a ersetzt. Das Resultat ist eine Funktion, die noch die Argumente y und z verlangt. Diese wird sofort auf b und c angewendet.

Überladung[Bearbeiten | Quelltext bearbeiten]

Angenommen, wir haben eine zweistellige Multiplikationsfunktion , die zwei ganze Zahlen multipliziert, d. h. einem Paar ganzer Zahlen ihr Produkt zuordnet:

mit  [9]

Per Definition wird diese Funktion auf zwei natürliche Zahlen angewendet und eine natürliche Zahl zurückgegeben, beispielsweise .

Wird nun zunächst das erste Argument besetzt (etwa mit ), das zweite noch freigelassen, entsteht eine einstellige ‚höhere Funktion’, die selbst ein (weiteres) Argument aufnimmt und das Produkt mit diesem festen Parameter (der Nummer ) zurückgibt:

 

und für ein beliebiges festes erstes Argument :

  .

Currying bedeutet nun bei einer n-stelligen Funktion, diesen Vorgang solange durchzuführen, bis nur eine noch einstellige höhere Funktion übrigbleibt. Für n=2 ist daher:

 [10]

Da die Bezeichnung als einstellige Funktion noch unbesetzt ist, kann diese überladen werden,[11] d. h. im einstelligen Fall wird als verstanden:

.

Geometrisches Beispiel[Bearbeiten | Quelltext bearbeiten]

f(x, y) = x^2 + x y + y^2

Man kann sich die Situation für eine Funktion mit zwei Argumenten wie folgt vorstellen: das Fixieren einer Argumentvariable entspricht einer Einschränkung der zweidimensionalen Definitionsmenge auf eine eindimensionale Teilmenge, z. B. , die resultierende Funktion entspricht der Schnittkurve des Graphen von mit der Ebene aller Punkte . Alle Punkte des Graphen können somit auch durch eine zweistufige Auswahl erreicht werden: zunächst durch die Festlegung der Schnittebene und dann durch die Auswertung der Schnittkurve an der Stelle .

Anwendung[Bearbeiten | Quelltext bearbeiten]

Currying wird überwiegend in Programmiersprachen und Kalkülen verwendet, in denen Funktionen nur ein einzelnes Argument erhalten dürfen. Dazu gehören beispielsweise ML, Unlambda und der Lambda-Kalkül sowie das nach Curry benannte Haskell. Viele dieser Sprachen bieten dem Programmierer allerdings syntaktische Möglichkeiten, dies zu verschleiern. Ein Beispiel hierfür ist die Äquivalenz der Funktionsdefinition im oben gezeigten Beispiel.

JavaScript[Bearbeiten | Quelltext bearbeiten]

Das nachfolgende Beispiel zeigt Currying in JavaScript. Zunächst wird eine Funktion addiere definiert, die einerseits als Ergebnis die Summe der beiden Argumente hat, andererseits, wenn sie nur mit einem Argument aufgerufen wird (partielle Anwendung), eine als Closure definierte Funktion zurückgibt.

function addiere(x,y) {
  if (typeof y === "undefined" ) {
    return function (yy) {
      return x + yy;
    }
  }
  return x + y;
}

addiere(2,4); // normaler Aufruf. ergibt 6

var addiere_zu_drei = addiere(3); // Currying
addiere_zu_drei(5);  // ergibt 8

document.write(addiere(2,4) +"<br />")
document.write(addiere_zu_drei(5) +"<br />")

Durch Currying wird die Funktion partiell angewandt, wobei die Funktionsargumente nacheinander übergeben werden und zwischenzeitlich in einer neuen Funktion gehalten werden, die beliebig weiterverwendet werden kann.

Einfacher geht es mit JavaScript ES2015:

const uncurriedAdd = (x, y) => x + y;
const curriedAdd = x => y => x + y;

uncurriedAdd(2, 5); // 7
curriedAdd(2)(5); // 7

C++[Bearbeiten | Quelltext bearbeiten]

C++ 11 führte das Lambda-Kalkül in die Sprache ein, später führte C++ 14 die Möglichkeit ein, einen Rückgabetyp auto zu definieren, um das Schreiben bestimmter Funktionen zu erleichtern. Diese beiden Erweiterungen ermöglichen eine Curryfizierung wie folgt:

#include <iostream>

auto uncurried_add(int a, int b){
    return a + b;
}

auto curried_add(int x){
    return [x](int y){return x + y;};
}

int main(int argc, char *argv[]){
    std::cout << uncurried_add(3, 4) << "\n";
    std::cout << curried_add(3)(4) << "\n";
}

Man beachte, dass seit C++ 17 die Erwähnung des Typs int im Argument des Lambda-Ausdrucks auch durch auto ersetzt werden kann, wodurch die Implementierung verallgemeinert wird (eine implizite Vorlage auf Kosten von der curried_add Methode).

Haskell[Bearbeiten | Quelltext bearbeiten]

Currying ist in Haskell essentiell. Jede Funktion erhält, wie oben erwähnt, nur ein Argument. Werden scheinbar mehrere Argumente definiert, so steckt immer Currying dahinter:

addiere x y = x + y

addiere 1 3 -- ist äquivalent zu (addiere 1) 3

addiereZu2 = addiere 2

addiereZu2 1 -- 3

Python[Bearbeiten | Quelltext bearbeiten]

In der Programmiersprache Python:

def uncurried_add (x, y):
    return x + y
def curried_add (x):
    return lambda y: x + y
print uncurried_add(3, 4)
print curried_add(3)(4)

Ruby[Bearbeiten | Quelltext bearbeiten]

In der Programmiersprache Ruby v1.9:

  p = Proc.new { |a,b| a+b } => #<Proc:0x00000000ff5208>

  #klassisch
  p.call(3) => "TypeError: nil can't be coerced into Fixnum"
  p.call(3,4) => 7

  #curryfiziert
  p.curry[3][4] => 7
  #gibt eine Fixnum zurück, da die korrekte Anzahl der Argumente angegeben wurde

  a = p.curry[3] => #<Proc:0x00000000f9b0c8>
  a.call(5) => 8
  a.call(10) => 13

Scheme[Bearbeiten | Quelltext bearbeiten]

  (define uncurried-add (lambda (x y)
                                (+ x y)))
  (define curried_add (lambda (x) (lambda (y) (+ x y))))
  (define add-three (curried_add 3))

Tcl[Bearbeiten | Quelltext bearbeiten]

proc uncurried_add {x y} {expr {$x + $y}}
proc curried_add x {list apply [list y [format {expr {%d + $y}} $x]]}

Einzelnachweise und Anmerkungen[Bearbeiten | Quelltext bearbeiten]

  1. Moses Schönfinkel: Über die Bausteine der mathematischen Logik. In: Mathematische Annalen 92 (1928). S. 305–316, Digitalisat.
  2. Gottlob Frege: Grundgesetze der Arithmetik. Hermann Pohle, Jena 1893 (Band I) 1903 (Band II) korpora.org.
  3. Haskell Brooks Curry, Robert Feys, Roger Hindley, Jonathan P. Seldin: Combinatory Logic. North Holland, 2 Bände, 1958, 1972.
  4. Dabei bezeichnet oder die Menge der Abbildungen von nach .
  5. Im nullstelligen Fall (n=0) würde das Currying einer Abbildung ohne Parameter und mit einem Wert eine einstellige Abbildung mit konstantem Wert zuordnen, also etwa
    .
  6. Ein Beispiel ist mit (wobei die Diagonale bezeichnet).
  7. Im obigen Beispiel ist dies .
  8. Voraussetzung ist, dass das Symbol nicht schon anderweitig mit Stelligkeit 1 überladen ist (siehe Beispiel unten, dies zwingt zwischen und zu unterscheiden).
  9. Zur Unterscheidung vom Platzhalter wird hier als Multiplikationszeichen verwendet.
  10. Dieser Funktion könnte man auch einen eigenen Namen vergeben:
    mit .
  11. Man unterscheide zwischen und der überladenen Funktion mit zur Stelligkeit und Faktoren . Zwar ist zweistellig , aber einstellig ist , während eine einstellige Funktion ist.