2013-01-04 9 views
6

Desidero implementare le funzioni di ordine superiore (HOF) in C come zucchero sintattico con il minimo sforzo. Ad esempio, il codice seguenteFunzioni di ordine superiore in C come zucchero sintattico con il minimo sforzo

function add(int x) { 
    return int(int y) { 
    return x + y; 
    }; 
} 

int main() { 
    function add1 = add(1); 
    return add1(2); 
} 

è transcompiled in puro C come

#include <stdlib.h> 

typedef struct { 
    void *ctx; 
    void* (*fun)(void *arg, void *ctx); 
} function; 

function new_function(void *ctx, void* (*fun)(void *, void *)) { 
    function f = {.ctx=ctx, .fun=fun}; 
    return f; 
} 

void* apply(function f, void *arg) { 
    return (*(f.fun))(arg, f.ctx); 
} 

typedef struct { 
    int x; 
} context$1; 

void* new_context$1(int x) { 
    context$1 *ctx = malloc(sizeof(context$1)); 
    ctx->x = x; 
    return ctx; 
} 

void* function$1(void *arg, void *ctx) { 
    int y = (int)arg; 
    int x = ((context$1*)ctx)->x; 
    return (void*)(x + y); 
} 

function add(int x) { 
    return new_function(new_context$1(x), function$1); 
} 

int main() { 
    function add1 = add(1); 
    return (int)apply(add1, (void*)2); 
} 

Ho eseguire questa versione (manualmente) transcompiled e funziona bene. Per l'implementazione, credo che alcune manipolazioni AST e il sollevamento di lambda sarebbero sufficienti.

Ci sono dei potenziali difetti nel mio approccio? Esistono metodi più semplici per HOF o posso migliorare il mio approccio per renderlo più facile da implementare?

risposta

2

Ci sono due problemi evidenti per ora:

  • Uso nulli * per rappresentare i parametri e restituire valori di qualsiasi tipo finirà per rompersi. Considerare i parametri "long long" su ia-32 o qualsiasi struttura passata per valore.
  • È difficile (se possibile) rendere più utili le funzioni di ordine superiore senza garbage collection. Puoi vederlo dal tuo esempio in cui il contesto $ 1 è mallocizzato ma mai liberato. Boehm GC può aiutare qui.
+0

Sono totalmente d'accordo con il tuo secondo punto e +1 per Boehm GC :-). Ma potrebbe per favore istruirmi come si annullerebbe alla fine?Credo che funzionerebbero bene perché sono generati automaticamente. –

+0

@XiaoJia: il problema con 'void *' è in 'function $ 1'. Cosa succede se il tipo di 'x + y' è più grande di' void * '? In questo esempio significherebbe 'sizeof (int)> sizeof (void *)', che sarebbe una strana implementazione in C, ma non così strano se 'x' avesse tipo' long long' invece di 'int'. Quindi il cast di "void *" perde informazioni. –

+0

Beh, puoi sempre dire che il tuo traduttore automatico si prenderà cura di esso in qualche modo (purché tu non descriva l'algoritmo ma fornisca solo una traduzione di esempio). Ma guardo (void *) 2 e vedo che perderebbe informazioni se ci fosse un valore più ampio del pointer invece di 2. (E il cast verso/da void * non funzionerebbe affatto per le strutture passate per valore; ti stai rifiutando di supportarli o tradurrai tali funzioni in modo diverso?) –

1

Si noti che il codice generato richiama il comportamento non definito. In diversi punti, stai convertendo tra tipi interi e tipi di puntatore tramite cast diretto. Questo non è legale in C. Non si ha alcuna garanzia che un puntatore e un int abbiano la stessa dimensione o che si possa persino effettuare il cast tra di essi senza alterare o corrompere il valore. Il codice potrebbe funzionare sul tuo particolare sistema per coincidenza, ma si romperà su molti altri sistemi.

L'unico modo per gestire genericamente sia i puntatori che i tipi di integrale (oltre alle strutture) è quello di passare i parametri utilizzando liste di argomenti a lunghezza variabile. In questo modo, puoi estrarre ogni argomento indipendentemente dalla dimensione del tipo di dati sottostante.

Un'altra opzione è quella di eliminare la struttura generica function e creare una struttura personalizzata per ogni HOF nel codice. Il puntatore della funzione potrebbe quindi elencare direttamente tutti i parametri necessari invece di provare ad astrarli dietro un'interfaccia generica, eliminando i cast problematici e consentendo al codice di funzionare come previsto indipendentemente dai tipi di dati utilizzati.

Per quanto riguarda l'usabilità va, potresti cambiare l'interfaccia in modo che sia specificato il tipo di ritorno della HOF (o almeno quotata) sulla riga in cui si è dichiarata. Gli oggetti C elencano sempre il loro tipo nella dichiarazione. Nel tuo esempio, la dichiarazione è function add1 = add(1);. Per scoprire quale tipo di dati restituisce questa funzione, devi scavare attraverso la definizione per l'HOF. Questo non è un compito difficile per il tuo codice di esempio, ma questo potrebbe essere non banale per codice più complesso. Potresti non avere alcun codice per l'HOF se proviene da una biblioteca. Forse qualcosa come function(int) add1 = add(1); potrebbe essere più esplicito.

In una nota a margine, si consiglia di definire le funzioni generate automaticamente come static per impedire le collisioni tra i moduli.

+0

Commento molto utile. Grazie! Cercherò di aggiornare la mia strategia per la traduzione. –