Definizione della funzione generica

0

1)

Di seguito è una funzione python summation , che può eseguire la somma di cubi / quadrati / .., operazioni simili .

def identity(k):
    return k

def cube(k):
    return pow(k, 3)

def square(k):
    return pow(k,2)

def summation(n, term):
    if n == 0:
        return 0
    else:
        return term(n) + summation(n-1, term)

def sum_cubes(n):
    return summation(n, cube)

if __name__ == '__main__':
    sum = sum_cubes(4)
    print(sum)

 """ In C, We can implement the same using function pointers. Goal is, to    
    perform similar operations(Sum of ..) using single function summation()"""  

2)

Considera, sotto l'ordinamento delle API da C,

void qsort(void *base, size_t nmemb, size_t size,
                            int (*compar)(const void *, const void *));

Qui, qsort può ordinare dati di qualsiasi tipo , array di float / nomi di file in una directory / stringhe /...

Domanda:

Come definire una funzione generica?

summation è una funzione generica?

o

qsort è una funzione generica?

o

Dati due esempi, la funzione generica è una terminologia non valida?

Nota: motivazione-a termine qsort o qualsiasi funzione di ordinamento che disegno

    
posta overexchange 17.12.2016 - 18:13
fonte

3 risposte

1

Ci sono diversi significati per "generico".

Definizione informale

"generico" nel linguaggio corrente qualcosa che condivide le proprietà comuni ma è in qualche modo meno specifico.

In questa prospettiva, potresti considerare qsort() come generico: il codice di questa funzione è in grado per ordinare qualsiasi struttura dati a dimensione fissa per la quale è possibile definire una funzione di confronto utilizzando l'algoritmo QSORT.

Lo stesso vale per la tua funzione summation() , che riassume i termini ottenuti utilizzando qualsiasi funzione con un parametro.

Definizione formale

I linguaggi di programmazione come C ++ o Java consentono la programmazione generica con l'uso di modelli o generici:

Definition from the C++14 standard: A template defines a family of classes or functions or an alias for a family of types.

Il principio è che una classe o un'implementazione di una funzione può essere parametrizzata dai tipi.

Secondo questo punto di vista più formale, qsort() non è una funzione generica. La sua implementazione non ha bisogno di determinare alcun tipo nella compilazione e il suo comportamento è di tipo indipendente. L'unica cosa di cui ha bisogno è la dimensione degli elementi ordinati, e questa dimensione è un argomento ordinario che viene elaborato in fase di esecuzione.

Per una lingua che non è tipizzata staticamente come Python , non sono sicuro su cosa rispondere per summation() . Penso che non sia generico perché la sua implementazione e il suo comportamento non dipendono dal tipo: questa funzione è solo una funzione di ordine superiore, con l'argomento term che è una funzione. Non usa alcuna funzione che altererebbe il comportamento di questa funzione in base ai tipi.

Per illustrare una funzione generica, puoi dare un'occhiata alla funzione standard C ++ std::sort() : la sua implementazione dipende dal tipo dei suoi argomenti (e opzionalmente una funzione di confronto con argomenti di un tipo determinato). Utilizzando le funzionalità dei modelli C ++, può ordinare qualsiasi contenitore di qualsiasi tipo, a condizione che abbia gli operatori / funzioni / tratti / iteratori richiesti dall'implementazione della funzione generica.

Un linguaggio digitato dinamico può avere funzioni generiche

Il linguaggio digitato dinamicamente richiede un codice meno generico rispetto alle lingue tipizzate in modo statico.

Ad esempio, se si dispone di un contenitore di oggetti di tipo dinamico, una funzione qsort può ordinare genericamente il contenitore, purché sia possibile confrontare qualsiasi combinazione di due elementi nel contenitore.

Ma anche in un ambiente così flessibile, la programmazione generica di tipo dipendente può essere utile. Il caso d'uso tipico è multimethods, in cui il comportamento o il codice dipende dal tipo di argomenti o anche dalla combinazione di tipi (come per determinare l'intersezione tra due forme diverse). Per ulteriori informazioni vedi:

