8

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?

Josh Lee
  • 171,072
  • 38
  • 269
  • 275
fuz
  • 88,405
  • 25
  • 200
  • 352
  • Do you understand closures (how lambda functions are implemented)? `(1+)` is just a shorter way of saying `(\ x -> 1 + x)`. – Jeremiah Willcock Apr 03 '11 at 18:36
  • Yes. But I want to know, how the compiler translates something like that into machine code / whatever. – fuz Apr 03 '11 at 18:37
  • 1
    If you're interested in this stuff, I highly recommend that you read [PLAI](http://www.cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/). While it's Scheme instead of Haskell, the core ideas are the same. Especially see Chapter 8: Implementing Laizness and pay attention to how they handle the `closureV` value type. – Dan Burton Apr 04 '11 at 04:58

3 Answers3

10

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.

Community
  • 1
  • 1
Don Stewart
  • 137,316
  • 36
  • 365
  • 468
7

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.

geekosaur
  • 59,309
  • 11
  • 123
  • 114
3

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

Thiago Arrais
  • 33,360
  • 7
  • 30
  • 34
  • Don't really know. I borrowed it from the local university library fivish years ago, but I don't think that's an option. Anyway, if you can get your hands on it, I highly recommend you to do so. It's a very light-weight text and a very good introduction to functional language implementation. – Thiago Arrais Apr 04 '11 at 17:16
  • 1
    It seems like there is an online version now that the book is out of print: http://research.microsoft.com/en-us/um/people/simonpj/Papers/pj-lester-book/ – Thiago Arrais Apr 04 '11 at 17:18
  • This book looks very interesting. I'm going to have a look at it. – fuz Apr 04 '11 at 18:12