A very small idea: skipping the arity satisfaction check 
Author Message
 A very small idea: skipping the arity satisfaction check

A very small but nice thought occurred to me when working on our compiler.

Background
~~~~~~~~~~
TIM-like evaluation models for functional languages often have two entry
points for each function:

        the "direct" entry, which is used when the caller is
        sure that it has supplied enough arguments to satisfy
        the function (its "arity"),

        the "slow" entry, which is used otherwise

The "slow" entry checks to see if there are enough arguments on the stack;
if not, it's time to perform an update [1].  

By "arity" I mean how many arguments a function needs before it can do any
work at all; or equivalently, how many lambdas its body is wrapped in.  Note
that a function's arity may be less than suggested by its type. For example

        f x = g where
                v = x*x
                g y = v+y

Here f has arity 1, but its type is (Int -> Int -> Int)

Obviously, one wants to use the direct entry as much as possible.  The
difficulty comes with imported functions: usually all one knows about
imported functions is their type.  The arity is unknown.

The usual solution (adopted by Lennart's LML/hbc compiler) is to add
annotations to the interface file for the imported module to indicate the
arity of the imported function as well as its type.  This is perfectly fine,
but it does mean cluttering the interface file a little, and a bit more
verbidge in the compiler to spit out and munch up the annotations.

The idea
~~~~~~~~
The Very Small Idea is this: you can get enough information from the type
to do almost everything you want.

Suppose you import a function f with type

        f :: t1 -> t2 -> Int

Then it certainly can't have arity more than 2!  So if you see f applied
to 2 arguments, you can use f's direct entry point.  (Of course, f might
have arity 1, so we could use f's direct entry point for applications of
f to only 1 argument.  Annotations would catch this, but inferring arity
constraints from types would not.)

Polymorphism
~~~~~~~~~~~~
At first it looks as if we can't use this idea unless the type at the
right-hand end of all the arrows is a *data* type.  For example,

        g :: a -> (a -> b) -> b

Here, in a particular call to g, b could be instantiated to a function type.
Does this mean the the function g may have arity > 2?  No, it does not!
The real type of g is

        g :: Forall a,b. a -> (a->b) -> b

Since there is ONE piece of code which handles all g's polymorphic
instances, this code can't possibly have arity greater than 2!  So
we can still use g's direct entry for any applications of g to two or
more args.

In short, one can simply count arrows in (the top level of) the type
of imported functions to get an upper bound on their arity.

Notice that this only applies to polymorphic functions (all imported
ones are).  It does NOT apply to function-valued arguments.  For example:

        map f (x:xs) = f x : map f xs

Here, f has type (a->b), but we CANNOT assume that f has arity one or less
and thus use the direct entry for the call (f x), because it is not
polymorphic.  Counter example: the call (map (+ 3) xs).

Conclusion
~~~~~~~~~~
Evan Ireland implements a more extreme version of this in his compiler.
His system LEGISLATES that a function may have no greater arity than
that suggested by its type, even if its type is monomorphic.

This approach is not without its problems; you can lose (full) laziness.
I won't elaborate, because he can do so better than I.

I heard a rumour that someone at Manchester was working on something similar.

My only claim is that the scheme is simple, dead easy to implement, and I
believe it catches a lot of cases (that is, the annotation scheme will only
catch a few more cases, except in contrived programs).

I bet someone else has done this before.  But, apart from the work I mention
above, I havn't heard of it.

Simon

Notes
~~~~~
[1] The original idea is in Fairbairn & Wray's first TIM paper; it also
shows up in the Spineless Tagless G-machine, and in Evan Ireland's FAM
machine, I think.  It is described in detail in "Implementing functional
langauges: a tutorial", PJ & Lester, Prentice Hall 1992.



Sun, 01 Jan 1995 19:07:35 GMT  
 A very small idea: skipping the arity satisfaction check

Quote:

>A very small but nice thought occurred to me when working on our compiler.

>TIM-like evaluation models for functional languages often have two entry
>points for each function:

> [...]

>The Very Small Idea is this: you can get enough information from the type
>to do almost everything you want.

>Suppose you import a function f with type

>    f :: t1 -> t2 -> Int

>Then it certainly can't have arity more than 2!  So if you see f applied
>to 2 arguments, you can use f's direct entry point.

> [...]

>My only claim is that the scheme is simple, dead easy to implement, and I
>believe it catches a lot of cases (that is, the annotation scheme will only
>catch a few more cases, except in contrived programs).

