Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

η-expansion in a pure functional language

In OCaml, it is legal to have in .mli:

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

and .ml:

let f x = x
let g = f

Yet in F#, this is rejected:

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.

One workaround is to η-expand the definition of g:

let g x = f x

If my code is purely functional (no exceptions, no side effects, etc.) this should be equivalent (actually, it might be even better with respect to polymorphism, depending on how the language generalizes types : in OCaml partial applications do not produce polymorphic functions, but their η-expansion does).

Is there any drawback to systematic η-expansion?

Two answers elude the question on η-expansion :-) and instead suggest that I add parentheses around my functional type. This is because, apparently, F# distinguishes at the typing level between "true" definition of functions (as λ-expressions and computed definitions, as in partial applications); presumably this is because λ-expressions directly map to CLR functions while computed definitions map to delegate objects. (I'm not sure of this interpretation and would appreciate if somebody very familiar with F# could point to reference documents describing this.)

A solution would be to systematically add parentheses to all the function types in .mli, but I fear this could lead to inefficiencies. Another would be to detect the computed functions and add parenthesize the corresponding types in the .mli. A third solution would be to η-expand the obvious cases, and parenthesize the others.

I'm not familiar enough with F# / CLR internals to measure which ones incur significant performance or interfacing penalties.

like image 636
David Monniaux Avatar asked Apr 05 '13 08:04

David Monniaux


1 Answers

In theory, the F# function type 'a -> 'b -> 'c is the same type as 'a -> ('b -> 'c). That is, multiple argument functions are represented using the curried form in F#. You can use one where the other is expected in most cases e.g. when calling a higher-order function.

However, for practical reasons, F# compiler actually distinguishes between the types - the motivation is that they are represented differently in the compiled .NET code. This has impact on performance and also interoperability with C#, so it is useful to make that distinction.

A function Foo : int -> int -> int is going to be compiled as a member int Foo(int, int) - the compiler does not use the curried form by default, because this is more efficient when calling Foo with both arguments (more common case) and it is better for interop. A function Bar : int -> (int -> int) will be compiled as FSharpFunc<int, int> Bar(int) - actually using the curried form (and so it is more efficient to call it with just a single parameter and it will be hard to use from C#).

This is also why F# does not treat the types as equal when it comes to signatures - signature specifies the type, but here it also specifies how is the function going to be compiled. The implementation file has to provide function of the right type, but - in this case - also of the right compiled form.

like image 164
Tomas Petricek Avatar answered Oct 09 '22 17:10

Tomas Petricek