Why do we need PAP (partial aplication) objects in heap?
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 map functional:

(* map : ∀α,β. (α → β) → list α → list β *)
let rec map f xs = 
  match xs with 
  | []      -&gt; []
  | x :: xs -&gt; (f x) :: map f xs


This will take a function f as an argument, and then pass it one argument, once for each element of the list. Now, consider a two argument function foo:

(* val foo : int → int → int *)
let foo x y = 2*x + y 


Then, if you map foo over a list of integers:

(* val bar : list (int → int → int) *)
let bar = map foo [1; 2; 3]


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:

 let baz = match bar with
           | f :: fs -&gt; f 6 


Now, scrutinizing bar will get you f bound to THUNK (foo 1), and fs bound to map foo [2;3]. Then, to apply f 6, we first evaluate foo 1. This pushes 1 on the stack, and since foo is really a two-argument function, foo 1 will not evaluate further -- it will return a fresh p, bound to PAP(foo 1). 

Now the result is the thunk THUNK(p 6) -- to drive evaluation further, you have to demand this thunk.