È possibile avere funzioni di curry e variad allo stesso tempo?

13

Sto pensando di rendere le funzioni curry e variadiche sia disponibili in un linguaggio di programmazione funzionale tipizzato dinamicamente, ma mi chiedo se sia possibile o meno.

Ecco alcuni pseudocodici:

sum = if @args.empty then 0 else @args.head + sum @args.tail

che si suppone sommi tutti i suoi argomenti. Quindi, se sum stesso viene trattato con un numero, il risultato è 0 . ad esempio,

sum + 1

è uguale a 1, assumendo che + possa funzionare solo sui numeri. Tuttavia, anche sum == 0 è true, sum manterrà il suo valore e la proprietà funzionale indipendentemente dal numero di argomenti forniti (quindi "parzialmente applicati" e "variadic" allo stesso tempo), ad esempio, se dichiaro

g = sum 1 2 3

allora g equivale a 6 , tuttavia, possiamo ancora applicare ulteriormente g . Ad esempio, g 4 5 == 15 è true. In questo caso, non possiamo sostituire l'oggetto g con un valore letterale 6 , perché sebbene abbiano lo stesso valore quando trattati come un numero intero, contengono codici diversi all'interno.

Se questo design viene utilizzato in un linguaggio di programmazione reale, causerà confusione o ambiguità?

    
posta Michael Tsang 09.06.2015 - 10:13
fonte

3 risposte

6

Come possono essere implementati i vararg? Abbiamo bisogno di un meccanismo per segnalare la fine dell'elenco degli argomenti. Questo può essere

  • un valore terminatore speciale o
  • la lunghezza della lista vararg è passata come parametro extra.

Entrambi questi meccanismi possono essere utilizzati nel contesto del currying per implementare vararg, ma una corretta tipizzazione diventa un problema importante. Supponiamo di avere a che fare con una funzione sum: ...int -> int , tranne per il fatto che questa funzione utilizza il curring (quindi in realtà abbiamo un tipo più simile a sum: int -> ... -> int -> int , tranne per il fatto che non conosciamo il numero di argomenti).

Caso: valore terminatore: lascia che end sia il terminatore speciale e T sia il tipo di sum . Ora sappiamo che applicato a end la funzione restituisce: sum: end -> int , e che applicato a un int otteniamo un'altra funzione di somma: sum: int -> T . Pertanto T è l'unione di questi tipi: T = (end -> int) | (int -> T) . Sostituendo T , otteniamo vari tipi possibili come end -> int , int -> end -> int , int -> int -> end -> int , ecc. Tuttavia, la maggior parte dei sistemi di tipi non accetta tali tipi.

Caso: lunghezza esplicita: il primo argomento di una funzione vararg è il numero di vararg. Quindi sum 0 : int , sum 1 : int -> int , sum 3 : int -> int -> int -> int ecc. Questo è supportato in alcuni sistemi di tipi ed è un esempio di tipizzazione dipendente . In realtà, il numero di argomenti sarebbe un parametro di tipo e non un parametro regolare - non avrebbe senso che l'arità della funzione dipendesse da un valore di runtime, s = ((sum (floor (rand 3))) 1) 2 è ovviamente mal digitato: questo vale sia per s = ((sum 0) 1) 2 = (0 1) 2 , s = ((sum 1) 1) 2 = 1 2 o s = ((sum 2) 1) 2 = 3 .

In pratica, nessuna di queste tecniche dovrebbe essere utilizzata poiché è soggetta a errori e non ha un tipo (significativo) nei sistemi di tipi comuni. Invece, basta passare un elenco di valori come un parametro: sum: [int] -> int .

Sì, è possibile che un oggetto appaia sia come funzione che come valore, ad es. in un sistema di tipo con le coercizioni. Lascia che sum sia un SumObj , che ha due coercizioni:

  • coerce: SumObj -> int -> SumObj consente di utilizzare sum come funzione e
  • coerce: SumObj -> int ci consente di estrarre il risultato.

Tecnicamente, questa è una variazione del caso del valore terminatore sopra, con T = SumObj e coerce che è un non wrapper per il tipo. In molti linguaggi orientati agli oggetti, questo è banalmente implementabile con sovraccarico dell'operatore, ad es. C ++:

#include <iostream>
using namespace std;

class sum {
  int value;
public:
  explicit sum() : sum(0) {}
  explicit sum(int x) : value(x) {}
  sum operator()(int x) const { return sum(value + x); }  // function call overload
  operator int() const { return value; } // integer cast overload
};

int main() {
  int zero = sum();
  cout << "zero sum as int: " << zero << '\n';
  int someSum = sum(1)(2)(4);
  cout << "some sum as int: " << someSum << '\n';
}
    
risposta data 09.06.2015 - 11:58
fonte
2

Potresti dare un'occhiata a questa implementazione di printf in Haskell , insieme a questa descrizione di come funziona . C'è un link su quest'ultima pagina al documento di Oleg Kiselyov sul fare questo genere di cose, che vale anche la pena di leggere. In effetti, se stai progettando un linguaggio funzionale, il sito web di Oleg dovrebbe probabilmente essere una lettura obbligatoria.

Secondo me, questi approcci sono un po 'incisivi, ma mostrano che è possibile. Se la tua lingua è caratterizzata da una digitazione completa, tuttavia, è molto più semplice. Una funzione variadica per sommare i suoi argomenti interi potrebbe quindi assomigliare a questo:

type SumType = (t : union{Int,Null}) -> {SumType, if t is Int|
                                         Int,     if t is Null}
sum :: SumType
sum (v : Int) = v + sum
sum (v : Null) = 0

Un'astrazione per definire il tipo ricorsivo senza bisogno di dargli un nome esplicito potrebbe rendere più semplice la scrittura di tali funzioni.

Modifica: ovviamente, ho appena letto di nuovo la domanda e hai detto un linguaggio tipizzato dinamicamente , a quel punto ovviamente la meccanica del tipo non è veramente rilevante, e quindi la risposta di @ amon contiene probabilmente tutto hai bisogno. Oh bene, lascerò questo qui nel caso in cui qualcuno si imbatta in questo mentre ti chiedi come farlo in un linguaggio statico ...

    
risposta data 15.08.2016 - 10:04
fonte
0

Ecco una versione per la conversione di funzioni variadiche in Python3 che usa l'approccio "terminator" di @amon, sfruttando gli argomenti opzionali di Python:

def curry_vargs(g):
    actual_args = []
    def f(a, force=False):
        nonlocal actual_args
        actual_args.append(a)
        if force:
            res = g(*actual_args)
            actual_args = []
            return res
        else:
            return f
    return f

def g(*args): return sum(args)
f = curry_vargs(g)
f(1)(2)(3)(4,True) # => 10

La funzione restituita f raccoglie gli argomenti passati ad essa in chiamate successive in un array che è associato nello scope esterno. Solo quando l'argomento force è true, la funzione originale viene chiamata con tutti gli argomenti raccolti finora.

I caveat di questa implementazione sono che devi sempre passare un primo argomento a f in modo da non poter creare un "thunk", una funzione in cui tutti gli argomenti sono vincolati e possono essere chiamati solo con la lista di argomenti vuota (ma io pensate che questo è in linea con l'implementazione tipica di curry).

Un altro avvertimento è che una volta passato un argomento errato (ad esempio del tipo sbagliato) è necessario ri-curry la funzione originale. Non c'è altro modo per ripristinare l'array interno, questo viene fatto solo dopo aver eseguito con successo la funzione al curry.

Non so se la tua domanda semplificata, "può un oggetto essere una funzione e un valore non-funzione allo stesso tempo?", può essere implementata in Python, come riferimento a una funzione senza parentesi che valuta il oggetto funzione interna. Non so se questo può essere piegato per restituire un valore arbitrario.

Probabilmente sarebbe facile in Lisp, poiché i simboli Lisp possono avere un valore e un valore di funzione allo stesso tempo; il valore della funzione viene semplicemente selezionato quando il simbolo appare nella posizione della funzione (come il primo elemento in una lista).

    
risposta data 14.08.2016 - 20:20
fonte

Leggi altre domande sui tag