What is the difference between explicit parameters and closures

Question

In F#, a tail recursive List.filter function can be implemented like:

let filter f =
    let rec filterImpl f acc = function
        | [] -> List.rev acc
        | h :: t -> filterImpl f (if f h then h :: acc else acc) t
    filterImpl f []

But it can also be implemented by a closure (i.e. without passing f explicitly into filterImpl)

let filter f =
    let rec filterImpl acc = function
        | [] -> List.rev acc
        | h :: t -> filterImpl (if f h then h :: acc else acc) t
    filterImpl []

What is the difference and which is preferred in F# or functional programming in general?

Answer 1

From the compiler's point of view, there's very little difference between a closed over variable and a function argument. They are just given to the function's symbol table at different times.

In general you would prefer the closure version, because it is simpler, but if it were a longer function, or shared by other functions, you might want to pull it out and just accept the extra parameter.

Answer 2

Afaic, at least in C#, at least sometimes behind the scenes a class is generated to store captured variables in it's fields. It is a significant overhead compared to stack allocation to pass parameter directly.

As of C#, Raymond Chen has excellent explanation of closures:

When faced with this “hard” type of anonymous method, wherein variables are shared with the lexically-enclosing method, the compiler generates a helper class

Answer 3

A closure is generally implemented as some data structure mixing code (e.g. a pointer to a routine) and data (the closed data, or environment).

Imagine that you implement a F# to C compiler. Then a closure is translated to a struct mixing a function pointer with more data.

Queinnec's Lisp In Small Pieces book explains that well.

Pitrat's book Artificial Beings, the conscience of a conscious machine also explains that well.

The Dragon book also explains that.

See also the RefPerSys project, which generates C code and has closures too.