Welche Werkzeuge gibt es für die funktionale Programmierung in C?

Ich habe in letzter Zeit viel darüber nachgedacht, wie ich funktionale Programmierung in C (nicht C++). Offensichtlich ist C eine prozedurale Sprache und unterstützt die funktionale Programmierung nicht wirklich nativ.

Gibt es Compiler-/Spracherweiterungen, die der Sprache einige funktionale Programmierkonstrukte hinzufügen? GCC bietet verschachtelte Funktionen als Spracherweiterung; Verschachtelte Funktionen können auf Variablen aus dem übergeordneten Stapelrahmen zugreifen, aber dies ist noch weit entfernt von ausgereiften Closures.

Eine Sache, die meiner Meinung nach in C sehr nützlich sein könnte, ist zum Beispiel, dass Sie überall dort, wo ein Funktionszeiger erwartet wird, einen Lambda-Ausdruck übergeben können, wodurch ein Abschluss erstellt wird, der in einen Funktionszeiger zerfällt. C++0x wird Lambda-Ausdrücke enthalten (was ich großartig finde); Ich suche jedoch nach Tools, die auf reines C anwendbar sind.

[Edit] Zur Verdeutlichung: Ich versuche nicht, ein bestimmtes Problem in C zu lösen, das besser für die funktionale Programmierung geeignet wäre; Ich bin nur neugierig, welche Tools es gibt, wenn ich das tun möchte.

Sie können die verschachtelten Funktionen von GCC verwenden, um Lambda-Ausdrücke zu simulieren. Tatsächlich habe ich ein Makro, das dies für mich erledigt:

#define lambda(return_type, function_body) \
  ({ \
    return_type anon_func_name_ function_body \
    anon_func_name_; \
  })

Verwenden Sie so:

int (*max)(int, int) = lambda (int, (int x, int y) { return x > y ? x : y; });

Bei der funktionalen Programmierung geht es nicht um Lambdas, sondern um reine Funktionen. Das Folgende fördert also im Großen und Ganzen den funktionalen Stil:

1. Verwenden Sie nur Funktionsargumente, verwenden Sie keinen globalen Zustand.

2. Minimieren Sie Nebenwirkungen, dh printf oder beliebige IO. Geben Sie Daten zurück, die IO beschreiben, die ausgeführt werden können, anstatt die Seiteneffekte direkt in allen Funktionen zu verursachen.

Dies kann in einfachem c erreicht werden, keine Notwendigkeit für Magie.

FFCALL ermöglicht das Erstellen von Closures in C — callback = alloc_callback(&function, data) gibt einen solchen Funktionszeiger zurück callback(arg1, ...) ist gleichbedeutend mit anrufen function(data, arg1, ...). Sie müssen die Garbage Collection jedoch manuell durchführen.

Dementsprechend Blöcke wurden zu Apples Fork von GCC hinzugefügt; Sie sind keine Funktionszeiger, aber sie lassen Sie Lambdas herumreichen, während Sie vermeiden, dass Speicherplatz für erfasste Variablen von Hand erstellt und freigegeben werden muss (effektiv findet ein gewisses Kopieren und Zählen von Referenzen statt, das hinter einigen syntaktischen Zucker- und Laufzeitbibliotheken verborgen ist).

Hartel & Mullers Buch, Funktionelles Cist heute (02.01.2012) zu finden unter: http://eprints.eemcs.utwente.nl/1077/ (Link zur PDF-Version).

Voraussetzung für funktionalen Programmierstil ist eine erstklassige Funktion. Es könnte in portablem C simuliert werden, wenn Sie als nächstes tolerieren:

• manuelle Verwaltung von lexikalischen Bereichsbindungen, auch Closures genannt.
• manuelle Verwaltung der Lebensdauer der Funktionsvariablen.
• alternative Syntax der Funktion Anwendung/Aufruf.

/* 
 * with constraints desribed above we could have
 * good approximation of FP style in plain C
 */

int increment_int(int x) {
  return x + 1;
}

WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS(increment, increment_int);

map(increment, list(number(0), number(1)); // --> list(1, 2)


/* composition of first class function is also possible */

function_t* computation = compose(
  increment,
  increment,
  increment
);

*(int*) call(computation, number(1)) == 4;

Die Laufzeit für solchen Code könnte so klein wie eine darunter sein

struct list_t {
  void* head;
  struct list_t* tail;
};

struct function_t {
   void* (*thunk)(list_t*);
   struct list_t* arguments;
}

void* apply(struct function_t* fn, struct list_t* arguments) {
  return fn->thunk(concat(fn->arguments, arguments));
}

/* expansion of WRAP_PLAIN_FUNCTION_TO_FIRST_CLASS */
void* increment_thunk(struct list_t* arguments) {
  int x_arg = *(int*) arguments->head;
  int value = increment_int(x_arg);
  int* number = malloc(sizeof *number);

  return number ? (*number = value, number) : NULL;
}

struct function_t* increment = &(struct function_t) {
  increment_thunk,
  NULL
};

/* call(increment, number(1)) expands to */
apply(increment, &(struct list_t) { number(1), NULL });

Im Wesentlichen imitieren wir eine erstklassige Funktion mit Closures, die als Paar Funktion/Argumente plus eine Reihe von Makrosen dargestellt werden. Vollständiger Code konnte gefunden werden hier.

Da fällt mir vor allem der Einsatz von Codegeneratoren ein. Wären Sie bereit, in einer anderen Sprache zu programmieren, die die funktionale Programmierung bereitstellt, und daraus dann den C-Code zu generieren?

Wenn das keine attraktive Option ist, dann könnten Sie CPP missbrauchen, um einen Teil des Weges dorthin zu gelangen. Das Makrosystem sollte es Ihnen ermöglichen, einige funktionale Programmierideen zu emulieren. Ich habe gehört, dass gcc auf diese Weise implementiert ist, aber ich habe es nie überprüft.

C kann natürlich Funktionen mithilfe von Funktionszeigern herumreichen, die Hauptprobleme sind das Fehlen von Closures und das Typsystem neigt dazu, im Weg zu stehen. Sie könnten leistungsfähigere Makrosysteme als CPP wie M4 erkunden. Ich denke, was ich letztendlich vorschlage, ist, dass echtes C der Aufgabe nicht ohne großen Aufwand gewachsen ist, aber Sie könnten C erweitern, um es der Aufgabe gewachsen zu sein. Diese Erweiterung würde am ehesten wie C aussehen, wenn Sie CPP verwenden, oder Sie könnten ans andere Ende des Spektrums gehen und C-Code aus einer anderen Sprache generieren.

Wenn Sie Closures implementieren möchten, müssen Sie sich mit Assemblersprache und Stack-Swapping/-Management vertraut machen. Nicht dagegen empfehlen, nur sagen, dass Sie das tun müssen.

Ich bin mir nicht sicher, wie Sie mit anonymen Funktionen in C umgehen werden. Auf einer von Neumann-Maschine könnten Sie jedoch anonyme Funktionen in asm ausführen.