risposta data 17.12.2016 - 19:26
fonte
2

Le funzioni generiche prendono il tipo di almeno un argomento di funzione genericamente al momento della compilazione. Cioè, il compilatore scopre quale tipo è usato in un certo posto e applica esattamente questo tipo dove è usato nella funzione. Per esempio. se nella tua funzione hai un argomento generico che viene utilizzato con un operatore + , il tipo deve disporre di metodi appropriati. Per stringhe / array questo sarebbe in molti casi una concatenazione e per e un intero / float un'aggiunta. Il compilatore può rilevare che si applica l'operazione corretta. La routine C non è generica in questo senso, poiché è il programmatore che applica alcune informazioni sulla dimensione e non il compilatore che rileva il tipo e utilizza la dimensione corretta.

es. in qualche linguaggio fittizio

func add(p1,p2) {
  return p1+p2
}

print add("a", "b") // yields "ab"
print add(1, 2) // yields 3

Qui il compilatore rileva nel primo caso che vengono applicate due stringhe e si espanderà internamente qualcosa come

func add(p1:string, p2:string) 

e considera + come concatenazione mentre nel secondo caso si espande

func add(p1:int, p2:int)

come da parametri interi forniti. Mezzi generici, il compilatore genera un codice individuale durante la compilazione. Python ad esempio non è tipizzato e farebbe quel tipo di sostituzione durante il runtime. Mezzi: Python non ha funzioni generiche poiché tutto è un po 'generico.

    
risposta data 17.12.2016 - 18:31
fonte
-1

Ho intenzione di iniziare questo dal punto di vista del C ++, quindi passare a C.

In linguaggi tipizzati staticamente come C, C ++, Java, ecc., una funzione "generica" consente di specificare le operazioni della funzione una volta , utilizzando segnaposto per qualsiasi tipo che può variare tra chiamate diverse (il che significa che funzioni come qsort e bsearch sono più decisamente non funzioni generiche). Idealmente, ti piacerebbe anche che il compilatore rilevasse automaticamente tutte le chiamate a questa funzione generica e generasse il codice reale, se necessario.

C ++ semplifica 1 offrendo modelli :

template <typename T>
T summation( T *values, size_t numValues )
{
  T result = 0;
  for ( size_t i = 0; i < numValues; i++ )
    result += values[i];
  return result;
}

T è un segnaposto per qualsiasi tipo 2 , quindi puoi chiamarlo come

int ivals[]    = {1,2,3,4,5,6,7,8,9};
double dvals[] = {1,2,3,4,5,6,7,8,9};

int sumi    = summation( ivals, 10 );
double sumd = summation( dvals, 10 );

Quando il codice è compilato, il compilatore vede le due chiamate su summation e deduce i tipi degli argomenti. Per ogni tipo diverso, genera una nuova istanza della funzione, dandole un nome univoco:

int summation_i( int *values, size_t numValues )  // actual compilers will generate
{                                                 // more complex "mangled" names
  int result = 0;                                 // than this
  ...
}

double summation_d( double *values, size_t numValues )
{
  double result = 0;
  ...
}

Quindi genera codice tale che il risultato di summation_i è assegnato a sumi e summation_d è assegnato a sumd .

C non offre nulla di simile alla funzione modello. Tradizionalmente, abbiamo attaccato la programmazione generica in due modi: utilizzando macro o utilizzando void * ovunque e delegando operazioni di tipo aware ad altre funzioni.

Ecco un cattivo esempio di una soluzione basata su macro:

#include <stdio.h>

#define SUMMATION_DEF(t) \
t summation_##t( t *values, size_t numValues ) \
{                                              \
  t result = 0;                                \
  for ( size_t i = 0; i < numValues; i++ )     \
    result += values[i];                       \
  return result;                               \
}

#define SUMMATION(t,x,s)  summation_##t(x, s)

SUMMATION_DEF(int)
SUMMATION_DEF(double)

