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

Question

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

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

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

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

Answer 1

Вы можете использовать вложенные функции 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; });

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

Answer 6

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

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

Answer 7

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

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

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

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

Answer 8

Посмотрите на книгу Хартеля и Мюллера, Функциональный С

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

Answer 9

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

Answer 10

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

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

Привет