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

StackOverflow https://stackoverflow.com/questions/2535631

Вопрос

Существует ли «правильный» способ реализации функций более высокого порядка в C.

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

Редактировать:Причина, по которой я хочу знать, как создавать функции более высокого порядка, заключается в том, что я написал систему для преобразования списков 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.Мне бы очень хотелось сохранить стиль функций более высокого порядка, но если это не одобряется, я очень ценю способы сделать это другим способом.

Это было полезно?

Решение

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

[РЕДАКТИРОВАТЬ]:Чтобы использовать/адаптировать ваш пример:

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

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

Другие советы

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

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

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

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

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) с пробелом между ними, затем складывает все символы вместе в accum, и каждый раз, когда это происходит, он снова распечатывает список символов.

Надеюсь это поможет.Между прочим, блоки очень заметны в API-интерфейсах Mac OS X Snow Leopard, и я полагаю, что они появятся в будущем стандарте C++0x, так что на самом деле они не так уж необычны.

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

Это ответ на вопрос:как составлять функции на 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

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

typedef void (*fun)();

или

typedef (*fun)();

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top