Funzioni di ordine superiore in C come zucchero sintattico con il minimo sforzo

Question

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

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?

Answer 1

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.

Answer 2

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.