Функции высшего порядка в C - PullRequest
Новая
       40

Функции высшего порядка в C

17 голосов
/ 29 марта 2010

Есть ли "правильный" способ реализации функций высшего порядка в C.

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

Edit: Причина, по которой я хочу знать, как создавать функции более высокого порядка, заключается в том, что я написал систему для преобразования списков PyObject (которые вы получаете при вызове скриптов Python) в список структур C, содержащих те же данные, но организованных способом, не зависящим от библиотеки python.h. Таким образом, мой план состоит в том, чтобы иметь функцию, которая перебирает питонический список и вызывает функцию для каждого элемента в списке и помещает результат в список, который затем возвращает.

Так что это в основном мой план: 

typedef gpointer (converter_func_type)(PyObject *)

gpointer converter_function(PyObject *obj)
{
    // do som stuff and return a struct cast into a gpointer (which is a void *)
}

GList *pylist_to_clist(PyObject *obj, converter_func_type f)
{
   GList *some_glist;
   for each item in obj
   {
       some_glist = g_list_append(some_glist, f(item));
   }
   return some_glist;
}

void some_function_that_executes_a_python_script(void)
{
   PyObject *result = python stuff that returns a list;
   GList *clist = pylist_to_clist(result, converter_function);
}

И чтобы прояснить вопрос: я хочу знать, как сделать это в более безопасной и правильной C. Я действительно хотел бы сохранить стиль функции более высокого порядка, но если это осуждается, я очень ценю способы сделать это каким-то другим способ.

Ответы [ 8 ]

19 голосов
/ 29 марта 2010

Технически, функции высшего порядка - это просто функции, которые принимают или возвращают функции. Такие вещи, как qsort, уже более высокого порядка.

Если вы имеете в виду что-то более похожее на лямбда-функции, встречающиеся в функциональных языках (именно здесь функции высшего порядка действительно становятся полезными), то они немного сложнее и не могут быть выполнены естественным образом в текущем стандарте C. Они просто не часть языка. Расширение блоков Apple - лучший кандидат. Это работает только в GCC (и компиляторе C LLVM), но они действительно полезны. Надеюсь, что-то подобное поймет. Вот несколько соответствующих ресурсов:

7 голосов
/ 29 марта 2010

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

4 голосов
/ 29 марта 2010

Если вы заинтересованы в том, чтобы делать это в простом C, вам нужно не забыть включить опцию для передачи указателя контекста от вызывающей функции функтора (функция высшего порядка) к переданной функции. Это позволяетвы имитируете достаточно замыкания, чтобы заставить вещи работать достаточно легко.На что указывает этот указатель ... ну, это зависит от вас, но это должно быть void* в API функтора (или один из множества его псевдонимов, например gpointer в мире GLib или ClientDataв Tcl C API).

[EDIT]: Чтобы использовать / адаптировать ваш пример: 

typedef gpointer (converter_func_type)(gpointer,PyObject *)

gpointer converter_function(gpointer context_ptr,PyObject *obj)
{
    int *number_of_calls_ptr = context_ptr;
    *number_of_calls_ptr++;
    // do som stuff and return a struct cast into a gpointer (which is a void *)
}

GList *pylist_to_clist(PyObject *obj, converter_func_type f, gpointer context_ptr)
{
   GList *some_glist;
   for each item in obj
   {
       some_glist = g_list_append(some_glist, f(context_ptr,item));
   }
   return some_glist;
}

void some_function_that_executes_a_python_script(void)
{
   int number_of_calls = 0;
   PyObject *result = python stuff that returns a list;
   GList *clist = pylist_to_clist(result, converter_function, &number_of_calls);
   // Now number_of_calls has how often converter_function was called...
}

Это тривиальный пример того, как это сделать, но он должен показать вамспособ.

4 голосов
/ 29 марта 2010

В прямом с это на самом деле делается только с помощью функциональных указателей, которые являются болью и не предназначены для этого типа вещей (отчасти поэтому они и являются болью). Однако блоки (или замыкания, по словам не-Apple) фантастичны для этого. Они компилируются в gcc-4.x или что-то, и что-то в icc, но независимо от того, что вы ищете. К сожалению, я не могу найти ни одного хорошего учебника в Интернете, но достаточно сказать, что он работает примерно так: 

void iterate(char *str, int count, (^block)(str *)){
  for(int i = 0; i < count; i++){
    block(list[i]);
  }
}

