<p>Functions can be <em>partially applied</em>, so you can end up with a situation in which a function is called with "not enough" arguments. For example, consider the <code>map</code> functional:</p>

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

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

<pre><code>(* val foo : int → int → int *)
let foo x y = 2*x + y 
</code></pre>

<p>Then, if you map <code>foo</code> over a list of integers:</p>

<pre><code>(* val bar : list (int → int → int) *)
let bar = map foo [1; 2; 3]
</code></pre>

<p>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:</p>

<pre><code> let baz = match bar with
           | f :: fs -&gt; f 6 
</code></pre>

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

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

CC BY-SA 3.0
2012-11-29T14:07:43.660Z
This example is not relevant. “(f x) :: map f xs” normalizing ==> “let fx = f x in fx :: map f xs”. “Let” creates a heap object and does not read or write stack at all. So the condition “if there aren’t enough pending arguments on the stack” is meaningless. And we only know that “f” has at least 1 argument. 1 argument is full application, 2 or 3 arguments is partial application. We don't know if this is a partial application.
beroal
CC BY-SA 3.0
2012-11-29T14:10:12.853Z
Besides, there is no “function call” in push/enter. There is only “enter”.
beroal
CC BY-SA 3.0
2012-11-29T19:42:46.790Z
Sorry, I forgot about laziness -- I added a small bit at the end to force evaluation, so that you can see when the partial application objects are constructed.
Neel Krishnaswami
CC BY-SA 3.0
2012-11-30T12:43:55.053Z
Actually, you are describing “eval/apply” because you are evaluating “f” in “f 6”. When using “push/enter”, “f 6” does: push 6, enter f = THUNK (foo 1), push 1, enter foo. No PAP. Still looking for an answer… (P.S. IMHO the “map” with its big definition is not important here.)
beroal
CC BY-SA 3.0
2012-11-29T13:52:21.237Z
2012-11-29T19:43:03.887Z
2012-11-29T19:43:03.887Z
Neel Krishnaswami
<p>Consider the following lazy functional program:</p>

<pre><code>doArith :: Int -&gt; Int
doArith n = if n &lt; 0 then 1 + 2 else 3 - 4
</code></pre>

<p>A compiler can figure out that it doesn't need to build a thunk for <code>1 + 2</code> or <code>3 - 4</code> in the <code>if</code> expression. This is because that an <code>if</code> expression is strict in the branch position, since either <code>1 + 2</code> or <code>3 - 4</code> will surely be evaluated after evaluating <code>n &lt; 0</code>. In this way, the compiler can generate better code while still preserving the lazy semantics.</p>

<p>However, the following program shows some problem:</p>

<pre><code>getFunction :: Int -&gt; Int -&gt; Int
getFunction n = if n &lt; 0 then (+) 1 else (-) 2
</code></pre>

<p>Here, the compiler will still generate strict code that enters either <code>(+)</code> or <code>(-)</code> with only one argument. But <code>(+)</code> or <code>(-)</code> require two arguments... So here comes the PAp object.</p>

<p>For further reading, I would suggest Simon Peyton Jones's <a href="http://research.microsoft.com/en-us/um/people/simonpj/papers/pj-lester-book/" rel="nofollow">implementing functional languages: a tutorial</a>. It illustrates, step by step, three ways to implement lazy functional programming language.</p>

CC BY-SA 3.0
2013-09-24T21:18:11.950Z
“A compiler can figure out that it doesn't need to build a thunk for 1 + 2” In the push/enter model, a compiler does not build a thunk for 1 + 2. It pushes 1, 2, then enters (+).
beroal
CC BY-SA 3.0
2013-01-08T14:07:54.510Z
2013-01-08T14:07:54.510Z
Overmind Jiang
<p>In the paper <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=67488">“Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages”</a> 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.</p>

<pl.programming-languages><functional-programming><machine-models><compilers>
Why do we need PAP (partial aplication) objects in heap?
beroal
# Why do we need PAP (partial aplication) objects in heap?

(Asked by: username_0 on 2012-11-29)

In the paper [“Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order Languages”](http://research.microsoft.com/apps/pubs/default.aspx?id=67488) 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.

**Tags:** pl.programming-languages, functional-programming, machine-models, compilers


---

## 2 answers

### Answer by username_1 on 2012-11-29. Score: 4

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 
  | []      -> []
  | x :: xs -> (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 -> 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.

> **Comments:**
> **username_0**: This example is not relevant. “(f x) :: map f xs” normalizing ==> “let fx = f x in fx :: map f xs”. “Let” creates a heap object and does not read or write stack at all. So the condition “if there aren’t enough pending arguments on the stack” is meaningless. And we only know that “f” has at least 1 argument. 1 argument is full application, 2 or 3 arguments is partial application. We don't know if this is a partial application.  
> **username_0**: Besides, there is no “function call” in push/enter. There is only “enter”.  
> **username_1**: Sorry, I forgot about laziness -- I added a small bit at the end to force evaluation, so that you can see when the partial application objects are constructed.  
> **username_0**: Actually, you are describing “eval/apply” because you are evaluating “f” in “f 6”. When using “push/enter”, “f 6” does: push 6, enter f = THUNK (foo 1), push 1, enter foo. No PAP. Still looking for an answer… (P.S. IMHO the “map” with its big definition is not important here.)  

---

### Answer by username_2 on 2013-01-08. Score: 2

Consider the following lazy functional program:
doArith :: Int -> Int
doArith n = if n < 0 then 1 + 2 else 3 - 4

A compiler can figure out that it doesn't need to build a thunk for 1 + 2 or 3 - 4 in the if expression. This is because that an if expression is strict in the branch position, since either 1 + 2 or 3 - 4 will surely be evaluated after evaluating n < 0. In this way, the compiler can generate better code while still preserving the lazy semantics.
However, the following program shows some problem:
getFunction :: Int -> Int -> Int
getFunction n = if n < 0 then (+) 1 else (-) 2

Here, the compiler will still generate strict code that enters either (+) or (-) with only one argument. But (+) or (-) require two arguments... So here comes the PAp object.
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.

> **Comments:**
> **username_0**: “A compiler can figure out that it doesn't need to build a thunk for 1 + 2” In the push/enter model, a compiler does not build a thunk for 1 + 2. It pushes 1, 2, then enters (+).  

---

