[Haskell-cafe] help understanding pj-lester-book

[Bernie Pope]

On 13/04/2008, at 12:09 AM, minh thu wrote:
> Hi!
>
> I don't understand something in there :
>
> pj-lester-book :
> Implementing functional languages: a tutorial
> by Simon Peyton Jones and David Lester,
> available at http://research.microsoft.com/~simonpj/Papers/pj- 
> lester-book/
>
> eval/apply :
> Making a Fast Curry: Push/Enter vs. Eval/Apply for Higher-order  
> Languages
> by Simon Marlow and Simon Peyton Jones,
> available at http://www.haskell.org/~simonmar/papers/
>
> The introduction in eval/apply states the arity of a function and the
> number of arguments in a call can match or differs (and it should be
> dealt with).
>
> In pj-lester-book (bottom of page 46 and top of page 47), it is stated
> that if the program has been type-cheched, the underflow check is
> unnecessary.
> When continuing to the G-machine then to the TIM-machine chapters, I
> haven't found discussion of an arity-mismatch.
>
> What am I missing ?

Hi Minh,

If I understand the pj-lester book properly, what they are saying is:  
if you have an
expression which is a function application, and type checking has  
determined that
the result of the expression is _not a function_, then you can be  
sure that the
outermost redex in the expression has enough arguments. If it is not  
a function
then it cannot be a partial application. Thus you don't have to
do the underflow check for that redex. You either have a saturated  
application or
an over saturated application, but either way there is guaranteed to  
be enough
arguments.

Unfortunately, instead of saying "not a function", they say "a  
number, or say, a list".

If you are writing a compiler, and you are about to generate code for  
a function application,
and the type checker tells you the result is not a function, then you  
can omit generating
the code for the underflow test - which is a performance gain.

I believe the eval/apply paper is referring to the general case of a  
function application,
where you don't always know that the result is not a function. For  
example,
suppose you are generating code for the "map" function. In the body  
of "map" you have:

    case list of
       Nil -> Nil
       Cons x xs -> Cons (f x) (map f xs)

In the application (f x), you can't statically determine if it is  
saturated or not, because it depends on
the arity of the function subsituted for "f", which is of course  
unknown. (You could turn it into a
known by doing an arity-based specialisation of the program, but that  
is a fairly heavyweight
option, which would require multiple versions of functions like map.)

Cheers,
Bernie.