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

153

Ich habe in letzter Zeit viel darüber nachgedacht, wie man funktionale Programmierung in C ( nicht in C ++) durchführt. Offensichtlich ist C eine prozedurale Sprache und unterstützt die funktionale Programmierung von Haus aus nicht wirklich.

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, dies ist jedoch noch weit von ausgereiften Abschlüssen entfernt.

Eine Sache, die meiner Meinung nach in C wirklich nützlich sein könnte, ist, 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 Werkzeugen für Straight C.

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

Adam Rosenfield
quelle
1
Anstatt nach Hacks und nicht portablen Erweiterungen zu suchen, um C in etwas zu verwandeln, das es nicht ist, warum verwenden Sie nicht einfach eine Sprache, die die gesuchte Funktionalität bietet?
Robert Gamble
Siehe auch verwandte Frage: < stackoverflow.com/questions/24995/… >
Andy Brice
@AndyBrice Diese Frage bezieht sich auf eine andere Sprache und scheint eigentlich keinen Sinn zu ergeben (C ++ hat kein "Ökosystem" im gleichen Sinne wie.
Kyle Strand

Antworten:

40

Mit FFCALL können Sie Abschlüsse in C erstellen - callback = alloc_callback(&function, data)gibt einen Funktionszeiger zurück, der callback(arg1, ...)dem Aufruf entspricht function(data, arg1, ...). Sie müssen die Speicherbereinigung jedoch manuell durchführen.

In ähnlicher Weise wurden Blöcke zu Apples GCC-Gabel hinzugefügt. Sie sind keine Funktionszeiger, aber Sie können Lambdas weitergeben, ohne dass Speicher für erfasste Variablen von Hand erstellt und freigegeben werden müssen (effektiv werden einige Kopier- und Referenzzählungen durchgeführt, die sich hinter einigen syntaktischen Zucker- und Laufzeitbibliotheken verbergen).

kurzlebig
quelle
89

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 wie folgt:

int (*max)(int, int) = lambda (int, (int x, int y) { return x > y ? x : y; });
Joe D.
quelle
12
Das ist wirklich cool. Es scheint __fn__nur ein beliebiger Name für die im Block definierte Funktion zu sein ({... })nicht eine GCC-Erweiterung oder ein vordefiniertes Makro? Die Wahl des Namens für __fn__(der der GCC-Definition sehr ähnlich sieht) hat mich wirklich am Kopf kratzen lassen und die GCC-Dokumentation nach keinem guten Effekt durchsucht.
FooF
1
Leider funktioniert dies in der Praxis nicht: Wenn der Abschluss etwas erfassen soll, ist ein ausführbarer Stapel erforderlich, was eine schreckliche Sicherheitspraxis darstellt. Persönlich halte ich es überhaupt nicht für nützlich.
Demi
Es ist nicht aus der Ferne nützlich, aber es macht Spaß. Deshalb wird die andere Antwort akzeptiert.
Joe D
65

Bei der funktionalen Programmierung geht es nicht um Lambdas, sondern um reine Funktionen. Folgendes fördert also allgemein den funktionalen Stil:

  1. Verwenden Sie nur Funktionsargumente, keinen globalen Status.

  2. Minimieren Sie Nebenwirkungen, z. B. printf oder E / A. Rückgabedaten, die E / A beschreiben und ausgeführt werden können, anstatt die Nebenwirkungen direkt in allen Funktionen zu verursachen.

Dies kann in der Ebene c erreicht werden, ohne dass Magie erforderlich ist.

Andy Till
quelle
5
Ich denke, Sie haben diese extreme Sichtweise der funktionalen Programmierung bis zur Absurdität gebracht. Was nützt eine reine Spezifikation, z. B. mapwenn man nicht die Möglichkeit hat, eine Funktion an sie zu übergeben?
Jonathan Leonard
27
Ich denke, dieser Ansatz ist weitaus pragmatischer als die Verwendung von Makros, um eine funktionale Sprache in c zu erstellen. Die angemessene Verwendung reiner Funktionen verbessert ein System eher als die Verwendung von Map anstelle von for-Schleifen.
Andy bis
6
Sicher wissen Sie, dass die Karte nur der Ausgangspunkt ist. Ohne erstklassige Funktionen ist jedes Programm (auch wenn alle seine Funktionen "rein" sind) niedrigerer Ordnung (im Sinne der Informationstheorie) als das Äquivalent zu erstklassigen Funktionen. Meiner Ansicht nach ist dieser deklarative Stil, der nur mit erstklassigen Funktionen möglich ist, der Hauptvorteil von FP. Ich denke, Sie tun jemandem einen schlechten Dienst, um zu implizieren, dass die Ausführlichkeit, die sich aus dem Mangel an erstklassigen Funktionen ergibt, alles ist, was FP zu bieten hat. Es sollte angemerkt werden, dass der Begriff FP historisch mehr erstklassige Funktionen als Reinheit implizierte.
Jonathan Leonard
PS Vorheriger Kommentar war von Mobile - unregelmäßige Grammatik war nicht beabsichtigt.
Jonathan Leonard
1
Die Antwort von Andy Tills zeigt eine sehr pragmatische Sicht auf die Dinge. "Rein" in C zu sein, erfordert nichts Besonderes und bringt einen großen Vorteil. Erstklassige Funktionen im Vergleich zu "Comfort Living". Es ist praktisch, aber es ist praktisch, einen reinen Programmierstil zu verwenden. Ich frage mich, warum niemand über Tail Calls in Bezug auf all das spricht. Wer erstklassige Funktionen möchte, sollte auch nach Tail Calls fragen.
BitTickler
17

Hartel & Mullers Buch Functional C ist heutzutage (2012-01-02) unter folgender Adresse zu finden: http://eprints.eemcs.utwente.nl/1077/ (es gibt einen Link zur PDF-Version).

FooF
quelle
2
Es gibt keinen Versuch, irgendetwas in diesem Buch zu tun (im Zusammenhang mit der Frage).
Eugene Tolmachev
4
Es scheint, Sie haben ganz recht. In der Tat heißt es im Vorwort, dass der Zweck des Buches darin besteht, imperative Programmierung zu lehren, nachdem sich die Schüler bereits mit funktionaler Programmierung vertraut gemacht haben. Zu Ihrer Information, dies war meine erste Antwort in SO und sie wurde nur als Antwort geschrieben, weil ich keinen Ruf benötigt hatte, um eine vorherige Antwort mit einem faulen Link zu kommentieren. Ich frage mich immer, warum die Leute diese Antwort +1 behalten ... Bitte tu das nicht! :-)
FooF
1
Vielleicht hätte das Buch besser als postfunktionale Programmierung bezeichnet werden sollen (erstens, weil "Imperativ C" nicht sexy klingt, zweitens, weil es mit dem Paradigma der funktionalen Programmierung vertraut ist, drittens als Wortspiel, weil das imperative Paradigma wie ein Rückgang von Standards und Standards erscheint korrekte Funktionalität und vielleicht viertens, um auf Larry Walls Begriff der postmodernen Programmierung zu verweisen - obwohl dieses Buch vor dem Artikel / der Präsentation von Larry Wall geschrieben wurde).
FooF
Und dies ist eine doppelte Antwort
PhilT
8