int main( void )
{
  int ivals[] = {1, 2, 3, 4, 5};
  double dvals[] = {1, 2, 3, 4, 5};

  int sumi = SUMMATION(int, ivals, 5);
  double sumd = SUMMATION(double, dvals, 5);

  printf( "sumi = %d\n", sumi );
  printf( "sumd = %f\n", sumd );

  return 0;
}

Il SUMMATION_DEF è approssimativamente simile a un modello in quanto specifica le operazioni della funzione, utilizzando il parametro macro t come segnaposto di tipo. Usiamo anche t come parte del nome della funzione - il ## è l'operatore che incolla i token, e il preprocessore espanderà t e aggiungerà quel valore al nome della funzione 3 .

Il punto in cui differisce dal C ++ è il fatto che una macro è solo una stupida sostituzione del testo. Non attiva alcuna operazione speciale sulla parte del compilatore. Le istanze della funzione effettiva non vengono generate automaticamente in base a qualsiasi richiamo della macro SUMMATION : dobbiamo generare in modo esplicito le funzioni che vogliamo (quindi SUMMATION_DEF(int) e SUMMATION_DEF(double) prima di main ). Significa anche che quando chiamiamo summation_xxx attraverso la macro SUMMATION , dobbiamo passare il tipo come parte dell'elenco di argomenti macro, in modo tale che venga chiamata la funzione giusta. Che dolore.

Lo standard C 2011 ha aggiunto la parola chiave _Generic , che può semplificare la vita a tale riguardo:

#include <stdio.h>

#define SUMMATION_DEF(t) \
t summation_##t( t *values, size_t numValues ) \
{                                              \
  t result = 0;                                \
  for ( size_t i = 0; i < numValues; i++ )     \
    result += values[i];                       \
  return result;                               \
}

#define SUMMATION(x,s)  _Generic((x),                         \
                                 int *     : summation_int,   \
                                 double *  : summation_double \
                                )(x, s)

SUMMATION_DEF(int)
SUMMATION_DEF(double)

int main( void )
{
  int ivals[] = {1, 2, 3, 4, 5};
  double dvals[] = {1, 2, 3, 4, 5};

  int sumi = SUMMATION(ivals, 5);
  double sumd = SUMMATION(dvals, 5);

  printf( "sumi = %d\n", sumi );
  printf( "sumd = %f\n", sumd );

  return 0;
}

La parola chiave _Generic ti consente di valutare espressioni basate su tipi ; quindi, se il tipo del primo argomento a SUMMATION è int * , chiamiamo summation_int ; è double * , chiamiamo summation_double . In questo modo non dobbiamo specificare il nome del tipo negli argomenti della macro.

L'altro approccio, come hai visto, è utilizzare void * e delegare le operazioni di tipo aware ad altre funzioni. Come ho detto sopra, non si tratta di una programmazione veramente "generica", poiché è necessario implementare manualmente ciascuna funzione di confronto per ciascun tipo. Non puoi semplicemente codificarlo una volta e averlo fatto. E usando void * , in pratica getti la sicurezza del tipo fuori dalla finestra e nel traffico in arrivo.

E prima che qualcuno si lamenti - no, nessuna di queste funzioni di sommatoria verifica o gestisce l'overflow aritmetico. Questo è un argomento per un altro giorno.

  1. Per le definizioni sufficientemente sciolte di "facile". Il linguaggio di metaprogrammazione utilizzato per supportare i modelli è completo di Turing, quindi puoi fare * incredibilmente * e impossibile capire le cose con esso.
  2. Per le definizioni sufficientemente allentate di "qualsiasi tipo". Nota che qualunque sia il tipo che usi deve supportare l'operatore += , altrimenti il compilatore ti urlerà contro.
  3. Questo codice sarà interrotto per tipi come unsigned int o long double poiché hanno spazi bianchi nel nome. Non conosco immediatamente la soluzione a questo problema e ho dedicato abbastanza tempo a questa risposta.

risposta data 20.12.2016 - 18:28
fonte

Leggi altre domande sui tag