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

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ć.

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).

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

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.

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).

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 .

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.

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.

Spójrz na książkę Hartel & Muller, Functional C

http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf
http://www.cs.bris.ac.uk/~henkm/f2c/index.html

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

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

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

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ę.

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.