I'd claim that it depends on program style.  If you use a lot of
higher-order functions, then this scheme will have a much higher
"failure" rate.  But for mainly first-order programs you will
catch most cases.

As an alternative, you could *compile* multiple entry points up to the
number of type arrows.  Now you know when compiling a function which
of these entry points are "fast" and which "slow", so entry points for
different arities can be aliased to the correct entry.

I claim that this catches *all* cases that arity annotations will
*without needing these annotations*.  The argument satisfaction test
is still necessary, of course, to handle partial applications.

        f :: a -> (a -> (a -> b)) -> a -> b
        f a g = g a

        f_0:
        f_1:
        f_slow:
                argument satisfaction check

        f_2:
        f_3:
        f_fast:
                code to evaluate f

When compiling code in another module, simply call f_0, f_1, f_2, f_3 or
f_fast depending on the number of arguments that f is applied to:
0, 1, 2, 3, or more than 3.

Kevin
--

                                                           ^^^



Sun, 01 Jan 1995 19:46:44 GMT  
 A very small idea: skipping the arity satisfaction check

Quote:

>As an alternative, you could *compile* multiple entry points up to the
>number of type arrows.  Now you know when compiling a function which
>of these entry points are "fast" and which "slow", so entry points for
>different arities can be aliased to the correct entry.

>I claim that this catches *all* cases that arity annotations will
>*without needing these annotations*.  The argument satisfaction test
>is still necessary, of course, to handle partial applications.

>    f :: a -> (a -> (a -> b)) -> a -> b
>    f a g = g a

>    f_0:
>    f_1:
>    f_slow:
>            argument satisfaction check

>    f_2:
>    f_3:
>    f_fast:
>            code to evaluate f

>When compiling code in another module, simply call f_0, f_1, f_2, f_3 or
>f_fast depending on the number of arguments that f is applied to:
>0, 1, 2, 3, or more than 3.

You can avoid the argument satisfaction test even for partial
applications.  

The scheme
==========

Compile evaluation methods for partial application, full application,
and overfull application.

        partial methods
        --------------
        f_0_1   : closured 0 arguments, applied 1 arguments

        full methods
        -----------
        f_0_2   : closured 0 arguments, applied 2 arguments
        f_1_1   : closured 1 arguments, applied 1 arguments

        overfull methods
        ----------------
        f_0_3   : closured 0 arguments, applied 3 arguments
        f_1_2   : closured 1 arguments, applied 2 arguments
        f_2_1   : closured 2 arguments, applied 1 arguments

(The overfull entrys are required in a strict environment, where

        f a g x = g a x         not equivalent to
        f a g   = g a

i.e. "eta-enrichment" is not allowed.)

Now build a method table for f:

        CODE eval_methods_f[] = {
                f_0_1,f_0_2,f_0_3,
                f_1_1,f_1_2,
                f_2_1
        };

The initial closure for f is a data structure of the form

        struct clos_f {
                CODE methods = eval_methods_f;
                CODE direct_entry = <<point to the direct entry of f>>;
                OBJ arg1, arg2;
        };

For the evaluation of some closure to i arguments, code:

        (closure->methods[i-1])(closure,a1,...,ai)

The method f_0_1 for partial application is coded f.i. as:

        OBJ f_0_1(closure,arg){
           <<copy closure, if no sharing information is present,
                otherwise reuse it ...>>
           closure->arg1 = arg;
           closure->methods = closure->methods + 3;
           return closure;
        }

The method f_1_1 for full application (1 argument closured) is coded
f.i. as:

        OBJ f_1_1(closure,arg){
           return (closure->direct_entry)(closure->arg1,arg);
        }              

The methode f_1_2 for overfull application (1 argumet closured) is
coded as:

        OBJ f_1_2(closure,arg1,arg2){
           OBJ nextClos = (closure->direct_entry)(closure->arg1,arg1);
           return (nextClos->methods[1-1])(arg2);    
        }

Remarks
=======

In fact, it is not necessary to code all the evaluation methods and
method tables for each function again. They can be precoded in the rts
(provided some uniform object representation).  For a maximal arity of
16, about 300 methods are required. (which is a lot, but link
optimization helps out).

In the case of a normal full application (f_0_2) piped over the method
table, the loosage compared to direct application is 2 indirect calls
against 1 direct call. Of course, this calls might still be optimized
by arity annotations (BTW, i would prefer the notion rank annotations),
which are naturally available, if inter-module optimization is
enabled.

