η-espansione in un linguaggio funzionale puro

Question

In OCaml, è legale avere in .mli:

val f : 'a -> 'a 
val g : 'a -> 'a 

e .ml:

let f x = x 
let g = f 

Eppure in F #, questa viene rifiutata:

eta_expand.ml(2,5): error FS0034: Module 'Eta_expand' contains 
    val g : ('a -> 'a)  
but its signature specifies 
    val g : 'a -> 'a  

The arities in the signature and implementation differ. The signature specifies that 'g' is function definition or lambda expression accepting at least 1 argument(s), but the implementation is a computed function value. To declare that a computed function value is a permitted implementation simply parenthesize its type in the signature, e.g. 
    val g: int -> (int -> int) 
instead of 
    val g: int -> int -> int. 

Una soluzione è quella di η-espandere la definizione di g:

let g x = f x 

Se il mio codice è puramente funzionale (senza eccezioni, senza effetti collaterali, ecc) questo dovrebbe essere equivalente (in realtà, potrebbe essere ancora migliore rispetto al polimorfismo, a seconda di come il linguaggio generalizza tipi: in OCaml le applicazioni parziali non producono funzioni polimorfiche, ma la loro espansione η lo fa).

Esiste qualche svantaggio nell'espansione η sistematica?

Due risposte eludono la domanda su η-expansion :-) e suggeriscono invece di aggiungere parentesi attorno al mio tipo funzionale. Questo perché, a quanto pare, F # si distingue a livello di digitazione tra la definizione "vera" di funzioni (come espressioni λ e definizioni calcolate, come nelle applicazioni parziali); presumibilmente perché le espressioni λ si mappano direttamente alle funzioni CLR mentre le definizioni calcolate mappano per delegare oggetti. (Non sono sicuro di questa interpretazione e apprezzerei se qualcuno molto familiare con F # potrebbe puntare a documenti di riferimento che descrivono questo.)

Una soluzione sarebbe quella di aggiungere sistematicamente parentesi a tutti i tipi di funzione nel .mli, ma Temo che questo potrebbe portare a inefficienze. Un altro sarebbe quello di rilevare le funzioni calcolate e aggiungere parentesi i tipi corrispondenti nel .mli. Una terza soluzione sarebbe quella di η-espandere i casi più ovvi e scegliere tra parentesi gli altri.

Non ho dimestichezza con gli interni F #/CLR per misurare quali sono le prestazioni significative o le penalità di interfaccia.

Answer 1

È interessante notare che la mia fsi dà un messaggio di errore più utili:

/test.fs(2,5): error FS0034: Module 'Test' contains 
    val g : ('a -> 'a) but its signature specifies 
    val g : 'a -> 'a The arities in the signature and implementation differ. 
      The signature specifies that 'g' is function definition or lambda expression 
      accepting at least 1 argument(s), but the implementation is a computed 
      function value. To declare that a computed function value is a permitted 
      implementation simply parenthesize its type in the signature, e.g. 
     val g: int -> (int -> int) instead of 
     val g: int -> int -> int. 

Se si aggiungono le staffe per ottenere g :('a -> 'a) tutto va bene

Answer 2

In teoria, la F # funzione di tipo 'a -> 'b -> 'c è dello stesso tipo di 'a -> ('b -> 'c). Cioè, le funzioni a più argomenti sono rappresentate usando la forma al curry in F #. Puoi usarne uno in cui l'altro è previsto nella maggior parte dei casi, ad es. quando si chiama una funzione di ordine superiore.

Tuttavia, per motivi pratici, il compilatore F # distingue effettivamente i tipi: la motivazione è che sono rappresentati in modo diverso nel codice .NET compilato. Questo ha un impatto sulle prestazioni e anche sull'interoperabilità con C#, quindi è utile fare questa distinzione.

Una funzione Foo : int -> int -> int sta per essere compilato come un membro int Foo(int, int) - il compilatore non utilizza il modulo curry per default, perché questo è più efficace quando si chiama Foo con entrambi gli argomenti (caso più comune) ed è meglio per interoperabilità .Una funzione Bar : int -> (int -> int) verrà compilata come FSharpFunc<int, int> Bar(int) - in realtà utilizzando il modulo al curry (e quindi è più efficiente chiamarla con un solo parametro e sarà difficile utilizzarla da C#).

Questo è anche il motivo per cui F # non considera i tipi come uguali quando si tratta di firme - la firma specifica il tipo, ma qui specifica anche come deve essere compilata la funzione. Il file di implementazione deve fornire la funzione del tipo giusto, ma, in questo caso, anche del modulo compilato corretto.