Funções de ordem superior em C

https://stackoverflow.com/questions/2535631

22-09-2019
|

Pergunta

Existe uma maneira "correta" de implementar funções de ordem superior em C.

Estou mais curioso sobre coisas como portabilidade e correção de sintaxe aqui e se há mais de uma maneira, quais são os méritos e falhas.

Editar:A razão pela qual quero saber como criar funções de ordem superior é que escrevi um sistema para converter listas PyObject (que você obtém ao chamar scripts python) em uma lista de estruturas C contendo os mesmos dados, mas organizadas de uma forma que não depende de as bibliotecas python.h.Portanto, meu plano é ter uma função que itere através de uma lista pythônica e chame uma função em cada item da lista e coloque o resultado em uma lista que ela retorna.

Então este é basicamente o meu plano:

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

E para esclarecer a questão:Quero saber como fazer isso em C mais seguro e correto.Eu realmente gostaria de manter o estilo de função de ordem superior, mas se isso for desaprovado, aprecio muito as maneiras de fazer isso de outra maneira.

Solução

Se você estiver interessado em fazer isso na lisão C, precisa se lembrar de incluir a opção de passar em um ponteiro de contexto do chamador do functor (a função de ordem superior) para a função aprovada. Isso permite simular o suficiente de um fechamento que você pode fazer com que as coisas funcionem com bastante facilidade. O que esse ponteiro aponta para ... bem, isso depende de você, mas deve ser um void* na API do functor (ou um dos muitos aliases, como gpointer no mundo glib ou ClientData na API TCL C).

Editar]: Para usar/adaptar seu exemplo:

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

Este é um exemplo trivial de como fazê -lo, mas deve mostrar o caminho.

Outras dicas

Tecnicamente, as funções de ordem superior são apenas funções que recebem ou devolvem funções. Então, coisas como o QSORT já são de alta ordem.

Se você quer dizer algo mais parecido com as funções Lambda encontradas em idiomas funcionais (que é onde as funções de ordem superior realmente se tornam úteis), essas são um pouco mais difíceis e não podem ser feitas naturalmente no padrão atual C. Simplesmente não são parte de o idioma. A extensão dos blocos da Apple é o melhor candidato. Ele funciona apenas no GCC (e no compilador C da LLVM), mas eles são realmente úteis. Esperançosamente, algo assim vai pegar. Aqui estão alguns recursos relevantes:

Documentação da Apple sobre o recurso (Referências algumas tecnologias específicas da Apple e também aborda o Objective-C, mas o material do bloco principal faz parte de sua extensão para c)
Aqui está uma boa introdução em blocos
Cacau para a visão geral dos cientistas dos blocos C

O grande problema com a implementação de funções de ordem superior em C é que para fazer qualquer coisa não trivial você precisa de encerramentos, que são ponteiros de função aumentados com estruturas de dados contendo variáveis locais às quais eles têm acesso.Como a ideia por trás dos encerramentos é capturar variáveis locais e passá-las junto com o ponteiro de função, é difícil fazer isso sem o suporte do compilador.E mesmo com o suporte do compilador é difícil dispensar a coleta de lixo porque variáveis podem existir fora de seu escopo, tornando difícil descobrir quando liberá-las.

Em C Straight C, isso realmente é feito apenas por meio de ponteiros de função, que são uma dor e não destinados a esse tipo de coisa (e é parcialmente por isso que eles são uma dor). Os blocos (ou fechamentos, de acordo com não apple) são fantásticos para isso. Eles compilam no GCC-4.x ou algo assim, e a ICC algo, mas independentemente é isso que você está procurando. Infelizmente, não consigo encontrar bons tutoriais on -line, mas basta dizer que funciona algo assim:

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

Obviamente, esse código é inútil, mas imprime cada caractere de uma string (str) com um espaço entre ele, depois adiciona todos os caracteres no Accum e, toda vez que ele imprime, imprime a lista de caracteres novamente.

Espero que isto ajude. A propósito, os blocos são muito visíveis no Mac OS X Snow Leopard API-S, e acredito que estão no próximo padrão C ++ 0x, para que eles não sejam realmente tão incomuns.

Praticamente qualquer aplicativo de função de ordem superior interessante requer fechamentos, que em C implica a rotina trabalhista e propensa a incorreção de argumentos de função de definição e preenchimento manualmente.

Esta é uma resposta à pergunta:como compor funções em C, que é redirecionado aqui.

Você pode criar uma estrutura de dados para implementar um tipo de dados de lista.essa estrutura pode conter ponteiros de função.

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

podemos escrever uma função comp que aplica uma lista de funções:

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

Um exemplo de como funciona.Usamos (f g h) como uma notação curta para cons(f,cons(g,cons(h,nil))), que é aplicada a um determinado argumento 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)))

se você tivesse usado o tipo de lista polimórfica em uma linguagem digitada como SML ou Haskell, o tipo de comp deveria ser:

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

porque nesse contexto todos os membros de uma lista têm o mesmo tipo.C pode ser mais flexível nesse sentido.Talvez algo como

typedef void (*fun)();

typedef (*fun)();

você deve ver o que o manual C diz sobre isso.E certifique-se de que todas as funções contíguas tenham tipos compatíveis.

As funções a compor devem ser puras, ou seja,sem efeitos colaterais nem variáveis livres.

É muito difícil fazer em C direto.É mais possível em C++ (veja tutorial de funtores ou Boost's vincular e função bibliotecas).Finalmente, C++0x adiciona suporte nativo para funções lambda, que se encarrega de capturar no fechamento todas as variáveis das quais sua função depende.

Se você deseja criar funções de ordem superior, não use C. Existem soluções C para o seu problema. Eles podem não ser elegantes, ou podem ser mais elegantes que você percebe.

Editar] Sugeri que a única maneira de conseguir isso era usar uma linguagem de script. Outros me chamaram. Então, estou substituindo essa sugestão por isso: [/edit

O que você está tentando alcançar? Se você deseja imitar o fechamento, use um idioma que os suporta (você pode amarrar rubi, lua, javascript, etc por meio de bibliotecas). Se você deseja usar retornos de chamada, os ponteiros da função estão OK. Os ponteiros da função combinam as áreas mais perigosas de C (ponteiros e o sistema de tipo fraco), portanto, tenha cuidado. As declarações de ponteiro da função também não são divertidas de ler.

Você encontra algumas bibliotecas C usando ponteiros de função porque eles precisam. Se você está escrevendo uma biblioteca, talvez você precise usá -los também. Se você está apenas usando -os em seu próprio código, provavelmente não está pensando em C. Você está pensando em Lisp ou esquema ou rubi ou ... e tentando escrevê -lo em C. Aprenda o caminho C.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow