Jakie narzędzia są dostępne do programowania funkcjonalnego w C?


153

Ostatnio dużo myślałem o tym, jak zrobić programowanie funkcjonalne w C ( nie C ++). Oczywiście C jest językiem proceduralnym i nie obsługuje natywnie programowania funkcjonalnego.

Czy są jakieś rozszerzenia kompilatora / języka, które dodają pewne konstrukcje programowania funkcjonalnego do języka? GCC udostępnia zagnieżdżone funkcje jako rozszerzenie języka; funkcje zagnieżdżone mogą uzyskiwać dostęp do zmiennych z nadrzędnej ramki stosu, ale jest to wciąż daleko od dojrzałych zamknięć.

Na przykład jedna rzecz, która moim zdaniem może być naprawdę przydatna w C, to to, że wszędzie tam, gdzie oczekiwany jest wskaźnik funkcji, możesz być w stanie przekazać wyrażenie lambda, tworząc zamknięcie, które rozpada się na wskaźnik funkcji. C ++ 0x będzie zawierał wyrażenia lambda (które moim zdaniem są niesamowite); jednak szukam narzędzi, które można zastosować do prostego C.

[Edytuj] Aby wyjaśnić, nie próbuję rozwiązywać konkretnego problemu w C, który byłby bardziej odpowiedni dla programowania funkcjonalnego; Jestem po prostu ciekawy, jakie narzędzia są dostępne, gdybym chciał to zrobić.


1
Zamiast szukać hacków i nieprzenośnych rozszerzeń, aby spróbować zmienić C w coś, czym nie jest, dlaczego nie użyjesz po prostu języka, który zapewnia funkcjonalność, której szukasz?
Robert Gamble,

Zobacz także powiązane pytanie: < stackoverflow.com/questions/24995/… >
Andy Brice,

@AndyBrice To pytanie dotyczy innego języka i właściwie nie wydaje się mieć sensu (C ++ nie ma „ekosystemu” w tym samym sensie, co.
Kyle Strand

Odpowiedzi:


40

FFCALL pozwala budować domknięcia w C - callback = alloc_callback(&function, data)zwraca wskaźnik funkcji taki, który callback(arg1, ...)jest równoważny wywołaniu function(data, arg1, ...). Będziesz jednak musiał ręcznie obsługiwać czyszczenie pamięci.

W związku z tym bloki zostały dodane do rozwidlenia GCC firmy Apple; nie są one wskaźnikami funkcji, ale pozwalają ci przekazywać lambdy, unikając konieczności ręcznego budowania i zwalniania przechowywania przechwyconych zmiennych (w praktyce zachodzi pewne kopiowanie i liczenie referencji, ukryte za niektórymi bibliotekami składniowymi i uruchomieniowymi).


89

Możesz użyć zagnieżdżonych funkcji GCC do symulacji wyrażeń lambda, w rzeczywistości mam makro, które zrobi to za mnie:

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

Użyj w ten sposób:

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

12
To jest naprawdę fajne. Wygląda na __fn__to, że to dowolna nazwa funkcji zdefiniowanej w bloku ({... a })nie jakieś rozszerzenie GCC lub predefiniowane makro? Wybór nazwy __fn__(wyglądającej bardzo podobnie do definicji GCC) naprawdę skłonił mnie do podrapania się po głowie i przeszukania dokumentacji GCC pod kątem żadnego dobrego efektu.
FooF

1
Niestety, to nie działa w praktyce: jeśli chcesz, aby zamknięcie przechwytywało cokolwiek, wymaga stosu wykonywalnego, co jest okropną praktyką bezpieczeństwa. Osobiście uważam, że nie jest to w ogóle przydatne.
Demi

To nie jest przydatne, ale jest fajne. Dlatego inna odpowiedź jest akceptowana.
Joe D

65

W programowaniu funkcyjnym nie chodzi o lambdy, chodzi o czyste funkcje. Tak więc następujące szeroko promują funkcjonalny styl:

  1. Używaj tylko argumentów funkcji, nie używaj stanu globalnego.

  2. Zminimalizuj efekty uboczne, np. Printf lub jakiekolwiek IO. Zwraca dane opisujące IO, które można wykonać zamiast wywoływania efektów ubocznych bezpośrednio we wszystkich funkcjach.

Można to osiągnąć zwykłym c, bez potrzeby używania magii.


5
Myślę, że doprowadziłeś ten skrajny pogląd na programowanie funkcjonalne do punktu absurdu. Po co jest czysta specyfikacja, np. mapJeśli nie ma się możliwości przekazania jej funkcji?
Jonathan Leonard

27
Myślę, że to podejście jest o wiele bardziej pragmatyczne niż używanie makr do tworzenia języka funkcjonalnego wewnątrz c. Właściwe użycie czystych funkcji jest bardziej prawdopodobne, aby ulepszyć system niż użycie mapy zamiast pętli for.
Andy Do

6
Na pewno wiesz, że mapa to tylko punkt wyjścia. Bez funkcji pierwszej klasy każdy program (nawet jeśli wszystkie jego funkcje są „czyste”) będzie niższego rzędu (w sensie teorii informacji) niż jego odpowiednik z funkcjami pierwszej klasy. Moim zdaniem to właśnie ten deklaratywny styl możliwy tylko w przypadku pierwszorzędnych funkcji jest główną zaletą FP. Myślę, że robisz komuś krzywdę, sugerując, że gadatliwość wynikająca z braku pierwszorzędnych funkcji to wszystko, co ma do zaoferowania FP. Należy zauważyć, że historycznie termin FP sugerował, że funkcje pierwszej klasy są czymś więcej niż czystością.
Jonathan Leonard

PS Poprzedni komentarz pochodzi z telefonu komórkowego - gramatyka nieregularna nie była zamierzona.
Jonathan Leonard

1
Odpowiedź Andy'ego Tillsa pokazuje bardzo pragmatyczne spojrzenie na sprawy. Przejście na „czystość” w C nie wymaga niczego wyszukanego i daje ogromne korzyści. Funkcje pierwszej klasy, w porównaniu z „komfortowym życiem”. Jest to wygodne, ale przyjęcie czystego stylu programowania jest praktyczne. Zastanawiam się, dlaczego nikt nie omawia odgłosów ogonów w związku z tym wszystkim. Ci, którzy chcą funkcji pierwszej klasy, powinni również poprosić o wywołania ogonowe.
BitTickler

17

Książka Hartela & Mullera, Functional C , jest obecnie (2012-01-02) dostępna pod adresem : http://eprints.eemcs.utwente.nl/1077/ (jest link do wersji PDF).


2
W tej książce nie ma próby niczego funkcjonalnego (w odniesieniu do pytania).
Eugene Tolmachev

4
Wygląda na to, że masz rację. Rzeczywiście, przedmowa stwierdza, że ​​celem książki jest nauczenie programowania imperatywnego po tym, jak student zapoznał się już z programowaniem funkcjonalnym. FYI, to była moja pierwsza odpowiedź w SO i została napisana jako odpowiedź tylko dlatego, że nie wymagałem reputacji, aby skomentować poprzednią odpowiedź ze zgniłym linkiem. Zawsze się zastanawiam, dlaczego ludzie dają +1 tej odpowiedzi ... Proszę, nie rób tego! :-)
FooF

