How is a partial application represented at runtime?

Question

When I write something like map (1+) list in Haskell, what is the internal representation of (1+)? Since it is a partial application of (+), the argument 1 has to be saved somewhere, but I can't get my head around this. Can somebody give me a brief explanation, how currying and partial application is implemented?

Answer 1

You may also want to check out Implementing Functional Languages: A Tutorial, a book by Simon Peyton Jones and David Lester.

Answer 2

Partially applied functions (and, indeed, pretty much everything else in the Haskell heap) are represented as closures -- a structure combining a code pointer, and argument slots. Specifically, we call values that are not in a fully evaluated form thunks.

See this earlier question on boxed data and the GHC manual on how thunks are represented.

Answer 3

Think of it this way: everything is represented by a chunk of code (a "thunk") that has to be invoked directly to get a result. When you write a literal 1, it gets compiled to a chunk of code that returns 1 (actually, fromIntegral 1) when invoked, and that chunk of code is then used in place of the literal 1. This is also key to laziness: instead of calculating something immediately, a thunk is created that when invoked will do the calculation. If you pass that expression to another function, it's the wrapper thunk that's passed, and so the calculation doesn't happen until/unless something needs to explicitly examine its result.

In Haskell, function applications are represented the same way: a thunk that processes one parameter and returns a thunk that either processes the next parameter or produces the result. So (1+) is the function application (+) 1: (+) is a thunk that expects to be passed a single number and returns a thunk that expects to be passed another single number. Since (+) is strict, that second thunk actually does the addition instead of returning a thunk that has to be invoked to do the actual addition. So (1+) evaluates to that second thunk, which needs to be invoked with another number which will be supplied by map as it iterates over list.