In the paper “Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages” by Simon Marlow and Simon Peyton Jones it is told that a PAP heap object may be created in the push/enter model (Figure 2. “The evaluation rules.” “Rules for push/enter.”). It is created “if there aren’t enough pending arguments on the stack.” I can't figure out an example of a type correct program which execution may lead to such a situation.
Functions can be partially applied, so you can end up with a situation in which a function is called with "not enough" arguments. For example, consider the
This will take a function
Then, if you map
You get a thunk (because this paper is about lazy evaluation). To force one of these thunks, you need to scrutinize the list to get its head, and then force the evaluation of the head by applying it:
Now, scrutinizing bar will get you
Now the result is the thunk
Consider the following lazy functional program:
A compiler can figure out that it doesn't need to build a thunk for
However, the following program shows some problem:
Here, the compiler will still generate strict code that enters either
For further reading, I would suggest Simon Peyton Jones's implementing functional languages: a tutorial. It illustrates, step by step, three ways to implement lazy functional programming language.