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.
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
