Какие инструменты есть для функционального программирования на C?

В последнее время я много думал о том, как заниматься функциональным программированием на C ( не на C ++). Очевидно, что C является процедурным языком и на самом деле не поддерживает функциональное программирование изначально.

Существуют ли какие-либо расширения компилятора / языка, которые добавляют некоторые функциональные программные конструкции к языку? GCC предоставляет вложенные функции как расширение языка; Вложенные функции могут обращаться к переменным из родительского стекового фрейма, но до зрелых замыканий это еще далеко.

Например, одна вещь, которая, на мой взгляд, может быть действительно полезной в C, заключается в том, что в любом месте, где ожидается указатель на функцию, вы можете передавать лямбда-выражение, создавая замыкание, которое распадается в указатель на функцию. C ++ 0x будет включать в себя лямбда-выражения (что, я думаю, круто); Тем не менее, я ищу инструменты, применимые к прямой C.

[Править] Чтобы уточнить, я не пытаюсь решить конкретную проблему в C, которая больше подходит для функционального программирования; Мне просто любопытно, какие инструменты существуют, если я хочу это сделать.

FFCALL позволяет вам создавать замыкания в C - callback = alloc_callback(&function, data)возвращает указатель на функцию, который callback(arg1, ...)эквивалентен вызову function(data, arg1, ...). Вам придется обрабатывать сборку мусора вручную.

Кроме того, блоки были добавлены в форк Apple GCC; они не являются указателями на функции, но они позволяют вам передавать лямбда-выражения, избегая при этом необходимости создавать и освобождать хранилище для захваченных переменных вручную (фактически, происходит некоторое копирование и подсчет ссылок, скрытые за некоторыми синтаксическими сахарами и библиотеками времени выполнения).

Вы можете использовать вложенные функции GCC для имитации лямбда-выражений, на самом деле у меня есть макрос, чтобы сделать это для меня:

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

Используйте как это:

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

Функциональное программирование не о лямбдах, а о чистых функциях. Таким образом, следующие широко продвигают функциональный стиль:

1. Используйте только аргументы функции, не используйте глобальное состояние.

2. Минимизируйте побочные эффекты, например, printf или любой ввод-вывод. Возвратите данные, описывающие IO, которые могут быть выполнены вместо того, чтобы вызывать побочные эффекты непосредственно во всех функциях.

Это может быть достигнуто в простой с, нет необходимости в магии.

Книгу Hartel & Muller, Functional C , в настоящее время (2012-01-02) можно найти по адресу: http://eprints.eemcs.utwente.nl/1077/ (есть ссылка на PDF-версию).

Необходимым условием для функционального стиля программирования является функция первого класса. Это может быть смоделировано в переносном C, если вы допустите следующее:

• ручное управление привязками лексических областей видимости, или замыканиями.
• ручное управление временем жизни функциональных переменных.
• альтернативный синтаксис приложения функции / вызова.

/* 
 * 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;

время выполнения для такого кода может быть как один ниже

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

По сути, мы имитируем функцию первого класса с замыканиями, представленными как пара функций / аргументов плюс куча макросов. Полный код можно найти здесь .

Главное, что приходит на ум - это использование генераторов кода. Желаете ли вы программировать на другом языке, обеспечивающем функциональное программирование, а затем генерировать код C из этого?

Если это не очень привлекательный вариант, вы можете злоупотребить CPP, чтобы получить часть пути туда. Макросистема должна позволять вам подражать некоторым идеям функционального программирования. Я слышал, что gcc реализован таким образом, но я никогда не проверял.

C, конечно, может передавать функции с помощью указателей функций, основные проблемы - отсутствие замыканий, а система типов имеет тенденцию мешать. Вы можете исследовать более мощные макро-системы, чем CPP, такие как M4. В конечном счете, я предполагаю, что настоящий C не справляется с задачей без больших усилий, но вы можете расширить C, чтобы она соответствовала этой задаче. Это расширение будет больше всего похоже на C, если вы используете CPP или можете перейти на другой конец спектра и сгенерировать C-код на каком-то другом языке.

Если вы хотите реализовать замыкания, вам нужно будет познакомиться с языком ассемблера и обменом / управлением стека. Не рекомендую против этого, просто говорю, что это то, что вам придется сделать.

Не уверен, как вы будете обрабатывать анонимные функции в C. На машине фон Неймана вы можете выполнять анонимные функции в asm.

Посмотрите на книгу Hartel & Muller, Functional C

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

Язык Феликса компилируется в C ++. Может быть, это может быть ступенькой, если вы не против C ++.

Ну, довольно много языков программирования написано на C. И некоторые из них поддерживают функции как граждан первого класса, языки в этой области - ecl (embribabble common lisp IIRC), Gnu Smalltalk (gst) (Smalltalk имеет блоки), затем есть библиотеки для "замыканий", например, в glib2 http://library.gnome.org/devel/gobject/unstable/chapter-signal.html#closure, которые по крайней мере приблизились к функциональному программированию. Так что, возможно, использование некоторых из этих реализаций для функционального программирования может быть вариантом.

Ну или вы можете пойти изучать Ocaml, Haskell, Моцарта / Oz или тому подобное ;-)

С уважением

То, как я начал заниматься функциональным программированием на C, заключалось в написании интерпретатора функционального языка на C. Я назвал его Fexl, что сокращенно от «Язык выражения функций».

Интерпретатор очень маленький, компилируется до 68 КБ в моей системе с включенным -O3. Это тоже не игрушка - я использую его для всего нового производственного кода, который я пишу для своего бизнеса (веб-учет инвестиционных партнерств).

Теперь я пишу код на C только для (1) добавления встроенной функции, которая вызывает системную подпрограмму (например, fork, exec, setrlimit и т. Д.), Или (2) оптимизации функции, которая в противном случае могла бы быть написана на Fexl (например, поиск для подстроки).

Механизм модуля основан на понятии «контекст». Контекст - это функция (написанная на Fexl), которая сопоставляет символ с его определением. Когда вы читаете файл Fexl, вы можете разрешить его в любом контексте. Это позволяет создавать пользовательские среды или запускать код в ограниченной «песочнице».

http://fexl.com

Что в Си вы хотите сделать функциональным, синтаксис или семантику? Семантика функционального программирования, безусловно, может быть добавлена ​​в компилятор C, но к тому времени, когда вы закончите, вы по существу получите эквивалент одного из существующих функциональных языков, таких как Scheme, Haskell и т. Д.

Было бы лучше использовать время только для изучения синтаксиса тех языков, которые непосредственно поддерживают эту семантику.

Не знаю о C. Есть некоторые функциональные возможности в Objective-C, хотя, GCC на OSX также поддерживает некоторые функции, однако я бы снова рекомендовал начать использовать функциональный язык, есть много упомянутых выше. Я лично начал со схемы, есть несколько отличных книг, таких как «Маленький интриган», которые могут помочь вам в этом.