1
Być może książka powinna była lepiej nazwać programowanie postfunkcjonalne (po pierwsze dlatego, że „Imperative C” nie brzmi seksownie, po drugie dlatego, że zakłada znajomość paradygmatu programowania funkcjonalnego, po trzecie jako gra słów, ponieważ imperatywny paradygmat wydaje się być upadkiem standardów i poprawna funkcjonalność i być może czwarta, aby odnieść się do koncepcji programowania postmodernistycznego Larry'ego Walla - chociaż ta książka została napisana przed artykułem / prezentacją Larry'ego Walla).
FooF

A to jest
podwójna

8

Warunkiem koniecznym dla funkcjonalnego stylu programowania jest funkcja pierwszej klasy. Można to zasymulować w przenośnym C, jeśli będziesz tolerować:

  • ręczne zarządzanie powiązaniami zakresów leksykalnych, czyli domknięciami.
  • ręczne zarządzanie okresem życia zmiennych funkcyjnych.
  • alternatywna składnia aplikacji / wywołania funkcji.
/* 
 * 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;

Środowisko wykonawcze takiego kodu może być tak małe, jak poniżej

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 });

W istocie imitujemy funkcję pierwszej klasy z domknięciami reprezentowanymi jako para funkcji / argumentów plus kilka makr. Pełny kod można znaleźć tutaj .


7

Najważniejsze, co przychodzi na myśl, to użycie generatorów kodu. Czy chciałbyś programować w innym języku, który zapewniłby programowanie funkcjonalne, a następnie wygenerować na jego podstawie kod w języku C?

Jeśli to nie jest atrakcyjna opcja, możesz nadużywać CPP, aby dostać się tam częściowo. System makr powinien umożliwiać emulację niektórych pomysłów dotyczących programowania funkcjonalnego. Słyszałem, że gcc jest zaimplementowane w ten sposób, ale nigdy nie sprawdzałem.

C może oczywiście przekazywać funkcje za pomocą wskaźników funkcji, główne problemy to brak domknięć, a system typów zwykle przeszkadza. Możesz zbadać potężniejsze systemy makr niż CPP, takie jak M4. Myślę, że ostatecznie sugeruję, że prawdziwe C nie sprosta zadaniu bez wielkiego wysiłku, ale możesz rozszerzyć C, aby sprostać zadaniu. To rozszerzenie wyglądałoby najbardziej jak C, gdybyś używał CPP lub mógłbyś przejść na drugi koniec spektrum i wygenerować kod C z innego języka.


To najszczersza odpowiedź. Próba napisania C w sposób funkcjonalny jest walką z samym projektem i strukturą języka.
josiah

5

Jeśli chcesz zaimplementować domknięcia, będziesz musiał opanować język asemblera i wymianę / zarządzanie stosem. Nie polecam przeciwko temu, po prostu mówię, że musisz to zrobić.

Nie jestem pewien, jak poradzisz sobie z anonimowymi funkcjami w C. Na maszynie von Neumanna możesz jednak wykonywać anonimowe funkcje w asm.



2

Język Felix kompiluje się do C ++. Może to byłby krok do przodu, jeśli nie masz nic przeciwko C ++.


9
⁻¹, ponieważ α) Autor wyraźnie wspomniał „nie C ++”, β) C ++ wyprodukowany przez kompilator nie byłby „czytelnym dla człowieka C ++”. γ) Standard C ++ obsługuje programowanie funkcjonalne, nie ma potrzeby używania kompilatora z jednego języka na inny.
Hi-Angel,

Kiedy wymyślisz język funkcjonalny za pomocą makr lub tym podobnych, automatycznie zasugerujesz, że nie przejmujesz się tak bardzo C. Ta odpowiedź jest poprawna i w porządku, ponieważ nawet C ++ zaczynał jako impreza makr na szczycie C. Jeśli ty idź tą drogą wystarczająco daleko, a skończysz z nowym językiem. Potem wszystko sprowadza się do końcowej dyskusji.
BitTickler

1

Cóż, sporo języków programowania jest napisanych w C. A niektóre z nich obsługują funkcje jako obywatele pierwszej klasy, języki w tym obszarze to ecl (embbedabble common lisp IIRC), Gnu Smalltalk (gst) (Smalltalk ma bloki), wtedy są biblioteki dla "domknięć" np. w glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure, które przynajmniej zbliżyło się do programowania funkcjonalnego. Więc może użycie niektórych z tych implementacji do programowania funkcjonalnego może być opcją.

Cóż, albo możesz się uczyć Ocaml, Haskell, Mozart / Oz lub tym podobne ;-)

pozdrowienia


Czy mógłbyś mi powiedzieć, co jest tak strasznego w używaniu bibliotek, które przynajmniej wspierają styl programowania FP?
Friedrich

1

Sposób, w jaki zrobiłem programowanie funkcjonalne w C, polegał na napisaniu interpretera języka funkcjonalnego w C. Nazwałam go Fexl, co jest skrótem od „Function EXpression Language”.

Interpreter jest bardzo mały, kompiluje do 68K w moim systemie z włączonym -O3. To też nie jest zabawka - używam go do całego nowego kodu produkcyjnego, który piszę dla mojej firmy (internetowe rozliczanie partnerstw inwestycyjnych).

Teraz piszę kod w C tylko po to, aby (1) dodać wbudowaną funkcję, która wywołuje procedurę systemową (np. Fork, exec, setrlimit itp.) Lub (2) zoptymalizować funkcję, która w innym przypadku mogłaby być zapisana w Fexl (np. Search dla podciągu).

Mechanizm modułu oparty jest na koncepcji „kontekstu”. Kontekst to funkcja (napisana w Fexl), która odwzorowuje symbol na jego definicję. Kiedy czytasz plik Fexl, możesz go rozwiązać w dowolnym kontekście. Umożliwia to tworzenie niestandardowych środowisk lub uruchamianie kodu w ograniczonej „piaskownicy”.

http://fexl.com


-3

Co takiego jest w C, co chcesz uczynić funkcjonalnym, składnią lub semantyką? Semantykę programowania funkcjonalnego z pewnością można by dodać do kompilatora C, ale zanim skończysz, będziesz miał zasadniczo odpowiednik jednego z istniejących języków funkcyjnych, takich jak Scheme, Haskell itp.

Byłoby lepiej wykorzystać czas, aby po prostu nauczyć się składni tych języków, które bezpośrednio obsługują tę semantykę.


-3

Nie wiem o C. Jest kilka funkcji funkcjonalnych w Objective-C, chociaż GCC na OSX obsługuje również niektóre funkcje, jednak ponownie zalecałbym rozpoczęcie używania języka funkcjonalnego, jest wiele wymienionych powyżej. Osobiście zacząłem od schematu, jest kilka doskonałych książek, takich jak The Little Schemer, które mogą ci w tym pomóc.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.