The scheme has been implemented for the new OPAL-1 compiler at the TUB
and is published in a dissertation.

Greetings from Berlin

--



Mon, 02 Jan 1995 21:40:16 GMT  
 A very small idea: skipping the arity satisfaction check

Quote:

> The usual solution (adopted by Lennart's LML/hbc compiler) is to add
> annotations to the interface file for the imported module to indicate the
> arity of the imported function as well as its type.  This is perfectly fine,
> but it does mean cluttering the interface file a little, and a bit more
> verbidge in the compiler to spit out and munch up the annotations.

This is the solution I also use in my P-RISC compiler.  I'm not sure why you're
worried about ``cluttering the interface file'',  since it's not read by humans
anyway-- the compiler spits it out and later reads it back in.  Also, re. the ``bit
more verbiage'', is the code for counting arrows in types likely to be any shorter?

In my system, there are no explicit arity checks.  Given a source
function:

     f x y z = body

my compiler expands this as follows (called "unrolling"):

     F1(ENV,X)   = MK_CLOSURE F2 [X]
     F2(ENV,Y)   = MK_CLOSURE F3 (Y:ENV)
     F3([Y,X],Z) = F4(X,Y,Z)
     F4(X,Y,Z)   = body

Then, applications are transformed as follows (called "classifying"),
depending on how many arguments are given to "f":

     f e1 e2 e3  => F4(E1,E2,E3)
     f e1 e2     => MK_CLOSURE F3 [E2,E1]
     f e1        => MK_CLOSURE F2 [E1]
     f           => MK_CLOSURE F1 []

The first line represents a conversion to a "direct call".
For all other applications:

     e1 e2       => let x = e1
                    in x.code(x.env, e2)

I have used upper and lower case to emphasize that these are two
different languages.  The output language (uppercase) has no currying
at all, and N-ary function application is written FOO(ARG1,..,ARGN),
i.e.  this is not a tuple argument.  The form MKCLOSURE FOO ENV is a
special form, i.e. MKCLOSURE is not a function, because FOO is not a
function value--- it is only the name of a function (and becomes a
code pointer that points at FOO's code).

Thus, in a general application of a closure to an arg, it always calls
the ``correct'' intermediate function, which knows exactly how many
arguments it already has.  Further, F3 knows exactly how to unpack its
environment (illustrated above by the 2-list pattern in its first
formal parameter)

My compiler also spits out arity declarations of the form:

    ARITY f 3 F1 F2 F3 F4

so that all the "classifying" transforms are also performed in other
modules that imports this one.




Tue, 03 Jan 1995 04:30:36 GMT  
 A very small idea: skipping the arity satisfaction check

|>
|> As an alternative, you could *compile* multiple entry points up to the
|> number of type arrows.  Now you know when compiling a function which
|> of these entry points are "fast" and which "slow", so entry points for
|> different arities can be aliased to the correct entry.
|>
|> I claim that this catches *all* cases that arity annotations will
|> *without needing these annotations*.  The argument satisfaction test
|> is still necessary, of course, to handle partial applications.
|>

  This simple scheme is exactly the one used in my Caml-Light to C code
generator. Caml-Light uses a simple module system a la Modula-2 where the
interface files contain the type signature for a given module, which is
independent from its actual implementation. So arity annotations are not
available, but the type of an imported function gives you its maximal arity.

  For a better look at the implementation issues, refer to my article
"An optimizing ML to C compiler", ACM SIGPLAN '92 Workshop on ML and its
applications, San Francisco.

 Regis Cridlig, Computer Laboratory  | Phone: (+44) 223 334602


 CAMBRIDGE CB2 3QG, England, UK      | UUCP: ...!mcsun!ukc!cam-cl!rc136



Tue, 03 Jan 1995 18:43:15 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Idea: arity as a range

2. Forged email from skip@calendar.com and/or skip@automatrix.com

3. Ideas for small projects

4. Idea for a small app

5. Idea: Array Boundary Checks on Write Access Only

6. Proven Weight Loss, Satisfaction Guaranteed! wombv

7. Can't get no satisfaction

8. constraint satisfaction programming

9. Constraint Satisfaction Problems (CSP) w/ non-finite domains?

10. Constraint satisfaction in LOG(F)

11. constraint satisfaction programming

12. Looking for programs for constraints propagation/satisfaction

 

 
Powered by phpBB® Forum Software