Voraussetzung für einen funktionalen Programmierstil ist eine erstklassige Funktion. Es könnte in tragbarem C simuliert werden, wenn Sie Folgendes tolerieren:

  • Manuelle Verwaltung von lexikalischen Bereichsbindungen, auch bekannt als Verschlüsse.
  • manuelle Verwaltung der Lebensdauer von Funktionsvariablen.
  • alternative Syntax der Funktionsanwendung / des Aufrufs.
/* 
 * 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 einen solchen Code kann so klein wie die folgende 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 ahmen wir erstklassige Funktionen mit Abschlüssen nach, die als Paar von Funktionen / Argumenten plus Makros dargestellt werden. Den vollständigen Code finden Sie hier .

Viktor Shepel
quelle
7

Die Hauptsache, die mir in den Sinn kommt, ist die Verwendung von Codegeneratoren. Wären Sie bereit, in einer anderen Sprache zu programmieren, die die funktionale Programmierung bereitstellt, und daraus den C-Code zu generieren?

Wenn dies keine attraktive Option ist, können Sie CPP missbrauchen, um einen Teil des Weges dorthin zu finden. Mit dem Makrosystem sollten Sie einige funktionale Programmierideen emulieren können. 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 weitergeben, die Hauptprobleme sind fehlende Verschlüsse und das Typsystem neigt dazu, im Weg zu sein. Sie könnten leistungsfähigere Makrosysteme als CPP wie M4 untersuchen. Ich denke letztendlich, was ich vorschlage, ist, dass wahres C der Aufgabe nicht ohne großen Aufwand gewachsen ist, aber Sie könnten C erweitern, um es der Aufgabe gewachsen zu machen. Diese Erweiterung würde C am ähnlichsten aussehen, wenn Sie CPP verwenden oder zum anderen Ende des Spektrums gehen und C-Code aus einer anderen Sprache generieren könnten.

Jason Dagit
quelle
Dies ist die ehrlichste Antwort. Der Versuch, C funktional zu schreiben, bedeutet, gegen das Sprachdesign und die Sprachstruktur selbst zu kämpfen.
Josiah
5

Wenn Sie Closures implementieren möchten, müssen Sie sich mit Assemblersprache und Stack Swapping / Management vertraut machen. Ich empfehle nicht dagegen, sondern sage nur, dass Sie das tun müssen.

Sie sind sich nicht sicher, wie Sie mit anonymen Funktionen in C umgehen sollen. Auf einem von Neumann-Computer können Sie jedoch anonyme Funktionen in asm ausführen.

Paul Nathan
quelle
2

Die Felix-Sprache wird in C ++ kompiliert. Vielleicht könnte das ein Sprungbrett sein, wenn Ihnen C ++ nichts ausmacht.

LennyStackOverflow
quelle
9
⁻¹ weil α) Der Autor erwähnte ausdrücklich «nicht C ++», β) Das von einem Compiler erzeugte C ++ wäre kein «von Menschen lesbares C ++». γ) Der C ++ - Standard unterstützt eine funktionale Programmierung, ohne dass ein Compiler von einer Sprache in eine andere verwendet werden muss.
Hi-Angel
Sobald Sie mithilfe von Makros oder Ähnlichem eine funktionale Sprache gefunden haben, implizieren Sie automatisch, dass Sie sich nicht so sehr für C interessieren. Diese Antwort ist gültig und in Ordnung, da sogar C ++ als Makro-Party über C begann. Wenn Sie Wenn Sie diesen Weg weit genug gehen, erhalten Sie eine neue Sprache. Dann kommt es nur noch auf eine Backend-Diskussion an.
BitTickler
1

Nun, einige Programmiersprachen sind in C geschrieben. Einige von ihnen unterstützen Funktionen als erstklassige Bürger. Sprachen in diesem Bereich sind ecl (eingebettetes Common Lisp IIRC), Gnu Smalltalk (gst) (Smalltalk hat Blöcke), dann gibt es Bibliotheken für "Verschlüsse" zB in glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure, die zumindest in die Nähe der funktionalen Programmierung kamen. Vielleicht ist die Verwendung einiger dieser Implementierungen für die funktionale Programmierung eine Option.

Na oder du kannst Ocaml, Haskell, Mozart / Oz oder ähnliches lernen ;-)

Grüße

Friedrich
quelle
Würde es Ihnen etwas ausmachen, mir zu sagen, was so schrecklich daran ist, Bibliotheken zu verwenden, die zumindest den FP-Programmierstil unterstützen?
Friedrich
1

Die Art und Weise, wie ich funktionale Programmierung in C durchführte, bestand darin, einen funktionalen Sprachinterpreter in C zu schreiben. Ich nannte ihn Fexl, was für "Function EXpression Language" steht.

Der Interpreter ist sehr klein und kompiliert auf meinem System mit aktiviertem -O3 auf 68 KB. Es ist auch kein Spielzeug - ich verwende es für den gesamten neuen Produktionscode, den ich für mein Unternehmen schreibe (webbasierte Buchhaltung für Investitionspartnerschaften).

Jetzt schreibe ich C-Code nur, um (1) eine integrierte Funktion hinzuzufügen, die eine Systemroutine aufruft (z. B. Fork, Exec, Setrlimit usw.), oder (2) eine Funktion zu optimieren, die sonst in Fexl geschrieben werden könnte (z. B. Suche) für einen Teilstring).

Der Modulmechanismus basiert auf dem Konzept eines "Kontextes". Ein Kontext ist eine Funktion (in Fexl geschrieben), die ein Symbol seiner Definition zuordnet. Wenn Sie eine Fexl-Datei lesen, können Sie sie in einem beliebigen Kontext auflösen. Auf diese Weise können Sie benutzerdefinierte Umgebungen erstellen oder Code in einer eingeschränkten "Sandbox" ausführen.

http://fexl.com

Patrick Chkoreff
quelle
-3

Was ist an C, das Sie funktionsfähig machen möchten, die Syntax oder die Semantik? Die Semantik der funktionalen Programmierung könnte sicherlich zum C-Compiler hinzugefügt werden, aber wenn Sie fertig sind, haben Sie im Wesentlichen das Äquivalent einer der vorhandenen funktionalen Sprachen wie Schema, Haskell usw.

Es wäre besser, die Zeit zu nutzen, um nur die Syntax der Sprachen zu lernen, die diese Semantik direkt unterstützen.

Barry Brown
quelle
-3

Ich weiß nichts über C. Es gibt einige funktionale Funktionen in Objective-C, GCC unter OSX unterstützt jedoch auch einige Funktionen. Ich würde jedoch erneut empfehlen, eine funktionale Sprache zu verwenden. Es gibt viele, die oben erwähnt wurden. Ich persönlich habe mit Schema begonnen, es gibt einige ausgezeichnete Bücher wie The Little Schemer, die Ihnen dabei helfen können.

Shiv
quelle