New subject: [polyml] Re: On understanding Poly/ML function definition IR

9 Feb 2011


      On 08/02/2011 00:31, Yue Li wrote:
...
I'm trying to get better understanding about the code tree of Poly/ML
function definition. I would appreciate if I can gain some insights from
you.
For instance, given the following definition:
...
fun f a b = a + b;
The first point to appreciate is that this is syntactic sugar for
val rec f = fn a => fn b => op+ (a, b);
However this general form isn't the best way of compiling the function. 
  Frequently a curried function is applied to several or all of its 
arguments e.g.
val x = f y z
Using the general form would be inefficient.  Applying f to y would 
result in a closure being created on the heap which would then be 
applied to z.  Instead Poly/ML processes "fun" declarations specially.
fun f a b = a + b
is rewritten as
val rec f' = fn <a,b> => a + b
and rec f = fn_inline a => fn_inline b => f'<a,b>
i.e. a pair of mutually recursive functions, because f' could contain 
recursive applications of f.  The <> here denote multiple arguments in 
registers or on the stack, something that doesn't have an exact 
equivalent in ML since every function takes exactly one argument.
...
The compiler prints out 3 sections of code tree: a block, a lambda and
another block:
BLOCK(MUTUAL(DECL #2{0 uses} =
LAMBDA(
f(2)
CL=false CR=0 LEV=0 LOCALS=0
ARGS=G G
ARGLIVES=
RES=G CLOS=()
BLOCK(BLOCK(DECL #1{0 uses} = RECCONSTR(PARAM(0,1), PARAM(0,2));
DECL #3{0 uses} = LOCAL(0,1);
DECL #4{0 uses} = INDIRECT(0, LOCAL(0,3));
DECL #5{0 uses} = INDIRECT(1, LOCAL(0,3));
GLOBAL (FUN "run_call2(1)",
LAMBDAINLINE(
run_call2(1)
CL=false CR=0 LEV=0 LOCALS=0
ARGS=G
ARGLIVES=
RES=G CLOS=()
LOCAL(1,1) G
$(INDIRECT(0, PARAM(0,1)) G, INDIRECT(1, PARAM(0,1)) G)){LAMBDA}
) (*GLOBAL*){early} G $(RECCONSTR(LOCAL(0,4), LOCAL(0,5)) G)
)
)){LAMBDA} AND
This is the body of "f'".  The name "f(2)" represents that it takes two 
arguments but the name is only used for exception tracing and profiling. 
  It has no significance to ML.
...
DECL #1{0 uses} =
LAMBDAINLINE(
f(1)
CL=false CR=0 LEV=0 LOCALS=0
ARGS=G
ARGLIVES=
RES=G CLOS=()
LAMBDAINLINE(
f(1)(1)
CL=false CR=0 LEV=0 LOCALS=0
ARGS=G
ARGLIVES=
RES=G CLOS=()
LOCAL(2,2) G $(PARAM(0,1) G, PARAM(1,1) G)){LAMBDA}){LAMBDA}
);
This is the body of "f".  It consists of two inline functions, one 
inside the other.
...
RECCONSTR(LOCAL(0,1))
)
This is the result of a top-level declaration.  The final result is a 
1-tuple containing a reference to the function "f".  Actually because 
these are all small functions it's likely that the result will be the 
reference to the code-tree itself so that subsequent uses of "f" at the 
top-level will expand the code in-line and reduce down to a use of the 
addition operation.  Top-level declarations can be simple function 
declarations such as this example but just as often they involve 
extensive computation and return the results as multiple declarations.
...
I have three questions regarding this block:
(1) First I'm wondering what do LOCAL(2, 2), and LOCAL(1, 1) refer to?
My understanding so far is that the second number of the LOCAL operator
means the number of DECL, but what does the first number refers to?
This is the nesting depth.  Zero means local to the function, one means 
local to the immediately containing function etc.  So
LOCAL(2,2) G $(PARAM(0,1) G, PARAM(1,1) G))
means:  apply the function declared by a DECL #2 two levels out to the 
first or only parameter of the current function and the first or only 
parameter of the immediately containing function.  (Oh, there's some 
oddity about the order of multiple parameters).
I hope this answers your other questions as well but let me know if 
you'd like any more clarification.
Regards,
David