main() {
  char str[20];
  iterate(str, 20, ^(char c){
    printf("%c ", c);
  });

  int accum = 0;
  iterate(someList, 20, ^(char c){
    accum += c;
    iterate(str, 20, ^(char c){
      printf("%c ", c);
    });
  });
}

очевидно, что этот код не имеет смысла, но он печатает каждый символ строки (str) с пробелом между ними, затем добавляет все символы вместе в целую, и каждый раз, когда это происходит, выводит список символов еще раз.

Надеюсь, это поможет. Кстати, блоки хорошо видны в Mac OS X Snow Leopard api-s, и я верю, что они соответствуют будущему стандарту C ++ 0x, так что они не так уж и необычны.

3 голосов
/ 29 марта 2010

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

2 голосов
/ 20 мая 2017

Это ответ на вопрос: как составлять функции в C, который перенаправлен сюда.

Вы можете создать структуру данных для реализации типа данных списка. эта структура может содержать указатели на функции. 

#include<stdlib.h>
#include<malloc.h>

typedef (*fun)();

typedef struct funList { fun car; struct funList *cdr;} *funList;

const funList nil = NULL;

int null(funList fs){ return nil==fs; }

fun car(funList fs)
{
   if(!null(fs)) return fs->car; 
   else 
   {
     fprintf(stderr,"error:can't car(nil) line:%d\n",__LINE__);
     exit(1);
   }
}

funList cdr(funList ls)
{ if(!null(ls)) return ls->cdr; 
  else 
  {
    fprintf(stderr,"error:can't cdr(nil) line:%d\n",__LINE__);
    exit(1);
  }
}

funList cons(fun f, funList fs)
{  funList ls;

   ls=(funList) malloc(sizeof(struct funList));
   if(NULL==ls)
   {
     fprintf(stderr,"error:can't alloc mem for cons(...) line:%d\n",__LINE__);
     exit(1);
   }

   ls->car=f;
   ls->cdr=fs;

   return ls;
}

мы можем написать функцию comp, которая применяет список функций: 

type_2 comp(funList fs, type_1 x)
{  
   return (null(fs)) ? x : car(fs)(comp(cdr(fs),x)); 
}

Пример того, как это работает. Мы используем (f g h) как короткую запись для cons (f, cons (g, cons (h, nil))), которая применяется к данному аргументу x: 

comp((f g h),x)

= 

f(comp((g h),x))

= 

f(g(comp((h),x)))

= 

f(g(h(comp(nil,x))))

= 

f(g(h(x)))

если вы использовали полиморфный тип списка в типизированном языке, таком как SML или Haskell, тип comp должен быть следующим: 

comp :: ([a -> a],a) -> a

потому что в этом контексте все члены в списке имеют одинаковый тип. С может быть более гибким в этом смысле. Может быть, что-то вроде 

typedef void (*fun)();

или 

typedef (*fun)();

вы должны увидеть, что руководство C говорит по этому поводу. И убедитесь, что все смежные функции имеют совместимые типы.

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

1 голос
/ 29 марта 2010

Это очень сложно сделать на прямом C. Это более возможно в C ++ (см. учебник по функторам или Boost bind и function библиотеки). Наконец, C ++ 0x добавляет встроенную поддержку лямбда-функций , которая заботится о том, чтобы вы захватывали при закрытии все переменные, от которых зависит ваша функция.

0 голосов
/ 29 марта 2010

Если вы хотите создать функции более высокого порядка, не используйте C. Есть решения C для вашей проблемы. Они могут быть не элегантными, или они могут быть более элегантными, как вы понимаете.

[Edit] Я предположил, что единственный способ достичь этого - использовать язык сценариев. Другие вызвали меня на это. Итак, я заменяю это предложение следующим: [/ Edit]

Чего ты пытаешься достичь? Если вы хотите имитировать замыкания, используйте язык, который их поддерживает (вы можете связать Ruby, lua, javascript и т. Д. С помощью библиотек). Если вы хотите использовать обратные вызовы, указатели функций в порядке. Функциональные указатели объединяют наиболее опасные области C (указатели и система слабого типа), поэтому будьте осторожны. Декларации указателей на функции тоже неинтересны.

Вы найдете некоторые библиотеки C, использующие указатели функций, потому что они должны. Если вы пишете библиотеку, возможно, вам тоже нужно их использовать. Если вы просто используете их в своем собственном коде, вы, вероятно, думаете не на языке C. Вы думаете на языке lisp, или в схеме, или на языке ruby, или ... и пытаетесь написать это на языке C. Изучите способ на C.

...